I’m a bit late, so here are days 7 to 9. As now usual, all my solutions are available on https://git.sr.ht/~schnouki/advent-of-code.

Day 7: Handy Haversacks

Bags inside bags inside bags… Do we have recursive bags now? 😯

Anyway. The first step is to parse those descriptions into something more usable. I’ve decided to do it without regexps, and storing data in simple dicts:

def parse_rule_line(line: str) -> Tuple[str, Dict[str, int]]:
    """Parse 1 rule line.

    >>> parse_rule_line("light red bags contain 1 bright white bag, 2 muted yellow bags.")
    ('light red', {'bright white': 1, 'muted yellow': 2})
    >>> parse_rule_line("faded blue bags contain no other bags.")
    ('faded blue', {})
    """

    words = line.split()
    container_color = " ".join(words[:2])

    if words[4] == "no":
        return (container_color, {})

    bags = {}
    for idx in range(4, len(words), 4):
        color = " ".join(words[idx + 1 : idx + 3])
        bags[color] = int(words[idx])

    return (container_color, bags)


data = {}
for line in raw_data.splitlines():
    color, bags = parse_rule_line(line.strip())
    data[color] = bags

Part 1: how many bags can contain a shiny gold bag?

The first obvious (to me) way to solve this was to rewrite rules android substitute colors that can contain the target color recursively. It works… but is slow and complex.

A better, simpler solution is to a list of colors that can contain the target color, iterate over the rules to add colors that can contain any bag in that list, and keep doing that until that list is stable.

Here’s how the code looks like:

def check_content(rules: Rules, target: str) -> int:
    containers = {target}
    n = 0
    while len(containers) != n:
        n = len(containers)
        for bag_color, bag_content in rules.items():
            inter = containers.intersection(set(bag_content.keys()))
            if inter:
                containers.add(bag_color)
    return len(containers) - 1

print(check_content(data, "shiny gold"))

This is not super nice, nor super fast, but it does the job. This takes between 2 and 3 ms to run.

Part 2: how many bags in a shiny gold bag?

This part is a bit easier! Using our rules as described above, we can do it recursively: the size of a bag is the number of bags it contains multiplied by their own size.

The code is almost as simple:

def count_bags(rules: Rules, color: str) -> int:
    res = 1 + sum(
        qty * count_bags(rules, bag_color) for bag_color, qty in rules[color].items()
    )
    return res

print(count_bags(data, "shiny gold"))

This is actually much faster: less than 0.2 ms!

Another excellent solution

My amazing coworker Lucia also published her own solution on GitHub. She used a clever way of parsing the rules, to build a top-down and a down-top version, which makes it very easy to solve both parts.

Day 8: Handheld Halting

Yay, another pseudo-VM! Reminds me of IntCode last year. Hopefully, it will be a one-time thing and not a full-blown CPU with 3 addressing modes…

…but just to be sure I still implemented this as a “VM” that can easily be reused and extended. The full code is a bit long to include here, but can be found on sourcehut.

(By the way, did you notice that today’s title is a not-so-subtle reference to the famous halting problem?)

Part 1: detecting an infinite loop

That’s easy: by adding a callback to our VM, we can examine the value of the “instruction pointer” before executing every instruction. So we just need to log all visited values. Once we’re back to one we’ve already visited, we know we’re done.

visited_ips = set()
result = None

def check_visited_ips(vm):
    nonlocal result
    if vm.ip in visited_ips:
        vm.stopped = True
        result = vm.acc
    else:
        visited_ips.add(vm.ip)

vm = data.clone()
vm.callback = check_visited_ips
vm.run()
print(result)

Simple enough. This is a bit like attaching a debugger to a running program. This takes about 0.2 ms to run.

Part 2: uncorrupting the program

Ok, so now we need to fix exactly one instruction to make the program avoid going into an infinite loop.

The hard part is of course to figure out which instruction needs to be changed. If we change the wrong one, we still go into an infinite loop. And our input program has 1000 instructions.

Simple solution: brute-force it. Try to change every instruction, run the program, see if it terminates. This works, but is slow.

More complex but more efficient solution: try to run the code, and if the next instruction would send us into a loop but flipping it wouldn’t, then flip it. Restart if the patched program still loops, and don’t try to fix that specific instruction again.

I’ve implemented both solutions (the code is on sourcehut again). Unsurprisingly, the simple solution is shorter, but also slower. But we’re talking about 30 ms vs 4 ms, so it’s probably not that important anyway.

Day 9: Encoding Error

Ooh, searching stuff in a list of numbers. That should be easy enough!

Part 1

To see if a number is valid, check if there’s a pair that sums to that number in the previous 25 elements of the list. This reminds me of day 1! Instead of iterating over all pairs, we can iterate over each of the previous numbers, calculate the one needed to sum to the target number, and check if it’s here. We can safely convert to a set before so lookup is faster.

Then, we need to find the first invalid number… So we iterate over the whole list and repeat this :)

def is_valid(stream: list[int], pos: int, size: int = 25) -> bool:
    """
    Check if the number at position `pos` is valid, considering a preamble of size `size`.
    """
    n = stream[pos]
    prev = set(stream[pos - size : pos])
    for a in prev:
        b = n - a
        if b in prev:
            return True
    return False


def find_invalid_pos(stream: list[int], size: int = 25) -> int:
    """Find the position of the first invalid number."""
    for pos in range(size, len(stream)):
        if not is_valid(stream, pos, size):
            return pos
    raise ValueError()

print(find_invalid_pos(data))

Simple and effective enough, as it takes 0.8 ms.

Part 2

Okay, now we need to find a contiguous set of numbers that sum to that invalid number.

Brute-forcing this is trivial: 1 loop for the start of the set, 1 nested loop for the end of the set, keep searching while the sum is less than the target; if it’s greater than it, then continue with the next start value; and if it’s equal, then we’ve found our set.

With our previous functions it’s pretty simple:

pos = find_invalid_pos(data)
target = data[pos]

for i in range(pos - 2):
    for j in range(i + 1, pos - 1):
        r = data[i : j + 1]
        s = sum(r)
        if s == target:
            return min(r) + max(r)
        elif s > target:
            break

Aaand we’re done. This is nice, readable, and really Pythonic… but also pretty slow: about 150 ms. Slowest solution for this year so far 😉

Let’s optimize it a bit. Looking at this code, it looks like the slow parts are extracting the set (r = data[i:j+1]) and computing its sum (s = sum(r)). We can probably avoid them both by using a more efficient way to compute the sum:

• when starting a new iteration of the outer loop (i), initialize the sum to data[i];
• when starting a new iteration of the inner loop (j), increment that sum by data[j].

This way our sum is good, but we don’t do any new expensive allocation or operation in every inner loop operation: just adding 1 integer to another integer.

Then, once we’ve found the right bounds, we can recreate the list so it’s easier to use min() and max().

The optimized version looks like this:

pos = find_invalid_pos(data)
target = data[pos]

for i in range(pos - 2):
    tot = data[i]
    for j in range(i + 1, pos - 1):
        tot += data[j]
        if tot == target:
            r = data[i : j + 1]
            return min(r) + max(r)
        elif tot > target:
            break

And it takes a bit less than 9 ms to run. Almost 17 times faster 😋

See you soon for the next part!