The eleventh day presents us with a grid where each square is associated with its “power” (a function of its coordinates). We are supposed to find square windows in the grid with the largest sum of powers.
The input is a single integer
serial. We prepare a function to calculate the power of a square at coordinates .
In the first part, we are supposed to find a window with the largest power sum.
In order to avoid needless calls to
power when iterating over windows, we will use a standard trick and construct a grid
gcs of “up-left” cummulative sums in the grid. More specifically,
gcd, we use the recursive relationship
At this point, we can calculate the sum of powers in the window with the upper-left corner at position in constant time, as
Finally, we prepare a function
max_window which, given an integer , returns a triple with being the maximal possible sum of powers over windows, and is the upper-left corner of such a window. To solve the first part, we only need a single call
In the second part, we are after maximal sum of powers over windows of arbitrary size. For this it suffices to use the function
max_window from before, iterating over all possible windows sizes.
In the day 12, we are presented with a toy version of the »Conway’s Game of Life«, that is an (infinite) population of alive (
#) and dead (
.) cells, represented as a sequence. Each consecutive generation of the population is determined according to given rules: we take a look at a particular cell’s neighbourhood (2 cells to the left and 2 to the right), look up which rule applies to it, based on which we decide whether the cell will be alive or not in the next generation.
The key idea will be that we will be only retaining the portion of the cell population which contains some alive cells, keeping track of the index of this portion in the sequence (for this purpose the variable
shift will be used).
To apply rules at both ends of the portion correctly, we also make sure that we include at least 5 dead cells at either end, in each generation. This will be the job of the function
pad. The function
update will update the population to the next generation.
We will also need the
evaluate function. The “evaluation” of a generation will be the sum of indices of all cells that are alive.
Finally, we parse the initial population and the rules/instructions.
In the first part, we are supposed to find the “evaluation” of the 20-th generation.
In the second part, we are supposed to find the “evaluation” of the 50000000000-th generation. As this is a large number, we will need to be more clever here.
By observing how the generations evolve, one will notice that from some point onwards, each generation will be of the same pattern, only shifted by a constant (presumably, the problem input was designed to have this property). Assume that is the smallest integer such that the -th generation has the same pattern as the -th generation, only shifted.
The key observation is that for any , the “evaluation” of the -th generation is a simple linear function:
The input for the thirteenth day is hiding an ASCII “art” representing a system of tracks, in which a few carts are buzzing around. At intersections, the carts are turning according to a specific rule. Our task will be to simulate the whole system and examine the crashes of the carts. A toy example of such a system is depicted below.
The problem is a very nice object-oriented programming task and we hence prepare a class
Cart representing the carts in the system. For each cart, we need to remember:
- Position. For a more compact solution, we will use the standard trick where the whole grid is represented as integer points in the complex plane. A position of the cart will in this representation be just a single complex number .
- Direction. We will need to know whether the cart is facing north, west, south or east. These four directions are in our representations the 4 complex units .
- Whether a cart has crashed. For this we only need a boolean variable
- The number of times the cart has crossed an intersection. This is needed to determine where the cart is turning at intersections, as specified by the problem’s intersection rule, and will be stored as an integer
The cart will also have the three following methods:
turn, which will take a look at the type of track currently below the cart, and change its direction accordingly. Note that turning left and right can be nicely represented as multiplication by the complex numbers .
move, which will move the cart to the next position.
crash, which will “crash” the cart.
Finally, we read the ASCII grid and create a
Cart object for each cart encountered.
In the first part, we need to find out where the first crash in the system occurs. For simplicity, we simply print the first crash while solving the second part.
In the second part, we are supposed to find the position of the only remaining cart after all of the other carts have crashed (yes, the input contains an odd number of carts). For this, we simply keep moving the carts, iterating in the manner specified by the problem (top-bottom and left-right), and crashing any two carts whose positions coincide.
In the day 14, we are being presented with a list and two pointers. At each step, we extend the list and update the pointers according to the specified rule.
The problem input is just a single integer.
In the first part, we are asked to keep updating the list until it is reaches the length , then print out the last 10 digits. Although the problem statement itself assumes the list to be actually a string, we shall be using only a list of integers throughout. As Python’s conversions between integers and strings are quite expensive, this speeds up the process substantially.
In the second part, we are asked to keep updating the list until it contains a sublist (continuous) representing the digits of , then print out the index of such a sublist.
In the day 15, we will be simulating a war between Elfs and Goblins. This will be purely an object oriented programming task, where care will be needed to avoid pitfalls in many of the problem statement’s subtleties.
We construct a class
Unit representing the units in the war, equipped with three core methods needed to simulate the war:
turn, which takes the whole turn of the unit in the current round. The turn will consist of (possibly) moving and attacking.
move, which moves the unit towards the nearest enemy (according to given rules).
attack, which attacks the neighbouring enemy unit.
For the sake of compactness, we will (again) use the complex coordinates (as in Day 13). Related to this, a helper function
access_grid will come handy. This function, given a complex number and a two dimensional array, returns the entry corresponding to the coordinates represented by the complex number.
Finally, we read the input; a two dimensional grid.
In the first part, we are to simulate the war, where each unit, regardless of whether it is Elf or Goblin, has a fighting strength 3. We need to return the “value” of such a war, which is defined as the number of complete rounds multiplied by the sum of the health points of all surviving units.
In the second part, we are to find the smallest possible fighting strength for Elves, such that they win the war without any loses. After such a value is found, we need to return the “value” of the corresponding war again. Note that a linear search is necessary here, since the rules of the war are such that “elves with strength win the war without any losses” does not imply “elves with strength win the war without any losses”.