Advent of Code 2021

Just like last year, I am attempting the Advent of Code. Last time I managed to finish it in time, even if posting on the solutions was less punctual. I expect this time will not be different, I am not committing to write the blog posts every day; I will be happy enough if I can find the time to once again do each exercise on its day. This year's code will be in this repo in GitHub.

For convenience, I will repeat from the original intro post.

There are some general aspects of the repo, that may be relevant to highlight. First, the exercises for each day are in a puzzleXX.py file, where XX is the corresponding day. The puzzle input if needed is in a file with the same name and .in extension. In some cases the puzzle gives a smaller example that is useful for testing, and those have a .in.test extension; since each puzzle has a read_input() method, changing the file that is read there will switch between the full and test input. Remember that the input files are personalized, so using mine will not give you the right answer for you, you'll need to substitute your own input files.

The different aoc.* scripts help in removing boilerplate. aoc.py allows to run specific puzzles and parts, with aoc and aoc.bat being thin wrappers (for Linux and Windows, respectively) so that part p of day d can be run with [./]aoc d p. All puzzles return the expected answer so it can be copied directly.

I will link to the posts for each day below, or you can use the aoc2021 tag to filter them.

Links to posts:

• Day 1

Advent of Code 2020 - Day 25

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.

Part 1

After going through the problem description, we get the following cryptographic process:

• A transformation starts with value 1 and multiplies it modulo 20201227 by the input number a certain number of times (the loop size)
• For the handshake:
• Each side transforms the number 7 using their (secret) loop size; the result is each side's public key
• Each side transforms the other's public key, and the result is the encryption key, which is the same in both cases

We get both public keys and we are asked to find the encryption key.

There is probably a fancy, clever way to do this (or maybe not), but we will start by trying brute forcing it, to see if it finishes in a reasonable time (spoiler alert: it does).

The first step is finding the loop sizes. Given the input number (7) and the public key, we can run one loop of the transformation at a time and check if we have obtained the public key. Once we do, that iteration sets the loop size.

If we want to scrape a bit more of performance, we can check both public keys in the same loop until we find both, instead of restarting the search for each.

Once we have that, it's just a matter of applying the transformation with the corresponding loop size.

Part 2

There is no part 2 on day 25! We get our last star for free.

This finishes the Advent of Code 2020 series. See you for Advent of Code 2021.

Advent of Code 2020 - Day 24

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 is Conway's Game of Life once again, only this time on a hexagonal grid. The first part deals with initialization, and the second one with the Game of Life itself.

Part 1

First, we need to decide on a coordinate system for the hexagonal grid. There are multiple approaches, with different tradeoffs, but for something simple as this we can opt for a straightforward one. We will not use the true Cartesian coordinates of the (centres of the) hexagons or the 3-component variants. Instead, we will number the columns so that to adjacent hexagons are separated by two units, allowing for the additional, vertically shifted, column that wedges between them. We do this based on columns because the movement directions are east (e), west (w), north-east (ne), north-west(nw), south-east (se), and south-west (sw); which puts a vertex on top and bottom and edges to the sides. Movements e and w then move 2 steps in the appropiate direction, while ne, nw (se, sw) move one step up (down) and one to the corresponding side.

This part sets the initial field by flipping some tiles. Each time, the specified tile is changed from its white or black state to the opposite, and all start white. The tile is specified as a sequence of e, w, ne, nw, se, sw movements starting from the origin. As we have done several times before, we will use complex numbers to make it very simple to operate with the 2d vectors. The real part grows towards the east, and the imaginary part towards the north. Thus, for instance, nw moves (-1+i).

When reading the sequence of movements we need to disambiguate whether the e's and w's stand on their own or as part of a ne, nw, se, sw movement. Since n and s cannot appear on their own, we can just take the next character (which must be e or w) as part of that movement, and any other e or w that we come across stands alone.

This means that we only have a complete movement on an e or w character. We can accumulate the movement as we go, starting with 0 (no movement). When we find an n or s, we increment the movement by i or -i accordingly; when we find an e or w, we increment by 1 or -1 if there is already some movement (i.e. right after n or s), or by 2 or -2 otherwise. In either case, we return the movement and reset it to 0. If we add up all the movements in the path, we get to the specified tile.

To answer this first part, we just need to count the tiles that were visited an odd number of times, as those are the ones that will be in a different state than at the beginning, therefore black.

Part 2

Now comes the Game of Life. The starting grid is given by part 1. We build it in the code by doing the flipping, but we could also just create a set of the tiles returned in part 1.

With an infinite grid, rather that checking all tiles, which is obviously impossible, we will only check those that can be black in the next step: the ones that are black now, and their neighbours (a white tile that is not adjacent to any black tiles will not become black).

We define the neighbours by adding each potential movement e, w, ne, nw, se, sw. We use this twice: once to determine the candidate tiles, and then again to count the number of black tiles adjacent to each candidate (which could also be calculated as the size of the intersection of the set of black tiles and the set of neighbours). The rest of the logic is trivial, especially after seeing several variants of the game in previous days.

Advent of Code 2020 - Day 23

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 exercise requires tracking the positions of numbers 1 through nine in a circular buffer, starting in the sequence given in the input, and performing 100 moves like this:

• Take the three number following the current one out.
• Select the destination as current number minus one, keep going down if it is not in the buffer (i.e. if it has been taken out), and wrap around to the highest value if you go below the lowest one.
• Insert the three numbers you took out next to the destination number.
• The new current number is the one next to the current one

Part1

We will represent the circular buffer as a deque. We will keep the current number at position 0 as a way to easily track it.

The step function performs one move. We start by looking at which is the current number, then rotate the buffer one place to the left, both updating the current position for the next step and setting the numbers that have to be taken at the beginning of the buffer so we can take them out using popleft. We next find the destination number (keep subtracting one as long as the destination is not in the buffer, i.e. while it is in the taken out triplet, with wraparound), and the corresponding position (index), and insert the numbers right after it. We insert them in reverse order at the same position, but we could also insert them in order incrementing the position with each step.

Part 2

For this part we will take 1,000,000 numbers. The initial ones are scrambled as given in the input, and after that in order. And also we perform 10,000,000 moves.

With these numbers, the approach from part 1 is too slow, it requires too many memory reorganizations when performing the moves.

To solve this we will build a data structure that doesn't require moving the data around: a linked list, where only the references of which number follows which need to be updated, and it can be done locally (in our previous version, taking out the initial numbers requires moving close to the full million numbers, and then all numbers after the destination for each insertion). Although I have to admit that I spent some time looking for a more mathematical approach.

We will create a CircularList class for this specific problem. It will keep a list of nodes, so that the node content (the number) matches the position in the list. Each node contains a value (the number) and a reference to the next node in the list. It will also have a head, a reference to the current number.

Since Python lists are 0-indexed, we will shift all numbers by -1 (it does not change the behaviour), and undo the change afterwards. There is no significant performance penalty: the subtraction need only be made for the initial 9 numbers, as the rest is generated already shifted; and only two numbers of the output need to be converted back.

A different option would be representing the linked list as a dictionary with the numbers as keys, and the successors as values. The way we have it is more explicit on the linked list concept, but the dictionary would be more efficient.

As we are making the class specific to the problem, we will give the initial sequence and the total size as inputs. We generate all the nodes, without connections, and then set the connections. For the first nine we need to follow the initial sequence (modified by the -1), and then they go in order, until the last one which connects back to the first number (not necessarily the first node!).

We build extract and insert methods to make the intent clearer. Inserting is relatively easy: we get the destination node, take its successor for later (the restart), and connect it instead to the head of the list to insert. Then we take the last node of the list we are inserting, and connect it to the restart.

Extraction is a little bit more complicated, but not much. We take the head, and move four steps through the links to record where it will restart. Then we build the extracted list by taking the three nodes following the head, and disconnecting the last of them from its successor. Finally we connect the head to the restart.

With this operations, the step is trivial, and now the problem is solved efficiently enough.

Advent of Code 2020 - Day 22

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 exercise consists of a simulation of a card game. We get as input two decks, each a sequence of integers (the values of the cards), for the two players. We read that in two stages, one per player, skipping the headers (that´s the purpose of the line = next(f) lines). We store the decks as deques, as we will be adding and removing items on both ends. We use appendleft to add the cards, so that the topmost one is at the end (so it can be popped).

Part 1

The game is quite straightforward. We play until one of the decks runs out (the condition for the while). In each step, we remove the topmost card from each deck, compare and put both at the end of the winner's deck. By keeping the same deque objects all the time we can check the winner by checking the ID of the deck (winner is deck1).

Since that is the way we check for the winner, we need to return the deck that still has cards, that's the winner. The line return deck1 or deck2 works exactly like that combining Python's truthiness evaluation and short-circuiting or.

Part 2

We now have a recursive version of the game.

The first difference is that we need to keep track of the states at different stages. We will keep them in a set, and represent each state as a tuple of two elements, each a tuple version of each deck. With that we can check at each step the winning condition of repeating a state.

The other difference is that, when we draw the cards, we check their values against the number of cards in the decks, and if either deck has fewer cards than the value of its current playing card we go into the recursive game. Otherwise, we play the usual game as before.

The recursive game is, as it would appear, just a recursive call to the game. We just need to be careful to use a copy of the decks for the recursive game, and check the winner against these copies.

Advent of Code 2020 - Day 21

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.

In this problem we get some foods (as the list of ingredients) and allergens contained (although some maybe omitted). We will read the input as a list of tuples, one tuple for each food containing the set of ingredients and the set of allergens.

Part 1

This part requires finding out the ingredients that do not contain any allergens. We will do it in two steps.

First, we will find the candidate ingredients for each allergen. We just go over each food, and add its ingredients to the set of candidates for each allergen it contains. The answer is the set of ingredients not in the union of the candidates to all allergens.

Part 2

We now need to identify the sources of each allergen. We will start from the candidates determined in part 1, and apply the same elimination strategy we applied for identifying fields in a previous problem.

Advent of Code 2020 - Day 20

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.

For this problem we get a set of tiles, each a (potentially rotated and/or flipped) fragment of a global image. Each tile is 10x10 with the inner 8x8 actually the image data, while the outer edges are there just to indicate matching of two tiles: to form the global image, the edges of adjacent tiles must match; that means applying different flipping and rotation to each tile to build a coherent whole.

Part 1

For this part we need to identify the corner tiles. We don't need to rebuild the whole image, just find the tiles with edges matching other tiles on two edges. Since we will need to do that for part 2, we will start to create a Tile class, that we will extend later; but if we were just concerned about this part, we wouldn't need this level of complexity.

We will initialize the tiles from the input, with the tile ID and the ten, ten-char lines. We need to keep the ID, keep the inner 8x8 part as the tile itself, and the boundaries. We need to establish a convention for storing the edges, to make sure that we are matching them in the right way (not really important at this stage, but unavoidable when rotating and flipping tiles to build the whole thing). We will store the edges in clockwise order starting at the top, horizontal edges left-to-right and vertical ones top-to-bottom. These directions need to be absolute like this; if we choose relative directions, such as clockwise, the bottom edge of one tile and the top edge of the tile below (for instance) would be stored in opposite directions, and would not match.

We will further consider all edges inverted as potential boundaries, to account for potential flips and rotations. With this, we can pair-wise compare the tiles and look for adjacency, which happens if the intersection of one tiles edges and the potential edges of the other one is non-empty. We use this condition to build an adjacency matrix using a dictionary with each tile ID as key and the set of compatible tiles as value. With this matrix, we just need to take the IDs of the tiles with degree 2 (i.e. the set of compatible tiles has two elements).

Part 2

For the second part we need to find sea monsters in the image, which means we need to assemble the whole image first. We will add some functionality to the tiles to help in this. First, the ability to rotate and flip themselves; these are quite straightforward, but we must take care to properly apply the operation to the edges. Next we will use the adjacency matrix to give each tile links to the tiles it matches with, so it has a direct way to refer to its neighbours.

We will build the image one row at a time. We choose any corner as the top left. The choice is irrelevant; the result of each choice can be converted in one of the others by rotating and/or flipping the image.

We will use the match function to apply the necessary operations to a tile until its top and left match the given tiles, using None for borders. This is as easy as rotating the tile until the top matches its target. If the left does not march like that, a horizontal flip must do the trick.

We match the right position of the initial corner. Then we can fill in the first row; we know the next tile is the right-neighbour of the previous one, and we match it to None and the previous tile.

Next we fill in subsequent rows, each starting with the bottom-neighbour of the first tile in the previous row, matched to that tile and None, and continuing matching to the corresponding tile in the previous row and the previous tile in the current row.

Once we are done, we stitch everything together into a single image.

Now for the monsters. We will define a monster by the positions of '#' characters with respect to the top left position in the 'window' that contains the monster, as well as the window's width and height.

To find the monsters we slide the window over the image, convolution-like, and at each position we check if all the monster positions contain a '#' in the image. If so, we mark those positions.

Since the image may be flipped or rotated we try all combinations until we find one with monsters.

Once we have that, we get the positions of all the '#' characters in the image. The answer to the problem is the size of the difference of the two sets. The difference of the sizes will not work, as there may be overlaps in the monsters.