125 lines
3.7 KiB
C#
125 lines
3.7 KiB
C#
namespace aoc2021;
|
|
|
|
/// <summary>
|
|
/// Day 18: <see href="https://adventofcode.com/2021/day/18"/>
|
|
/// </summary>
|
|
public sealed class Day18 : Day
|
|
{
|
|
private readonly List<string> _fishes;
|
|
|
|
public Day18() : base(18, "Snailfish")
|
|
{
|
|
_fishes = Input.ToList();
|
|
}
|
|
|
|
private static Tree<int> Parse(string input)
|
|
{
|
|
static Tree<int>.Node ParseFish(Tree<int>.Node? parent, string input, ref int cursor)
|
|
{
|
|
if (input[cursor] != '[') return new(parent, input[cursor++] - '0');
|
|
|
|
var node = new Tree<int>.Node(parent, -1);
|
|
cursor++;
|
|
node.Left = ParseFish(node, input, ref cursor);
|
|
cursor++;
|
|
node.Right = ParseFish(node, input, ref cursor);
|
|
cursor++;
|
|
return node;
|
|
}
|
|
|
|
var cursor = 0;
|
|
return new(ParseFish(null, input, ref cursor));
|
|
}
|
|
|
|
private static Tree<int> Add(Tree<int> a, Tree<int> b)
|
|
{
|
|
var reduced = new Tree<int>(new(null, -1) {Left = a.Root, Right = b.Root});
|
|
Reduce(reduced);
|
|
return reduced;
|
|
}
|
|
|
|
private static Tree<int>.Node? SiblingOf(Tree<int>.Node from, Func<Tree<int>.Node, Tree<int>.Node?> move1,
|
|
Func<Tree<int>.Node, Tree<int>.Node?> move2)
|
|
{
|
|
var current = from;
|
|
while (current.Parent != null)
|
|
{
|
|
if (move1(current.Parent) == current)
|
|
{
|
|
var other = move2(current.Parent);
|
|
while (other?.Data == -1)
|
|
other = move1(other) ?? move2(other);
|
|
return other;
|
|
}
|
|
|
|
current = current.Parent;
|
|
}
|
|
|
|
return null;
|
|
}
|
|
|
|
private static void Reduce(Tree<int> tree)
|
|
{
|
|
bool ReduceRecurse(Tree<int>.Node node, Func<Tree<int>, Tree<int>.Node, bool> reducer)
|
|
{
|
|
if (reducer(tree, node)) return true;
|
|
if (node.Left != null && ReduceRecurse(node.Left, reducer)) return true;
|
|
return node.Right != null && ReduceRecurse(node.Right, reducer);
|
|
}
|
|
|
|
bool Explode(Tree<int> t, Tree<int>.Node node)
|
|
{
|
|
if (node.Data != -1 || node.DistanceToParent(t.Root) < 4) return false;
|
|
var left = SiblingOf(node, n => n.Right, n => n.Left);
|
|
if (left != null) left.Data += node.Left!.Data;
|
|
var right = SiblingOf(node, n => n.Left, n => n.Right);
|
|
if (right != null) right.Data += node.Right!.Data;
|
|
|
|
node.Left = null;
|
|
node.Right = null;
|
|
node.Data = 0;
|
|
return true;
|
|
}
|
|
|
|
bool Split(Tree<int> t, Tree<int>.Node node)
|
|
{
|
|
if (node.Data < 10) return false;
|
|
node.Left = new(node, node.Data / 2);
|
|
node.Right = new(node, node.Data / 2 + node.Data % 2);
|
|
node.Data = -1;
|
|
return true;
|
|
}
|
|
|
|
var changed = true;
|
|
while (changed)
|
|
{
|
|
changed = false;
|
|
while (ReduceRecurse(tree.Root, Explode)) changed = true;
|
|
if (ReduceRecurse(tree.Root, Split)) changed = true;
|
|
}
|
|
}
|
|
|
|
private static long Magnitude(Tree<int>.Node? node)
|
|
{
|
|
if (node?.Data >= 0) return node.Data;
|
|
return 3 * Magnitude(node?.Left) + 2 * Magnitude(node?.Right);
|
|
}
|
|
|
|
public override object Part1() =>
|
|
Magnitude(_fishes.Skip(1).Aggregate(Parse(_fishes.First()), (a, b) => Add(a, Parse(b))).Root);
|
|
|
|
public override object Part2()
|
|
{
|
|
var best = 0L;
|
|
for (var i = 0; i < _fishes.Count; i++)
|
|
best = _fishes
|
|
.Where((_, j) => i != j)
|
|
.Select(t => Add(Parse(_fishes[i]), Parse(t)))
|
|
.Select(result => Magnitude(result.Root))
|
|
.Prepend(best)
|
|
.Max();
|
|
|
|
return best;
|
|
}
|
|
}
|