The Historians are quite pixelated again. This time, a massive, black building looms over you - you’re right outside the CPU!
While The Historians get to work, a nearby program sees that you’re idle and challenges you to a race. Apparently, you’ve arrived just in time for the frequently-held race condition festival!
Solution in Java
Full source can be found: in GitHub
Part 1
To represent each point in the grid of the assignment I created the GridPlace class. Which contains the value of the character in the grid as well as the distance from the start (as computed by the path taken).
1private static class GridPlace {
2 private final char value;
3 private int distance = Integer.MAX_VALUE;
4
5 private GridPlace(char value) {
6 this.value = value;
7 }
8
9 public void setDistance(int distance) {
10 this.distance = distance;
11 }
12
13 public boolean isNotWall() {
14 return value != '#';
15 }
16}
With the GridPlace class it is then possible to create the initial Grid instance using the input for todays assignment. Later on this grid instance can be used to compute any good places to put the cheats of the assignment.
1/**
2 * Prepares and processes a grid based on the inputLoader data.
3 *
4 * @return the prepared Grid object after processing and setting distances for grid places
5 */
6 private Grid<GridPlace> prepareGrid() {
7 var grid = Grid.of(
8 Arrays.asList(inputLoader.split("\n")),
9 (point, value) -> new GridPlace(value));
10
11 var startPos = grid.find(place -> place.value == 'S');
12 var investigate = Set.of(startPos.getFirst());
13
14 var currentDistance = 0;
15 while (!investigate.isEmpty()) {
16 var nextInvestigate = new HashSet<Point>();
17
18 for (var lookAt : investigate) {
19 var gridPlace = grid.at(lookAt);
20 gridPlace.setDistance(currentDistance);
21 for (var neighbor : lookAt.neighbours()) {
22 var nGridPlace = grid.at(neighbor);
23 if (nGridPlace.isNotWall() && nGridPlace.distance == Integer.MAX_VALUE) {
24 nextInvestigate.add(neighbor);
25 }
26 }
27 }
28
29 currentDistance++;
30 investigate = nextInvestigate;
31 }
32 return grid;
33}
Creating the method that can compute the walls to be removed using the amount of cheating picoseconds allowed is then only a matter of looping through the distance between any of the points in the path. For each of those you determine the potential gain if you move directly from point a to b.
1private int countCheatsWithMaxSteps(int steps) {
2 var grid = prepareGrid();
3 resetWalls(grid);
4
5 var cheats = 0;
6 var pathPositions = grid.find(GridPlace::isNotWall);
7 for (var cheatStart : pathPositions) {
8 for (var cheatEnd : pathPositions) {
9 var stepDistance = Vector.stepsInVector(cheatEnd, cheatStart);
10 if (stepDistance <= steps) {
11 var cheatDistance = grid.at(cheatEnd).distance - grid.at(cheatStart).distance - stepDistance;
12 if (cheatDistance >= 100) {
13 cheats++;
14 }
15 }
16 }
17 }
18 return cheats;
19}
20
21/**
22 * Resets the distance value of all grid places that are not walls to -1.
23 * This makes sure the gain computation is not exceeding the actual gain.
24 *
25 * @param grid the grid containing the grid places to reset
26 */
27 private void resetWalls(Grid<GridPlace> grid) {
28 grid.find(Predicate.not(GridPlace::isNotWall))
29 .stream()
30 .map(grid::at)
31 .forEach(gridPlace -> gridPlace.distance = -1);
32}
To complete the code for the first part of today is a matter of starting the countCheatsWithMaxSteps providing it 2 allowed steps, as we are allowed to cheat for 2 picoseconds.
1public void part1() {
2 validator.part1(countCheatsWithMaxSteps(2));
3}
Part 2
Since the first part of the code was already prepared to accept any number of picoseconds to cheat, for part 2 of today it was just a matter of changing it to allow 20 picoseconds.
1public void part2() {
2 validator.part2(countCheatsWithMaxSteps(20));
3}