You all arrive at a Lava Production Facility on a floating island in the sky. As the others begin to search the massive industrial complex, you feel a small nose boop your leg and look down to discover a reindeer wearing a hard hat.
Solution in Java
Full source can be found: in GitHub
Part 1
The first step of today is to write a path finding algorithm based on Dijkstra. This will look for any path where each step size would be exactly 1 (line 12). And if the number 9 is found then the amount of found paths is increased.
1private int resolvablePaths(Point tailhead, CharGrid grid, boolean trackVisited) {
2 var visited = new HashSet<Point>();
3 var score = 0;
4
5 var processing = new LinkedList<Point>();
6 processing.offer(tailhead);
7
8 while (!processing.isEmpty()) {
9 var current = processing.poll();
10 for (var neighbour : current.neighbours()) {
11 if ((!trackVisited || !visited.contains(neighbour)) && (grid.at(current) - '0') == (grid.at(neighbour) - '1')) {
12 visited.add(neighbour);
13 if ((grid.at(neighbour) - '0') == 9) {
14 score++;
15 } else {
16 processing.offer(neighbour);
17 }
18 }
19 }
20 }
21
22 return score;
23}
For the part 1 solution it is as simple as creating a CharGrid from the input and then finding all tailheads (represented by 0). For each found tailhead I call the resolvablePaths to compute the amount of paths that can be made in the grid.
1public void part1() {
2 var grid = inputLoader.charGrid();
3 var tailheads = grid.findChar('0');
4
5 var paths = tailheads.stream()
6 .mapToLong(tailhead -> resolvablePaths(tailhead, grid, true))
7 .sum();
8
9 validator.part1(paths);
10}
Part 2
For part 2 of today I only set the flag to track visits to false and run the exact same pathfinding algorithm again. This bool flag will ensure that the algorithm allows visiting the same point in the grid multiple times.
1public void part2() {
2 var grid = inputLoader.charGrid();
3 var tailheads = grid.findChar('0');
4
5 var paths = tailheads.stream()
6 .mapToLong(tailhead -> resolvablePaths(tailhead, grid, false))
7 .sum();
8
9 validator.part2(paths);
10}