benharri.org
my advent of code solutions
1namespace Solutions._2021;
2
3public record Node
4{
5 public int X { get; init; }
6 public int Y { get; init; }
7 public int Risk { get; init; }
8 public int Distance { get; set; } = int.MaxValue;
9 public bool Visited { get; set; }
10}
11
12/// <summary>
13/// Day 15: <a href="https://adventofcode.com/2021/day/15"/>
14/// </summary>
15public sealed class Day15Chiton() : Day(2021, 15, "Chiton")
16{
17 private static readonly (int x, int y)[] Adjacent = [(-1, 0), (1, 0), (0, -1), (0, 1)];
18 private Dictionary<(int x, int y), Node>? _fullGrid;
19 private Dictionary<(int x, int y), Node>? _grid;
20 private int _width;
21
22 public override void ProcessInput()
23 {
24 _grid = Input
25 .SelectMany((line, y) =>
26 line.Select((c, x) => (coord: (x, y), node: new Node { X = x, Y = y, Risk = c - '0' })))
27 .ToDictionary(t => t.coord, t => t.node);
28
29 _width = (int)Math.Sqrt(_grid.Count);
30
31 _fullGrid =
32 Enumerable.Range(0, 5).SelectMany(i =>
33 Enumerable.Range(0, 5).SelectMany(j =>
34 _grid.Select(kvp =>
35 {
36 var ((x, y), node) = kvp;
37 var newKey = (x: x + _width * i, y: y + _width * j);
38 return (newKey,
39 node: new Node { X = newKey.x, Y = newKey.y, Risk = (node.Risk + i + j - 1) % 9 + 1 });
40 })))
41 .ToDictionary(t => t.newKey, t => t.node);
42 }
43
44 private static IEnumerable<Node> GetNeighborsAt(IReadOnlyDictionary<(int x, int y), Node> grid, Node node)
45 {
46 foreach (var (i, j) in Adjacent)
47 {
48 var key = (node.X + i, node.Y + j);
49 if (grid.ContainsKey(key) && !grid[key].Visited)
50 yield return grid[key];
51 }
52 }
53
54 private static int DijkstraCost(Dictionary<(int x, int y), Node> grid, Node target)
55 {
56 var searchQueue = new PriorityQueue<Node, int>();
57 grid[(0, 0)].Distance = 0;
58 searchQueue.Enqueue(grid[(0, 0)], 0);
59
60 while (searchQueue.Count > 0)
61 {
62 var current = searchQueue.Dequeue();
63 if (current.Visited) continue;
64 current.Visited = true;
65 if (current == target) return target.Distance;
66
67 foreach (var neighbor in GetNeighborsAt(grid, current))
68 {
69 var alt = current.Distance + neighbor.Risk;
70 if (alt < neighbor.Distance) neighbor.Distance = alt;
71 if (neighbor.Distance != int.MaxValue) searchQueue.Enqueue(neighbor, neighbor.Distance);
72 }
73 }
74
75 return target.Distance;
76 }
77
78 public override object Part1() =>
79 DijkstraCost(_grid!, _grid![(_width - 1, _width - 1)]);
80
81 public override object Part2() =>
82 DijkstraCost(_fullGrid!, _fullGrid![(5 * _width - 1, 5 * _width - 1)]);
83}