Advent of Code 2021 - Day 7

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Today's problem is very interesting, even if it looks simple. We start with a set of values, which we read into a list as usual: strip, split on comma, cast to int.

Part 1

We are asked to find the value that minimizes the sum of distances to the given values. This is a well-known problem in optimization, and the answer is the median of the points. In one dimension there is little to think about; for higher-dimensional spaces, the result depends on the norm used.

The median is easily calculated: sort the values and take the value in the central position of the ordered array (same number of elements above and below). For an even number of items, take the midpoint of the two central values.

Part 2

Now we change the definition of the distance, and for an absolute difference of n we have a distance of 1 + ... + n. The first thing we note is that this is the harmonic series, and the sum is known to be n*(n+1)/2, which will be an integer as either n or n+1 will be even. That will save some looping.

With this new distance, the median is no longer a valid answer. Instead we will run an optimization algorithm. In this case, a modified bisection. Since the distance behaves like a norm, the optimization problem of minimizing the sum of distances is convex, and the derivative (with respect to the selected point) will be increasing, starting negative and ending positive.

So we are looking for a point that is lower in this sum of distances than the points surrounding it on either side. We set the high and low limits at the extremes of the points, and look at the midpoint of that. If the points to either side are both larger in sum of distances, we have our answer. If the sum increases (lower on the left, higher on the right), we are on the far side of the objective function, so we drop the high limit to the midpoint. If it's the contrary, we raise the low limit to the midpoint. We repeat this until we find the point we look for.

Since the span of the interval is halved at each step, this is guaranteed to happen in log2(N) steps for an initial range span of N.

Advent of Code 2021 - Day 6

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Once we strip this of the lanternfish, we have an array. Each element is an int which decreases by 1 at each step. If one element would decrease below 0, a new one with a value of 8 is added at the end of the array, and the element that would pass below 0 resets to 6. The initial values in the array are the puzzle input.

Reading the initial array is trivial (strip, split on comma, cast each element to int).

Part 1

How many elements will there be in the array after 80 steps? We will try the simple solution of directly simulating the process as described. Probably enough for this part, and not for part 2, but we don't know if that's the case, so let's avoid premature optimization.

The simulation of a step is straightforward: run along the array; if an element is 0, set it to 6 and add a new element of value 8 at the end; if it's other value, just decrement it by one. Since we will be modifying the array as we traverse it, we loop over the indices with the initial length, so that we do not go into the elements newly added at this step.

Rinse and repeat 80 times.

Part 2

The direct simulation will not do for 256 steps with the hinted exponential growth. We have to get clever. Maybe it's the fish, but this smells of recursion.

For each element, we can try to calculate the size of the population it will spawn in the remaining time. At first we have a population of one (the item itself). We decrease the remining time by the initial value of the element (the steps needed to reach 0), and enter the loop of spawning. The loop ends when there is no remaining time, which can be even before it is entered (if the initial value is greater than the remaining time). This is the base case of the recursion, where no recursive call is made . Inside the loop, we add the population of the newly spawned item: this is the recursive call, using the current remaining time, and an initial value of 9 (starting from eight down to, and including, zero). We keep adding population of new elements after removing 7 steps from the remaining time, and the recursion keeps track of all the details for us.

Since there can be many recursive calls inside each calculation, and many number will repeat even in the initial step, we could calculate the population for each value 0-6, and apply that to the initial array. Instead, we will just call the function on each element and adding them up, which is easier to understand. To avoid repeating calculations, and probably even beyond the initial values, we just cache the recursive function.

Advent of Code 2021 - Day 5

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Today we follow straight lines. Each is given by its endpoints as x, y coordinates. For the first part we only look at orthogonal lines (aligned with either axis), which suggests that in the second part we will use all, so we will build the method to read data considering an option to filter out the diagonal ones (the only non-orthogonal ones).

First we read each line: split on the ' -> ' to get the two endpoints, then split on the comma in each endpoint to separate the coordinates. We write it in a general way that would work for points in any dimension. We convert the endpoints to ints.

For each line we yield it, or skip it if it is not orthogonal and we have the flag. Checking orthogonality is just a matter of checking if both endpoints have the same x or y coordinate.

Part 1

The question we are asked is how many points are crossings of two or more lines. So, we will count how many lines pass each point. We start by creating a counter, a dictionary indexed by the points where we will add the lines passing. Points not in the dictionary have no lines passing, and are not relevant.

Now we only need to enumerate the points that each line passes, and add one to the corresponding counter. This is little more than a loop keeping the common coordinate constant, and the other one ranging from the minimum to the maximum of the endpoints (both included, careful of the off-by-one error: ranges in Python do not include the stopping point).

Finally, we count how many values in the counter dictionary are two or more.

Part 2

As we had foreseen, now we use all lines. The rest is just the same. Only two tweaks needed: first, remove the flag to filter non-orthogonal lines; second, we need to enumerate the points in diagonal lines, which we did not have before.

For the enumeration, we take the endpoints in the order given, and build the ranges for each x and y. The main issue is ensuring we go in the right direction. We look at the difference, and set the corresponding delta to 1 or -1 accordingly. And we add the delta to the second endpoint: adding 1 works when the range is increasing, but not if it's decreasing.

Just zip both coordinates to step along the line. The rest is just as before.

Advent of Code 2021 - Day 4

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

It's bingo time. The input to today's problem is one line with a sequence of numbers, the ones that will be called, and then several boards: each five lines of five numbers; boards are separated by blank lines. In fact, we won't make assumptions on the size (except expecting that the sizes are coherent).

We take the first line and map the int constructor to each number in there. Then, we build a list of boards: we start with an empty list, and an empty board. For each line, we interpret it as a list of ints, and add that as a row to the board. When we reach a blank line, the board is compete; we add it to the list of boards and start a new one. If at the end there is a non-empty board (it will happen if the file does not end with a blank line), we add that one, too.

Part 1

We will run the game by marking numbers as they are called on the boards. Once a board has a full row or column marked, it wins; the resulting score is the sum of unmarked numbers in the board, and that's the answer to our puzzle.

Rather than checking every row and column of every board after each number, we will use some data structures to make keeping track of things easier. We will use a dictionary to know where each number can be found, identified by a triplet of board, row, column. That's number_placements. Then we use a couple of arrays to count how many numbers are marked in each row and column of each board. The rows array is a list, and each item in it is a list for the corresponding board, with one element for each row, initialized to 0. The columns array is exactly the same.

We start calling numbers. For each, we add it to the marked set and check the number_placements to see where to mark it; then we go to the appropriate elements in the rows and columns array to increment the marked counters, and if one reaches 5 (the length of a row or column), we have the winner board.

We just take the board, as a set, so we can directly take out the marked numbers as set difference, and add up the remaining ones.

Part 2

Now we want to let the wookie giant squid win, so we will look at the last board to win. We will need to add a new set of remaining boards (identified by their indices), initialized with all of them. Once a board becomes a winner, we remove it from the remaining set, and add it to the winners set. We need the winners set, not just the remaining set, because when remaining gets to one element, that is the one we have to chose, but we still need to keep calling numbers until it marks a full row or column so we can calculate its score.

If we add the winning board to the winners set before removing it from the remaining set, and check that there is a single remaining element which is also included in winners at this point we identify this precise moment.

We can include all of this into the same loop of part 1 by using a to_win flag to chose which conditions to check.

Advent of Code 2021 - Day 3

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Today we wrangle binary numbers. We will read each as a list of 0's and 1's, and keep a list of them, so we can look at it as a matrix, with one number per row.

To convert back to decimal, we will use the classical approach of iteratively adding a bit and multiplying by 2, going from the most significant bit towards the least significant one, avoiding the use of exponentiation.

Part 1

The first part consists on calculating two simple indicators: one where each digit is the most common in that position across all numbers (i.e. the most common in the corresponding column of the matrix), and the other with the least common. Which means the complement of the first.

Once we have the first, we get the second one by transforming each digit x into 1 - x. If we were using binary numbers as such, the obvious would be to just XOR the first with a number all ones, but it's not worth doing the transformations.

To find out which digit is more common, we can just add the digits along the column. If we get more than half the length, ones are more common, otherwise zeros. We can use the length divided by two checking for a strictly greater sum or the length plus one divided by two accepting also equality; in both cases using integer division. This ensures that it works properly for both odd and even lengths.

For odd lengths, we need to divide by two and round up, and there is no possibility of a tie. For even lengths, there is the possibility of a tie; it is ignored for now, but it will be relevant in the second part. In this case the length divided by two marks the exact threshold (the tie, which can be assigned any way for the moment).

Part 2

In the second part we need to calculate two other indicators, a little more complex in this case. For both indicators, it's a matter of filtering out rows in stages until only one is left. Starting with the leftmost bit, and moving rightwards, we keep the rows that have the most (least for the second indicator) common bit in that position among the remaining rows at each step.

The reasoning about the threshold for the sum is as above, taking care of the possibility of ties. By using the (length + 1) // 2 threshold and accepting equality manages exactly that: in the case of even length, this still returns the exact half, which includes the tie, and in the case of odd length it returns the half rounded up as expected.

As for the implementation, the main potentially sticking points are making sure to work on a copy of the matrix to avoid modifying it before passing it on to the calculation of the second indicator and iterating over the rows (to be selected) and the current column (to use as filter).

Advent of Code 2021 - Day 2

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Today we process some directions consisting of a command and an argument. We start at (0, 0) in a two-dimensional space, and there are commands of the form direction argument, where direction can be forward, up or down, and the argument is a positive integer. The exact interpretation changes in each part.

Part 1

The interpretation of the commands is straightforward in this part: forward increases x, up decreases y, and down increases y; up and down seem to be inverted, but the story is about a submarine and the y axis represents depth, so it makes sense, and the description reminds us often of this. The argument is the step taken in the given direction.

Rather than updating after each step, we can take advantage of the associative property of addition to just add together the arguments for each direction and then calculate the movement horizontally (forward)  and vertically (down - up). We use a defaultdict as accumulator for easier reading; otherwise we would need to use a normal dictionary with the three values initialized as 0.

Part 2

For this part there is a third concept: aim, a sort of heading. up and down now change the heading, and forward moves horizontally by its argument as before, but also vertically by aim times the argument. This forces to track the state step by step, but it's just a matter of having three variables (two for the position, one for the aim) and applying each command with a plain if-elif-else structure.

Advent of Code 2021 - Day 1

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

This year's first exercise is quite straightforward. The input is a sequence of numbers.

Part 1

The task is to count how many of the numbers in the input are greater than the previous one. Using indexes, we could build a generator of the differences as:

diffs = (numbers[idx+1] - numbers[idx] for idx in range(len(numbers) - 1)

But this looks more like C than Python. We will avoid the indexing by zipping together the sequence and a shifted version:

diffs = (succ - pred for pred, succ in zip(numbers, numbers[1:]))

Then it's just a matter of filtering the positive differences and counting them.

Part 2

For the second part we only have to count the increasing numbers over a smoothed version of the sequence, a moving average of sorts (actually the sum of the rolling window, without dividing by its size). That means that it's only necessary to preprocess the numbers sequence.

The only point that needs some care is to ensure that the new sequence is of the right length: we are calculating sum(numbers[idx : idx + window]) for all indices idx from 0 to len(numbers) - window (including the last one, so the end of the range is that + 1). Stop before and not all possible windows will be included; stop later, and windows of smaller size at the end of the list will be included: the mistake will not cause an error, as slicing silently ignores indices beyond the end.

Luckily for those who make the mistake of going beyond the right index, with all the numbers being positive the extra windows will never increase compared to the one before, so the answer will actually be right. By stopping short it is possible to get the wrong answer, but only if the last window was increasing.