d18p1

5 files changed, 287 insertions, 0 deletions

diff --git a/aoc2021.test/DayTests.cs b/aoc2021.test/DayTests.cs
index 7c7f7b7..2d08c5b 100644
--- a/aoc2021.test/DayTests.cs
+++ b/aoc2021.test/DayTests.cs
@@ -38,6 +38,7 @@ public class DayTests
     [DataRow(typeof(Day15), "702", "2955")]
     [DataRow(typeof(Day16), "852", "19348959966392")]
     [DataRow(typeof(Day17), "12090", "5059")]
+    [DataRow(typeof(Day18), "4289", "")]
     public void CheckAllDays(Type dayType, string part1, string part2)
     {
         var s = Stopwatch.StartNew();
@@ -85,6 +86,7 @@ public class DayTests
     [DataRow(typeof(Day15), "40", "315")]
     [DataRow(typeof(Day16), "16", "15")]
     [DataRow(typeof(Day17), "45", "112")]
+    [DataRow(typeof(Day18), "4140", "")]
     public void CheckTestInputs(Type dayType, string part1, string part2)
     {
         Day.UseTestInput = true;
diff --git a/aoc2021/Day18.cs b/aoc2021/Day18.cs
new file mode 100644
index 0000000..06fce6b
--- /dev/null
+++ b/aoc2021/Day18.cs
@@ -0,0 +1,116 @@
+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 Tree<int>.Node(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;
+            if (node.Right != null && ReduceRecurse(node.Right, reducer)) return true;
+            return false;
+        }
+
+        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()
+    {
+        var result = _fishes.Skip(1).Aggregate(Parse(_fishes.First()), (a, b) => Add(a, Parse(b)));
+        return Magnitude(result.Root);
+    }
+
+    public override object Part2() => "";
+}
diff --git a/aoc2021/Tree.cs b/aoc2021/Tree.cs
new file mode 100644
index 0000000..cfd8633
--- /dev/null
+++ b/aoc2021/Tree.cs
@@ -0,0 +1,59 @@
+namespace aoc2021;
+
+public class Tree<T>
+{
+    public class Node
+    {
+        public Node? Parent { get; private set; }
+        public T Data { get; set; }
+        private List<Node?> Children { get; }
+
+        public Node? Left
+        {
+            get => Children.Count >= 1 ? Children[0] : null;
+
+            set
+            {
+                if (value != null) value.Parent = this;
+                if (Children.Count >= 1) Children[0] = value;
+                else Children.Add(value);
+            }
+        }
+
+        public Node? Right
+        {
+            get => Children.Count >= 2 ? Children[1] : null;
+
+            set
+            {
+                if (value != null) value.Parent = this;
+                if (Children.Count >= 2) Children[1] = value;
+                else if (Children.Count == 0) Children.Add(null);
+                Children.Add(value);
+            }
+        }
+
+        public Node(Node? parent, T data)
+        {
+            Parent = parent;
+            Data = data;
+            Children = new();
+        }
+
+        public int DistanceToParent(Node parent)
+        {
+            var current = this;
+            var dist = 0;
+            while (current != parent)
+            {
+                dist++;
+                current = current?.Parent;
+            }
+
+            return dist;
+        }
+    }
+
+    public Node Root { get; }
+    public Tree(Node root) => Root = root;
+}
\ No newline at end of file
diff --git a/aoc2021/input/day18.in b/aoc2021/input/day18.in
new file mode 100644
index 0000000..e6ac9d1
--- /dev/null
+++ b/aoc2021/input/day18.in
@@ -0,0 +1,100 @@
+[1,[[3,6],[0,[6,3]]]]
+[[[5,2],[[5,0],6]],[6,[5,1]]]
+[[5,[[2,3],[7,1]]],[4,[9,[8,3]]]]
+[[8,[[3,4],[8,7]]],[[[4,0],[3,5]],[[0,1],6]]]
+[[1,[6,[9,0]]],[[7,[5,7]],[[8,9],3]]]
+[[[[6,7],[4,9]],7],9]
+[[7,3],[[8,9],[7,[4,2]]]]
+[[[4,[2,9]],[0,3]],[[4,[0,8]],[[4,4],3]]]
+[[[[6,9],9],8],[[[4,0],[1,6]],[4,[3,6]]]]
+[[4,[4,[3,3]]],[[2,1],[[6,1],[9,4]]]]
+[[5,[6,7]],[[[5,8],[4,3]],[4,[0,8]]]]
+[[6,[[9,6],5]],[0,[6,6]]]
+[[[[1,5],9],[[5,3],5]],[[[2,0],3],9]]
+[4,3]
+[[1,8],[[[1,0],[3,8]],3]]
+[[[[2,0],[6,5]],4],[[[9,8],[0,1]],3]]
+[[8,[7,8]],[[6,[3,2]],[[8,1],[7,5]]]]
+[[[[1,4],2],[[4,8],[3,2]]],[[[2,2],6],6]]
+[[[4,[0,5]],[[8,8],[7,2]]],[[4,[4,1]],2]]
+[[1,[4,[4,0]]],[2,[[2,3],1]]]
+[[[[2,1],0],[[3,4],1]],[[2,4],3]]
+[[9,[8,7]],[7,[0,[8,0]]]]
+[[[9,9],7],[[0,[2,1]],[[7,1],4]]]
+[[6,[[3,2],[0,0]]],[[[4,1],9],[7,3]]]
+[[[5,[5,6]],[[7,7],[7,8]]],4]
+[[8,[[4,1],4]],[[[6,4],[0,3]],[5,[6,4]]]]
+[[[9,0],[2,8]],[[6,5],5]]
+[[[3,[1,6]],[[5,3],6]],[[[7,4],[4,9]],[[2,3],[6,5]]]]
+[[8,[6,7]],6]
+[[[[6,0],[1,3]],[0,0]],[[[4,7],[7,8]],[[7,2],2]]]
+[[6,[[9,6],[1,1]]],7]
+[[[2,3],[6,0]],[3,[[9,3],9]]]
+[[[3,0],0],[[[6,0],3],[[1,5],4]]]
+[[8,[[0,3],8]],[[[0,8],[4,3]],[8,[3,4]]]]
+[[[4,4],0],[[1,[8,0]],[[9,6],3]]]
+[8,[[6,[6,7]],[8,7]]]
+[[8,[0,[1,4]]],3]
+[[[[9,5],0],[[5,3],[1,9]]],[[[7,3],5],[[4,3],9]]]
+[[[[9,0],[4,2]],[0,[3,2]]],1]
+[[[6,[4,2]],[[5,5],9]],[[[6,1],9],[[3,8],[8,1]]]]
+[[[3,[5,0]],[[5,2],[2,2]]],[[0,2],[7,4]]]
+[[3,[[5,7],[2,8]]],4]
+[[[4,8],5],0]
+[[[6,9],[[7,0],7]],[8,7]]
+[[7,[[1,3],[0,2]]],[[[4,8],0],[[7,0],6]]]
+[[[1,7],[6,6]],[[6,[4,0]],[0,4]]]
+[[[[2,2],[3,9]],9],3]
+[0,[[4,9],[[5,5],[5,9]]]]
+[[[[4,4],2],[6,4]],[[[4,1],[2,0]],[[9,4],0]]]
+[[[0,[3,4]],[2,3]],[[7,[2,3]],[3,3]]]
+[[[[0,3],9],7],[7,[4,[9,6]]]]
+[[9,[[0,8],4]],[5,[2,[4,9]]]]
+[[6,2],[[1,7],0]]
+[[[[1,6],[8,3]],1],[[[6,7],2],[[4,4],8]]]
+[[[[7,1],[0,3]],0],[5,[4,[8,4]]]]
+[[[[4,2],[6,2]],[[5,7],8]],[[7,9],4]]
+[[[0,[0,4]],5],2]
+[[2,[[0,6],6]],[[[3,4],3],[4,5]]]
+[[[[6,4],9],[[7,1],0]],[[[8,2],[3,2]],[[1,9],7]]]
+[7,[[7,8],[[5,5],0]]]
+[[[1,2],[8,5]],[[5,4],[8,0]]]
+[[4,[1,3]],[[[4,5],[1,2]],[5,1]]]
+[[[[0,7],[4,5]],[9,[2,2]]],[4,[[1,8],[7,5]]]]
+[[4,[[0,4],[8,8]]],[[[9,2],[7,1]],[8,[9,5]]]]
+[1,3]
+[[[[8,9],5],0],[1,6]]
+[[[[6,6],[3,5]],[[2,8],[3,3]]],[[[5,3],[5,9]],[0,[1,4]]]]
+[[7,[7,[5,5]]],[4,[4,[9,9]]]]
+[[[7,[6,7]],[4,2]],[0,[[7,8],1]]]
+[[[[6,0],4],[3,[6,9]]],5]
+[[[[9,8],6],[[7,4],[3,4]]],[[[8,8],[2,1]],0]]
+[9,[[1,7],[7,1]]]
+[6,[[3,[3,6]],[2,9]]]
+[[[6,9],[[1,4],2]],[7,3]]
+[[1,[6,[8,5]]],[[[0,0],0],[7,2]]]
+[[[4,[2,7]],[[0,0],8]],[[4,[4,5]],[[4,8],[3,3]]]]
+[[[[7,4],[7,5]],[[5,8],3]],[[[6,9],[0,9]],[[7,2],[4,0]]]]
+[4,[4,[9,[5,7]]]]
+[[[[8,7],3],[6,[0,5]]],[[[7,8],[5,1]],[[0,4],2]]]
+[6,[0,[4,3]]]
+[[[[6,5],3],7],[[[0,1],5],[6,[2,6]]]]
+[[[9,1],[[8,8],[8,2]]],0]
+[[[[3,4],1],3],[8,[[1,5],[5,6]]]]
+[[[[6,8],2],4],[[5,8],[[1,5],[7,0]]]]
+[[3,8],[[[9,0],2],[7,[5,8]]]]
+[[[[7,5],6],[[4,4],[5,0]]],[4,[3,[3,0]]]]
+[[[7,9],[1,[8,8]]],[[[6,8],4],4]]
+[[4,[[6,7],[5,7]]],[6,7]]
+[[[[8,8],[0,4]],[[5,5],1]],6]
+[[[7,7],[[5,8],[3,4]]],[[0,[7,4]],5]]
+[8,[[1,2],[6,9]]]
+[[[[9,5],[0,6]],[2,[8,7]]],[[[9,2],4],6]]
+[[[1,[5,2]],5],[[1,0],3]]
+[[7,[7,[3,7]]],[[2,6],3]]
+[1,[[8,[7,1]],[3,8]]]
+[[[[3,2],[5,6]],2],[7,[0,0]]]
+[[[7,[4,6]],[9,[7,8]]],9]
+[[[[4,3],9],8],[[8,5],6]]
+[3,[[3,1],[[8,4],8]]]
+[[[9,[3,5]],[[0,9],[8,5]]],5]
diff --git a/aoc2021/input/test18.in b/aoc2021/input/test18.in
new file mode 100644
index 0000000..1368dc4
--- /dev/null
+++ b/aoc2021/input/test18.in
@@ -0,0 +1,10 @@
+[[[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]]]