This year I took part in Advent of Code for the first time. Advent of Code is an exciting and challenging annual competition in which a task has to be solved every day from December 1st to December 25th. The task can be solved using any programming language such as Java, Typescript, Python, Rust, SQL and Go, and some participants even solve some tasks manually. Each task is divided into two parts. Only when the first easy part of the task has been solved can work on the second part begin.
The tasks touch on a whole range of sub-disciplines of computer science. It is therefore helpful to be familiar with standard algorithms, binary logic and optimization strategies. The aim of the competition is to find the correct solution to the task as quickly as possible, so many of the solutions are not particularly elegant.
For me, the task from December 20 is a good example of finding a solution in the competition. I solved the first subtask with a simple brute-force algorithm that had to be abandoned for the second subtask. In addition, code from another solution was reused for the solutions. To help the participants, a simplified example is always presented in the task, so an important step in finding a solution is to first find a solution for the example. If you have done everything correctly, your own algorithm will not only work for the example, but also for the actual input data.
This task from December 20 deals with a labyrinth problem, some of which appeared in the competition. In this case, the task is to find shortcuts through the maze. The following maze was given as an example. The start and finish are shown as S and E.
############### #...#...#.....# #.#.#.#.#.###.# #S#...#.#.#...# #######.#.#.### #######.#.#...# #######.#.###.# ###..E#...#...# ###.#######.### #...###...#...# #.#####.#.###.# #.#...#.#.#...# #.#.#.#.#.#.### #...#...#...### ###############
The signs # and . represent walls and paths respectively. If you look closely, you will see that it is not actually a labyrinth because there is only one path. The example is a square with a side length of 15, the actual input data contains a square with a side length of 142.
The task in the first part was to find shortcuts that allow two steps through a wall element. The first step goes into the wall, the second out again. Depending on the position of this step, the shortcut can be longer or shorter. The solution for this task was all shortcuts that were at least 100 steps shorter than the original route.
Various approaches are available to solve this task. As the aim of the competition is to find a solution as quickly as possible, the first step is to take a practical and not necessarily attractive route.
I have implemented all my solutions as JUnit 5 tests. This has the advantage that I can call up the tasks quickly from the IDE and have a variety of test methods for the intermediate results at hand. Of course, I can’t find the fastest solutions this way, but at least I’m quickly in developer mode.
To solve the task, I first need the correct path through the labyrinth. Because without knowing the overall route, no shortcut can be assessed.
In hindsight, of course, this is not entirely correct, because if you consider all alternative paths, i.e. shortcuts and detours, then the shortest path is smaller than the original path. But as mentioned above, it’s not the best or smartest solution that counts, but the time it takes to solve it. You have to work with the ideas you have after the starting signal and not with those that come to mind after the competition.
The test method described here shows my solution. First, the input data for the competition was read into the RaceTrack record. Then the original route is read in using the getBestWay method. This is followed by the brute force solution approach in the two for loops.
@Test
void first() {
RaceTrack raceTrack = getRaceTrack();
int sum = 0;
int limit = 100;
final CheatResult bestWaysResult = getBestWay(raceTrack);
for (int y = 1; y < raceTrack.height - 1; y++) {
for (int x = 1; x < raceTrack.width - 1; x++) {
Position newCheat = new Position(x, y);
if (raceTrack.fields.contains(newCheat)) {
continue;
}
List<Position> nextPositions = getNextPositions(newCheat, raceTrack.fields);
if (nextPositions.size() < 2) {
continue;
}
record PositionWithWeight(Position pos, int weight) { }
Comparator<PositionWithWeight> comparing = Comparator.comparing(PositionWithWeight::weight);
Position cheatStart = nextPositions.stream().map(p -> new PositionWithWeight(p, bestWaysResult.weights.get(p))).min(comparing).map(PositionWithWeight::pos).orElse(null);
Position cheatEnd = nextPositions.stream().map(p -> new PositionWithWeight(p, bestWaysResult.weights.get(p))).max(comparing).map(PositionWithWeight::pos).orElse(null);
int diff = bestWaysResult.weights.get(cheatEnd) - bestWaysResult.weights.get(cheatStart);
if (diff > limit) {
sum++;
}
}
}
assertEquals(XXX, sum);
}
Before I go into the brute force approach, I will explain the approach used here as the best way (the only way in this task). The basic idea is a diffusion from the start. The first path position is given the value 0 and the adjacent paths the value 1. Then, for all paths that have been given a value n, the adjacent paths are given the value n+1.
If weighted sections already meet, the adjacent sections are assigned the value n+1 starting from the smaller value. The route with the larger value must be a detour and is therefore discarded.
The value that is assigned to the destination at the end is the length of the shortest route. If you memorize the selected sections of the route in the meantime, you will also receive the route as a list of positions.
The brute force approach runs over all positions in the square and checks whether this position leads to a shortcut. Three checks are carried out for this purpose.
@Test
void first() {
RaceTrack raceTrack = getRaceTrack();
int sum = 0;
int limit = 100;
final CheatResult bestWaysResult = getBestWay(raceTrack);
for (int y = 1; y < raceTrack.height - 1; y++) {
for (int x = 1; x < raceTrack.width - 1; x++) {
Position newCheat = new Position(x, y);
if (raceTrack.fields.contains(newCheat)) {
continue;
}
List<Position> nextPositions = getNextPositions(newCheat, raceTrack.fields);
if (nextPositions.size() < 2) {
continue;
}
record PositionWithWeight(Position pos, int weight) { }
Comparator<PositionWithWeight> comparing = Comparator.comparing(PositionWithWeight::weight);
Position cheatStart = nextPositions.stream().map(p -> new PositionWithWeight(p, bestWaysResult.weights.get(p))).min(comparing).map(PositionWithWeight::pos).orElse(null);
Position cheatEnd = nextPositions.stream().map(p -> new PositionWithWeight(p, bestWaysResult.weights.get(p))).max(comparing).map(PositionWithWeight::pos).orElse(null);
int diff = bestWaysResult.weights.get(cheatEnd) - bestWaysResult.weights.get(cheatStart);
if (diff > limit) {
sum++;
}
}
}
assertEquals(XXX, sum);
}
The first check looks to see if the selected position is on the path. For it to be a shortcut, the position must be in the wall. Positions on the path are therefore discarded. The second check looks to see how many neighboring squares are on the path. If there is only one neighboring field on the path, then the position is a dead end that leads into a thicker wall. The third check validates the length of the shortcut. To do this, the largest and smallest weighted value for the neighboring fields is determined. The difference between the two values is the distance saved by this shortcut. If this value is greater than the desired limit of 100, then this shortcut is one of the shortcuts searched for.
The solution for the first subtask was thus found quite quickly and the second subtask could be started. The task changed so that not just one field could be run through, but a maximum of 10. The brute force approach no longer seemed practicable here, so a different approach was needed. In the end, the second subtask was solved using the following approach.
@Test
void second() {
RaceTrack raceTrack = getRaceTrack();
int limit = 100;
int sum = 0;
CheatResult bestWaysResult = getBestWay(raceTrack);
List<Position> result = bestWaysResult.result;
for (int i = 0; i < result.size() - 1; i++) {
for (int j = i + limit; j < result.size(); j++) {
Position cheatStart = result.get(i);
Position cheatEnd = result.get(j);
int brickTrackLength = brickTrack(cheatStart, cheatEnd);
if (brickTrackLength > 20) {
continue;
}
int diff = j - i;
if (diff - brickTrackLength >= limit) {
sum++;
}
}
}
assertEquals(XXX, sum);
}
Although the source code looks quite similar, the approach is different. In the first approach, all positions in the square were examined. This approach uses the property that the start and end of a shortcut must be on the original path. In addition, the end of the shortcut must lie after the beginning of the shortcut and, of course, with the minimum distance required for the length of the shortcut.
For all these pairs on the original route, their distance is calculated and then checked to see whether this shortcut fulfills all length criteria. The distance between the two positions on the route is important for the calculation. In fact, this calculation took some time due to a misunderstanding.
The illustration above shows the distance between two positions on the path. Regardless of which step sequence (yellow, blue or red) is used, the distance in steps is always x + y. With this approach, the second subtask was also solved.
The competition has now ended and I am looking forward to Advent of Code 2025. If you are a software developer and have not yet taken part, I would highly recommend this competition.