day 23

8 files changed, 554 insertions, 61 deletions

diff --git a/aoc2021.test/DayTests.cs b/aoc2021.test/DayTests.cs
index 54d5997..3aa8804 100644
--- a/aoc2021.test/DayTests.cs
+++ b/aoc2021.test/DayTests.cs
@@ -43,6 +43,7 @@ public class DayTests
     [DataRow(typeof(Day20), "5306", "17497")]
     [DataRow(typeof(Day21), "512442", "346642902541848")]
     [DataRow(typeof(Day22), "658691", "1228699515783640")]
+    [DataRow(typeof(Day23), "15365", "52055")]
     public void CheckAllDays(Type dayType, string part1, string part2)
     {
         var s = Stopwatch.StartNew();
@@ -95,6 +96,7 @@ public class DayTests
     [DataRow(typeof(Day20), "35", "3351")]
     [DataRow(typeof(Day21), "739785", "444356092776315")]
     [DataRow(typeof(Day22), "590784", "39769202357779")]
+    [DataRow(typeof(Day23), "12521", "44169")]
     public void CheckTestInputs(Type dayType, string part1, string part2)
     {
         Day.UseTestInput = true;
diff --git a/aoc2021/Day21.cs b/aoc2021/Day21.cs
index 7b045fe..4f74632 100644
--- a/aoc2021/Day21.cs
+++ b/aoc2021/Day21.cs
@@ -48,7 +48,7 @@ public sealed class Day21 : Day
         if (playerTurn == 1)
             foreach (var (key, value) in _possibleRollOutComes)
             {
-                var pts = (key + player1Pos - 1) % 10 + 1;
+                var pts = MoveSpaces(key, player1Pos);
                 if (player1Points + pts < 21)
                     RollDiracDie(player1Points + pts, player2Points, pts, player2Pos, 2, (value * universes));
                 else
@@ -57,7 +57,7 @@ public sealed class Day21 : Day
         else
             foreach (var (key, value) in _possibleRollOutComes)
             {
-                var pts = (key + player2Pos - 1) % 10 + 1;
+                var pts = MoveSpaces(key, player2Pos);
                 if (player2Points + pts < 21)
                     RollDiracDie(player1Points, player2Points + pts, player1Pos, pts, 1, (value * universes));
                 else
@@ -65,6 +65,23 @@ public sealed class Day21 : Day
             }
     }
 
+    private static int MoveSpaces(int numSpaces, int currentSpace)
+    {
+        int spaceLandOn, toAdd;
+
+        if (numSpaces > 10)
+            toAdd = numSpaces % 10;
+        else
+            toAdd = numSpaces;
+
+        if (currentSpace + toAdd > 10)
+            spaceLandOn = (currentSpace + toAdd) % 10;
+        else
+            spaceLandOn = currentSpace + toAdd;
+
+        return spaceLandOn;
+    }
+
     public override object Part1()
     {
         int p1Score = 0, p2Score = 0, p1Pos = _player1, p2Pos = _player2;
diff --git a/aoc2021/Day23.cs b/aoc2021/Day23.cs
new file mode 100644
index 0000000..3c6929c
--- /dev/null
+++ b/aoc2021/Day23.cs
@@ -0,0 +1,126 @@
+namespace aoc2021;
+
+/// <summary>
+/// Day 23: <see href="https://adventofcode.com/2021/day/23"/>
+/// </summary>
+public sealed class Day23 : Day
+{
+    private readonly List<char> _crabs;
+
+    public Day23() : base(23, "Amphipod")
+    {
+        _crabs = Input.SelectMany(l => l).Where(char.IsLetter).ToList();
+    }
+
+    private static IEnumerable<int> BreadthFirstSearch(string s, int i)
+    {
+        var visited = new HashSet<int>();
+        var queue = new Queue<int>();
+        queue.Enqueue(i);
+        visited.Add(i);
+        while (queue.Count > 0)
+        {
+            var next = queue.Dequeue();
+            var near = new[] { next - 1, next + 1 }.Where(p => !visited.Contains(p) && p >= 0 && p < s.Length);
+            foreach (var n in near)
+            {
+                if (!char.IsWhiteSpace(s[n])) continue;
+                yield return n;
+                queue.Enqueue(n);
+                visited.Add(n);
+            }
+        }
+    }
+
+    private static Dijkstra<State, (State state, int distance)> GetPathFinder(int size)
+    {
+        return new()
+        {
+            Neighbors = state =>
+            {
+                // Find all neighbors from the current state
+                var possible = new List<(State, int)>();
+                var entries = new[] { 2, 4, 6, 8 };
+                // Add each way of taking an item out of a hole into the hallway
+                foreach (var i in entries)
+                {
+                    var hole = state[i / 2 - 1];
+                    if (string.IsNullOrWhiteSpace(hole)) continue;
+                    var targets = BreadthFirstSearch(state.Hallway, i).Except(entries).ToList();
+                    foreach (var target in targets)
+                    {
+                        var data = state.Hallway.ToCharArray();
+                        data[target] = hole.Trim()[0];
+                        var newHole = hole.Trim()[1..].PadLeft(size);
+                        var next = State.New(state, data, i / 2 - 1, newHole);
+                        var cost = Math.Abs(target - i) + (size - newHole.Trim().Length);
+                        cost *= 10.Pow(data[target] - 'A');
+                        possible.Add((next, cost));
+                    }
+                }
+
+                foreach (var (at, which) in state.Hallway.Indexed().WhereValue(char.IsLetter))
+                {
+                    var dest = which - 'A';
+                    if (!BreadthFirstSearch(state.Hallway, at).Intersect(entries).Select(i => i / 2 - 1)
+                            .Contains(dest)) continue;
+                    if (state[dest]!.Trim().Any(c => c != which)) continue;
+                    var data = state.Hallway.ToCharArray();
+                    data[at] = ' ';
+                    var next = State.New(state, data, dest, (which + state[dest]!.Trim()).PadLeft(size));
+                    var cost = Math.Abs(at - (dest + 1) * 2) + (size - state[dest]!.Trim().Length);
+                    cost *= 10.Pow(dest);
+                    possible.Add((next, cost));
+                }
+
+                return possible;
+            },
+            Distance = tuple => tuple.distance,
+            Cell = (_, tuple) => tuple.state
+        };
+    }
+
+    public override object Part1()
+    {
+        var start = new State("           ",
+            $"{_crabs[0]}{_crabs[4]}",
+            $"{_crabs[1]}{_crabs[5]}",
+            $"{_crabs[2]}{_crabs[6]}",
+            $"{_crabs[3]}{_crabs[7]}");
+        var dest = new State("           ", "AA", "BB", "CC", "DD");
+
+        return GetPathFinder(2).ComputeFind(start, dest);
+    }
+
+    public override object Part2()
+    {
+        var start = new State("           ",
+            $"{_crabs[0]}DD{_crabs[4]}",
+            $"{_crabs[1]}CB{_crabs[5]}",
+            $"{_crabs[2]}BA{_crabs[6]}",
+            $"{_crabs[3]}AC{_crabs[7]}");
+        var dest = new State("           ", "AAAA", "BBBB", "CCCC", "DDDD");
+
+        return GetPathFinder(4).ComputeFind(start, dest);
+    }
+
+    private record State(string Hallway, string A, string B, string C, string D)
+    {
+        public string? this[int i] =>
+            i switch
+            {
+                0 => A,
+                1 => B,
+                2 => C,
+                3 => D,
+                _ => null
+            };
+
+        public static State New(State from, char[] hall, int i, string hole) =>
+            new(new(hall),
+                i == 0 ? hole : from.A,
+                i == 1 ? hole : from.B,
+                i == 2 ? hole : from.C,
+                i == 3 ? hole : from.D);
+    }
+}
\ No newline at end of file
diff --git a/aoc2021/Extensions.cs b/aoc2021/Extensions.cs
index 58efece..a04c4e1 100644
--- a/aoc2021/Extensions.cs
+++ b/aoc2021/Extensions.cs
@@ -50,4 +50,27 @@ public static class Extensions
             ? new[] { array }
             : array.SelectMany(t => Permute(array.Where(x => !x!.Equals(t))), (v, p) => p.Prepend(v));
     }
+    
+    public static int Pow(this int i, int power)
+    {
+        var pow = (uint) power;
+        var ret = 1;
+        while (pow != 0)
+        {
+            if ((pow & 1) == 1) ret *= i;
+            i *= i;
+            pow >>= 1;
+        }
+        return ret;
+    }
+    
+    public static IEnumerable<KeyValuePair<int, T>> Indexed<T>(this IEnumerable<T> source)
+    {
+        return source.Select((t, i) => new KeyValuePair<int, T>(i, t));
+    }
+    
+    public static IEnumerable<KeyValuePair<TKey, TValue>> WhereValue<TKey, TValue>(this IEnumerable<KeyValuePair<TKey, TValue>> source, Func<TValue, bool> func)
+    {
+        return source.Where(pair => func(pair.Value));
+    }
 }
diff --git a/aoc2021/Tree.cs b/aoc2021/Tree.cs
deleted file mode 100644
index cfd8633..0000000
--- a/aoc2021/Tree.cs
+++ /dev/null
@@ -1,59 +0,0 @@
-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/Utils.cs b/aoc2021/Utils.cs
new file mode 100644
index 0000000..78cce81
--- /dev/null
+++ b/aoc2021/Utils.cs
@@ -0,0 +1,374 @@
+namespace aoc2021;
+
+public class DefaultDict<TKey, TValue> : Dictionary<TKey, TValue> where TKey : notnull
+{
+    public DefaultDict()
+    {
+    }
+
+    public DefaultDict(IDictionary<TKey, TValue> dict) : base(dict)
+    {
+    }
+
+    public TValue? DefaultValue;
+
+    public DefaultDict(IEnumerable<KeyValuePair<TKey, TValue>> pairs) : base(pairs)
+    {
+    }
+
+    public new TValue? this[TKey key]
+    {
+        get => TryGetValue(key, out var t) ? t : DefaultValue;
+        set
+        {
+            if (value != null) base[key] = value;
+        }
+    }
+}
+
+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;
+}
+
+public class Dijkstra<TCell, TMid> where TCell : notnull
+{
+    public Func<TCell, IEnumerable<TMid>>? Neighbors;
+    public Func<TMid, int>? Distance;
+    public Func<TCell, TMid, TCell>? Cell;
+
+    public Dictionary<TCell, int> ComputeAll(TCell start, IEnumerable<TCell> all)
+    {
+        var dist = new Dictionary<TCell, int>();
+        foreach (var cell in all)
+        {
+            dist[cell] = int.MaxValue;
+        }
+
+        dist[start] = 0;
+        var queue = new PriorityQueue<TCell, int>(dist.Select(pair => (pair.Key, pair.Value)));
+        while (queue.Count > 0)
+        {
+            var cell = queue.Dequeue();
+            var current = dist[cell];
+            foreach (var neighbor in Neighbors!(cell))
+            {
+                var other = Cell!(cell, neighbor);
+                var weight = Distance!(neighbor);
+                if (current + weight < dist[other])
+                {
+                    dist[other] = current + weight;
+                }
+            }
+        }
+
+        return dist;
+    }
+
+    public Dictionary<TCell, int> Compute(TCell start)
+    {
+        var dist = new DefaultDict<TCell, int> { DefaultValue = int.MaxValue, [start] = 0 };
+        var seen = new HashSet<TCell>();
+        var queue = new PriorityQueue<TCell, int>();
+        queue.Enqueue(start, 0);
+        while (queue.Count > 0)
+        {
+            var cell = queue.Dequeue();
+            if (seen.Contains(cell)) continue;
+            seen.Add(cell);
+            var current = dist[cell];
+            foreach (var neighbor in Neighbors!(cell))
+            {
+                var other = Cell!(cell, neighbor);
+                var weight = Distance!(neighbor);
+                if (!seen.Contains(other)) queue.Enqueue(other, current + weight);
+                if (current + weight < dist[other])
+                {
+                    dist[other] = current + weight;
+                }
+            }
+        }
+
+        return dist;
+    }
+
+    public int Count(TCell start, Func<TCell, bool> count)
+    {
+        var total = 0;
+        var seen = new HashSet<TCell>();
+        var queue = new Queue<TCell>();
+        queue.Enqueue(start);
+        while (queue.Count > 0)
+        {
+            var cell = queue.Dequeue();
+            if (seen.Contains(cell)) continue;
+            seen.Add(cell);
+            foreach (var neighbor in Neighbors!(cell))
+            {
+                var other = Cell!(cell, neighbor);
+                if (count(other))
+                {
+                    total++;
+                    continue;
+                }
+
+                if (!seen.Contains(other)) queue.Enqueue(other);
+            }
+        }
+
+        return total;
+    }
+
+    public Dictionary<TCell, int> ComputeWhere(TCell start, Func<TCell, bool> valid)
+    {
+        var dist = new DefaultDict<TCell, int> { DefaultValue = int.MaxValue, [start] = 0 };
+        var seen = new HashSet<TCell>();
+        var queue = new PriorityQueue<TCell, int>();
+        queue.Enqueue(start, 0);
+        while (queue.Count > 0)
+        {
+            var cell = queue.Dequeue();
+            if (seen.Contains(cell)) continue;
+            seen.Add(cell);
+            var current = dist[cell];
+            foreach (var neighbor in Neighbors!(cell))
+            {
+                var other = Cell!(cell, neighbor);
+                if (!valid(other)) continue;
+                var weight = Distance!(neighbor);
+                if (!seen.Contains(other)) queue.Enqueue(other, current + weight);
+                if (current + weight < dist[other])
+                {
+                    dist[other] = current + weight;
+                }
+            }
+        }
+
+        return dist;
+    }
+
+    public Dictionary<TCell, (int Dist, TCell From)> ComputeFrom(TCell start, Func<TCell, bool>? valid = null)
+    {
+        valid ??= _ => true;
+        var dist = new DefaultDict<TCell, (int Dist, TCell From)>
+            { DefaultValue = (int.MaxValue, default)!, [start] = (0, default)! };
+        var seen = new HashSet<TCell>();
+        var queue = new PriorityQueue<TCell, int>();
+        queue.Enqueue(start, 0);
+        while (queue.Count > 0)
+        {
+            var cell = queue.Dequeue();
+            if (seen.Contains(cell)) continue;
+            seen.Add(cell);
+            var current = dist[cell].Dist;
+            foreach (var neighbor in Neighbors!(cell))
+            {
+                var other = Cell!(cell, neighbor);
+                if (!valid(other)) continue;
+                var weight = Distance!(neighbor);
+                if (!seen.Contains(other)) queue.Enqueue(other, current + weight);
+                if (current + weight < dist[other].Dist)
+                {
+                    dist[other] = (current + weight, cell);
+                }
+            }
+        }
+
+        return dist;
+    }
+
+    public Dictionary<TCell, (int Dist, TCell From)> ComputePath(TCell start, TCell target,
+        Func<TCell, bool>? valid = null)
+    {
+        valid ??= _ => true;
+        var dist = new DefaultDict<TCell, (int Dist, TCell From)>
+            { DefaultValue = (int.MaxValue, default)!, [start] = (0, default)! };
+        var seen = new HashSet<TCell>();
+        var queue = new PriorityQueue<TCell, int>();
+        queue.Enqueue(start, 0);
+        while (queue.Count > 0)
+        {
+            var cell = queue.Dequeue();
+            if (seen.Contains(cell)) continue;
+            seen.Add(cell);
+            if (Equals(cell, target)) return dist;
+            var current = dist[cell].Dist;
+            foreach (var neighbor in Neighbors!(cell))
+            {
+                var other = Cell!(cell, neighbor);
+                if (!valid(other)) continue;
+                var weight = Distance!(neighbor);
+                if (!seen.Contains(other)) queue.Enqueue(other, current + weight);
+                if (current + weight < dist[other].Dist)
+                {
+                    dist[other] = (current + weight, cell);
+                }
+            }
+        }
+
+        return dist;
+    }
+
+    public int ComputeFind(TCell start, TCell target, Func<TCell, bool>? valid = null)
+    {
+        valid ??= _ => true;
+        var dist = new DefaultDict<TCell, int> { DefaultValue = int.MaxValue, [start] = 0 };
+        var seen = new HashSet<TCell>();
+        var queue = new PriorityQueue<TCell, int>();
+        queue.Enqueue(start, 0);
+        while (queue.Count > 0)
+        {
+            var cell = queue.Dequeue();
+            if (seen.Contains(cell)) continue;
+            var current = dist[cell];
+            if (Equals(cell, target)) return current;
+            seen.Add(cell);
+            foreach (var neighbor in Neighbors!(cell))
+            {
+                var other = Cell!(cell, neighbor);
+                if (!valid(other)) continue;
+                var weight = Distance!(neighbor);
+                if (!seen.Contains(other)) queue.Enqueue(other, current + weight);
+                if (current + weight < dist[other])
+                {
+                    dist[other] = current + weight;
+                }
+            }
+        }
+
+        return -1;
+    }
+}
+
+public interface IDijkstra<TCell, TMid>
+{
+    IEnumerable<TMid> GetNeighbors(TCell cell);
+
+    int GetWeight(TMid mid);
+
+    TCell GetNeighbor(TCell from, TMid mid);
+}
+
+public static class DijkstraExtensions
+{
+    private static Dijkstra<TCell, TMid> Build<TCell, TMid>(this IDijkstra<TCell, TMid> dijkstra) where TCell : notnull
+    {
+        return new()
+        {
+            Neighbors = dijkstra.GetNeighbors,
+            Distance = dijkstra.GetWeight,
+            Cell = dijkstra.GetNeighbor
+        };
+    }
+
+    public static Dijkstra<TCell, TMid> ToDijkstra<TCell, TMid>(this IDijkstra<TCell, TMid> dijkstra)
+        where TCell : notnull
+    {
+        return dijkstra.Build();
+    }
+
+    public static Dictionary<TCell, int> DijkstraAll<TCell, TMid>(this IDijkstra<TCell, TMid> dijkstra, TCell start,
+        IEnumerable<TCell> all) where TCell : notnull
+    {
+        return dijkstra.Build().ComputeAll(start, all);
+    }
+
+    public static Dictionary<TCell, int> Dijkstra<TCell, TMid>(this IDijkstra<TCell, TMid> dijkstra, TCell start)
+        where TCell : notnull
+    {
+        return dijkstra.Build().Compute(start);
+    }
+
+    public static Dictionary<TCell, int> DijkstraWhere<TCell, TMid>(this IDijkstra<TCell, TMid> dijkstra, TCell start,
+        Func<TCell, bool> valid) where TCell : notnull
+    {
+        return dijkstra.Build().ComputeWhere(start, valid);
+    }
+
+    public static Dictionary<TCell, (int Dist, TCell From)> DijkstraFrom<TCell, TMid>(
+        this IDijkstra<TCell, TMid> dijkstra, TCell start, Func<TCell, bool>? valid = null) where TCell : notnull
+    {
+        return dijkstra.Build().ComputeFrom(start, valid);
+    }
+
+    public static int DijkstraFind<TCell, TMid>(this IDijkstra<TCell, TMid> dijkstra, TCell start, TCell target,
+        Func<TCell, bool>? valid = null) where TCell : notnull
+    {
+        return dijkstra.Build().ComputeFind(start, target, valid);
+    }
+
+    public static Dictionary<TCell, (int Dist, TCell From)> DijkstraPath<TCell, TMid>(
+        this IDijkstra<TCell, TMid> dijkstra, TCell start, TCell target, Func<TCell, bool>? valid = null)
+        where TCell : notnull
+    {
+        return dijkstra.Build().ComputePath(start, target, valid);
+    }
+
+    public static IReadOnlyCollection<TCell> GetPathTo<TCell>(this Dictionary<TCell, (int Dist, TCell From)> dist,
+        TCell target) where TCell : notnull
+    {
+        var list = new LinkedList<TCell>();
+        list.AddFirst(target);
+        while (true)
+        {
+            if (!dist.TryGetValue(target, out var pair)) return Array.Empty<TCell>();
+            if (pair.Dist == 0) break;
+            list.AddFirst(target = pair.From);
+        }
+
+        return list;
+    }
+}
\ No newline at end of file
diff --git a/aoc2021/input/day23.in b/aoc2021/input/day23.in
new file mode 100644
index 0000000..e20bc37
--- /dev/null
+++ b/aoc2021/input/day23.in
@@ -0,0 +1,5 @@
+#############
+#...........#
+###A#D#C#A###
+  #C#D#B#B#
+  #########
diff --git a/aoc2021/input/test23.in b/aoc2021/input/test23.in
new file mode 100644
index 0000000..6a7120d
--- /dev/null
+++ b/aoc2021/input/test23.in
@@ -0,0 +1,5 @@
+#############
+#...........#
+###B#C#B#D###
+  #A#D#C#A#
+  #########