From fac10609e89df6e693f8b7838c244513a0f6b334 Mon Sep 17 00:00:00 2001 From: Ben Harris Date: Thu, 23 Dec 2021 13:23:35 -0500 Subject: day 23 --- aoc2021.test/DayTests.cs | 2 + aoc2021/Day21.cs | 21 ++- aoc2021/Day23.cs | 126 ++++++++++++++++ aoc2021/Extensions.cs | 23 +++ aoc2021/Tree.cs | 59 -------- aoc2021/Utils.cs | 374 +++++++++++++++++++++++++++++++++++++++++++++++ aoc2021/input/day23.in | 5 + aoc2021/input/test23.in | 5 + 8 files changed, 554 insertions(+), 61 deletions(-) create mode 100644 aoc2021/Day23.cs delete mode 100644 aoc2021/Tree.cs create mode 100644 aoc2021/Utils.cs create mode 100644 aoc2021/input/day23.in create mode 100644 aoc2021/input/test23.in 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; + +/// +/// Day 23: +/// +public sealed class Day23 : Day +{ + private readonly List _crabs; + + public Day23() : base(23, "Amphipod") + { + _crabs = Input.SelectMany(l => l).Where(char.IsLetter).ToList(); + } + + private static IEnumerable BreadthFirstSearch(string s, int i) + { + var visited = new HashSet(); + var queue = new Queue(); + 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 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> Indexed(this IEnumerable source) + { + return source.Select((t, i) => new KeyValuePair(i, t)); + } + + public static IEnumerable> WhereValue(this IEnumerable> source, Func 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 -{ - public class Node - { - public Node? Parent { get; private set; } - public T Data { get; set; } - private List 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 : Dictionary where TKey : notnull +{ + public DefaultDict() + { + } + + public DefaultDict(IDictionary dict) : base(dict) + { + } + + public TValue? DefaultValue; + + public DefaultDict(IEnumerable> 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 +{ + public class Node + { + public Node? Parent { get; private set; } + public T Data { get; set; } + private List 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 where TCell : notnull +{ + public Func>? Neighbors; + public Func? Distance; + public Func? Cell; + + public Dictionary ComputeAll(TCell start, IEnumerable all) + { + var dist = new Dictionary(); + foreach (var cell in all) + { + dist[cell] = int.MaxValue; + } + + dist[start] = 0; + var queue = new PriorityQueue(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 Compute(TCell start) + { + var dist = new DefaultDict { DefaultValue = int.MaxValue, [start] = 0 }; + var seen = new HashSet(); + var queue = new PriorityQueue(); + 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 count) + { + var total = 0; + var seen = new HashSet(); + var queue = new Queue(); + 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 ComputeWhere(TCell start, Func valid) + { + var dist = new DefaultDict { DefaultValue = int.MaxValue, [start] = 0 }; + var seen = new HashSet(); + var queue = new PriorityQueue(); + 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 ComputeFrom(TCell start, Func? valid = null) + { + valid ??= _ => true; + var dist = new DefaultDict + { DefaultValue = (int.MaxValue, default)!, [start] = (0, default)! }; + var seen = new HashSet(); + var queue = new PriorityQueue(); + 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 ComputePath(TCell start, TCell target, + Func? valid = null) + { + valid ??= _ => true; + var dist = new DefaultDict + { DefaultValue = (int.MaxValue, default)!, [start] = (0, default)! }; + var seen = new HashSet(); + var queue = new PriorityQueue(); + 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? valid = null) + { + valid ??= _ => true; + var dist = new DefaultDict { DefaultValue = int.MaxValue, [start] = 0 }; + var seen = new HashSet(); + var queue = new PriorityQueue(); + 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 +{ + IEnumerable GetNeighbors(TCell cell); + + int GetWeight(TMid mid); + + TCell GetNeighbor(TCell from, TMid mid); +} + +public static class DijkstraExtensions +{ + private static Dijkstra Build(this IDijkstra dijkstra) where TCell : notnull + { + return new() + { + Neighbors = dijkstra.GetNeighbors, + Distance = dijkstra.GetWeight, + Cell = dijkstra.GetNeighbor + }; + } + + public static Dijkstra ToDijkstra(this IDijkstra dijkstra) + where TCell : notnull + { + return dijkstra.Build(); + } + + public static Dictionary DijkstraAll(this IDijkstra dijkstra, TCell start, + IEnumerable all) where TCell : notnull + { + return dijkstra.Build().ComputeAll(start, all); + } + + public static Dictionary Dijkstra(this IDijkstra dijkstra, TCell start) + where TCell : notnull + { + return dijkstra.Build().Compute(start); + } + + public static Dictionary DijkstraWhere(this IDijkstra dijkstra, TCell start, + Func valid) where TCell : notnull + { + return dijkstra.Build().ComputeWhere(start, valid); + } + + public static Dictionary DijkstraFrom( + this IDijkstra dijkstra, TCell start, Func? valid = null) where TCell : notnull + { + return dijkstra.Build().ComputeFrom(start, valid); + } + + public static int DijkstraFind(this IDijkstra dijkstra, TCell start, TCell target, + Func? valid = null) where TCell : notnull + { + return dijkstra.Build().ComputeFind(start, target, valid); + } + + public static Dictionary DijkstraPath( + this IDijkstra dijkstra, TCell start, TCell target, Func? valid = null) + where TCell : notnull + { + return dijkstra.Build().ComputePath(start, target, valid); + } + + public static IReadOnlyCollection GetPathTo(this Dictionary dist, + TCell target) where TCell : notnull + { + var list = new LinkedList(); + list.AddFirst(target); + while (true) + { + if (!dist.TryGetValue(target, out var pair)) return Array.Empty(); + 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# + ######### -- cgit 1.4.1