Advent of Code

This was a though one for me, but extremely satisfying once I got it right. But clearly: performance optimization is not my forte.

Part 1 - it’s easy… too easy

Each step, every number is changed according to a set of rules. Each rule has an applicability condition, and we have to go through the rules in order, applying the first applicable one. The rules are:

The goal is, from a starting sequence, to find how many numbers you’ll have after 25 steps. So for instance, we could have starting from 0:

This is not too hard to implement, and I thought that the second part might add some new rules so I tried to make things a bit generic, with rules encoded as a list of tuples of (Predicate, Action), with Predicate being a function str \(\rightarrow\) bool (testing if the rule is applicable), and Action a function str \(\rightarrow\) list[str] (transforming the number into a list of one or two other numbers). I decided to keep the numbers as str so that the “split” operation is easier to manage. With that, I could have a generic apply_rules function:

Predicate = Callable[[str], bool]
Action = Callable[[str], list[str]]
Rule = tuple[Predicate, Action]

class NoTruePredicateException(Exception):
    pass

def apply_rules(x: str, rule_chain: list[Rule]) -> list[str]:
    for predicate, action in rule_chain:
        if predicate(x):
            return action(x)
    
    raise NoTruePredicateException(f"No true predicate for value {x}")

rule_chain = [
        (lambda x : x == '0', lambda x : ['1']),
        (lambda x : (len(x)%2) == 0, lambda x : [x[:len(x)//2], str(int(x[len(x)//2:]))]),
        (lambda x : True, lambda x : [str(int(x)*2024)])
    ]

And the update step will just apply the rules to each element, and flatten the list.

def flatten(values: list[list[str]]) -> list[str]:
    return list(itertools.chain.from_iterable(values))

def step(values: list[str], rule_chain: list[Rule]) -> list[str]:
    return flatten([apply_rules(x, rule_chain) for x in values])

With that, we can reasonably quickly compute the right answer (with data the initial list of str in the puzzle input):

for _ in range(25):
    data = step(data, rule_chain)
    
print(f"Part 1 answer: {len(data)}")

Part 2 - oh no, I’ve made a terrible mistake

I thought part 2 would have some twists in the rule set, but no. As soon as I read it, I knew I would suffer: how many numbers do we have if we update the list 75 times.

There can only be one reason for such a short part 2: exploding computation time. I still tried to run my code just to check, but there was just no way I was going to be able to compute that far.

So I had to think. I first tought that, since the state at step n+1 of a number only depended on itself (and not any of its neighbours), I could use the fact that numbers repeated in the list: if I have encountered this number before, I already know its next value. But I still couldn’t manage to avoid to keep track of every single current value in the list, which was very clearly to core of the issue.

Then I got it, once I had written on paper the sequence starting from ["0"].

Part 2, part 2 - it’s a tree!

The whole “update” pattern is a tree – a recursive tree (okay, technically a graph, but I wrote “tree” in my code so I’m running with it)!

Let’s rewrite the sequence from ["0"], but this time I just look at the “next update” from any of the number we can visit in that sequence:

We can see that we have many cycles. In fact, the whole tree is finite. I wrote some code to compute the whole tree from a given number:

def compute_full_tree(start: str, rule_chain: list[Rule]) -> dict[str, list[str]]:
    tree = {}
    queue = [start]
    while len(queue) > 0:
        v = queue.pop()
        if v in tree:
            next_v = tree[v]
        else:
            next_v = apply_rules(v, rule_chain)
            tree[v] = next_v

        for v in next_v:
            if v not in tree:
                queue.append(v)
    
    return tree

Starting from 0, we can actually only visit 54 different numbers. Here they are, if you’re interested (for some reason):

More interesting: every number in the input sequence also has a finite “tree” (graph). So how can we use that? Now, we actually no longer need to keep track of the current list. The only thing we have to do is to compute, for each node in the tree, the “number of branches” it will have a time step n. Which is equal to the sum of the number of branches of its children at time step n-1.

So for 0, for instance, we have one child: 1. So after one step, it just has a single branch. Since 1 also has a single branch, 0 will still have one branch after two steps (so it goes [0] -> [1] -> [2024]). But 2024 has two branches, so after the third step 0 will have two branches: [0] -> [1] -> [2024] -> [20, 24]. How many branches will it have on the fourth? The sum of the number of branches of 20 after three steps and the number of branches of 24 after three steps.

Therefore, the only thing we need to keep track of are the current number of lines of each node.

First, we have to build the full tree for the problem, which is the union of the trees stemming from all the input numbers:

tree = {}
for v in data:
    tree.update(compute_full_tree(v, rule_chain))

Then we can initialize the count at the number of children for each node, and start updating that count for the desired number of steps:

count_in_tree = {key: len(tree[key]) for key in tree}
for _ in range(1, 75):
    newcount = {key: sum(count_in_tree[n] for n in tree[key]) for key in tree}
    count_in_tree = newcount

To get our total, we just have to sum the counts of all the values for the input numbers:

total = sum(count_in_tree[key] for key in data)
print(f"Part 2 answer: {total}")