This one was quite difficult. It took me 2 days to solve this one.
Part 1
Show challenge - day 18, part 1
You descend into the ocean trench and encounter some snailfish. They say they saw the sleigh keys! They’ll even tell you which direction the keys went if you help one of the smaller snailfish with his math homework.
Snailfish numbers aren’t like regular numbers. Instead, every snailfish number is a pair - an ordered list of two elements. Each element of the pair can be either a regular number or another pair.
Pairs are written as [x,y], where x and y are the elements within the pair.
Here are some example snailfish numbers, one snailfish number per line:
[1,2]
[[1,2],3]
[9,[8,7]]
[[1,9],[8,5]]
[[[[1,2],[3,4]],[[5,6],[7,8]]],9]
[[[9,[3,8]],[[0,9],6]],[[[3,7],[4,9]],3]]
[[[[1,3],[5,3]],[[1,3],[8,7]]],[[[4,9],[6,9]],[[8,2],[7,3]]]]
This snailfish homework is about addition.
To add two snailfish numbers, form a pair from the left and right parameters of the addition operator. For example, [1,2] + [[3,4],5] becomes [[1,2],[[3,4],5]].
There’s only one problem: snailfish numbers must always be reduced, and the process of adding two snailfish numbers can result in snailfish numbers that need to be reduced.
To reduce a snailfish number, you must repeatedly do the first action in this list that applies to the snailfish number:
- If any pair is nested inside four pairs, the leftmost such pair explodes.
- If any regular number is 10 or greater, the leftmost such regular number splits.
Once no action in the above list applies, the snailfish number is reduced.
During reduction, at most one action applies, after which the process returns to the top of the list of actions. For example, if split produces a pair that meets the explode criteria, that pair explodes before other splits occur.
To explode a pair, the pair’s left value is added to the first regular number to the left of the exploding pair (if any), and the pair’s right value is added to the first regular number to the right of the exploding pair (if any).
Exploding pairs will always consist of two regular numbers.
Then, the entire exploding pair is replaced with the regular number 0.
The homework assignment involves adding up a list of snailfish numbers (your puzzle input). The snailfish numbers are each listed on a separate line. Add the first snailfish number and the second, then add that result and the third, then add that result and the fourth, and so on until all numbers in the list have been used once.
To check whether it’s the right answer, the snailfish teacher only checks the magnitude of the final sum. The magnitude of a pair is 3 times the magnitude of its left element plus 2 times the magnitude of its right element. The magnitude of a regular number is just that number.
So, given this example homework assignment:
[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]
The final sum is:
[[[[6,6],[7,6]],[[7,7],[7,0]]],[[[7,7],[7,7]],[[7,8],[9,9]]]]
The magnitude of this final sum is 4140.
Add up all of the snailfish numbers from the homework assignment in the order they appear. What is the magnitude of the final sum?
Here’s the provided input. It’s quite long so don’t try to scroll through:
Show input - day 18
[[2,[[1,1],9]],[[0,[3,0]],[[1,6],[4,2]]]]
[[8,[0,5]],[[[9,9],0],[[2,9],2]]]
[[[[6,4],[5,8]],[[0,9],[6,5]]],[[5,1],4]]
[[[9,[2,8]],[[0,2],[8,3]]],[[[5,6],[5,8]],[[4,8],2]]]
[[0,[[0,1],[6,0]]],[[[6,4],1],[8,6]]]
[[[[8,5],6],8],[[[9,1],[0,6]],[4,[2,4]]]]
[7,[[4,3],[8,5]]]
[[8,[1,[3,4]]],[[3,8],[0,1]]]
[[[1,1],[[2,1],[0,3]]],[[7,[1,8]],[[3,8],[5,2]]]]
[[2,[[4,6],[6,2]]],[[0,5],[3,7]]]
[[[[9,8],[4,6]],[7,[9,1]]],[[[8,7],[4,7]],[[6,6],[8,1]]]]
[[[2,[5,1]],[[0,4],3]],[[9,7],[[0,2],0]]]
[[[[5,0],2],5],[[3,[5,8]],[5,[8,9]]]]
[[6,[3,6]],[[[2,7],6],[[6,0],4]]]
[[8,8],7]
[[[[7,9],3],8],[[0,[1,7]],[[3,2],[4,5]]]]
[[[1,1],[7,2]],[3,[4,[6,4]]]]
[[[9,[6,6]],[[4,8],[1,3]]],[[[4,7],8],[[5,2],[3,8]]]]
[[[6,[6,7]],[3,4]],5]
[[[[0,0],2],9],[[[2,1],1],[5,[4,7]]]]
[[[2,[9,8]],[5,8]],[[[3,4],6],[5,0]]]
[[[7,[9,4]],[7,[7,2]]],[[1,[9,6]],1]]
[[[[9,1],1],[4,[2,6]]],3]
[[0,[8,[3,4]]],[8,[9,8]]]
[[[1,6],[6,7]],[[[0,4],1],7]]
[[6,[5,[0,0]]],[7,[[5,4],1]]]
[[2,[[9,5],[9,1]]],[[3,0],4]]
[[[5,7],[[1,0],[3,5]]],[4,[5,[4,0]]]]
[[3,3],[2,2]]
[[[[6,2],[1,7]],[1,7]],[[[6,7],6],9]]
[[[[9,8],[8,8]],[2,1]],[[8,4],8]]
[[[[1,4],1],[2,0]],[4,[[0,5],5]]]
[[[7,[6,0]],[[7,3],1]],9]
[[[[2,4],0],[[6,9],8]],[[3,[0,9]],[[4,4],[5,4]]]]
[[7,3],[0,[2,[7,2]]]]
[[[[8,8],5],9],[[8,6],6]]
[[[[9,5],7],9],0]
[[[1,4],8],[[7,[5,3]],[[6,4],6]]]
[[9,[[9,3],[3,7]]],[[[6,9],1],[[2,3],[4,4]]]]
[[4,[9,2]],[3,4]]
[[1,[[0,9],2]],[1,[1,[8,7]]]]
[[[4,1],8],[9,[9,[2,9]]]]
[[[[7,9],[9,7]],8],[[[3,0],5],[[7,8],[3,1]]]]
[[[[9,4],[9,9]],[[9,5],[8,9]]],[[2,[7,4]],[[4,6],6]]]
[[[[8,7],1],[6,8]],[[4,2],5]]
[7,[3,[3,3]]]
[[[4,9],[0,2]],[[[4,2],9],[[5,8],6]]]
[[[[1,3],1],[[7,5],[4,0]]],[[[6,3],4],[[1,2],8]]]
[[[[3,2],2],[4,7]],[[[5,6],[6,3]],3]]
[[[[4,0],6],[4,2]],[7,5]]
[[[[9,5],[2,0]],[[6,8],[0,9]]],[[[7,4],[3,6]],1]]
[[[4,[9,3]],[[9,4],8]],[[6,[1,2]],2]]
[[[[4,1],[1,1]],[[4,8],9]],[[[1,0],[0,3]],2]]
[[[3,[3,8]],[[0,6],7]],[[2,5],9]]
[[[0,[6,8]],[[2,7],[4,1]]],6]
[[6,3],0]
[[[3,[7,1]],[3,[2,0]]],[[[3,5],9],[[5,2],[7,8]]]]
[[7,8],[1,[[7,1],5]]]
[[[9,[8,9]],2],[9,[[8,8],4]]]
[[[8,[5,8]],[[9,1],[6,0]]],[[[9,1],[4,7]],8]]
[5,[[[4,9],7],[[6,0],[9,0]]]]
[[[[8,8],[6,7]],[[1,0],6]],[[5,[2,8]],[[8,0],[3,7]]]]
[[0,[6,6]],[[0,1],[3,[9,2]]]]
[[1,[0,[8,1]]],[[0,[0,0]],[8,[0,0]]]]
[[[4,[1,4]],[8,[9,5]]],7]
[7,[[[0,0],[4,3]],8]]
[[[9,1],[[7,5],[9,2]]],[5,[9,0]]]
[[[[2,0],9],[8,[3,0]]],[[9,8],[4,[0,7]]]]
[4,[5,[5,[0,3]]]]
[[6,[[6,9],8]],[1,[0,[6,0]]]]
[[7,[4,3]],[[0,6],[[5,2],[6,9]]]]
[[[[7,2],[4,6]],[[5,0],9]],6]
[[[0,1],[0,2]],[0,[5,2]]]
[[[[5,0],[5,4]],[[5,9],[9,9]]],[2,[[3,0],[8,1]]]]
[[[[9,2],[2,9]],[[5,5],2]],[[1,3],[[3,6],[1,8]]]]
[[0,[2,4]],[[[6,9],1],[[7,9],[9,8]]]]
[[[[2,1],1],[7,3]],[4,[[1,2],[2,6]]]]
[[[6,[0,1]],[[6,4],[4,2]]],[1,[[0,0],[9,7]]]]
[[[[9,2],3],[9,8]],[[6,5],[7,[1,7]]]]
[[3,9],7]
[[[6,9],[[0,2],0]],[[[8,6],2],9]]
[[[[2,2],2],[[6,7],7]],[[0,3],9]]
[[[7,[2,7]],3],4]
[[[[1,9],6],[0,7]],[[[2,2],1],2]]
[9,9]
[0,[9,[[4,1],1]]]
[[[[7,6],1],2],[[[6,9],[9,1]],0]]
[[[[4,3],[4,2]],3],[[5,[6,5]],[[2,6],0]]]
[[[0,[5,1]],[6,[1,4]]],[5,[[8,1],3]]]
[6,[9,6]]
[[8,[9,[6,8]]],[[4,9],[[2,4],[7,1]]]]
[[5,[[9,9],[3,3]]],[[[9,8],[5,0]],6]]
[[6,7],1]
[1,[4,[[9,6],0]]]
[[[[9,8],[7,8]],[5,[4,6]]],[[[5,9],6],[[4,6],4]]]
[[[2,7],4],[[[0,3],0],[[7,4],[7,4]]]]
[7,[0,4]]
[1,[3,2]]
[[3,0],8]
[[[3,2],5],8]
Here’s the solution to part 1:
function explode(s::String)
while true
backup = s
s = explode(eachmatch(r"(\[)([\d]*)(,)([\d]*)(\])", s), s)
backup == s ? break : continue
end
return s
end
function explode(pairs::Base.RegexMatchIterator, s::String=expr)
for p in pairs
level = count(==('['), s[begin:p.offsets[1]-1]) -
count(==(']'), s[begin:p.offsets[1]-1])
if level >= 4
s = explode([s[begin:p.offsets[1]-1]; p.captures;
s[p.offsets[end]+1:end]])
return s
end
end
return s
end
function explode(chunks::Vector)
left_explode = match(r"([\d]*)([\[\],]*)$", chunks[begin]).captures
if left_explode[1] == ""
left_chunks = chunks[begin] * "0"
else
replacement = (parse(Int, left_explode[1]) + parse(Int, chunks[3])
|> string) * left_explode[2]
left_chunks = replace(chunks[1], r"([\d]*)([\[\],]*)$" => replacement)
end
right_explode = match(r"^([\[\],]*)([\d]*)", chunks[end]).captures
if right_explode[2] == ""
right_chunks = "0" * chunks[end]
else
replacement = right_explode[1] *
(parse(Int, right_explode[2]) + parse(Int, chunks[5]) |> string)
right_chunks = replace(chunks[end], r"^([\[\],]*)([\d]*)" => replacement)
end
return replace(left_chunks * right_chunks,
",]" => ",0]",
"[," => "[0,")
end
function split_pair(s::String)
while true
backup = s
m = match(r"([\d]{2,})", s)
if m !== nothing
s = s[1:m.offset-1] * split_pair(m.match) * s[m.offset+2:end]
s = explode(s)
end
backup == s ? break : continue
end
return s
end
function split_pair(s::SubString)
"[" * string(floor(Int,parse(Int,s)/2)) *
"," * string(ceil(Int,parse(Int,s)/2)) * "]"
end
function reduce(s::String)
while true
backup = s
s = explode(s)
s = split_pair(s)
backup == s ? break : continue
end
return s
end
reduce(v::Vector) = reduce("[" * join(v,",") * "]")
function add(v::Vector)
while length(v) > 1
reduced_two = reduce(splice!(v, 1:2))
pushfirst!(v, reduced_two)
end
return v[1]
end
magnitude(x::Integer) = x
magnitude(x::Vector) = magnitude.(x) .* [3, 2] |> sum
split(strip(input), "\n") .|> string |> add |>
Meta.parse |> eval |> magnitude |> print
Part 2
Show challenge - day 18, part 2
You notice a second question on the back of the homework assignment:
What is the largest magnitude you can get from adding only two of the snailfish numbers?
Note that snailfish addition is not commutative – that is, x + y and y + x can produce different results.
Again considering the last example homework assignment above:
[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]
The largest magnitude of the sum of any two snailfish numbers in this list is 3993.
This is the magnitude of [[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]] + [[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]], which reduces to [[[[7,8],[6,6]],[[6,0],[7,7]]],[[[7,8],[8,8]],[[7,9],[0,6]]]].
What is the largest magnitude of any sum of two different snailfish numbers from the homework assignment?
Here’s the solution to part 2:
function explode(s::String)
while true
backup = s
s = explode(eachmatch(r"(\[)([\d]*)(,)([\d]*)(\])", s), s)
backup == s ? break : continue
end
return s
end
function explode(pairs::Base.RegexMatchIterator, s::String=expr)
for p in pairs
level = count(==('['), s[begin:p.offsets[1]-1]) -
count(==(']'), s[begin:p.offsets[1]-1])
if level >= 4
s = explode([s[begin:p.offsets[1]-1]; p.captures;
s[p.offsets[end]+1:end]])
return s
end
end
return s
end
function explode(chunks::Vector)
left_explode = match(r"([\d]*)([\[\],]*)$", chunks[begin]).captures
if left_explode[1] == ""
left_chunks = chunks[begin] * "0"
else
replacement = (parse(Int, left_explode[1]) + parse(Int, chunks[3])
|> string) * left_explode[2]
left_chunks = replace(chunks[1], r"([\d]*)([\[\],]*)$" => replacement)
end
right_explode = match(r"^([\[\],]*)([\d]*)", chunks[end]).captures
if right_explode[2] == ""
right_chunks = "0" * chunks[end]
else
replacement = right_explode[1] *
(parse(Int, right_explode[2]) + parse(Int, chunks[5]) |> string)
right_chunks = replace(chunks[end], r"^([\[\],]*)([\d]*)" => replacement)
end
return replace(left_chunks * right_chunks,
",]" => ",0]",
"[," => "[0,")
end
function split_pair(s::String)
while true
backup = s
m = match(r"([\d]{2,})", s)
if m !== nothing
s = s[1:m.offset-1] * split_pair(m.match) * s[m.offset+2:end]
s = explode(s)
end
backup == s ? break : continue
end
return s
end
function split_pair(s::SubString)
"[" * string(floor(Int,parse(Int,s)/2)) *
"," * string(ceil(Int,parse(Int,s)/2)) * "]"
end
function reduce(s::String)
while true
backup = s
s = explode(s)
s = split_pair(s)
backup == s ? break : continue
end
return s
end
reduce(v::Vector) = reduce("[" * join(v,",") * "]")
function add(v::Vector)
while length(v) > 1
reduced_two = reduce(splice!(v, 1:2))
pushfirst!(v, reduced_two)
end
return v[1]
end
magnitude(x::Integer) = x
magnitude(x::Vector) = magnitude.(x) .* [3, 2] |> sum
lines = split(strip(input), "\n") .|> string
[lines[[i,j]] for i in 1:length(lines), j in 1:length(lines) if i != j] .|>
add .|> Meta.parse .|> eval .|> magnitude |> maximum |> print