The advent of code is an event known among competitive programmers. It is a fun contest that releases a small algorithmic problem each day during the period before Christmas. Every day has two puzzles, from which the second is usually a harder extension of the original problem.
The advent of code usually has a strong daily increase in difficulty during the first days. The increase in difficulty slows down after a while (it felt for me like the increase in difficulty slowed down after about 10 days), and even stagnates for the last few days. In these last 10 days, the difficulty is mostly dependent on your background and your knowledge/strong suit.
This post is about my favorite days, meaning the problems that I enjoyed solving most. I will explain the posed puzzle and describe how I solved them.
Day 12
Part 1
Part 1 shows a rectangle filled with characters. All of them are lower case letters, with the exception of “S” and “E”, which stand for start and end. The question posed is to find the shortest path from “S” to “E”, where you can move from a lowercase letter to any letter that is a maximum of one higher than the current (e.g. you can move from c to d, but also to a, b and c. You can not move to any “higher” letter than d.).
For this solution, I used Dijkstra’s shortest path algorithm. This algorithm works as follows. You start at a position and add every other position that you can reach to a queue. These are added together with the “cost” it would take to reach them. If you were to add a node that is already in the queue, you only keep the one with the lowest cost. Now the most important part of Dijkstra is that this queue must be a priority queue, handling the lowest cost node first. This ensures that once you’ve handled a node, you’ve found the shortest path to reach that specific node.
For this specific problem, I knew that the cost to reach a node would always be exactly 1. Hence, I did not need a priority queue and I could stop the algorithm once I found the endpoint.
Part 2
Part 2 extended the problem. Now instead of starting from “S”, we could start from any point with an “a” as well. This means that we could try to find every possible start point (“S” and every “a”) and execute the same algorithm. However this didn’t please me at all. Instead I reversed the algorithm to start from “E” and search until it found either “S” or “a”. Once I found this, I could terminate the algorithm again, because I found my optimal solution.
Day 15
Part 1
Part 1 is about beacons with their respective range. The objective was to count the amount of positions on a specific row that were not reached by the beacons. The beacons make use of a Manhattan distance (this means left/right or up/down is in steps of 1, while going diagonal requires an up/down, followed by right/left, resulting in distance 2).
My initial thought was to read the beacons and calculate the reached spots. However, this would result in an enormous amount of objects being created without ever being used. The consequence of this would be a very slow algorithm.
I ended up only holding the positions and ranges of the beacons and, when asked, calculated the reached spots for that line. Because of the fact that it uses Manhattan distance, it was very easy to just calculate the range of positions that was reached by this beacon.
Part 2
Part 2 tells us that there is another beacon that we need to find, but it is not picked up by our beacons. The puzzle gives us a range in which we have to search and ensures us that there is only one valid solution.
The initial thought would be to loop over the given range and check if it’s within the distance of any of the beacons. This would be a compute intensive operation because of the amount of beacons and the size of the range.
However when you do read the hint given in the puzzle, it states that there is exactly 1 valid spot, which means it should be located at a distance of 1 more than the range of 1 or more of the beacons. Hence all we need to do here is check at these positions and verify whether the location is picked up by any of the other beacons.
Day 16
Part 1
Part 1 of this puzzle is about caves with building pressure. To lower the pressure, you can open valves. The speed at which it lowers the pressure is expressed in flow rate. Each cave has a valve, but not every cave has the same flow rate when opening the valve. The exercise also shows from which cave you can move to which other caves. There is also a limited time. For example, if you open the first valve (supposed to have a flow rate of 2) at minute 1, there is 29 minutes with a flowrate of 2, resulting in a decrease in pressure of 58. Each minute, you can choose to either open a valve, or move to a neighboring cave.
This is actually an exercise on graphs, in which you want to maximize the total flow rate. To make this puzzle easier to solve, I calculated the total time it would take from every single cave, to every other cave (e.g. if the caves are connected as a -> b -> c, it would take 1 minute to go from a to b, but it would take 2 minutes to go from a to c). With this, I did not need to simulate every minute, but I could make jumps instead, to go from each cave to another cave. This is required because choosing the best cave is a local optimum, which means choosing the best one might result in 2 slightly less optimal valves which are close to each other being skipped.
Because of this calculation and the usage of jumps, I had a pretty good branch pruning (= skipping certain branches) of my solution tree. Another optimization I used was acting like the caves with flow rate 0 as if they were open already.
Part 2
Part 2 of the puzzle gave me a second person (actually an elephant) opening valves, but less turns and wanted me to see what the maximum flow rate was in this case. To solve this, I actually used exactly the same solution tree as part 1, but only 26 turns deep. Now I chose combinations of 2 leaves to see what gave me the optimal solution. Since this gave me a feasibly fast solution, I did not bother optimizing further, but it should be possible to skip many branches by never letting the second worker go to a cave that is opened by the first one (because they are both doing all combinations of the solution tree).
Day 17
Part 1
Part 1 of this puzzle describes the problem. You have 5 blocks (think of tetris shaped blocks) that fall down. These blocks are picked one at a time in the same order. Further, the cave has a jet pattern, which means in each turn, a push to the left or to the right is given to a rock. At the end of the last jet, you have to use the first one again (think of it as a circular list). This is in essence tetris with a width of 7, the exercise is to see how high the tower being built is after dropping 2022 rocks.
For part one, I simply did the simulation to get the result. To make sure I did not have to do any special checks, I placed 7 squares as an initial row.
Part 2
Part 2 is where it becomes really interesting. This exercise is exactly the same as part 1, but instead you need to give the height of the tower after dropping 1.000.000.000.000 blocks. After simulating (my initial solution) this for about 10.000 rocks, I immediately knew that this would never work (because of performance).
My initial thought was still very naive. I was thinking about only holding the top X rows to speed up the check whether a block could drop further. This posed me with two concerns. The first one was what the amount of rows to hold should be. To make this issue clear, think of a lot of pushes to one side, this would mean that the one side builds a big tower, while the other side would remain empty (resulting in the need to hold many rows). The other concern is that even with this optimization, the amount of blocks to drop is still way too high.
My solution in the end was based on three hints given in the exercise. First of all, there are only 5 shapes of rocks. Second, there is a jet pattern, with pattern being the key word. Finally, the cave has a width of only 7. This means that there should be a pattern in increasing heights. In practice, if I have exactly the same jet as before, with exactly the same rock and exactly the same top layout of the tower, exactly the same as the previous time should happen.
To find the pattern, I created a record that holds the dropped rock, the initial jet (with index in original order) and the layout. To store this layout, I used the difference in height between each block and the height of the tower for each position. Once I had the pattern, all I had to do was to find the amount of times that pattern was repeated, add the height before it happens the first time (because of the initial row) and add the final amount of blocks after the last time the full pattern could be used. This gives the result in about a second.
Day 18
Part 1
Part 1 introduces the problem. There are drops of lava, which are represented as cubes with 3D coordinates. This part requires us to count the amount of touches with each other. This can be easily solved by taking the absolute value of the differences of each coordinate of the two cubes. After summing these up, I concluded that they touch when the result is equal to one.
Part 2
Once again, part 2 is an interesting one. Instead of counting touches with each other, we need to find how fast the lava drops will cool down, so we need to count the amount of exterior air. The difficulty here lies in situations where the lava drops have some 3D form with a non-occupied open space inside (this is not considered to be exterior air).
For this solution, I searched for the minimal and maximum values of the 3 coordinates. I made sure I could add cubes around it, so I needed to start at one less than the minimum and add cubes in all directions. The checks I needed to do was that the newly added cubes were within the borders (of my new minimum values and new maximum values) and were not yet in the grid (grid of new cubes combined with the original lava cubes). Now for every cube that I’m adding (recursively), I need to count the amount of touches with the initial lava cubes using the same technique as part 1.
Day 19
Part 1
Part 1 tells us about some resources that we want to mine. There are 4 resources in total. To mine these resources, we have multiple blueprints, each with their effectiveness (which we have to calculate). These blueprints tell us about the 4 robots (one for each resource respectively) their costs. We have 24 turns to maximize the amount of mined ores of the last resource. Each turn we can build a maximum of one robot, and each robot will mine one ore of its type.
I solved this issue by going depth first through the branches (for optimizations which is explained later, I need to visit all branches anyway to find the maximum). I calculated which robots I can build each turn and create a branch for each robot. I also created a branch for the decision not to build any robots at all.
The problem with this exercise is performance. The complexity of this solution in theory is O(n^5), since every node potentially could have up to five branches (4 robots or not building at all). To tackle this performance issue, I used an aggressive branch pruning technique. For this branch pruning, I used the following heuristics (= assumptions):
- We want to maximize the last resource, hence if we can build a robot for the last resource, we always decide to do so.
- For the other 3 robots, we check if we can build the robots.
- For the robots we can build, we check if we should build them. We should not build them if we already have as many robots of that resource as the biggest cost for that resource.
- We also should not build the robot if we have twice as many resources in stock as the biggest cost for that resource.
- For every branch we start, we calculate the amount of the last resource we would have if we were to build such a robot each turn (e.g. 4 turns to go means 3 robots building, hence mining 1 + 2 + 3 additional resources). If the amount is lower than the current maximum, we skip the branch as a whole.
This fifth heuristic had the biggest impact on performance in the end.
Part 2
Part 2 increased the problem size from 24 turns to 32. I used the same technique for this. My input did give a correct result with this, but I had one ore of the last resource short for the example input. Probably some branches were too aggressively pruned by heuristic 1 or 4, but I did not bother to figure it out.
Day 21
Part 1
Part 1 once again describes the problem. You need to crack a code, where a certain monkey knows that the result is an operation (+, -, / or *) of the value of two other monkeys. This continues until some monkeys have a simple number as a result instead of an operation. In essence, we’re creating a calculator.
For this exercise, I created a binary tree. Each node represented a monkey, where the result was a function calling the same function on the children and using an operator on the result. The leaves returned their value as a result of the function (end operation of the recursion).
Part 2
Part 2 changed the exercise quite a bit. Instead of an operation for the root, we needed to make the equality true. There also was one human among the monkeys (supposed to be us). Now we need to find which number we need to pass on upward in order to make the equality true. For this solution, I start at the leaf (which is the solution answer) and move up the binary tree to check what solution we need in order to fulfill the equality. Like this, I calculate again and again what value the parent needs in order to fulfill the equality until I end up at the “human” node.
My code
I published all my solutions on github. If you are interested in the exact implementation I used, go check out my github project. Also feel free to check out my personal website at https://www.dreeki.be to find out more about me and what I do.
Andreas De Witte
Java Crafter
Andreas is a highly motivated and competent Java Software Crafter. He holds a Bachelor and Master degree in Computer Science and is passionate about Information Technology
