Advent of Code 2020 - Day 12

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

In this puzzle we just need to keep track of the position of a ship that follows a sequence of commands. Commands consist of a letter and an integer as argument (immediate to parse). Following the path of the ship is only a matter of keeping straight what each command does.

We need two values to keep the state: a 2-vector for the position, and the angle of the heading. At each step we apply the corresponding command:

• N, S, W, E: move in the specified direction as many units as given in the argument, a matter of adding or subtracting for the proper component of the position.
• L, R: modify heading by as many degrees as given in the argument, which just needs to add or subtract that to the current heading (modulo 360 to keep it in range).
• F: move in the heading direction as many units as given in the argument; basic trigonometry to apply cosine to the x coordinate and sine to the y coordinate (and remember to convert to radians).

Finally, just add the absolute values of the components to get the answer.

Part 2

The 'waypoint' now becomes a vector rather than just a heading, and the R and L commands now rotate this vector; F moves in the direction of the waypoint, and the argument specifies how many times its length.

We could still use some trigonometry to determine the initial waypoint angle and length, then do as in Part 1, but multiplying by the waypoint length (which cannot change) the coordinate updates of the F command. But where's the fun in that?

Python has built-in complex numbers, and they have a couple of interesting properties: their addition works just like 2d vector addition, which matches what we expect of the N, S, W, E commands; if we add in that multiplication by a scalar results in scaling, we can apply the F command trivially. And multiplication of complex numbers results in a rotation (plus scaling); by properly designing the multiplicand, we can obtain the desired rotation for the L and R commands.

In particular, we want a unitary complex number forming the desired angle (using negative angles for rotating right), or exp(i*angle) in polar notation, which corresponds to cos(angle) + i*sin(angle) in Cartesian notation.

With this in mind, redefining the effects of commands results in:

• N, S, W, E: add to position the argument times the corresponding complex unitary vector.
• L, R: multiply the waypoint vector by the corresponding complex rotation as explained above.
• F: add to position argument times the waypoint vector.

Finally add the absolute values of the real and imaginary parts of the position. abs(position) exists, but it results in the length of the complex vector, which is Euclidean rather than Manhattan distance.

Advent of Code 2020 - Day 11

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 puzzle is a small modification of Conway's Game of Life. There are lots of implementation, sites, and information of all kinds on this topic. The main changes is that the voids (the dots in the input) have to be considered as dead, and can never become alive; that translates into considering them dead, and skipping them in the update.

For the implementation, we will move directly to part 2, as they can be refactored together. Obviously, this was done after the fact originally, but the changes were not too large. The one point worth mentioning is the use of tuples to represent the board, and keeping the previous state to check when the system stabilizes. Also, having a non-mutable data structure ensures that we don't give in to the temptation of updating it in-place, which would result in erroneous updates.

Part 2

The difference in this part is that the voids do not count for the neighbourhood structure; instead, the first seat following the direction is the neighbour (unless the end of the matrix is reached before a seat).

The state update at each step and checking for the repeating state do not need additional comment. They are quite straightforward. The only part that is relatively tricky is defining the neighbours for each cell.

For that, we will make use of the symmetry of the neighbouring relation, visit each cell and add it as a neighbour to each cell that it 'sees' as a neighbour. We start by defining the 8 possible directions as the tuple of row and column increment of a step in that direction. We will store the neighbours in a defaultdict with the row, column pair identifying each cell as keys and the set of corresponding neighbours as values. The defaultdict(set) will helpfully provide an empty set when we first try to add a neighbour.

So we iterate over rows and cols. For void cells, we just skip to the next one; they are not neighbours to anyone (which is equivalent to counting them as dead, since we evaluate the number of live neighbours for the state change). For seats, we take each direction, and start stepping in that direction. We break out of the loop after the first step for part 1 (that's the condition of the while), if we step out of bounds of the board, or if we reach a seat. In the latter case, we add the current cell as a neighbour of that seat.

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

This puzzle builds a little on previous ones. The input parsing requires building groups, separated by blank lines, and we already did that for Day 4. In this case each line will be a set, and the group a list of those sets (the simplest to build the groups). Apply the same caution as before with potential empty groups.

Part 1

We have to count the number of distinct elements in each group, then add the all groups together. Or, in other words, for each group the cardinality of the union of the sets in the group. We just build a quick loop that emulates a reduce operation applying set union, starting with one of the sets in the group.

That gives us the count or each group, we then add them together.

Part 2

Now we are required to count the elements present in all sets in the group instead of all elements present in all sets, or the intersection of the sets. We repeat the procedure above applying the intersection instead of the union for the reduction, and done.

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

Another one for parsing and validating.

Part 1

The parsing part is a little more complex than what we have seen so far, as we can no longer assume that a record corresponds to a line. Other than that, it's just colon-separated key, value pairs. So instead of building a record in one go, we start with an empty one, adding key, value pairs as they come until reaching a newline, which marks a record switch.

Two potential pitfalls to look out for. First, remember to add the record still being built at the end of the loop. Second, both at this step, and whenever closing a record and opening a new one, check whether the record has any contents; two consecutive blank lines or a blank line at the end of the file would introduce an empty record otherwise.

The validation in this part just needs to check if a record contains all required fields; once again generator expressions make this condition sound almost as natural language:

all(field in record for field in fields)

Then just go through all the records and count those that are valid.

Part 2

This part makes the validation a little bit more involved by specifying requirements for the values in each field. Just validate each.

Some are straightforward, especially after converting the value into a number. Others require a little more work. Some points of interest:

• The sets defined at the top of the module allow a quick check of some fields. In particular, the pid field needs to be checked like this to ensure that it has leading zeroes to pad up to 9 digits.
• Height needs to be treated with care, as the units are not always present, and assuming so may leave an empty string for the numeric part; therefore we require at least four characters, or return there as invalid. After that, it's easy.

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

A quick and easy one. This exercise consists on traversing a field defined by the input file following a given pattern, and counting how many of the positions traversed contain a '#' character (a tree in the puzzle). The pattern is given by a pair (r, c), meaning that each step advances r rows and c columns, with columns wrapping over if the width is exceeded.

Part 1

We are given a pattern, and we have to count the trees. Parsing the input is trivial and doesn't merit additional explanation.

The traversal itself is not especially complex, either. We update row and column with each step, using modulo arithmetic to easily wrap the columns around, and check if the new position is a tree. We end once we run out of rows.

Part 2

Rinse and repeat, with several patterns. If you were careful to use the condition row < height rather than row != height when checking the stopping condition everything will work, otherwise, some patterns may skip the row where row == height and never end.

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

Still on the warm-up phase, but we are already bringing in regular expressions. The patterns are easy enough to solve with basic string methods, but the regular expressions make it much clearer.

Part 1

We get a file in which each line is a constraint specification followed by a word, and we are asked to count how many lines are consistent (i.e. the word is valid according to the constraint). Each line is of the form:

n-m x: word

Here, n and m are integer numbers, and x is any single letter. The constraint is that the letter given by x must appear between n and m times in word.

So we have two tasks:

1. Parse the file into paired costraint specifications and words
2. Evaluate validity of each pair

The first task is straightforward matching on each line the regular expression:

(?P<min>\d+)-(?P<max>\d+) (?P<letter>[a-z]): (?P<pwd>[a-z]+)

We can then use the named groups to retrieve each relevant piece of information (and cast min and max to ints). With this small modification we can directly use the dictionary that we get from match.groupdict() as the specification.

Validation is equally straightforward. We can use a generator expression to compress counting the number of times the letter appears in the word while making it more readable than the equivalent loop:

sum(1 for c in spec['pwd'] if c == spec['letter'])

Compare it with:

total = 0
for c in spec['pwd']:
    if c == spec['letter']:
        total += 1

Part 2

For this part the validation rules change, so we keep the same parsing. The new validation rule is that the letter must appear in exactly one of the two given positions (interpreting n and m as 1-based indices).

The first gotcha is the 1-based indices. Not difficult, but easy to forget. Otherwise the validation seems to be quite direct as a XOR of the conditions that the letter at each of the two positions be the given letter:

(pwd[pos1] == letter) != (pwd[pos2] == letter)

However, this can lead to out-of-bounds errors, so there is some accounting to do before reaching this. If the word is so short that the first position is not even included, then it is not valid; if only the first position is within the word, the word is valid if the letter at that position is the given letter. If both are included, we fall back to the XOR.

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.

Advent of Code 2020

 I have followed the Advent of Code site for several years now. I don't usually have the time to fully finish it, as the time required for the latest and hardest exercises becomes more than I can spare for it. But who knows? This year might be different. It has definitely been a very different year so far.

As an additional exercise, I will keep a log of the solutions here; one post per day. The code will be in this GitHub repo, if you want to follow it. The posts will deal with the rationale behind the solutions and the choices made.

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 aoc2020 tag to filter them.

Links to posts:

• Day 1
• Day 2
• Day 3
• Day 4
• Day 5
• Day 6
• Day 7
• Day 8
• Day 9
• Day 10
• Day 11
• Day 12
• Day 13
• Day 14
• Day 15
• Day 16
• Day 17
• Day 18
• Day 19
• Day 20
• Day 21
• Day 22
• Day 23
• Day 24
• Day 25