Hi again, I'm back after some time of during the holidays. I realize it's a bit late to finish this series, but I'll do it anyway. I did manage to complete all the challenges in time for the 25th, but finding time to do the write up has been difficult during the holidays. So let's continue with Day 18.
We've got to help some snailfish with their math homework. It turns out it's not like regular math. Each snailfish number is a pair, an ordered list of two elements. Each element can be a regular number, or another pair. Here are some examples, one example on each 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]]]]
The homework is about addition. To add two number, we form a pair from the left and right parameters of the operation. So [1,2] + [[3,4],5] equals [[1,2],[[3,4],5]]. But, then we also have to reduce the numbers, since it's snailfish math we're doing. To reduce a number, we must repeatedly perform 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 greated, the leftmost such regular number splits.
When no more of these actions can be performed, the 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.
To split a regular number, replace it with a pair; the left element of the pair should be the regular number divided by two and rounded down, while the right element of the pair should be the regular number divided by two and rounded up. For example, 10 becomes [5,5], 11 becomes [5,6], 12 becomes [6,6], and so on.
For the homework, we need to add up a list of snailfish numbers. Start by adding the first number to the second, add that result to the third, add that result to the fourth and so on. the numbers are reduced after each adding operation.
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.
For example, the magnitude of [9,1] is 3*9 + 2*1 = 29; the magnitude of [1,9] is 3*1 + 2*9 = 21. Magnitude calculations are recursive: the magnitude of [[9,1],[1,9]] is 3*29 + 2*21 = 129.
For Part 1 we need to find the magnitude of the final sum, after adding all our snailfish numbers. For Part 2, we need to find the largest possible magnitude we can get by adding any two snailfish numbers in any order. And remember that with snailfish numbers a + b does not always produce the same result as b + a.
To solve this, we have a basic Snail class:
public class Snail
{
public Snail(int value, int level)
{
Value = value;
Level = level;
}
public int Value { get; set; }
public int Level { get; set; }
}
We'll be using LinkedList alot in this challenge, since it allows us to remove and insert items at a certain places in the list easily. But first, we need to parse our input and create some snails:
private static IEnumerable<Snail> Parse(string line)
{
var level = 0;
foreach (var c in line)
{
level += c switch
{
'[' => 1,
']' => -1,
_ => 0
};
if (char.IsDigit(c))
{
yield return new Snail(int.Parse(c.ToString()), level);
}
}
}
Here we use the brackets in a line to keep track of the level of the current snail, and return an enumerable of snails, with their value and their level. So far, nothing to special. Butm we'll also need methods to Add, Reduce and calculate Magnitude. Let's have a look at those:
private static LinkedList<Snail> Reduce(LinkedList<Snail> num)
{
Snail snail;
do
{
snail = num.FirstOrDefault(n => n.Level > 4);
if (snail != null)
{
var node = num.Find(snail);
if (node?.Previous != null)
{
node.Previous.Value.Value += node.Value.Value;
}
if (node?.Next?.Next != null)
{
node.Next.Next.Value.Value += node.Next.Value.Value;
}
Collapse(num, node, 0);
continue;
}
snail = num.FirstOrDefault(n => n.Value > 9);
if (snail != null)
{
var node = num.Find(snail);
if (node != null)
{
num.AddBefore(node, new Snail(node.Value.Value / 2, node.Value.Level + 1));
num.AddBefore(node, new Snail(node.Value.Value - (node.Value.Value / 2), node.Value.Level + 1));
num.Remove(node);
}
}
} while (snail != null);
return num;
}
Here we have a do - while that will keep looping until there is no mor snails that can be exploded or split. So first we try to find a snail that should be exploded. We add the values to previous and next node as instructed. The we use another helper method, Collapse, to create a new node with the regular number 0, and clean up among our nodes:
private static LinkedListNode<Snail> Collapse(LinkedList<Snail> num, LinkedListNode<Snail> node, int value)
{
var newNode = new LinkedListNode<Snail>(new Snail(value, node.Value.Level - 1));
num.AddBefore(node, newNode);
num.Remove(node.Next);
num.Remove(node);
return newNode;
}
The splitting above is a bit more straight forward. We find a regular number that is 10 or greater, create new nodes according to the rounding rules and remove the original node.
Our Add method uses the Reduce method to get the final sum of the addition:
private static LinkedList<Snail> Add(LinkedList<Snail> num, LinkedList<Snail> next)
{
return Reduce(new LinkedList<Snail>(num.Union(next).Select(s => new Snail(s.Value, s.Level + 1))));
}
We basically union the two snails, and add 1 to the level of each since they're now enclosed by another pair of brackets, meaning they're one level higher as a result of the addition.
To get our final answers we also need a method for calculating Magnitude:
private static long Magnitude(LinkedList<Snail> num)
{
while (num.Count > 1)
{
var level = num.Max(n => n.Level);
var node = num.First;
while (node != null && node.Next != null)
{
if (node.Value.Level == node.Next.Value.Level && node.Value.Level == level)
{
node = Collapse(num, node, node.Value.Value * 3 + node.Next.Value.Value * 2);
}
node = node.Next;
}
}
return num.First.Value.Value;
}
To get the Magnitude, we go through the snails until there's only one left. We use our Collapse method to create new nodes with the correct values, and remove the nodes that was collapsed. The last remaining node contains the magnitude of that snailfish number.
If we put it all together like this, we have our answers:
public static (long, long) Solve(string[] input)
{
var numbers = input.Select(line => new LinkedList<Snail>(Parse(line))).ToList();
var sum = numbers.Skip(1).Aggregate(numbers.First(), Add);
var sums = from a in numbers
from b in numbers
where a != b
select Magnitude(Add(a, b));
return (Magnitude(sum), sums.Max());
}
For Part 1 we use Aggregate to go through each number and adding them up. Then we get the Magnitude for the final sum. For Part 2, we create a list of the Magnitudes of adding any two numbers in our list, except adding a number with itself. Then we can just get the max sum from that list.