Day 6 assignment
The Historians use their fancy device again, this time to whisk you all away to the North Pole prototype suit manufacturing lab… in the year 1518! It turns out that having direct access to history is very convenient for a group of historians.
You still have to be careful of time paradoxes, and so it will be important to avoid anyone from 1518 while The Historians search for the Chief. Unfortunately, a single guard is patrolling this part of the lab.
Solution in Java
Full source can be found: in GitHub
For today I created a little parsing method to prepare the text input into a list blockades using Point instances. As well as parsing out the starting position of the guard.
1public void readInput() {
2 var row = 0;
3 var rows = 0;
4 for (var line : inputLoader.string().split("\n")) {
5 if (rows == 0) {
6 rows = line.length();
7 gridBounds = new Bounds(0, 0, rows - 1, line.length() - 1);
8 }
9
10 for (var i = 0; i < line.length(); i++) {
11 switch (line.charAt(i)) {
12 case '#':
13 blockades.add(new Point(i, row));
14 break;
15 case '^':
16 startPoint = new Point(i, row);
17 break;
18 default:
19 break;
20 }
21 }
22 row++;
23 }
24}
Part 1
The solution for part 1 of today is rather straight forward. We just move the currentPos using the currentDirection until we hit a point that is in the blockades list I created earlier.
As soon as we hit such a block we rotate the direction clock wise and continue walking. This repeats until we find the exit of the grid, marked by the position moving of the grid entirely.
1public void part1() {
2 var currentPos = startPoint;
3 var currentDirection = new Point(0, -1);
4
5 var visited = new HashSet<Point>();
6 while (gridBounds.inBounds(currentPos)) {
7 visited.add(currentPos);
8
9 var updatedPos = currentPos.translate(currentDirection);
10 if (blockades.contains(updatedPos)) {
11 currentDirection = currentDirection.rotateCW();
12 } else {
13 currentPos = updatedPos;
14 }
15 }
16
17 validator.part1(visited.size());
18}
Part 2
For part 2 today it becomes a bit more complicated. I chose to loop over all points in the grid and add a single wall at that point, unless there already was one. Then we replay the game and see if the guard gets stuck in a loop.
To speed things up a bit I chose to utilize the virtual thread concept added into Java 21. This would allow Java to find the path for each potential change in parallel.
1private record PointWithDirection(Point point, Point direction) {}
2
3public void part2() {
4 var counter = new AtomicInteger();
5 try (var executors = Executors.newVirtualThreadPerTaskExecutor()) {
6 for (var x = 0; x < gridBounds.width(); x++) {
7 for (var y = 0; y < gridBounds.height(); y++) {
8 var point = new Point(x, y);
9 if (!blockades.contains(point)) {
10 var updatedBlockades = new ArrayList<>(blockades);
11 updatedBlockades.add(point);
12
13 executors.submit(() -> {
14 if (playRound(updatedBlockades) == -1) {
15 counter.incrementAndGet();
16 }
17 });
18 }
19 }
20 }
21
22 executors.shutdown();
23 executors.awaitTermination(1, TimeUnit.MINUTES);
24 } catch (InterruptedException e) {
25 throw new RuntimeException(e);
26 }
27
28 validator.part2(counter.get());
29}
30
31private int playRound(List<Point> blockades) {
32 var currentPos = startPoint;
33 var currentDirection = new Point(0, -1);
34
35 var visited = new HashSet<PointWithDirection>();
36 while (gridBounds.inBounds(currentPos)) {
37 if (visited.contains(new PointWithDirection(currentPos, currentDirection))) {
38 return -1;
39 }
40 visited.add(new PointWithDirection(currentPos, currentDirection));
41
42 var updatedPos = currentPos.translate(currentDirection);
43 if (blockades.contains(updatedPos)) {
44 currentDirection = currentDirection.rotateCW();
45 } else {
46 currentPos = updatedPos;
47 }
48 }
49
50 return visited.size();
51}