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 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 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.

Advent of Code 2020 - Day 19

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 problem consists of the validation of messages according to a set of nested rules. The simplest are just a string, others are a sequence of rules (which is to be interpreted as the message being partitionable into substrings that match exactly those rules in that order), and the more complex ones include multiple alternative sequences (i.e. at least one of those sequences must match).

Since the numbers of rules is not too large, we will attempt a simple approach to begin with, and refine it if needed. Let's build all potential matching patterns for each rule.

Part 1

We'll start by building a Rule class. It will hold the patterns (once evaluated), a rule 'specification', and a pointer to the set (actually a dictionary) of rules, so it can refer to other rules when evaluating the patterns. It will also provide the overall behaviour, like creating the Rule from the textual specification given in the input, accessing the patterns, and checking for a match. Then we will have subclasses that specialize the evaluation of patterns according to the three types of rules described above.

Reading the input is quite straightforward: in each line the colon separates the key (an int identifying the rule) and the specification fed to the Rule constructor. The resulting rule will be the corresponding value in the ruleset dictionary.

The Rule constructor is a class method that will decide which subclass to use depending on the specification. Each subclass has a different representation of its specification:

• Leaf Rules just have the string they match (stripped from the quotation marks)
• Sequence Rules have a list of the identifiers of the rules they concatenate
• Alternative Rules have a list whose elements (the alternatives) are in turn lists like those in Sequence Rules

Evaluation of the patterns is similarly different for each rule type, but they all generate a set containing all messages matching the rule.

Leaf Rules generate just one pattern, the string they match.

For Sequence Rules, we go back to itertools.product to generate the Cartesian product of patterns matched by each rule in the sequence.

For Alternative Rules, we apply the same procedure as for Sequence Rules on each alternative, and join those together (actually, we could just have Alternative Rules,  where Sequence Rules would have just one alternative).

Once all rules are built, we take rule zero, which is the one we need to check, and build its patterns (this is done implicitly in the first match, and cached for subsequent ones; it will recursively build the patterns of all rules that are referenced from it). Then we check the match against the messages.

The matching is trivial: is the message in the set of matching messages?

Part 2

This part introduces loops in two of the rules. Handling the general case would be complex, but we can examine the specific rules given here and notice what they mean.

Our root rule is (8, 11); rule 8 is (42 | 42, 8); rule 11 is (42, 31 | 42, 11, 31). So rule 8 is one or more 42s, and rule 11, though a little harder to see, is one or more 42s followed by the same number of 31s. So if we take this rule 11, and prepend to it at least one 42, our root rule becomes one or more 42s followed by one or more 31s, with strictly fewer 31s than 42s.

Since everything else is the same, we can look at the results of part 1 to see that all patterns for 42 and 31 are of the same length, so we can divide the message in chunks of that length. The it's a matter of checking that we have one or more chunks that match 42, that they cover more than half of the message, and that the rest match 31.

For additional efficiency, we can discard any message that doesn't divide neatly into these chunks.

Advent of Code 2020 - Day 18

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 problem is basically evaluating expressions with varying operator precedence rules. It screams abstract syntax trees (ASTs), but I am a little out of my depth there, not my area of expertise. I'm sure that there are more elegant ways to solve this, potentially using the , but I decided to build quite an ad-hoc approximation.

Part 1

Addition and multiplication have the same precedence for this part, operations are evaluated left-to-right, and parenthesis remain highest priority as usual.

We will begin building our simplified version of an AST by defining a Node class and a Leaf class. The Nodes will have an operation to perform and left and right attributes pointing to the arguments (all operators are binary). We use a property to recursively evaluate the operation. The Leaves just contain values, and offer the same property as the Nodes to return the value (this is the base case for the recursion).

With this, we only need to build the AST from the literal expression. We will do it in two steps: tokenizing and parsing. The former will convert the expression into its semantic components (tokens), while the latter will build the AST from the sequence of tokens.

We are actually complicating the tokenization a little bit by considering multi-digit numbers (after looking at the input, all numbers are single-digit), but it's not that bad, so we'll keep it.

Basically, we are just looking at each character, and returning the appropriate symbol for it: if it's a digit, convert it to a number and wrap it up as a Leaf; if it's a paren, it's its own symbol; if it's an operator, return the corresponding Node (without linking left and right for now).

To account for multi-digit numbers, we just keep appending digits to a number as long as we get digits, and when we get a paren or an operator we convert the accumulated number and reset the accumulator, besides producing the paren or operator symbol.

Since we will evaluate left-to-right, we will reverse the sequence of symbols. This allows for easier parsing; grouping the operations as they come will group them properly in this way, considering a recursive parsing, which is easier to grasp: the first operation is applying the rightmost operator on the rightmost value and the subtree resulting from parsing everything to the left of the operator (leaving parens out of the explanation for clarity).

So we can take this explanation, and use it as the template for the recursive parsing (this time including the parens):

1. Take the first token. If it's a Leaf, it becomes the root of the AST, if it's a closing paren the root is the (recursive) parsing of the following tokens, as we will return from the function when reaching an opening paren. The roles of opening and closing parens are intentionally inverted due to our inversion of the token stream.
2. If there are no more tokens, or the next token is an opening paren (which, remember, is actually closing the parenthesized sub-expression), return the AST (the current root).
3. Take the operator (the only remaining option for the next token) and assign the root to its right, then make the operator node the new root. Finally, assign to its left the (recursive) parsing of the rest of the sequence.

Evaluation of the expression is straightforward: tokenize, parse, return the value of the AST.

Part 2

In the first part we didn't have to look at the operators as both of them had the same precedence, so we just applied them as they came. For the second part addition takes precedence over multiplication (otherwise it would be too easy, as we could use the built-in eval function).

We will change strategy slightly now. We start by pre-parsing the token stream and making each parenthesized sub-expression a list (and remove the parens symbols). This is accomplished quite easily with a recursive implementation: tokens are kept as-is, starting a paren group gets a recursive call, end when reaching the end of a paren group or the end of the token stream.

The new parsing will recursively parse parenthesized sub-expressions, so that we always apply operations to flattened lists of Leaves and Nodes, but we need to consider that the Nodes may be tree roots already (from a parenthesized sub-expression). This means that we first parse the sub-expressions, then apply all the addition operators, then apply the multiplications, and we are left with the resulting tree. Since we will be doing all of this accumulating on a list, the result is a single-element list that we need to pop.

The application of the operators is the most delicate part of the exercise. Unlike in the first part, we cannot assume that any Node is an unbound operator, as there will be multiple passes, and parenthesized sub-expressions will be processed before. So, to check if a Node is the type of operator that we want to apply we need to check that it's the right type and also that its right attribute is not yet assigned. We define the isop function to check this throughout.

The first token goes directly into the sequence that will be returned. After that we have two possibilities:

• The new token is the type of operator we want to apply. If the latest token in the sequence is also of this type (which implies not having its right assigned) we assign the new token to its right (this is just for symmetry, this should never happen, and would actually leave the right of the new token unassigned and unassignable). In the normal case, we just pop the last token from the list, assign it to the left of the new one, and put the new one in the list.
• The new token is not an operator of interest. We just add it to the list, unless the currently last token is an operator, in which case this goes to its right.

What we are doing effectively is taking every operator of the specified type that hasn't been processed yet and connecting it to their right and left, taking care that there may be other operators around.

We now have all steps: tokenize (same as part 1), apply parens, apply the new parsing with multiple passes for the operators. Finally get the value of the resulting AST.

One interesting thing to note is the usefulness of iterators for all of the recursive implementations: when you pass the iterator to a recursive call it will keep drawing from the point where it was, rather than restart (which would happen with an array or list). This removes the need to keep track of the position across calls, which would make everything more cluttered (the additional variable in the function, in the signature so it can be passed in, and as a return value to know where to continue when the recursion returns).

Advent of Code 2020 - Day 17

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 (we have seen it before this year), only in higher dimensions. Since parts 1 and 2 just differ by the number of dimensions, we will just build a generic version that works in 2+ dimensions.

We will represent the state using a set of active cells. The input gives us the x and y coordinates for the active cells in the initial state (marked with '#'), and we just add zeros to pad the rest of dimensions.

Next we need to calculate the neighbours of a given cell. The 'steps' from the cell are given by the Cartesian product of {-1, 0, 1} for each dimension, excluding the specific combination (0, 0, ...), which corresponds to the cell itself. This is what we are doing in the line:

deltas = product(*(range(-1, 2) for _ in point))

Then we yield (cell + delta) for each delta, but we skip the zero vector (that's what the if any(delta) is there for). Note that product is itertools.product, which returns an iterator over the Cartesian product of its inputs.

We are now ready to calculate a step of the game. First, we will create a new state to update and return, so that we can refer to the old state throughout; in Game of Life all updates are simultaneous.

Since we are using a sparse representation, we cannot just go over all the board checking the rules, instead we need to explicitly build the set of candidate cells, the ones that may be active in the new state. Given the rules, that includes the currently active cells and their neighbours. A cell that is not neighbouring some currently active cells won't become active.

Then it's only a matter of checking the rules on the candidate cells and adding to the new state the ones that should be active there.

Just run for 6 steps with 3 and 4 dimensions respectively to get the solutions to parts 1 and 2.

Advent of Code 2020 - Day 16

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 puzzle we have a bunch of items, each represented as a sequence of numbers. There are some fields, with constraints on the values that they can take, and we need to eventually identify which filed corresponds to each position in the sequence.

The input is not difficult to parse, but it needs to be done in stages:

1. The field rules, first splitting field from the ranges, then interpreting the ranges. One field per line, until a blank line is reached
2. The item we will use to validate (your ticket, per the problem description), a sequence of comma-separated ints.
3. The rest of items to be used for deducing the positions of the fields, a sequence like that in (2) per line.

Part 1

To begin with, we need to identify items with values that do not match any of the fields. We will create a valid_fields function that, given a number, returns the sets for which it is valid. We do this in validity, using the parsed filed rules from the input. validity returns the valid_fileds function.

The function itself is quite simple: take the number, and check for each field rule if it is within the corresponding interval(s); if so, that field goes into the returned set, otherwise it doesn't. This is readily expressed as a set comprehension, using any to iterate over potentially multiple intervals.

We can identify the invalid values, as they result in the empty set when run through this function.

Part 2

Now it's time to actually find out the positions of the fields. We will apply a form of constraint propagation, or elimination. We start with a set of feasible fields for each position, which includes all fields, then eliminate the possibilities that are not valid for some ticket.

For each item, we take the value in each position, and remove form the feasible fields for that position the fields for which the value is not valid, or conversely, we keep the intersection of feasible and valid. We need to be careful to check that the set of valid fields is not empty (we know there are invalid tickets from part 1), or alternatively we can eliminate the invalid tickets in a preprocessing pass.

We now have all the information contained in the items themselves encoded in the feasible sets. To finish, we need to apply and propagate a new constraint, one that is somewhat implicit: there is a one-to-one relationship between positions and fields.

In practice, we will keep track of all the positions that have been determined, i.e. they have a single field that is possible for them. We iterate over the positions, and add it to the determined set if there is a single feasible field or remove the determined fields from the feasible ones. We do this until all positions are determined.

Once we know which field is which, we can answer the question of multiplying the values in 'my ticket' for specific fields (those starting with 'departure').

Advent of Code 2020 - Day 13

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 puzzle, once you remove the decoration about buses, everything consists on cycles of given periods, and it screams modular arithmetic. The input is quite simple, a list of cycle periods with some xs; these just serve to set up the positions of the cycles, which will be used in the second part. A quick analysis of the cycle periods shows that all are prime numbers, which simplifies operations (the least common multiple of a group of prime numbers is their product).

Part 1

The question is, after translation, to find which cycle is the first to recur on or after a given time, and how long it will take.

We can easily calculate the time since the last recurrence of each period at a given time as time mod period. Then, the period less that is the remaining time until the next recurrence (unless the last recurrence was exactly at the given time, in which case we keep the zero).

We define a function to calculate this value for each period, apply it and keep the minimum.

Part 2

This one is a little tougher. We need to find the earliest time t so that each period recurs at t + p, where p is the position of the period in the period list (this is what the xs in the input are setting up).

What we will do here is construct a global cycle step by step. At each step we will add a new period.

The first step is easy: we can arbitrarily take -delay as the start of the cycle (where delay is the position of the first period), so that the initial recurrence at time zero fulfills the condition. The global cycle period is just the first period, so that the delay is kept. This is not explicit in the code as the first period is at position zero, so we can just keep the position.

To add the next period, we need to update the start of the cycle so that it the new delay matches. As long as we advance in increments of the global cycle the previous conditions hold. So we just do that, add one cycle at a time to the start time until the delay matches, that is (-delay = start) (mod cycle), which is expressed in a different way in lines 31 and 32 in the code. Then we update the global cycle by multiplying it by the new period that has been added (the advantage of all periods being prime numbers). This ensures that in the next iterations the conditions hold for all periods up to this one (the global cycle always is a multiple of each period included in it, so the delay is kept).

Rinse and repeat until all periods are included, with their corresponding delays.

Advent of Code 2020 - Day 10

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 today's puzzle, after stripping it of the adaptor theme, we are asked to work with a sorted sequence of numbers, and the difference between one and the next. It has to be sorted because of the monotonicity imposed by the description of the adaptors. The first thing is to get the sequence from the input, sort it, and add the zero and last value (which is just the maximum of the input plus three). With this dealt with in get_adaptors, we can move on.

Part 1

The question in this part is, once translated, how many differences of 1 and how many differences of 3 are there in the full sorted sequence.

We start by finding the differences. we could iterate over the indices and take adaptors[i] - adaptors[i-1], then keep count of the counters for differences of one and three by hand:

count1, count3 = 0, 0
for idx in range(1, len(adaptors)):
    diff = adaptors[idx] - adaptors[idx - 1]
    if diff == 1:
        count1 += 1
    elif diff == 3:
        count3 += 1

Instead we note that adaptors[1:] gives us the sequence displaced by one position, and we can zip it with the original to get consecutive pairs. This makes it easy to build a generator expression for the differences, which we can feed directly to a Counter to do the counting for us.

Part 2

And now to the interesting part of today's puzzle: how many valid arrangements can be made by dropping zero or more items from the sequence, but keeping the maximum difference at most three.

We could recursively generate all possibilities, but I don't think I have that much time. So let's use graphs once again. I'm starting to sense a pattern here...

Let's say each item is a node, and we get and edge from it to every item afterwards that is at most itself plus three, i.e. to compatible items. Now the question is how many paths from the first to the last item can we have in that graph.

That's easy to answer if we only have one item: one path, starting and ending at itself. And we can go on by induction for there. To calculate the paths that reach any item, we take all the items that can reach it directly and add the number of paths reaching each of them. Since each item can only be reached from items before it in the sequence, we can just update them in that order and the values needed will be available.

We build the graph as usual, using a dictionary with each item as keys, and the set of items that can be reached from it as value. We initialize the paths of the first item to 1, and from there we push the number of paths to the successors instead of pulling from the predecessors. This avoids cumbersome reverse lookups in the graph. The result is the same, we just add the number of paths corresponding to an item to all the items that can be reached from it. By the time we reach an item, all items that could contribute have already been processed, so the number is already correct.

To get the final answer, we take the number of paths reaching the last item.

Advent of Code 2020 - Day 9

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

This exercise asks us to find the first number in a sequence that cannot be expressed as the sum of two numbers in the 25 before it (obviously starting from the 26th number on). This sounds familiar; we will import our find_pair function. It's a good thing that we made the effort to make it separate from the rest of the logic and to make it efficient, as we will use it repeatedly.

In fact, that's all we need to do: get the number, the ones before it, and apply find_pair. The first time it fails, that's our answer. Instead of hardcoding the length of 25 number for the previous block, we will use a variable preamble, if only to check the example which uses a different length.

Part 2

Now a slightly different question: finding a contiguous subsequence of numbers in the sequence that add up to the target (which happens to be the answer from part 1).

As in other cases, trying out all possible combinations is not practical. We can take a look at the input and realize that all numbers are positive, which will make our work easier. We can make our chink a kind of rolling window over the sequence. If the sum of the numbers within the window is less than the target, we increase the size of the window by moving its end one position up (we add the next number); if we overshoot, we remove the first number in the chunk by moving up its start position. If the sum matches the target, we have our chunk.

This only works because we want a contiguous block (otherwise we need completely different approach) and all numbers are positive; if there were negative numbers, extending the chunk after overshooting could still give the right answer.

From the implementation point of view, there are a couple of things to keep in mind. first, we can keep track of the sum of the numbers in the window by adding/subtracting the added/removed number instead of recalculating the whole thing with each step. And second, we must enforce the condition of at least two numbers in the window, or we would return with the target itself if we reach it before the chunk.

Finally adding the minimum and maximum to get the final answer is trivial.

Advent of Code 2020 - day 8

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 puzzle's core consists of emulating a (very simple) computer. I may have been a little overzealous to create the Computer class, possibly influenced by the repeated appearances of the intcode computer last year, but fortunately I didn't go overboard with it.

Part 1

We have a basic computer with a memory storing the program, the instruction pointer (ip) with the memory address of the next instruction to execute, a register called accumulator, and an obviously RISC instruction set: acc increments the accumulator by its argument, jmp provokes a jump in memory with an offset corresponding to its argument (i.e. it increments the instruction pointer by its argument), and nop which does nothing. Each instruction consists of the opcode and an integer value as argument, although the argument is ignored in the case of nop.

The operation is simple: on boot-up both the accumulator and the instruction pointer hold the value 0. The program is loaded in memory, and we represent it as a list (where the index corresponds to the address) of opcode, argument tuples. The parsing in this case is straightforward.

The only generalization design decision is to use the opcodes directly with the getattr method, so that we can add new behaviour by just adding new Computer methods named after the corresponding opcode. If multiple arguments are needed, we can define each method with its proper arity and change the call to getattr(self, cmd)(*args), using the star notation to unpack the arguments.

Executing an instruction takes it from memory using the index in the instruction pointer, applies the opcode and argument, and increments the ip by one to move to the next instruction. Because of this, the jmp instruction needs to insert a correction after applying the offset, but otherwise every non-jmp opcode would need to increment the ip by itself, which is easier to forget. The implementation of the opcodes is trivial.

The question in this part is to find a loop in the program. Given that there is no branching, that means an infinite loop. We do this in the find_loop method, by keeping track of the addresses of executed instructions. As usual, we keep a set for the quick membership lookups. As soon as we are about to execute an instruction that we have already gone through, that's our loop, so we stop.

Part 2

In the second part we are asked to fix the program to avoid the loop by changing exactly one instruction either from nop to jmp or from jmp to nop. Undoubtedly trying out every possibility is not an option, so we need to think of a smarter scheme. It's time to go back to graphs.

We can represent the execution path as a graph, wehere each instruction is a node, and edges represent transition from one instruction to the next, usually moving up one address, except for jmp instructions. The first for loop in find_valid_addresses builds this graph as a dictionary with a destination as value for each address as key. This works because there is no potential branching, so the destination is always fixed, independently of the state of the machine.

But what we actually need is the opposite, we need to know from which addresses we can reach a given address. In other words, we need to invert the dictionary, but carefully: while each origin has a unique destination, each destination may be reached from multiple origins or from non at all. A defaultdict of sets makes this terse without impairing readability.

Now we are ready to determine which addresses can reach the end of the program. We take the last instruction to begin with, then we add all addresses from which that one can be reached, then the addresses from which those ones can be reached, an so on recursively. The actual implementation in find_valid_addresses follows the same concept that we applied before in day 7 to find out which suitcases could contain ours.

Now that we know which addresses eventually lead to the termination of the program, we can go about fixing the infinite loop. We just need to check for each nop and jmp instruction, as they happen in the program execution, whether switching it would lead to one of those addresses; if so, we do the switch, and return. We need to do a dirty emulation of the computer to follow the flow of the program (but without regard for the accumulator), or we might end up changing an opcode that is not actually reached, which would be useless.

We can now run the fixed program to get the answer to the exercise.

Advent of Code 2020 - 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.

This puzzle starts to ramp up the difficulty. We are asked to work with a set of rules for suitcases. From the sample input, it seems that each type of suitcase, based on colour, must contain certain numbers of other two types, or no other suitcases. But checking the full input we can see that the number of types need not be that limited, so we will assume an arbitrary number when parsing.

The parsing is relatively simple, as the input format is heavily structured, allowing us to split on the word 'contains' to separate container from contents and then further separate the contents into individual types by splitting on commas. We can check the special case of no other types contained when only one block of contents is present, and then use a couple of regular expressions to extract the type of container and the types and numbers of contents.

We store the rules as a dictionary, for quick reference. For each type as key, the value is None if it can contain no other types, or a dictionary of type, number pairs.

Part 1

The question for part 1 is which types can contain, even if several levels deep, a specific type. If we assemble the rules as a tree, we only need to find the node for the target type and report the intervening nodes from the root. But that assumes that the combination of the rules will respect a tree structure.

Therefore, we will not make the assumption, and consider still a graph structure. We can ignore the numbers for this part, as we only need to check connectivity. If we invert the rules, making the edges going from content to container, we can just check which nodes are reachable from the node corresponding to the target type. We will call this the 'containment graph'.

A quick and dirty way to represent such a graph is a dictionary where the types are the nodes, represented as keys, and the corresponding values are sets of adjacent nodes, in this case the types that can contain it. We use a defaultdict(set) so that we can start with an empty graph and just add edges; the data structure will take care of creating an empty set the first time we add an edge associated to a node.

Once we have the graph, it's easy to evaluate the reachable nodes from our target type. We just start from the target, add all adjacent nodes and recursively do the same to each of them. In practice, we use a queue containing initially the target node. As long as we have elements to process in the queue, we take one, add it to the reachable set, and add all its successors that we haven't yet visited to the queue; once we have visited a node, we are guaranteed to reach all nodes reachable from it without revisiting it, and without this precaution we could end up in an infinite loop if there are cycles in the graph.

Part 2

The second part asks us how many suitcases we will need to have inside of our target type by applying the rules. This is conceptually simple using a recursive solution: the count of total suitcases for a type is 1 (itself) plus the sum of the counts for the types it must contain, each times the corresponding number in the rule. Those counts are recursive calls to this same calculation, and the base case corresponds to types that do not contain other types.

In practice it's necessary to be more careful, as this is multiply recursive and that can pose problems, as anyone who has tried a direct recursive implementation of the Fibonacci sequence can attest. Seriously, if you haven't, build a naive recursive implementation, see how times increase as you move up, and whether you are patient enough for fib(50). Here, you don't even have to write it:

def fib(n): 

    if n == 0 or n == 1:

        return 1

    return fib(n - 2)  + fib(n - 1)

To work around this, we will cache results as we reach them. We include an accumulator (acc), a dictionary that will hold known counts. Instead of going directly to calculating the result, in each call we first check the cache, use the cached value if it exists, and otherwise perform the calculation and store it into the cache.

Finally, when we get the count, we need to remove the initial target type suitcase, as the question is how many suitcases are required inside it!

If you're curious, the equivalent trick for the Fibonacci sequence would be:

def fib(n, acc=None):

    if acc is None:

        acc = {0: 1, 1: 1}

    if n not in acc:

        acc[n] = fib(n - 2, acc) + fib(n - 1, acc)

    return acc[n]

But for this you'd actually be better off just using the lru_cache decorator from the functools module on the naive version, just saying. Try either, and now you can know fib(50).

Advent of Code 2020 - 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.

This one is a breeze with the right idea. The common part is converting the seats into the numerical IDs. At first sight, it looks like a bisection scheme would fit the description perfectly: keep track of the upper and lower bound, and depending on the letter keep the high or low half-interval until it is reduced to a single number. Do that for the row and repeat for the column. It's not even hard to do, but it can be simplified.

Instead we can notice that the scheme it describes corresponds exactly to decimal encoded binary: each position encodes this half-interval concept by adding or not the corresponding power of two. So the first of the seven digits encoding the row leaves the number encoded with the other six bits in its [0, 63] range if it's 0, or moves it into the [64, 127] range, and so on.

Furthermore, multiplying by 8 is equivalent to shifting three positions to the left; then adding the column part just fills in those three positions. If we take the seat as given, and substitute the letters with 0s (for F, L) or 1s (for B, R), we only need to interpret that as a base-2 int to get the ID.

Part 1

Once we have the IDs, finding the maximum is trivial using the max built-in.

Part 2

Now we need to find the gap in the consecutive IDs, but the start and end are not known.

In reality we know the end, that was part 1. We can calculate the minimum in the same way, then go from minimum to maximum until we find the gap. That would require building a set of IDs to check each value in constant time. And it would be the most efficient approach (linear time to build the set, get minimum and maximum, and then traverse the range). The latest code does this with set operations. The resulting set should contain just one element, per the problem statement.

In the first commit for the day, I did it differently, in O(n log(n)),  by sorting the IDs, the traversing the sorted array looking at each value and the next. When the difference is greater than one, that's our gap.

Advent of Code 2020 - 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. 

The first day is just a warm-up exercise, but still there are some subtleties, specifically in the complexity of possible solutions.

Part 1

The first part reduces to finding a pair of numbers in a list that add up to 2020. I checked the list for duplicates, and there are none, which makes the use of sets a viable option. We will see why this is important in a moment.

The naive approach would be to check each possible pair, which would result in quadratic complexity, not bad, but this can be easily achieved in linear time. By using sets, so that membership checks are constant time, otherwise these would be linear time and we would be back to quadratic.

The solution is taking each value n in the set, and checking whether target - n is in the set. If it does, we have our answer. We return it as n * (target - n) as the requested answer is the product of the numbers.

This requires two linear operations: building the set, and running through it once checking each number (the check is constant time, as mentioned above).

Part 2

The next exercise is finding three numbers that add up to 2020. If we hadn't gone for a linear solution in the first part, we would be looking at a cubic time solution for this one. As it is, we can manage to limit it to quadratic time, by checking for each number n whether there are two numbers in the rest of the set that add up to target - n, and this can be done using the approach from Part 1.

Of course, in all the discussion complexities are worst case. The algorithms will end as soon as the right answer is found, which can happen with the first numbers that it evaluates. In the worst case, it will try all potential combinations to determine that there isn't one that meets the requirements. In that case, the return value will be None.

Solving 0h h1 Puzzles

You might have stumbled across these puzzles, and maybe even suffered from some degree of addiction to them. In case you haven't, here's the gist.

The puzzle consists of a square grid of cells, which can be red or blue. Some of the cells are set to either colour at the begining, while most are blank. The task is to assign red or blue to all cells so that:

• each row and column has the same number of red and blue cells
• there are no more than two adjacent cells of the same colour in the same direction (horizontal or vertical)

The rules are deceptively simple; a good measure of reasoning goes into finding the solution, though. As you go through a few of them, patterns emerge. But can the solution be automated?

The large puzzle is a ten by ten grid; with about 20 pre-set, about 80 cells need to be decided. In a brute force fashion, that means about 2^80 combinations, or somewhat over 10^24. Clearly brute force is not going to cut it.

Exploiting the conditions that the solution must meet can add some intelligence. This limits the actual number of combinations, but it forces the algorithm to be a lot more clever when selecting which assignments to make. Enter constraint propagation.

In constraint propagation, the two constraints defined above limit the values that some of the cells can take, wiping out large swaths of combinations at once. Once the constraint propagation gets stuck, the next step is just trying out one or the other colour in one of the remaining cells, and see how it goes from there.

Let's look at the search space as a binary tree, with each level corresponding to one cell, and the two branches are each of the two colours. The procedure becomes:

1. set the known cells to their colours
2. propagate the constraints to set as many cells as possible
3. if all cells get filled or the problem reaches inconsistency (there is no way to meet the constraints), the algorithm is done
4. otherwise, select one of the remaining cells and arbitrarily assign one colour, and try to solve that (going back to 2, starting a recursion); if this solves the problem, success
5. otherwise, try the other color (again, going back to 2, starting a recursion); if this solves the problem, again, success
6. otherwise, the procedure ends, but reporting that the problem is unsolvable

This process recursively explores the binary tree, using constraint propagation as a shortcut whereever possible. In practice, I still have to find a puzzle where more than 10 branching operations are needed, as constraint propagation does most of the heavy lifting.

The solution procedure can be summarized in pseudocode as:

solve(problem):
    propagate_constraints(problem)
    if solved(problem) or infeasible(problem)
        return problem
    cell = get_unset_cell(problem)
    new_problem = problem + set(cell, red)
    candidate_solution = solve(new_problem)
    if solved(candidate_solution)
        return candidate solution
    new_problem = problem + set(cell, blue)
    candidate_solution = solve(new_problem)
    return candidate solution

The recursion is seen clearly in this pseudocode. If the constraint propagation does not directly solve the puzzle, a new problem is created by setting one cell to red, and passed over to the recursive call. If that returns with infeasibility, there is still the option of making it blue. After that, there is nothing else to be done: the cell can only be red or blue.

Up to now I have glossed over the actual constraint propagation. Each of the two constraints will have its own constraint propagation function.

For the first constraint, it is quite simple: cycle through each row and column; if the number of red cells is half the puzzle size, mark all unset cells in the row or column blue, and vice versa. That's all there is to it.

For the second one, a little more care is needed. Cycle through all cells, and for each one (that is not yet set) check:

• the cells one and two positions above
• the cells one and two positions below
• the cell immediately above and the cell immediately below
• the cells one and two positions to the right
• the cells one and two positions to the left
• the cell immediately to the right and the cell immediately to the left

If any of these sets has both cells set to the same colour, the current cell must be assigned the other colour. In practice a little more care is needed, as the cells close to the boundaries will not have all of the sets.

If you are wondering how to put all of this together and make it work, I have built a short Python program that implements this concept. Check it out at GitHub.

If you are looking for a way to solve the puzzles by hand, this is not your best option. Computers are terribly good at the laborious tasks of checking over and over every rule while propagating the constraints, keeping a list of the steps they take and backtracking when they reach a dead end to try a different path down the tree. We humans soon lose track of this even at small depths.

Instead, we can solve puzzles like this by latching onto more complex patterns, and thinking through the combinations that might succeed. It also works, but is much harder to automate.

Next time you want to sautomate the solution of a combinatorial problem where success is defined in terms of the rules that the solution must follow, give constraint propagation a chance. It goes much easier on your CPU than a brute force approach.