DEV Community: matju

Advent of Code 2020 - Day 18

matju — Thu, 31 Dec 2020 12:40:33 +0000

https://adventofcode.com/2020/day/18 ('Operation Order')

I originally did this question in the quick'n'dirty way described below. However there are a few other approaches, including a very sneaky use of Python's own interpreter.

Quick and Dirty Method

In part 1, the * and + operators in the expressions we're given have the same precedence. Evaluating an expression without brackets is therefore pretty easy: we can work through the operators from left to right and apply them. This looks like:

def evaluate_simple(expression):
    'Take an expression without brackets and calculate its value'
    current_op = None
    result = None
    for item in expression.split():
        if item == '+' or item == '*':
            current_op = item
        else:
            value = int(item)
            if current_op is None:
                result = value
            elif current_op == '*':
                result *= value
            elif current_op == '+':
                result += value
            else:
                raise(Exception("Bad expression: " + expression))
    return result

But how do we handle brackets? There will always be an innermost sub-expression that doesn't itself contain brackets and this can be evaluated using evaluate_simple(). Substituting the result back in to the original expression will eliminate a set of brackets, and doing this repeatedly will gradually reduce the expression down to a single number.

For example, consider ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2:

Find innermost sub-expressions:
((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2
 ^^^^^^^^^^^   ^^^^^^^^^^^^^^^

Evaluate:
(54 * 126 + 6) + 2 + 4 * 2

Find innermost sub-expressions:
(54 * 126 + 6) + 2 + 4 * 2
^^^^^^^^^^^^^^

Evaluate:
6810 + 2 + 4 * 2

No brackets left, so evaluate:
13632

A simple way to look for the innermost sub-expressions is to use a regex. The sub-expressions we're looking for should be surrounded by brackets and contain only digits, addition or multiplication operators, or white space - they cannot contain brackets themselves:

SIMPLE_EXPRESSION_REGEX = re.compile(r'\(([\d +*]+)\)')

Therefore evaluating a whole expression involves repeated application of this regex to find a sub-expression that can be evaluated, followed by use of evaluate_simple() to get its value and then substitution of the value back into the expression string:

def evaluate(expression):
    while '(' in expression:
        # Find sub-expression without brackets
        for simple_expression in SIMPLE_EXPRESSION_REGEX.findall(expression):
            # Replace each sub-expression (and the surrounding
            # brackets) with its value
            result = evaluate_simple(simple_expression)
            expression = expression.replace('(' + simple_expression + ')', str(result))
    # At this point we have a single expression that contains
    # no brackets
    return evaluate_simple(expression)

Part 1 is therefore:

def part1():
    with open('day18.txt', 'rt') as input_file:
        return sum(evaluate(expression) for expression in input_file.read().splitlines())

In part 2, + has higher precedence than *. With a bit of tweaking we can apply the same technique as before as long as within the innermost sub-expressions we evaluate the additions first.

Consider again ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2:

Find innermost sub-expressions (as per part 1):
((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2
 ^^^^^^^^^^^   ^^^^^^^^^^^^^^^

Within those sub-expressions find additions:
((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2
  ^^^^^         ^^^^^   ^^^^^

Evaluate additions:
((6 * 9) * (15 * 14) + 6) + 2 + 4 * 2

Evaluate resulting bracketed sub-expressions:
(54 * 210 + 6) + 2 + 4 * 2

Find innermost sub-expressions (as per part 1):
(54 * 210 + 6) + 2 + 4 * 2
^^^^^^^^^^^^^^

Within those sub-expressions find additions:
(54 * 210 + 6) + 2 + 4 * 2
      ^^^^^^^

Evaluate additions:
(54 * 216) + 2 + 4 * 2

Evaluate resulting bracketed sub-expressions:
11664 + 2 + 4 * 2

No brackets left, so find additions:
11664 + 2 + 4 * 2
^^^^^^^^^^^^^

Evaluate additions:
11670 * 2

Evaluate resulting expression:
23340

In order to do this, we need to wrap every call to evaluate_simple() with some logic to pick out and evaluate the additions beforehand. We can find the additions using another regex: one that matches two numbers with some whitespace and a plus between them (a glance at the puzzle input suggests that the usage of whitespace is consistent and every operator has a space on either side):

ADD_EXPRESSION = re.compile(r'\d+ \+ \d+')

However we have to be careful when substituting the result back in to the expression string in place of the addition expression. In part 1 we just used the string .replace() method and this worked perfectly well as the string being replaced was always bookended by brackets but could never contain brackets itself. However imagine that we've just evaluated the addition expression 23 + 45 and want to substitute the result 68 back in to the string 23 + 45 + 123 + 456. Here a simple replace operation would result in the string 68 + 1686 - which is clearly not the desired result!

Taking all this into account we end up with this function that wraps evaluate_simple():

def evaluate_simple_with_additions_first(expression)
    match = ADD_EXPRESSION.search(expression)
    while match:
        result = evaluate_simple(match.group())
        # Ensure we replace only the bit of the string where
        # the addition expression was found
        expression = expression[:match.start()] + str(result) + expression[match.end():]
        match = ADD_EXPRESSION.search(expression)
    return evaluate_simple(expression)

The rest of the code is basically the same before, except that evaluate_simple_with_additions_first() is called instead of evaluate_simple():

def evaluate_advanced(expression):
    while '(' in expression:
        # Find sub-expression without brackets
        for simple_expression in SIMPLE_EXPRESSION.findall(expression):
            # Replace each sub-expression (and the surrounding 
            # brackets) with its value
            result = evaluate_simple_with_additions_first(simple_expression)
            expression = expression.replace('(' + simple_expression + ')', str(result))
    # At this point we should have an expression that contains 
    # no brackets
    return evaluate_simple_with_additions_first(expression)

def part2():
    with open('day18.txt', 'rt') as input_file:
        return sum(evaluate_advanced(expression) for expression in input_file.read().splitlines())

This regex-and-substitution approach runs for me in about 5ms for part 1 and 12ms for part 2.

Doing it Properly

There are all sorts of algorithms that can be used to parse expressions containing infix operators like + or * that may have different precedence:

To use any of these algorithms we need to turn the expression to be parsed into a stream of tokens, e.g. (, 123, + etc. We can almost do this by splitting on white space, except that the brackets aren't completely surrounded by white space so we must fix that first:

def get_tokenised_lines():
    with open('day18.txt', 'rt') as input_file:
        for line in input_file.read().splitlines():
            # Insert extra whitespace where necessary, then split on whitespace
            yield line.replace('(', ' ( ').replace(')', ' ) ').split()

As I'd written a Pratt parser before, I decided to see what would be involved in getting one working here. This kind of parser feels slightly mysterious and the write-up here certainly won't do it justice. Some better sources of information are:

Pratt Parsers: Expression Parsing Made Easy (in Java)
Simple but Powerful Pratt Parsing (in Rust)
Top Down Operator Precedence (in JavaScript - this article by Douglas Crockford introduced me to Pratt parsers, and goes on to extend one to parse a reasonable subset of JavaScript)

Usually the result of any parsing algorithm is an abstract syntax tree (AST), a data structure that represents the expression, which is then processed in a subsequent step (to evaluate it, or perhaps compile it into machine code or another target format). For example, consider 1 * 2 + 3 * 4. Using the precedence rules from part 2 one possible arrangement of an AST for this expression would be:

Once the tree is built it can be evaluated using depth-first recursion. As we're only dealing with integers and arithmetical operations, we can simplify things by merging the parsing and evaluation into a single step.

A Pratt parser tries to parse an expression recursively using the following rules:

An expression can only begin in certain ways. In our case this is either with a number or a (, but in many languages expressions could also start with operators like - or !. For us:
- If we read a number then that evaluates to itself
- If we read a ( then there's another expression lurking inside the brackets. Therefore we must recursively read and evaluate that before continuing, making sure we also consume the matching ).
If an infix operator (i.e. + and * in our case) is encountered then we must decide what to do: either this operator forms part of the expression being read, or operator precedence rules mean that we should stop parsing the current sub-expression and return to the caller.
- If we're parsing a sub-expression to the right of a + then we need to stop as soon as we hit a *. This is because + has a higher precedence than * so things either side of the + will 'bind' to it more readily than to a *.
- If we're parsing a sub-expression to the right of a * then there's no problem if we hit a +: as this has a higher precedence it should form a self-contained sub-expression of its own.
- As a result, when parsing an expression we need to remember the precedence of the operator we're parsing it for so we can decide whether to stop or continue.

This might be clearer with a couple of examples! For this to work we need to give numerical precedence values to our operators, so let's give * a precedence of 1 and + a precedence of 2.

First let's look at 1 + 2 * 3 (which should evaluate to 9 in part 2):

Start reading the expression. This is the outermost expression so it doesn't belong to any operator in particular - as a result we have a 'current precedence' of 0.
Get the next token. This is a 1, which evaluates to 1.
Look at the next token. It's a + and has a precedence of 2, which is higher than the current precedence of 0. Therefore the + will form part of the current expression and we need to read the sub-expression belonging to it on its right hand side. As a result we recurse, setting the current precedence to 2.
1. Start reading an expression with the current precedence set to 2.
2. Get the next token. This is a 2, which evaluates to 2.
3. Look at the next token. It's a * and has a precedence of 1, which is not higher than the current precedence of 2. Therefore the * does not form part of the current expression and we leave it alone, returning 2 as that's what we have so far.
We now know that the sub-expression on the right of the + evaluates to 2, so we can evaluate the addition itself: 1 + 2 gives 3.
Now we look at the next token. It's an asterisk and has a precedence of 1, which is higher than the current precedence of 0. Therefore the multiplication will form part of the current expression and we need to read the sub-expression belonging to it on its right-hand side. As a result we recurse, setting the current precedence to 1.
1. Start reading an expression with the current precedence set to 1.
2. Get the next token. This is a 3, which evaluates to 3.
3. There are no tokens left, so this sub-expression must evaluate to 3 and we return 3 to the caller.
We now know that the sub-expression on the right of the * evaluates to 3, so we can evaluate the multiplication itself: 3 * 3 gives 9.
There are no tokens left, so we return 9 to the caller.

Now consider 1 * 2 + 3 (which should evaluate to 5):

Start reading the expression. This is the outermost expression so it doesn't belong to any operator in particular - as a result we have a 'current precedence' of 0.
Get the next token. This is a 1, which evaluates to 1.
Look at the next token. It's a * and has a precedence of 1, which is higher than the current precedence of 0. Therefore the * will form part of the current expression and we need to read the sub-expression belonging to it on its right hand side. As a result we recurse, setting the current precedence to 1.
1. Start reading an expression with the current precedence set to 1.
2. Get the next token. This is a 2, which evaluates to 2.
3. Look at the next token. It's a + and has a precedence of 2, which is higher than the current precedence of 1. Therefore the + will form part of the current expression and we need to read the sub-expression belonging to it on its right hand side. As a result we recurse, setting the current precedence to 2.
  1. Start reading an expression with the current precedence set to 2.
  2. Get the next token. This is a 3, which evaluates to 3.
  3. There are no tokens left, so this sub-expression must evaluate to 3 and we return 3 to the caller.
4. We now know that the sub-expression to the right of the + evaluates to 3, so we can evaluate the addition itself: 2 + 3 gives 5.
5. There are no tokens left so we return 5 to the caller.
We now know that the sub-expression to the right of the * evaluates to 5, so we can evaluate the multiplication itself: 1 * 5 gives 5.
There are no tokens left so return 5 to the caller.

What about brackets?

If we encounter an ( then we recurse, setting the current precedence back to 0 as though we were reading the outermost expression.
If we encounter an ) we always want to stop reading the current sub-expression. We can do this by making ) an operator with a precedence of 0. As a precedence of 0 will never be higher than the current precedence, this will always terminate the current sub-expression.

To turn this into code, we first need a dictionary mapping each operator to its precedence and the function used when the operator is evaluated:

from operator import mul, add

# For part 1: addition and multiplication have the same
# precedence.
# As described above, ')' needs an entry here with a precedence
# of 0.
SIMPLE_OPERATORS = {
    '*': (1, mul),
    '+': (1, add),
    ')': (0, None)
}

# For part 2: addition has a higher precedence than
# multiplication.
ADVANCED_OPERATORS = {
    '*': (1, mul),
    '+': (2, add),
    ')': (0, None)
}

The evaluation function itself requires the tokens to be fed in in reverse order (it's easier to pop tokens from the end of a list than the beginning). It looks like:

def evaluate_pratt(tokens, operators, current_precedence=0):
    'Note: assumes that tokens is a list of tokens in reverse order'
    # At this point we are reading the start of an expression or 
    # sub-expression. The only possibilities here are a number
    # or an open bracket.
    token = tokens.pop()
    if token == '(':
        # Following tokens must be a sub-expression followed 
        # by a ')'. Read the sub-expression, resetting the
        # current_precedence to 0:
        result = evaluate_pratt(tokens, operators)
        # Remove the ')':
        tokens.pop()
    else:
        # Token must be an integer.
        result = int(token)

    while tokens:
        # At this point the left-hand sub-expression has been
        # read and evaluated. The next token must be one of the 
        # operators or a close bracket. Take a look and use the
        # operator dictionary to look up the precedence and the
        # operator's function (if any).
        peek = tokens[-1]
        operator = operators.get(peek)
        if operator is None:
            raise Exception('Unexpected token: ' + peek)
        (power, op) = operator
        # If this operator's precedence is higher than the
        # current precedence then include it in the current
        # expression - otherwise stop reading the expression.
        if power > current_precedence:
            tokens.pop()
            right = evaluate_pratt(tokens, operators, power)
            result = op(result, right)
        else:
            break

    return result

With the above, parts 1 and 2 become:

def part1_new():
    return sum(evaluate_pratt(tokens[::-1], SIMPLE_OPERATORS) for tokens in get_tokenised_lines())

def part2():
    return sum(evaluate_pratt(tokens[::-1], ADVANCED_OPERATORS) for tokens in get_tokenised_lines())

As the two parts are using exactly the same logic (the precedence tables of the operators being the only difference) they take roughly the same amount of time: about 6ms.

Doing it Sneakily

Of course, Python already knows how to parse expressions - it does this every time we run some Python code. Why don't we get Python to do the hard work for us?

To make this work we need to use the eval() built-in function to parse and evaluate the expressions. However we will need to do some tricks to get Python to treat addition and multiplication with same precedence for part 1 - or addition with a higher precedence for part 2.

If, rather than performing arithmetic with integers directly, Python is instead using instances of a class of our own then we can control what it means to multiply and add. Therefore instead of doing eval('1 + 2 * 3') we could do eval('Value(1) + Value(2) * Value(3)') where Value is a class we've defined that represents a numeric value.

However this only gets us part of the way there as Python will still perform Value(2) * Value(3) before the addition because the operator precedence is baked into the language. If we want the precedence of these operations to be the same then we'll need to manipulate things a bit more so we're actually calling eval('Value(1) / Value(2) * Value(3)') - i.e. we've replaced the + operator with the / operator as it has the same precedence as *, but we've also redefined / for the Value class to be addition.

For part 2 we need to go one step further and downgrade the precedence of the * operator. We can do this by replacing * with + (having previously replaced + with /) and defining + to be multiplication.

Putting these ideas together we have:

class Value:
    def __init__(self, value):
        self.value = value

    def __mul__(self, other):
        return Value(self.value * other.value)

    def __truediv__(self, other):
        'Override the / operator to perform addition'
        return Value(self.value + other.value)

    def __add__(self, other):
        'Override the + operator to perform multiplication'
        return Value(self.value * other.value)

VALUE_REGEX = re.compile(r'(\d+)')

def evaluate_sneaky(expression):
    # Wrap the numbers in the expression with a Value constructor
    expression = VALUE_REGEX.sub(r'Value(\1)', expression)
    # Upgrade addition to division to increase precedence
    expression = expression.replace('+', '/')
    return eval(expression).value

def part1():
    with open('day18.txt', 'rt') as input_file:
        return sum(evaluate_sneaky(expression) for expression in input_file.read().splitlines())

def evaluate_advanced_sneaky(expression):
    expression = VALUE_REGEX.sub(r'Value(\1)', expression)
    # Upgrade addition to division to increase precedence
    expression = expression.replace('+', '/')
    # Downgrade multiplication to addition to reduce precedence
    expression = expression.replace('*', '+')
    return eval(expression).value

def part2():
    with open('day18.txt', 'rt') as input_file:
        return sum(evaluate_advanced_sneaky(expression) for expression in input_file.read().splitlines())

This performs less well than the other solutions, taking about 35ms for either part. I guess spinning up the Python expression parsing machinery has a cost!

Advent of Code 2020 - Day 13

matju — Wed, 30 Dec 2020 18:44:32 +0000

https://adventofcode.com/2020/day/13 ('Shuttle Search')

Part 1 requires us to look for the bus number that has the smallest multiple greater than or equal to the minimum time.

One way to think about this is to look at the number of complete circuits of its route each bus has done by the minute before the minimum time. Knowing this we can determine the next departure time and this will be the first departure equal to or greater than the minimum time.

If the minimum time is min_time and the bus number is bus_no then the number of circuits completed by min_time - 1 will be (min_time - 1) // bus_no. The next departure time will be the time of completion of the next circuit, and we get this by adding 1 to the previous result (for one more circuit) and multiplying by the bus number: ((min_time - 1) // bus_no + 1) * bus_no.

Note that using min_time - 1 here ensures that we handle the possibility of min_time itself being the next possible departure time for one of the buses.

In Python this looks like:

def part1():
    # Puzzle input is sufficiently small there's no need to 
    # read in from a file.
    min_time = 1003681
    bus_nos = [int(n) for n in '23,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,431,x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,x,x,x,x,x,x,x,x,409,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29'.split(',') if n != 'x']
    # Map each bus number to a pair of (bus_no, next_departure)
    # and then find the pair with the minimum next_departure 
    # value.
    (first_bus, departure_time) = min(((bus_no, ((min_time - 1) // bus_no + 1) * bus_no) for bus_no in bus_nos), key=lambda x: x[1])
    # Calculate the waiting time and multiply by the bus number.
    return (departure_time - min_time) * first_bus

Part 2 wants to do things the other way round: instead of looking for bus departures around a particular timestamp, we need to find a timestamp that has a certain pattern of departures around it.

First let's understand exactly what's being asked: we are looking for a timestamp t such that the bus at index i in the list has a departure at t + i. In other words, if [(i_0, b_0), (i_1, b_1), ..., (i_n, b_n)] is a list of pairs of index and bus number for the n buses, we are looking for t such that:

(t + i_n) % b_n = 0  for all n

The simplest approach now would be to start at t = 0 and for each t check whether (t + i_n) % b_n = 0 for all n. However, this being part 2 of an Advent of Code puzzle it's extremely likely this won't complete in a sensible time!

It turns out that there is a much quicker way to solve a system of equations like this, but first we need to rearrange them into the form

t % b_n = r_n  for all n

The original set of equations is the same as:

((t % b_n) + (i_n % b_n)) % b_n = 0  for all n

From this we can move the i_n % b_n to the right hand side, making it negative. However as we're working modulo b_n we are free to add on b_n to keep things positive:

t % b_n = (b_n - i_n % b_n) % b_n  for all n

so we have r_n = (b_n - i_n % b_n) % b_n.

The example from the puzzle has the following (i_n, b_n) index/bus number pairs:

[(0, 7), (1, 13), (4, 59), (6, 31), (7, 19)]

Calculating r_n for each pair we get the following (r_n, b_n) pairs:

[(0, 7), (12, 13), (55, 59), (25, 31), (12, 19)]

In this example we're therefore looking for a value of t such that:

t % 7 = 0
t % 13 = 12
t % 59 = 55
t % 31 = 25
t % 19 = 12

What do we do now?

The first thing that sticks out is that all the bus numbers in the example are prime. A quick check shows that this is also the case for the puzzle input, and this is great as it means we can apply something called the Chinese Remainder Theorem to find the solution!

Getting to the answer will be fastest if we start with the largest bus number and work our way down, so lets re-order the equations:

t % 59 = 55
t % 31 = 25
t % 19 = 12
t % 13 = 12
t % 7 = 0

First, let's find a solution that works for the first two buses in the list. t = 55 will obviously satisfy the first equation, but so will t = 55 + 59, t = 55 + 59 * 2 etc. If we keep adding 59 we should eventually get to a value of t where we also find that the second equation holds. Let's call this t_2, so:

t_2 % 59 = 55
t_2 % 31 = 25

Now comes the clever trick: if we add 59 * 31 to t_2 we get another value of t that satisfies these two equations: we've added on a whole number of 59s so the remainder when dividing by 59 won't change, but we've also added on a whole number of 31s so the remainder when dividing by 31 doesn't change either. In fact, we can add on any multiple of 59 * 31 we like without changing things. This gives us a way to keep exploring for values of t that satisfy the third equation while making sure we don't break equations one and two. Let's say that after adding on 59 * 31 to t_2 a sufficient number of times we get to a value of t that works for the first three equations - call this t_3.

If we take a step back, we can see that the above process is exactly what we would have done when solving the first two equations if they had looked like:

t % (59 * 31) = t_2
t % 19 = 12

We can now do the same thing to look for a value t_4 that'll satisfy the fourth equation by starting with t_3 and repeatedly adding on 59 * 31 * 19. This is equivalent to solving the pair of equations:

t % (59 * 31 * 19) = t_3
t % 13 = 12

Finally we repeatedly add on 59 * 31 * 19 * 13 to t_4 to find a value t_5 that satisfies the fifth equation - i.e. we're solving:

t % (59 * 31 * 19 * 13) = t_4
t % 7 = 0

Therefore we need a function that will solve a pair of equations of the form:

x % p_1 = a_1
x % p_2 = a_2

This looks like:

def solve(p_1, a_1, p_2, a_2):
    x = a_1
    while x % p_2 != a_2:
        x += p_1
    return x

Now we can follow all these steps to solve part 2:

def part2():
    # Get the bus numbers from the input along with the 
    # corresponding indices.
    buses = [(i, int(n)) for (i, n) in enumerate('23,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,431,x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,x,x,x,x,x,x,x,x,409,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29'.split(',')) if n != 'x']

    # Figure out for each bus the remainder t must have 
    # when divided by the bus number.
    buses = [((b - i % b) % b, b) for (i, b) in buses]

    # Sort in decreasing order of bus number.
    buses.sort(key=lambda bus: -bus[1])

    # Starting with the first two equations, repeatedly 
    # solve to generate a new equation t % p = a where p is the
    # product of the moduli used so far and a is the result of 
    # solving the previous pair of equations.
    (a, p) = buses[0]
    for (remainder, bus_no) in buses[1:]:
        a = solve(p, a, bus_no, remainder)
        p *= bus_no

    return a

When originally doing this puzzle I'd completely forgotten about the Chinese Remainder Theorem, but the fact that the bus numbers were all prime indicated that something was up. I knew there were a few things in modulo arithmetic that were only true if the various moduli in use were coprime (i.e. share no common factors other than 1), and a quick rummage through Wikipedia pointed to the Theorem.

Advent of Code 2020 - Day 20

matju — Sun, 27 Dec 2020 10:42:55 +0000

https://adventofcode.com/2020/day/20 ('Jurassic Jigsaw')

Day 20 was the problem that required the most work this year. While there was nothing really conceptually hard involved, it was fiddly and I made lots of mistakes on the way that took time to track down. After finishing I felt like I'd just done a 3 and a half hour exam!

Part 1

A quick look at the puzzle input showed that there were 144 tiles, all 10 by 10 in size, and each tile had a 4-digit ID. It seemed most natural to represent the tile data as a dictionary mapping tile ID to an array of 10 10-character strings, one string per line in the tile. As a result, parsing the input was straightforward:

def read_input():
    tiles = {}
    with open('day20.txt') as input_file:
        tile_id = None
        current_tile = []
        for line in input_file.read().splitlines():
            if line.startswith('Tile'):
                if current_tile:
                    tiles[tile_id] = current_tile
                    current_tile = []
                tile_id = int(line[5:9])
            elif line.startswith(('.', '#')):
                current_tile.append(line)
        if current_tile:
            tiles[tile_id] = current_tile
            current_tile = []
    return tiles

Part 1 says:

Assemble the tiles into an image. What do you get if you multiply together the IDs of the four corner tiles?

This is a bit sneaky as we don't actually need to assemble the tiles into an image (yet). If we can find tiles that have two adjacent edges that don't match up with any other tiles then they must be the corner tiles.

To do this we need a way of labelling individual tile edges. I arbitrarily chose to number the edges clockwise from the top of the tile in the orientation it was presented in the puzzle input:

     0
   +---+
   |   |
 3 |   | 1
   |   |
   +---+
     2

Each edge therefore has a unique ID: a tuple of (tile_id, edge_no). We can now pull out a dictionary mapping edge ID to a string representing the edge itself:

def get_tile_edges(tiles):
    'Return a dictionary mapping (tile_id, edge_no) to strings for each tile edge'
    edges = {}
    for (tile_id, tile) in tiles.items():
        edges[(tile_id, 0)] = tile[0]  # top
        edges[(tile_id, 1)] = ''.join(row[-1] for row in tile)  # right
        edges[(tile_id, 2)] = tile[-1]  # bottom
        edges[(tile_id, 3)] = ''.join(row[0] for row in tile)  # left
    return edges

To find the corners we must see which edges match up with each other, with the possibility of needing to flip tiles to find a match. It is also not clear at this stage whether there might be multiple matches (I hoped not as I suspected part 2 would actually require assembling the whole image and this would be much harder if there were multiple possibilities!) Let's work on the assumption that each edge will match either exactly one other edge (allowing for flipping) or no edges at all - in which case it must lie on the outside of the completed image.

To find matching edges we can cycle through each of the 576 edges. For each edge we can look at the other 575 edges and see if they either have the same string or if reversing one makes them equal - and if so we have a match. The result is a dictionary mapping each edge to the edge it matches with or to None if there was no match.

def find_matching_edges(tiles):
    '''Return a dictionary mapping each (tile_id, edge_no) to 
    the (tile_id, edge_no) it matches with, or None if that 
    edge must lie on the outside edge of the resulting grid'''
    edge_strings = get_tile_edges(tiles)

    matches = {}

    for (edge, edge_string) in edge_strings.items():
        if edge in matches:
            continue
        found = False
        for (other_edge, other_edge_string) in edge_strings.items():
            if edge[0] == other_edge[0]:
                continue
            if edge_string == other_edge_string or edge_string == other_edge_string[::-1]:
                if edge in matches:
                    raise Exception(f'Multiple matches for {edge}')
                found = True
                matches[edge] = other_edge
                matches[other_edge] = edge
        if not found:
            matches[edge] = None

    return matches

Note that we have taken advantage of the fact that if (tile_1, edge_1) matches (tile_2, edge_2) then we also know that (tile_2, edge_2) matches (tile_1, edge_1) and the number of checks required is halved.

The code will also bail out if the assumption of unique matches is broken - but luckily it turns out that running it on the puzzle input doesn't result in the exception being thrown so it looks like this assumption is safe! The above code doesn't however check for weird situations like a tile edge only matching another edge on the same tile, but fortunately the puzzle wasn't quite this cruel.

Now we have the dictionary of matching edges, identifying the corners is straightforward:

from functools import reduce
from operator import mul

def part1():
    tiles = read_input()

    # Look for edges that match up
    matches = find_matching_edges(tiles)

    # Find edges that must be on the corners by seeing if the
    # edge is on the outside and then checking that the edge 
    # clockwise adjacent to it is also on the outside. The 
    # tiles owning such edges will be the corner tiles.
    corner_tiles = set(edge[0] for (edge, other_edge) in matches.items()
                       if other_edge is None and matches[(edge[0], (edge[1] + 1) % 4)] is None)

    return reduce(mul, corner_tiles)

Part 2

I did have a think about whether it might be possible to avoid assembling the whole image by looking for parts of a sea monster in each tile. I decided that this was probably an even more complicated rabbit hole to disappear down, and it actually made sense to bite the bullet and stitch together the whole image.

First are three functions it turned out to be useful to define as they represent operations that came up frequently. Given that we're labelling edges as a tuple of (tile ID, edge number), these functions each return a tuple representing a different edge on the same tile:

def cw(edge):
    'Return the next edge clockwise on the same tile'
    return (edge[0], (edge[1] + 1) % 4)

def acw(edge):
    'Return the next edge anticlockwise on the same tile'
    return (edge[0], (edge[1] + 3) % 4)

def opp(edge):
    'Return the edge opposite the given edge on the same tile'
    return (edge[0], (edge[1] + 2) % 4)

As there are 144 tiles and the puzzle's preamble implies that the resulting image is square, we can assume that we'll need a 12 x 12 grid of tiles to form the image.

Representing the Grid

The first question is: how should we model the grid of tiles? We need to allow for tiles being flipped or rotated, so for each grid position we could store the tile ID at that position and some value that indicates how the tile has been transformed. In the end it seemed simplest just to maintain a dictionary mapping grid position to a tuple of tile ID and the edge numbers of the tile's edges that are in the top, right, bottom and left positions once the tile has been oriented correctly.

For example, if tile 1000 needed to be flipped on its vertical axis then rotated clockwise in order to fit at grid position (3, 4) we would have the following entry in the dictionary:

(3, 4): (1000, 1, 0, 3, 2)

This is because flipping the tile then rotating it looks like this:

     0                 0                 1
   +---+             +---+             +---+
   |   |             |   |             |   |
 3 |   | 1  ---->  1 |   | 3  ---->  2 |   | 0
   |   |             |   |             |   |
   +---+             +---+             +---+
     2                 2                 3

As a result edge 1 is in the top position, edge 0 on the right, edge 3 on the bottom and edge 2 on the left. Storing the tiles this way keeps an unambiguous record of their final orientation, and has the advantage that when we're trying to find tiles that fit in adjacent slots it's easy to see which edges they need to match up with. (In fact, an unambiguous record of the tile's orientation only requires us to record where two adjacent sides end up, but recording all four saves us from having to repeatedly work out where the other two ended up).

Populating the Grid

Now we've decided how to represent the grid of tiles, how should we populate it? If we start from the top-left corner (call this (0, 0)) and work across each row in turn down to the bottom right corner ((11, 11)) then each time we're populating a grid square we'll be in one of the following situations:

There's no grid square to the left or above the current tile - i.e. we're looking at the top-left corner. As we did in part 1, we can pick a corner tile by looking for any tile that has two adjacent outside edges and orienting it so one is on the left and the other is at the top.
There's a grid square to the left but no grid square above - i.e. we're looking at a tile in the top row. Here we can determine which tile to use by looking at the right edge of the tile to the left, but we need to determine the tile's orientation by making sure the outside edge is at the top.
There's a grid square above but not to the left - i.e. we're looking at a tile in the leftmost column. As for situation 2, we can use the bottom edge of the tile above to find the correct tile and then orient it using by putting the outside edge on the left.
There are grid squares both to the left and above - i.e. we're looking at any other tile. We have both the right edge of the tile to the left and the bottom edge of the tile above to determine the tile to use and its orientation.

Having determined which tile we're using and which of its edges are going in the left and top positions of its grid square, we can simply use the opp() function defined above to get the right and bottom edges - which are important as they'll be needed to find the tiles to the right and below.

The whole process looks ike:

GRID_SIZE = 12

def generate_grid(matches):
    # Grid is a map from (x, y) to (tile, top_edge_no, right_edge_no, bottom_edge_no, left_edge_no)
    grid = {}

    for row in range(0, GRID_SIZE):
        for column in range(0, GRID_SIZE):
            # Determine which edges should go to the left and
            # top of this grid square. 
            left_edge = None
            top_edge = None
            if column == 0 and row == 0:
                # We're at the top left of the grid. Find a 
                # corner piece by looking for a tile with
                # two adjacent outside edges.
                for (left_edge, matching_edge) in matches.items():
                    top_edge = cw(left_edge)
                    if matching_edge is None and matches[top_edge] is None:
                        break
                else:
                    raise Exception('Could not find a corner piece for the top left corner.')
            else:
                if column > 0:
                    # Use the right edge of the tile to the left
                    # to determine the left edge of this tile.
                    (left_tile_id, _, left_tile_right_edge_no, _, _) = grid[(column - 1, row)]
                    left_edge = matches[(left_tile_id, left_tile_right_edge_no)]
                    if row == 0:
                        # We're on the top row. Any outside edge
                        # next to the left edge must be the top 
                        # edge.
                        top_edge = find_adjacent_outside_edge(left_edge, matches)
                if row > 0:
                    # Use the bottom edge of the tile above to
                    # determine the top edge of this tile.
                    (above_tile_id, _, _, above_tile_bottom_edge_no, _) = grid[(column, row - 1)]
                    top_edge = matches[(above_tile_id, above_tile_bottom_edge_no)]
                    if column == 0:
                        # We're on the leftmost column. Any 
                        # outside edge next to the top edge
                        # must be the left edge.
                        left_edge = find_adjacent_outside_edge(top_edge, matches)
                    else:
                        # We're in the middle of the grid. 
                        # Check the both edges belong to the 
                        # same tile.
                        if left_edge[0] != top_edge[0]:
                            raise Exception(
                                f'Inconsistency at {(column, row)}: right edge of tile to the left matches {left_edge[0]}.{left_edge[1]} but bottom edge of tile above matches {top_edge[0]}.{top_edge[1]}')

            # If we have the left and top edges we know the 
            # right and bottom edges.
            right_edge = opp(left_edge)
            bottom_edge = opp(top_edge)

            grid[(column, row)] = (left_edge[0], top_edge[1], right_edge[1], bottom_edge[1], left_edge[1])

    return grid

The above uses the following function when looking for outside edges on tiles in the top row or leftmost column:

def find_adjacent_outside_edge(edge, matches):
    'Look for an outside edge adjacent to the given edge on the same tile.'
    clockwise_edge = cw(edge)
    if matches[clockwise_edge] is None:
        return clockwise_edge
    anticlockwise_edge = acw(edge)
    if matches[anticlockwise_edge] is None:
        return anticlockwise_edge
    raise Exception(f'Expected an outside edge adjacent to edge {edge[0]}.{edge[1]}.')

Building the Image

Now we know which tiles are in which position on the grid we need to stitch together the complete image. The plan is to work from the top left again and:

Trim each tile to remove the outer edges (these are not part of the actual image data according to the puzzle text)
Using the data from the grid dictionary we just populated, flip and rotate the tile's image data until it has the right orientation.
Add the data to a giant tile that represents the whole image.

Trimming a tile is simple enough:

def trim_tile(tile):
    'Remove the outer edges of the tile'
    return [row[1:-1] for row in tile[1:-1]]

It's the second step here that's the trickiest. The grid dictionary will tell us which edges of a tile are in which positions. We need a way of taking an entry like (1000, 1, 0, 3, 2) (our example from before) and figuring out that this means we need to flip the tile data about its vertical axis and then rotate it clockwise.

There are actually only 8 possibilities here as we're talking about the group of symmetries of a square (this is the group D4, the dihedral group of order 8). As a result I didn't do anything clever - instead I just worked through all 8 and applied the appropriate transformation for each. This only requires looking at the edge numbers that are in the left and top positions, so if as in our example we see 2 in the left position and 1 in the top position we know we need to flip about the vertical axis and then rotate clockwise.

To perform the transformation of the tile we need functions that can manipulate the tile data to produce a flipped or rotated tile. It turns out that all symmetry transformations of a square can be generated by various combinations of flipping about the vertical axis and rotating one or more times by 90° clockwise (i.e. these transformations are generators of the symmetry group D4). These functions look like:

def flip_v(tile):
    'Flip around vertical axis'
    return [row[::-1] for row in tile]

def rotate_90(tile):
    'Rotate by 90 degrees clockwise'
    new_tile = []
    size = len(tile)
    for row in range(size):
        s = []
        for column in range(size):
            s.append(tile[size - 1 - column][row])
        new_tile.append(''.join(s))
    return new_tile

To see these in action, suppose we have a 3 by 3 tile like:

a b c
d e f
g h i

Rotating this tile clockwise should produce:

g d a
h e b
i f c

On the other hand, flipping it about its vertical axis should produce:

c b a
f e d
i h g

To check:

>>> tile = ['abc', 'def', ghi']
>>> rotate_90(tile)
['gda', 'heb', 'ifc']
>>> flip_v(tile)
['cba', 'fed', 'ihg']

so it looks like these functions work as expected.

Now we can work through the 8 possible distinct combinations of these transformations and write down which edge number ends up on the left side and which at the top (assuming we start with our standard edge numbering of 0 at the top, 1 on the right, 2 at the bottom and 3 on the left). Here's one way the two transformations flip_v and rotate_90 can be used to generate all the others:

     0                 3                 2                 1
   +---+             +---+             +---+             +---+
   |   |             |   |             |   |             |   |
 3 |   | 1  ---->  2 |   | 0  ---->  1 |   | 3  ---->  0 |   | 2
   |   |  rotate_90  |   |  rotate_90  |   |  rotate_90  |   |
   +---+             +---+             +---+             +---+
     2                 1                 0                 3

     |
     | flip_v
     v

     0                 1                 2                 3
   +---+             +---+             +---+             +---+
   |   |             |   |             |   |             |   |
 1 |   | 3  ---->  2 |   | 0  ---->  3 |   | 1  ---->  0 |   | 2
   |   |  rotate_90  |   |  rotate_90  |   |  rotate_90  |   |
   +---+             +---+             +---+             +---+
     2                 3                 0                 1

This gives the following table:

Transformation	Left edge	Top edge
Nothing	3	0
`rotate_90(tile)`	2	3
`rotate_90(rotate_90(tile))`	1	2
`rotate_90(rotate_90(rotate_90(tile)))`	0	1
`flip_v(tile)`	1	0
`rotate_90(flip_v(tile))`	2	1
`rotate_90(rotate_90(flip_v(tile)))`	3	2
`rotate_90(rotate_90(rotate_90(flip_v(tile))))`	0	3

All the code needs to do is see which left edge/top edge combination we have and apply the appropriate transformation:

def adjust_tile(tile, left_edge, top_edge):
    '''Given the edge numbers that should be on the left and at 
    the top, perform any necessary transformations to re-orient
    the tile'''
    if left_edge == 3 and top_edge == 0:
        return tile
    if left_edge == 2 and top_edge == 3:
        return rotate_90(tile)
    if left_edge == 1 and top_edge == 2:
        return rotate_90(rotate_90(tile))
    if left_edge == 0 and top_edge == 1:
        return rotate_90(rotate_90(rotate_90(tile)))
    if left_edge == 1 and top_edge == 0:
        return flip_v(tile)
    if left_edge == 2 and top_edge == 1:
        return rotate_90(flip_v(tile))
    if left_edge == 3 and top_edge == 2:
        return rotate_90(rotate_90(flip_v(tile)))
    if left_edge == 0 and top_edge == 3:
        return rotate_90(rotate_90(rotate_90(flip_v(tile))))
    raise Exception(f'Invalid combination of left and top edges: {left_edge}, {top_edge}')

Now we have all the pieces we need to put the image together!

TILE_SIZE = 10

def create_image(grid, tiles):
    '''Given the grid information and the tiles, stitch the 
    tiles together into an image'''
    image = []
    for row in range(0, GRID_SIZE):
        # We're stripping the outer edges from each tile, so 
        # only need space for TILE_SIZE - 2 image rows per 
        # grid row.
        for _ in range(TILE_SIZE - 2):
            image.append('')

        for column in range(0, GRID_SIZE):
            (tile_id, top_edge, _, _, left_edge) = grid[(column, row)]
            tile = tiles[tile_id]
            tile = adjust_tile(tile, left_edge, top_edge)
            tile = trim_tile(tile)

            for (i, tile_row) in enumerate(tile):
                image_row = row * (TILE_SIZE - 2) + i
                image[image_row] += tile_row

    return image

Finding Sea Monsters

But we're still not there! This really is a marathon question. We need to find the total number of hashes in the finished image that aren't part of a sea monster. A sea monster is defined as:

                  #
#    ##    ##    ###
 #  #  #  #  #  #

so contains 15 hashes. Therefore the answer to part 2 will be the total number of hashes in the image minus 15 times the number of sea monsters.

First let's find the total number of hashes, assuming image is the output of the create_image() function defined above:

hashes = sum(sum(1 for c in row if c == '#') for row in image)

Now we need to count the number of sea monsters. The puzzle wording isn't completely clear, but I took it to mean that only one orientation of the image would yield any sea monsters at all - all other orientations would have none. We have a choice here: we can either reorient the entire image and look for the untransformed sea monster, or reorient the sea monster and look for it in an untransformed image. Given that we already have functions to transform arbitrarily-sized tiles and the image is just a big tile, it seems easiest to reorient the image until we find the orientation that yields some sea monsters.

However, before we worry about finding the right image orientation we need to be able to detect a sea monster! The requirement for a sea monster is only that the hashes defined above are present - there could be extra hashes, and even the following would still count as a sea monster:

####################
####################
####################

The way to go seems to be to examine every 20 x 3 block of characters in the image and check just the characters that are required in the sea monster to see if they're hashes. To do this we can define the offsets at which we expect to find hashes, along with the width and height of a sea monster:

# These are the offsets that describe a sea monster shape
#
#   00000000001111111111
#   01234567890123456789
# 0                   #
# 1 #    ##    ##    ###
# 2  #  #  #  #  #  #
MONSTER_OFFSETS = [
    (18, 0),
    (0, 1), (5, 1), (6, 1), (11, 1), (12, 1), (17, 1), (18, 1), (19, 1),
    (1, 2), (4, 2), (7, 2), (10, 2), (13, 2), (16, 2)
]
MONSTER_WIDTH = 20
MONSTER_HEIGHT = 3

so checking for a monster at (x, y) in the image looks like:

def has_monster(image, x, y):
    'Return True if a sea monster can be found at (x, y) in the image'
    if y > len(image) - MONSTER_HEIGHT:
        return False
    if x > len(image[0]) - MONSTER_WIDTH:
        return False
    for offset in MONSTER_OFFSETS:
        sx = x + offset[0]
        sy = y + offset[1]
        if image[sy][sx] != '#':
            return False
    return True

and counting all the sea monsters is just repeated application of the above:

def count_monsters(image):
    'Return the total number of sea monsters in the image'
    count = 0
    for x in range(len(image[0]) - MONSTER_WIDTH):
        for y in range(len(image) - MONSTER_HEIGHT):
            if has_monster(image, x, y):
                count += 1
    return count

However as mentioned above, we also need to allow for reorienting the image! We already know how to generate all the possible symmetry transformations for a square, so we can just walk through them one at a time:

def reoriented_images(image):
    'Work through the 8 possible ways the image could be flipped and rotated'
    yield image
    yield rotate_90(image)
    yield rotate_90(rotate_90(image))
    yield rotate_90(rotate_90(rotate_90(image)))
    yield flip_v(image)
    yield rotate_90(flip_v(image))
    yield rotate_90(rotate_90(flip_v(image)))
    yield rotate_90(rotate_90(rotate_90(flip_v(image))))

Putting it All Together

We're on the home straight and the finish line is in sight! Using all the work done above we can actually solve part 2:

def part2():
    tiles = read_input()

    # Match up the tile edges
    matches = find_matching_edges(tiles)

    # Now build a grid of all the tiles, flipping and rotating as necessary
    grid = generate_grid(matches)

    # Gather all tiles together into one image
    image = create_image(grid, tiles)

    # Get the total number of hashes in the image
    hashes = sum(sum(1 for c in row if c == '#') for row in image)

    # Look for sea monsters
    # The assumption here (based on the puzzle wording) is that
    # sea monsters only appear in one orientation of the image,
    # so we just need to keep reorienting the image until we
    # find a non-zero number of monsters.
    for reoriented_image in reoriented_images(image):
        monsters = count_monsters(reoriented_image)
        if monsters > 0:
            # Return the number of hashes that aren't in a sea monster
            return hashes - monsters * len(MONSTER_OFFSETS)

Phew!

I would be interested to know of any shortcuts to all the above - this required much more code than any of the other days this year, so I was left with the nagging feeling I'd missed a clever trick!

Advent of Code 2020 - Day 10

matju — Fri, 25 Dec 2020 14:08:25 +0000

https://adventofcode.com/2020/day/10 ('Adapter Array')

This felt like the first more difficult problem in this year's set.

Part 1 is relatively straightforward: as each adaptor must have a lower-rated adaptor on one side and a higher-rated one on the other, the only way to use all the adaptors is to sort them in ascending order. Having done this we can workout the differences between adjacent adaptors and from this count the number of 1s or 3s:

def part1():
    adaptors = sorted(read_input())
    target = adaptors[-1] + 3
    adaptors = [0] + adaptors + [target]

    diffs = [adaptors[i + 1] - adaptors[i] for i in range(0, len(adaptors) - 1)]
    diff_1_count = sum(1 for d in diffs if d == 1)
    diff_3_count = sum(1 for d in diffs if d == 3)
    return diff_1_count * diff_3_count

Solving part 2 was a bit of a journey. My first instinct was to try a recursive solution:

Start with all the adaptors
Find the first adaptor in the list that can be removed (i.e. removing it wouldn't leave a gap bigger than 3 between the two adaptors that would become adjacent)
Create a copy of the list with the adaptor removed and recursively try to solve the same problem, removing only adaptors to the right of the one removed.
Go back to 2, looking for the next adaptor that can be removed.

This looks like:

def count_ways(adaptors, start=1):
    if start >= len(adaptors) - 1:
        return 1
    count = 1
    for i in range(start, len(adaptors) - 1):
        # See if we can remove adaptor i
        diff = adaptors[i + 1] - adaptors[i - 1]
        if diff <= 3:
            # We can remove adaptor i, so see which ones to the right of it we can also remove
            new_adaptors = adaptors[:i] + adaptors[i + 1:]
            count += count_ways(new_adaptors, i)
    return count

where adaptors[0] is the socket and adaptors[-1] is the device.

My puzzle input had 108 adaptors in it so the number of possible combinations to be checked could be as high as 2^108, or about 10^33. Counting these one at a time wasn't going to get anywhere fast! Of course, the problem can be simplified but it took me some time to work out how.

Simplifying the Problem

Looking at the larger example given in the puzzle (with 19,208 possibilities) we have the following adaptors (including the socket and the device at either end):

0 1 2 3 4 7 8 9 10 11 14 17 18 19 20 23 24 25 28 31 32 33 34 35 38 39 42 45 46 47 48 49 52

We can tell that some of these adaptors can't be removed as they would leave a gap of more than three - and the socket and device obviously can't be removed. Marking these non-removable adaptors with brackets we get:

(0) 1 2 3 (4) (7) 8 9 10 (11) (14) (17) 18 19 (20) (23) 24 (25) (28) (31) 32 33 34 (35) (38) (39) (42) (45) 46 47 48 (49) (52)

The trick now is not to regard this as a single problem. Instead we split the list of adaptors up into sets that are bookended by adaptors that can't be removed:

(0) 1 2 3 (4)
(7) 8 9 10 (11)
(14)
(17) 18 19 (20)
(23) 24 (25)
(28)
(31) 32 33 34 (35)
(38) (39)
(42)
(45) 46 47 48 (49)
(52)

Provided that the resulting groups are small enough, counting the number of possibilities for each group independently and then multiplying the result for each group together should be a much faster way of producing the same result. Looking at the example above, we have five kinds of group:

(n) - a group containing a single non-removable adaptor. There's only one possibility here as nothing can be removed.
(n), (n + 1) - a group containing two non-removable adaptors. Again, only one possibility.
(n), n + 1, (n + 2) - a group of consecutive integers with a removable adaptor in the middle. There are two possibilities as the middle adaptor can either be present or not.
(n), n + 1, n + 2, (n + 3) - consecutive integers with two removable adaptors in the middle. Either, both or neither can be removed so there are four possibilities.
(n), n + 1, n + 2, n + 3, (n + 4) - consecutive integers with three removable adaptors in the middle. In this case we can remove any combination of the middle adaptors as long as we don't remove all three at once (as the jump from n to n + 4 would be too big). This gives 7 possibilities.

Working through the groups then, the number of possibilities are 7, 7, 1, 4, 2, 1, 7, 1, 1, 7 and 1 - and multiplying these together gives 19,208 as expected.

Splitting the adaptors into groups is just a matter of collecting subsequent adaptors until the gap is 3 or more:

def split_adaptors(adaptors):
    group = []
    last_adaptor = adaptors[0]
    for adaptor in adaptors:
        if adaptor - last_adaptor >= 3:
            yield group
            group = []
        group.append(adaptor)
        last_adaptor = adaptor
    yield group

so part 2 becomes:

from functools import reduce
from operator import mul

def part2_recursive():
    adaptors = get_adaptors()

    return reduce(mul, (count_ways(group) for group in split_adaptors(adaptors)))

(where the code to read the adaptors, sort them and add on the outlet and device at the beginning and end of the list has been pulled out into get_adaptors()).

Luckily the largest group in my puzzle input had five adaptors so this worked perfectly! For my input the result was 226,775,649,501,184, calculated in about 0.3ms.

However the story doesn't end here - there are other ways of solving the problem that I also ended up exploring, culminating in a very neat non-recursive method that seems almost like magic...

Tribonacci Numbers

I noticed that the adaptors in my input were all either 1 or 3 apart - there were no differences of 2. This means that when split into groups book-ended by adaptors that can't be removed, each group is always of the form of n consecutive integers:

(x)   x + 1   x + 2   ...   x + n - 3   x + n - 2   (x + n - 1)

where x and x + n - 1 are the non-removable adaptors.

I wondered whether rather than recursively calculating the number of possibilities using the count_ways() function from above there might be some kind of closed-form expression for the number of possibilities for a group of size n. Continuing on from above and working out the number of possibilities for groups of 6 or 7 adaptors by hand we get:

Group size (`n`)	Possibilities
1	1
2	1
3	2
4	4
5	7
6	13
7	24

I didn't spot the pattern straight away and instead entered the sequence into the OEIS. This turned up sequence A000073, or the so-called tribonacci numbers. If this pattern holds true for all cases, we should be able to calculate the nth tribonacci number fairly quickly using recursion. There's a formula for the nth tribonacci number but, just as for Fibonacci numbers, it relies on exponentiation of irrational numbers so will be limited by the accuracy of floating-point arithmetic.

For a group of n consecutive adaptors, the middle n - 2 are removable. If we were allowed to remove any combination of adaptors there would be 2^(n - 2) possibilities. However we are constrained by not being allowed to remove three or more consecutive adaptors. Finding the number of possibilities is therefore equivalent to finding the number of binary numbers of length n - 2 that do not contain three consecutive zeros.

Let's say that B(n) is the number of binary numbers of length n that don't contain three consecutive zeros, so:

B(1) = 2 (i.e. 0 or 1)
B(2) = 4 (00, 01, 10 or 11)
B(3) = 7 (001, 010, 011, 100, 101, 110, 111, but not 000)
B(4) = 13 (16 combinations minus 1000, 0001 and 0000), etc.

Thinking about it, B(n) will contain binary numbers belonging to one of these categories:

1xxxxxx (i.e. a 1 followed by an n - 1 digit number that doesn't contain three consecutive zeros)
01xxxxx (i.e. 01 followed by an n - 2 digit number that doesn't contain three consecutive zeros)
001xxxx (i.e. 001 followed by an n - 3 digit number that doesn't include three consecutive zeros)

No numbers in B(n) can start with any other combination of digits (e.g. 0001) as this would give them three consecutive zeros at the start. We can immediately see that the number of numbers in the first category is B(n - 1), in the second is B(n - 2) and in the third is B(n - 3), so we must have B(n) = B(n - 1) + B(n - 2) + B(n - 3) - which is the definition of the tribonacci sequence!

Having proved that number of possibilities for a group of adaptors of size n do follow the tribonacci sequence, we can rewrite part 2 as:

from functools import lru_cache, reduce
from operator import mul

def part2():
    @lru_cache
    def tribonacci(n):
        if n == 1:
            return 2
        if n == 2:
            return 4
        if n == 3:
            return 7
        return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)

    def count(group_size):
        if group_size < 3:
            return 1
        return tribonacci(group_size - 2)

    adaptors = get_adaptors()
    return reduce(mul, (count(len(group)) for group in split_adaptors(adaptors)))

This is much simpler than before, though it's still recursive. The tribonacci numbers can be cached using the @lru_cache decorator from the functools module to ensure we only calculate each one once (though in reality tribonacci(n) is only called with n equal to 1, 2 or 3 for the puzzle input, so there's not much repetition). This evaluates to the same result as the previous method, but in 0.2ms - so a slight improvement on the 0.3ms from before!

Graphs - First Attempt

But we're still not done! So far we've regarded the adaptors as a set from which we can remove different combinations subject to certain rules. What if we think of the adaptors as a graph?

Let's regard each adaptor as a node in a graph with links to all the adaptors that could follow it (so adaptor 4 could have links to adaptors 5, 6 and 7 - if they exist - but not adaptor 8). Now solving the problem is equivalent to counting the number of routes through the graph from the socket to the device.

Constructing the graph is relatively straightforward, though it helps to have the adaptors as a set first:

# Build a graph so that each adaptor lists the adaptors that
# could follow it.
adaptors = set(adaptors)
follows = {}
for adaptor in adaptors:
    following_adaptors = []
    # There are only three possible adaptors that this one 
    # could connect to
    for i in range(3):
        following_adaptor = adaptor + i + 1
        # Only link to adaptors that actually exist
        if following_adaptor in adaptors:
            following_adaptors.append(following_adaptor)
    follows[adaptor] = following_adaptors

Counting the number of routes through the graph is another recursive problem: the number of routes from a given node is equal to the sum of the number of routes from each of the nodes that follow it, with the final node counting as having 1 route:

@lru_cache
def count_paths(start):
    if len(follows[start]) == 0:
        return 1
    return sum(count_paths(next_adaptor) for next_adaptor in follows[start])

Decorating the function with @lru_cache is definitely a good idea here as the counting process is likely to hit the same nodes repeatedly when tracing all the routes through the graph.

Now the answer is just a matter of calculating count_paths(0). This takes about 0.7ms, so is slower than either of the above techniques. However it does feel conceptually cleaner, especially when compared to the complicated recursion in the count_ways() function used in the first approach.

Graphs - Second Attempt

However this is one more step we can take - and this results in a solution which (to me at least) seems like wizardry.

Instead of counting the number of possible paths from a given node in the graph to the final node (the device), we can look at it the other way round and calculate the number of ways it's possible to get to a particular node. The overall answer would then be the number of ways of reaching the device at the end of the adaptor list.

The important thing to note is that each adaptor is unique (we don't have two adaptor 8s, say) and that adaptor a can only be connected to from adaptors a - 1, a - 2 and a - 3 (if they exist). As a result we don't need recursion at all: we can just start from 0 and work our way up through the adaptors in numerical order, knowing that by the time we've got to adaptor a we'll already have worked out the number of ways of getting to all the adaptors that could precede it!

So what does this magical solution look like? This is all it is:

def part2():
    adaptors = get_adaptors()

    # We start the process by saying that there's one way to 
    # get to the start node.
    counts = {0: 1}

    for a in adaptors[1:]:
        # Number of ways to get to adaptor a is equal to the
        # sum of the number of ways of getting to a - 1, a - 2
        # and a - 3.
        counts[a] = counts.get(a - 1, 0) + \
            counts.get(a - 2, 0) + counts.get(a - 3, 0)

    return counts[adaptors[-1]]

No recursion, no lru_cache, completes in just over 0.2ms - why didn't I think of this to start with?

Advent of Code 2020 - Day 23

matju — Wed, 23 Dec 2020 17:25:35 +0000

https://adventofcode.com/2020/day/23 ('Crab Cups')

After reading part 1 the first thing that came to mind was pretty much a literal translation of the problem into code using list slicing:

def part1():
    cups = [2, 4, 7, 8, 1, 9, 3, 5, 6]
    num_cups = len(cups)

    for _ in range(100):
        # Keep things arranged so the current cup is always at 
        # index 0
        current_cup = cups[0]

        # This means we always want to extract the cups at 
        # indices 1, 2 and 3.
        # The cup at index 4 will always be the next current 
        # cup, so should end up at the start.
        # The existing current cup should be moved to the end.
        extracted = cups[1:4]
        cups = cups[4:] + cups[:1]

        destination_cup = current_cup
        while True:
            destination_cup -= 1
            if destination_cup < 1:
                destination_cup += num_cups
            if destination_cup not in extracted:
                break

        destination_index = cups.index(destination_cup) + 1
        cups = cups[:destination_index] + extracted + cups[destination_index:]

    one_index = cups.index(1)
    cups = cups[(one_index + 1):] + cups[:one_index]
    return ''.join(str(cup) for cup in cups)

This ran in about 0.2ms, which seemed reasonably fast until I read part 2! It was immediately clear that the approach in part 1 wasn't going to cut it with an input 100,000 times as big over 100,000 times as many rounds:

I was creating lots of new list objects each round as a result of all the list slicing and concatenation operations.
Apart from the churn of creating lots of short-lived objects, the slicing and concatenation operations are O(n) as copies are being made of parts of the list data each time.
The destination cup is found through a linear search - also O(n).

Extending the list to a million items in the code above and running it for 100 iterations takes around 6s, or about 30,000 times as long as for a 9-element list. Extending the run from 100 to 10,000,000 iterations would therefore take about 7 days to complete!

There seemed to be two ways forward:

Remove as many of the O(n) operations as possible so the size of the list of cups isn't a factor when calculating each iteration, or
Spot a pattern in the way the cups move so that the two cups directly after cup 1 can be predicted without having to evaluate the whole problem.

Approach 2 has worked in the past for some previous AoC problems - 2019 Day 16 is an example where looking for a pattern collapses the problem down into something more manageable. However on this occasion after a fair bit of time staring at some examples I couldn't see any obvious way to simplify things.

This leaves option 1. As we're constantly adding/removing sublists from within a list, a linked list seems like a better option as splitting and concatenating a linked list is O(1).

Python doesn't have a linked list in its standard library, though it does have a double-ended queue or deque. I considered going down this route as adding/removing items to/from either end of a deque is an O(1) operation. However using a deque doesn't actually help us much: while removing and re-adding the three elements would be O(1), hunting for where to reinsert by repeatedly rotating the deque would still be O(n).

Surely a linked list will have the same problem? Searching in a linked list is also an O(n) operation so figuring out where to insert the extracted elements will still take a long time for a large list. After a bit of thought I realised that we can simply create an index! The linked list would consist of n objects, one for each cup, each with two properties: the cup number and a pointer to the next cup - something like this:

class Cup:
    def __init__(self, number, next_cup=None):
        self.number = number
        self.next_cup = next_cup # reference to next Cup object

The index would be a dictionary from cup number to cup object. This should give O(1) slicing/concatenation and O(1) search!

In fact, we can simplify this more:

As the index is a dictionary from cup number to Cup object and the cup numbers are a contiguous set of integers, we can just use an array instead of a dictionary as the index. The object for cup n would be stored at array index n.
As the index contains references to all the Cup objects, the Cup objects themselves don't have to point to other Cup objects - they can just contain the number of the following cup and the code can go via the index to get the corresponding cup object.
But doing this makes the Cup objects themselves redundant: we can just have an array where index n contains the number of the cup that follows cup n.

All this leads to the following for part 2:

def part2():
    MAX_CUP = 1000000

    # Create a 1,000,001-entry array where cups[n] gives the 
    # number of the cup following cup n.
    # As there's no cup zero we can set it to point to itself.
    cups = [0]
    # The cups in order are [2, 4, 7, 8, 1, 9, 3, 5, 6, 10, 11, 12, 13...]
    # So cup 9 follows cup 1, cup 4 follows cup 2, cup 5
    # follows cup 3 etc.
    cups.extend([9, 4, 5, 7, 6, 10, 8, 1, 3])
    # For cups[10] to cups[MAX_CUP - 1], each cup points to the
    # one one number higher
    cups.extend(range(11, MAX_CUP + 1))
    # The last cup (cups[MAX_CUP]) points back to cup 2
    cups.append(2)

    current_cup = 2

    for _ in range(10000000):
        # Cups to remove are the three following the current cup
        e1 = cups[current_cup]
        e2 = cups[e1]
        e3 = cups[e2]
        next_cup = cups[e3]

        # Close the gap by making the cup after the current cup
        # be the cup that was after the block being removed.
        cups[current_cup] = next_cup

        # Work out where to reinsert the extracted section
        destination_cup = current_cup
        while True:
            destination_cup -= 1
            if destination_cup < 1:
                destination_cup += MAX_CUP
            if not (destination_cup == e1 or destination_cup == e2 or destination_cup == e3):
                break

        # Move the current cup along one.
        current_cup = next_cup

        # Reinsert the extracted section by changing the
        # following index of the destination cup to point at
        # the extracted section, and the following index of the
        # extracted section to point at the original following 
        # index of the destination.
        next_cup = cups[destination_cup]
        cups[destination_cup] = e1
        cups[e3] = next_cup

    c2 = cups[1]
    c3 = cups[c2]

    return c2 * c3

During the loop there are no new lists being allocated and no linear searches through lists, so this ought to run equally fast for a million cups as it would for 9 cups. In fact it churns through 100,000,000 rounds in about 8.5 seconds - and it's more than twice as quick as the original implementation when applied to part 1.

This is one of those problems where choosing the right representation of the data makes an enormous difference. Looking back, I probably could have predicted that part 2 would be a scaled-up version of part 1 and thought a bit more before diving in and implementing the naive version.