Pages

2020/12/16

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.

2020/12/15

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.

2020/12/09

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

2020/12/08

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.