News
Hints Days 17 - 19
Written on 19.12.2022 12:44 by Sven Rahmann
Good morning,
it seems to get a bit colder at the university; but the ZBI building is still warm. Over the last few days, the AoC problems were getting quite demanding, so here are some comments.
Day 17 (Saturday):
Part 1 of this game of "Tetris without rotation" is in principle straightforward, although it is unfortunately easy to make off-by-1 errors when deciding where to start with a new falling rock and when it comes to rest. It is crucial to look at and to reproduce the examples. In terms of data structures, I just used a simple list to represent the tower. Each level is again a list of characters (so I can modify it). The cycle() function from itertools can be helpful to implement the infinitely cycling rocks and jets.
Part 2 is more demanding, since we must build the tower for a ridiculously large number of steps, so we cannot do it explicitly. Instead, we note that at some point, something repeats over and over again. Note that we can describe the current "state" of the system by: (a) where we are in the rock cycle, (b) where we are in the jet cycle, and (c) how the last few (how many?) topmost rows of the tower look like. If a state repeats after gaining some height dh after using dr rocks, we can use this information to take shortcuts.
Day 18 (Sunday):
This problem was relatively easy in comparison, especially part 1 is straightforward; you just check all neighbors of a cube.
For part 2, you need to be able to distinguish outside from inside. Again, a small variation of the "connected components" algorithm from the lecture can be helpful. Then, for every cube, you just count neighboring fields that belong to the outside.
Day 19 (Monday, today):
In principle, this is a straightforward recursion. In each minute, you can take one of several possible decisions and recursively solve the problem with the updated resources, number of robots, and remaining time. However, because there are many possible branches after each minute (you can buy a new robot of one of 4 types, or do nothing, so there are up to 5 possibilities), the total number of recursive calls might be close to 5**24, which is impossible to evaluate. Fortunately, in many situations, most of the branches are not possible (you cannot "buy" a new robot if you do not have the resources), but you will still need to find more clever ways to limit the recursion in order to have your program finish before the deadline. So think about it: When does it make sense (or no sense) to buy another robot of type X? When does it make sense (or not) to do nothing in one round?
This is even more important in part 2, where the time frame increases from 24 minutes to even more. Of course, you must make sure that your "shortcuts" do not cut away the actual optimal solution! On my laptop, I needed roughly 70 seconds to run both part 1 and part 2 in the end in pure Python, using just-in-time compilation of the recursive function, I could finish in 3 seconds. We will discuss compilation in January. Perhaps, if you think harder than I did, even your pure Python solution may be faster than 70 seconds.