You and The Historians look a lot more pixelated than you remember. You’re inside a computer at the North Pole!
Solution in Java
Full source can be found: in GitHub
Today the assignment involves yet another grid and pathfinding algorithm. So to read the input into memory I created this small method.
1public void readInput() {
2 grid = new CharGrid(71, 71);
3 inputLoader.splitOnNewLine()
4 .map(Point::of)
5 .limit(1024) // limit of bytes to fall part1
6 .forEach(point -> grid.set(point, '#'));
7}
Part 1
Since the best solution is using the Dijkstra pathfinding algorithm I created a HistorianStep implementation of the Node<T> that is required by the algorithm.
This implementation uses a cache to speed up computation for any already visited node in the grid.
1private class HistorianStep extends Node<HistorianStep> {
2 private final Point location;
3 private final Map<Point, HistorianStep> cache;
4
5 public HistorianStep(Point location, Map<Point, HistorianStep> cache) {
6 this.location = location;
7 this.cache = cache;
8 }
9
10 @Override
11 public List<NeighbourWithCost<HistorianStep>> neighbours() {
12 return location.neighbours()
13 .stream()
14 .filter(point -> grid.at(point) == '.')
15 .map(point -> cache.computeIfAbsent(point, key -> new HistorianStep(key, cache)))
16 .map(step -> new NeighbourWithCost<>(step, 1L))
17 .toList();
18 }
19}
Using the HistorianStep and the already processed input the remainder for part 1 is just a matter of preparing the Dijkstra and cache.
1public void part1() {
2 var stepCache = new HashMap<Point, HistorianStep>();
3 var start = new HistorianStep(Point.zero, stepCache);
4 var end = Point.of(grid.cols() - 1, grid.rows() - 1);
5
6 start.setCost(0L);
7 var cheapestRoute = PathFinding.dijkstra(List.of(start), step -> step.location.equals(end));
8 if (cheapestRoute.isEmpty()) {
9 throw new IllegalStateException("No path found.");
10 }
11
12 validator.part1(cheapestRoute.get().cost());
13}
Part 2
For the second part for today I chose a very naïve but simple approach. By creating a list of all not yet added blocks I could remove the first in a loop. Adding the removed block to the grid and re-running the pathfinding.
Then it is only a matter of repeating this exercise of removing the blockade and adding to the grid until the pathfinding no longer finds any routes.
1public void part2() {
2 var start = new HistorianStep(Point.zero, new HashMap<>());
3 var end = Point.of(grid.cols() - 1, grid.rows() - 1);
4
5 var allBlocks = new ArrayList<>(inputLoader.splitOnNewLine()
6 .map(Point::of)
7 .skip(1024)
8 .toList());
9
10 Point lastBlockAdded = null;
11 start.setCost(0L);
12 while (PathFinding.dijkstra(List.of(start), step -> step.location.equals(end)).isPresent()) {
13 lastBlockAdded = allBlocks.removeFirst();
14 grid.set(lastBlockAdded, '#');
15
16 start = new HistorianStep(Point.zero, new HashMap<>());
17 start.setCost(0L);
18 }
19
20 validator.part2(lastBlockAdded.x() + "," + lastBlockAdded.y());
21}