It’s time again for the Reindeer Olympics! This year, the big event is the Reindeer Maze, where the Reindeer compete for the lowest score.
Solution in Java
Full source can be found: in GitHub
Part 1
Since the problem statement clearly indicates that a path solving algorithm would be best suited I decided to re-use the existing Dijkstra implementation. To use it I added the Step class which implements the Node<T> used by the algorithm.
1private record StepDirection(Point location, Direction direction) {}
2
3private class Step extends Node<Step> {
4 private final Point location;
5 private final Direction direction;
6 private final HashMap<StepDirection, Step> cache;
7
8 private Step(Point location, Direction direction, HashMap<StepDirection, Step> cache) {
9 this.location = location;
10 this.direction = direction;
11 this.cache = cache;
12 }
13
14 @Override
15 public List<NeighbourWithCost<Step>> neighbours() {
16 return location.neighbours()
17 .stream()
18 .filter(point -> grid.at(point) != '#')
19 .map(step -> {
20 var direction = Vector.direction(location, step);
21 var cost = direction.equals(this.direction) ? 1L : 1001L;
22 if (!cache.containsKey(new StepDirection(step, direction))) {
23 var nextStep = new Step(step, direction, cache);
24 cache.put(new StepDirection(step, direction), nextStep);
25 return new NeighbourWithCost<>(nextStep, cost);
26 }
27
28 return new NeighbourWithCost<>(cache.get(new StepDirection(step, direction)), cost);
29 })
30 .toList();
31 }
32}
Then for the first part of today I indicated the algorithm to run to find the cheapest way for the reindeer to get through the maze.
1public void part1() {
2 var startPos = new Step(grid.findChar('S').getFirst(), Point.east, new HashMap<>());
3 var endPos = grid.findChar('E').getFirst();
4
5 startPos.setCost(0L);
6 var cost = PathFinding.dijkstra(
7 List.of(startPos),
8 step -> step.location.equals(endPos));
9
10 if (cost.isEmpty()) {
11 throw new IllegalStateException("No path found");
12 }
13
14 validator.part1(cost.get().cost());
15}