Advent of Code 2021

2021-12-31

Day 1 #

As per usual, the first day is easy to solve with just a little bit of q. These sorts of basic data processing tasks are where q really shines. Let’s break down the code, for anyone reading who isn’t familiar with q. Bear in mind that q is read/processed from right to left with no operator precedence except for square brackets, which are used for applying (i.e. calling functions) and indexing, and are applied to whatever is to the left of them before anything else is done to the thing to the left of them.

sum 1_0>\':"J"$read0`:01.in

sum                        // Take the sum to count how many bools in the vector are true.
    1_                     // Drop the first value from the list, as it's a comparison against 0 rather than anything
                           // from the input.
      0>                   // The dyadic function `>` (greater than), and an initial value for each prior.
        ':                 // Each prior: apply a dyadic function between each item and its preceding item.
          "J"$             // Parse each line into a long int. "j" is the character code for the `long` type in q,
                           // and it being uppercase in the code means the data should be parsed from strings rather
                           // than cast from some other numeric type.
              read0`:01.in // Read in the input file as a list of character vectors (one per line).

Part 2 is similar, but uses 2_3 msum to take sums over a moving window of 3 elements from the input, with the first 2 elements dropped because they are sums of partial windows.

-3 + sum 0>':2_3 msum "J"$read0`:01.in

I’ve used Pykdb to wrap these just for consistency (every other solution is a .py file), but they could’ve just as well been q files since I didn’t use anything from Python here. That certainly won’t be the norm as the complexity of the problems increases. Still, I hope that q (via Pykdb) will have some time in the spotlight in the more complex problems to come.

Day 2 #

Not much to say about day 2. For part 1 I used q just for convenience so that I could multiply the (dy, dx) tuples by the magnitudes, and then since I was already using q I also used it to take the sum and product. Could’ve done the same thing with Numpy.

from pykdb import q

with open('02.in') as f:
    t = [x.split() for x in f]

d = {'up': (-1, 0), 'down': (1, 0), 'forward': (0, 1)}

print(q('{prd sum x}', [int(x[1]) * q.K(d[x[0]]) for x in t]))

Part 2 wound up requiring a rewrite, but with how simple the problem was that was no trouble:

with open('02.in') as f:
    t = [x.split() for x in f]

aim = 0
depth = 0
horizontal = 0
for a, b in t:
    b = int(b)
    if a == 'up':
        aim -= b
    elif a == 'down':
        aim += b
    else:
        horizontal += b
        depth += aim * b

print(horizontal * depth)

Day 3 #

My solution for day 3 part 1 was done entirely q - here’s a breakdown of the q code, split at each inline assignment for ease of reading:

// Read the input, and convert it from a list of char vectors into a list of bool vectors, where
// it's true anywhere the character is "1", and false otherwise.
a:"1"=read0`:03.in

// Set `v` to where the column-wise sum of `a` is greater than the column-wise sum of its negation.
v:(sum a)>sum not a

Remember that a single q statement should be read from bottom to top, and from right to left. As such, the comment on the bottom applies first.

prd                    // Take the product the two integers.
    sv[2]each          // Convert each boolean vector into an integer.
             (not v;v) // Create a list of bool vectors of `v` and its negation.

Here’s the full solution as it is in the .py file:

from pykdb import q

print(q('prd sv[2]each(not v;v:(sum a)>sum not a:"1"=read0`:03.in)'))

My solution for day 3 part 2 was considerably messier. Still mostly in q, I only really used Python here to move the do-over iteration outside of the function, rather than around it. I’m generally not a fan of code that has you frequently having to pair brackets and other opening & closing glyphs across large horizontal or vertical distances, so pulling out count[x[1;1]]{...}\(0;x) into {...} followed by .over(len(a[0]), (0, a)) was an improvement. Granted it relies on the reader understanding Python, q, and Pykdb, but I’m not writing this code for anyone but myself, and I understand all of those things quite well.

The gist of the solution is that I take 2 copies (a and b) of the same parsed input as before, "1"=read0`:03.in, and then I use a function {(x[0]+1;x[1] where $[sum[v]<sum not v;not;::] v:flip[x[1]]x[0])} to apply one iteration of the algorithm for the oxygen generator rating. This is turned into a do-over iterator by Pykdb by calling .over on it, and then passing in the number of iterations as the first arguments. The second argument is a tuple (which turns into a q list) containing the starting index, and the data. By the end it returns a list with a single boolean vector, so we index into that list at 0 to get it. For the C02 scrubber rating it’s basically the same, but with the not;:: flipped, and some extra logic to not end up removing all of the values from the list.

We then turn the 2 boolean vectors into integers as before, and take their product.

from pykdb import q


a = b = q('"1"=read0`:03.in')
c = len(a[0])

a = q('{(x[0]+1;x[1] where $[sum[v]<sum not v;not;::] v:flip[x[1]]x[0])}').over(c, (0, a))[1][0]
b = q('{(x[0]+1;$[0~count r:x[1] where $[sum[v]<sum not v;::;not] v:flip[x[1]]x[0];x[1];r])}').over(c, (0, b))[1][0]

print(q('prd sv[2]each', (a, b)))

Maybe I should’ve used Python for this one, but I’m not so sure that it would’ve been much cleaner.

Day 4 #

The problem for day 4 this year was a lot of fun. It’s been a very long time since I’ve played any Bingo, so I wasn’t sure about the rules. I assumed that there could be no duplicate numbers on a card, which fortunately worked out (at least for my input).

My approach involved parsing the input into a list of the draws that would occur, and each board as a list of sets. There would be a set for every row and column in a board.

Part 1 was simply a matter of iterating over the draws, and for each draw remove that number from each set until one of the sets was empty.

with open('04.in') as f:
    draws, *boards = f.read().strip().split('\n\n')

draws = [int(x) for x in draws.split(',')]
boards = [[[int(z) for z in y.split()] for y in x.split('\n')] for x in boards]
boards = [[set(y) for y in (*x, *zip(*x))] for x in boards]

done = False
for draw in draws:
    for board in boards:
        for line in board:
            line.discard(draw)
            if not line:
                done = True
        if done:
            print(draw * sum(set().union(*board[:5])))
            exit()

Part 2 was a quick and easy (and slightly dirty) change to just keep track of the boards that have already won, and then exit once every board had won. Once every board had won, the one stored in the board variable is the final winner. I take the sum of the elements of the first 5 sets as those are the sets that correspond to the rows, and I don’t want to double-count by also counting the columns. I only want the elements that were not drawn, but fortunately that’s already what in the sets!

with open('04.in') as f:
    draws, *boards = f.read().strip().split('\n\n')

draws = [int(x) for x in draws.split(',')]
boards = [[[int(z) for z in y.split()] for y in x.split('\n')] for x in boards]
boards = [[set(y) for y in (*x, *zip(*x))] for x in boards]

done = False
skips = set()
for draw in draws:
    for i, board in enumerate(boards):
        if i in skips:
            continue
        for line in board:
            line.discard(draw)
            if not line:
                done = True
        if done:
            skips.add(i)
            done = False
            if len(skips) == len(boards):
                print(draw * sum(set().union(*board[:5])))
                exit()

This solution came together very smoothly. For both part 1 and 2 I had a clear plan for how to solve it right after reading (skimming) the problem text, didn’t have to change that plan, didn’t run into any bugs, and submitted the correct answer on my first attempt. It’s rare for things to work out so well, and perhaps unrealistic to expect it, but it sure feels great when it does.

The only reason I didn’t place in the top 100 for day 5 was my slow and steady pace, which almost certainly is why my solution worked out so well. Trying to place in the top 100 is a bit stressful, because it generally leaves me rushing to implement a half-baked idea, and then submitting the first reasonable value by program spits out and hoping I don’t get held up for a minute due to some tiny error.

Day 5 #

Day 5 went fairly well. My part 1 performance suffered from a bit of over-engineering, but that extra work paid off for part 2. The problem description tells us:

For now, only consider horizontal and vertical lines

Which I read as “part 2 will be the same as part 1, but with diagonal lines included”. As a result, I wrote part 1 with diagonals in mind, and arrived at the following solution:

from collections import Counter
import re


with open('05.in') as f:
    d = [[int(y) for y in re.findall(r'\d+', x)] for x in f]

def cmp(a, b):
    return (a > b) - (a < b)

c = Counter()
for x1, y1, x2, y2 in d:
    if not (x1 == x2 or y1 == y2): # Remove this line...
        continue                   # and this line to get the solution for part 2
    dx = cmp(x2, x1)
    dy = cmp(y2, y1)
    while (x1, y1) != (x2, y2):
        c[(x1, y1)] += 1
        x1 += dx
        y1 += dy
    c[(x1, y1)] += 1

print(len([x for x in c.values() if x >= 2]))

The input is parsed into 4 integers for each line, representing the starting and ending (x, y) coordinates. For part one we skip over diagonal lines, but for part 2 we simply don’t - and that’s the only difference. We use the cmp function (which was removed in Python 3, so we implemented it ourselves) to get the change in the x/y coordinate per iteration. I was a bit worried that the diagonal lines might not always be at 45° angles, but I assumed they wouldn’t be since that would be a bit complicated for a day 5 problem. A Counter is then used to count the number of times a line passes over any given coordinate.

My big mistake tonight was in the last line. Originally it was print(len([x for x in c.values() if x == 2])). Note the == 2 instead of >= 2. This worked fine for the example given in the problem, where there were no cases of more than 2 lines overlapping, but it fails for any real input. Took me a good several minutes to spot that bug, but once I saw it it was obvious, and I was able to fix it and get stars for part 1 and 2 in quick succession.

Also, say hello to the re module! I’m sure we’ll be seeing it again many more times before Christmas.

Day 6 #

I began by writing a brute-force solution with q that might have worked for part 1, but definitely wouldn’t have worked for part 2. Fortunately the approach was bugging me enough that I didn’t stick with it, to the detriment of my part 1 performance, but the benefit of my part 2 performance. I figured part 2 would just be a test to see if the solution for part 1 was efficient enough, so after scrapping my partial q solution, I paused and thought the problem through. I came to a couple key realizations:

We don’t need to care about where any of the timers are “located” - indexes are irrelevant. The way the problem is presented (with the timers arranged as a list, and new ones being appended) is a bit misleading.
We don’t need to track whether a fish is new or not because they can all be treated the same. Just decrement each timers at each iteration, and for each timer that passes 0, replace it with a timer at 6 and a timer at 8. As such, any two timers that have the same value are equivalent, and so we only need to count how many timers with that value currently exist rather than tracking each .

With these realizations in mind I decided to use a collections.Counter. Here’s my solution for part 2, though my solution for part 1 is the same but with 80 instead of 256:

from collections import Counter


with open('06.in') as f:
    c = Counter(int(x) for x in f.read().split(','))

for _ in range(256):
    z = c.get(0, 0)
    for t in sorted(filter(bool, c)):
        c[t - 1] += c.pop(t)
    c += Counter({0: -z, 6: z, 8: z})

print(c.total())

Essentially we read the input into a counter, then update it 80 or 256 times as appropriate. The update step consists of getting the number of timers at 0, shifting all of the non-zero timers down, then adjusting how many are at 0, 6, and 8 using the value we stored earlier.

Stuff like this really makes me with Python didn’t have a division between expressions and statements. If a try-except statement could be an expression, then I could’ve used z = c.pop(0) to do the job of 2 lines of my current solution, and just set z = 0 when a KeyError occurs. Closest I can get without changing anything in the language would be:

def try_expr(success, failure, *exceptions):
    try:
        return success()
    except exceptions or Exception:
        return failure() if callable(failure) else failure

z = try_expr(lambda: c.pop(0), 0, KeyError)
for t in sorted(c):
    c[t - 1] += c.pop(t)
c += Counter({6: z, 8: z})

I’d definitely use something like this if it was built into the language, but having to implement it myself makes it a bit clunky. Maybe I should get around to publishing my Python toolkit so that I can start using it as a proper dependency, rather than it just being something I install into some virtual environments to help me workshop stuff.

Don’t get me wrong though - I’m a fan of Python’s try-except statements, and its exception model in general. For a highly dynamic language, it works well. It’s nowhere near as nice as the guarantees provided by languages with robust type systems like Haskell, but it’s well-suited for its use-cases. I just don’t like how it forces me to use at least 4 lines for what could reasonably be done with 1.

Day 7 #

Well that was… fast. A little surprising for such an easy problem to come in on the 7th day, though it isn’t unprecedented.

from statistics import median

with open('07.in') as f:
    v = [int(x) for x in f.readline().split(',')]

print(sum(x - int(median(v)) for x in v))

I had my solution for part 1 submitted as quickly as I could type the code for it (above) and copy-paste the answer into the submission box. Times like these I consider writing scripts to automatically download my input, and submit my answer. Probably not worth it. If I start treating Advent of Code that seriously I’d probably start to feel bad when I don’t get a good placement on the leaderboards.

Part 2 gave me a brief pause, before I realized I could just brute-force the fuel cost for every possible best alignment positions, and then take the minimum of that.

with open('07.in') as f:
    v = [int(x) for x in f.readline().split(',')]

def sum_of_nats(x):
    return x * (x + 1) // 2

print(min(sum(sum_of_nats(abs(x - i)) for x in v) for i in range(max(v))))

Just for fun, I also solved part 2 in k:

min 0+/+div[;2](x+1)*x:abs'(v-)'!max v:"J"$","\:*0::`:07.in

I’m sure it could be improved somewhat, but it’s still a neat display of how array programming is different. There are no manual loops in that k code, whereas the Python code has 3. In that k code all of the data is being processed as a list, one operation at a time, from right to left. On the right we read in the file as a list of char vectors, and at each step in-between we apply some other operator to the list, until at the very end we take the minimum, which is our answer.

While I’m at it, here part 1 in q:

sum abs v - med v:"J"$"," vs first read0`:07.in

I’d rather not use k for part 1 if only because it doesn’t have the med (median) function.

Day 8 #

Part 1 was 90% a matter of reading comprehension. My mind was all over the place thinking about how to do all sorts of things that weren’t strictly required for the task at hand. Once I had reigned it in, and realized how simple what it was asking for was, I had my solution very quickly. Unfortunately it took a good few minutes to get to that point, so my performance for part 1 didn’t help my position in the leaderboards.

with open('08.in') as f:
    v = [x.strip().split(' | ')[1] for x in f.readlines()]

print(sum(len(b) in {2, 3, 4, 7} for a in v for b in a.split(' ')))

Part 2 had me a bit confused for a little while. It’s definitely the most difficult problem of 2021 thus far. I figured I could probably figure out a bunch of logical constraints, and either implement them manually, or use a theorem prover, or add/subtract from sets of candidates. I didn’t write any code for part 2 until I realized that while O(n!) certainly sounds bad, in this case n is 7, and 7! is only 5040, so its really not that bad.

from itertools import permutations
import multiprocessing as mp


with open('08.in') as f:
    v = [[y.split() for y in x.strip().split(' | ')] for x in f.readlines()]

m = [set(x) for x in ('abcefg', 'cf', 'acdeg', 'acdfg', 'bcdf', 'abdfg', 'abdefg', 'acf', 'abcdefg', 'abcdfg')]

def f(a, b):
    for p in permutations('abcdefg'):
        z = dict(zip('abcdefg', p))
        g = lambda w: sum(y * 10 ** i for i, y in enumerate(reversed([m.index({z[s] for s in x}) for x in w])))
        try:
            g(a)
        except ValueError:
            continue
        return g(b)

with mp.Pool() as pool:
    print(sum(pool.starmap(f, v)))

For fun, after I had submitted my answer, I parallelized my solution. It was such an embarrassingly parallel workload that I couldn’t help myself. Without the multiprocessing it runs in ~1400 ms on my machine, and with the multiprocessing it runs in ~200 ms.

I overused single letter variable names today. Won’t be the last time I do that (for toy code such as AoC solutions - I use better variable names for most code I write). The solution works by trying out different mappings between the 7 letters until it finds one that works for every letter in the input part of the line (everything before the |). Then it applies that same mapping to the output (the part after | in the line), and converts the list of ints into a single int, which is the value for that line of the puzzle input. Do that for every line, and take the sum over the results, and like that we’ve got the answer.

Day 9 #

Day 9 was a return to the classics for Advent of Code. Part 1 was a simple grid search for nodes that obtained a simple rule:

import itertools as it

with open('09.in') as f:
    v = [[int(x) for x in y] for y in f.read().strip().splitlines()]

def risk_of_low_point(x, y):
    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        if 0 <= dx + x < len(v[0]) and 0 <= dy + y < len(v) and v[y + dy][x + dx] <= v[y][x]:
            return 0
    return 1 + v[y][x]

print(sum(risk_of_low_point(x, y) for x, y in it.product(range(len(v)), repeat=2)))

And then part 2 was a simple graph search. Because of the fact that when visiting a point it didn’t matter which point we were coming from, I was able to do a depth-first search with memoization (via functools.cache). With memoization we process 7459 nodes, whereas without it we would need to process 39596 nodes. Still totally doable without it, but not as elegant.

from collections import Counter
from functools import cache
import itertools as it
from math import prod


with open('09.in') as f:
    v = [[int(x) for x in y] for y in f.read().strip().splitlines()]

@cache
def sink(x, y):
    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        if 0 <= dx + x < len(v[0]) and 0 <= dy + y < len(v) and v[y][x] > v[y + dy][x + dx]:
            return sink(dx + x, dy + y)
    return (x, y)

c = Counter(sink(x, y) for x, y in it.product(range(len(v)), repeat=2) if v[y][x] != 9).most_common(3)
print(prod((v for k, v in c)))

The Counter class is once again showing up to assist, as is often the case.

Day 10 #

I don’t have much to say about day 10. It was a fun little stack problem. I was hoping to use some Python built-in to parse the lines and locate the unmatched bracket, but I couldn’t think of one quickly, and it probably would’ve been difficult to handle the scoring like that. Plus it’s not like the task is particularly difficult - doing it from scratch only takes a few lines of Python.

with open('10.in') as f:
    v = f.read().splitlines()

score = 0
for line in v:
    stack = []
    for x in line:
        if r := dict(('()', '[]', '{}', '<>')).get(x):
            stack.append(r)
        elif stack.pop() != x:
            score += {')': 3, ']': 57, '}': 1197, '>': 25137}[x]
            break

print(score)

Part 2 was easy to make once I had part 1 working. I just had to move the scoring from right before the break to an else-block following the inner for-loop. In Python an else-block following a for-loop will be executed if and only if the iterator the for-loop is iterating over is exhausted.

from functools import reduce
from statistics import median


with open('10.in') as f:
    v = f.read().splitlines()


scores = []
for line in v:
    stack = []
    for x in line:
        if r := dict(('()', '[]', '{}', '<>')).get(x):
            stack.append(r)
        elif stack.pop() != x:
            break
    else:
        scores.append(reduce(lambda x, y: x * 5 + ' )]}>'.index(y), reversed(stack), 0))

print(median(scores))

It’s annoying that Python moved reduce from the builtins into functools. As anyone familiar with functional programming can attest to, it’s very useful. It generally works well for any situation in which you want to turn a list into a single value by applying the same operation between each element of the list. If I wanted to write that reduction in k using Pykdb it would be:

scores.append(q('k){0{?[`$/:" )]}>";y]+x*5}/|x}', stack))

If the reduction had more complex behaviour that we wanted to encode in Python, then we could pass in a function like this:

scores.append(q('k){0{x[z]+y*5}[y]/|x}', stack, lambda x: ' )]}>'.index(str(x))))

It would be nice if we could do something like this:

scores.append(q('k){0{x[z]+y*5}[y]/|x}', stack, ' )]}>'.index))

But str.index only works on strings, and pykdb.k.SymbolAtom is not a subclass of str (yet). Also, the inspect module cannot extract the function signature from str.index, which Pykdb currently relies on for passing Python functions into q/k. Hopefully that requirement can be alleviated in the not too distant future.

Day 11 #

For part 1 I made the grid into a Numpy array for convenience. Now I can index with tuples, and increment all of the cells at once. I wasted a bit of time trying to make a few other parts vectorized, before realizing that my approach relied on the grid values changing as I iterated over the coordinates.

Particularly attentive readers might notice that there is a bug in the code I’m using to iterate over adjacent coordinates.

import itertools as it

import numpy as np


with open('11.in') as f:
    g = np.array([[int(x) for x in y] for y in f.read().splitlines()])


def flash(y, x):
    flash.count += 1
    g[y, x] = -1
    for a, b in ((y + dy, x + dx) for dy, dx in it.product((-1, 0, 1), repeat=2)):
        if 0 <= a < len(g) and 0 <= b < len(g) and -1 != g[a, b]:
            g[a, b] += 1
            if g[a, b] >= 10:
                flash(a, b)

flash.count = 0

f = lambda x: (c for c in it.product(range(len(g)), repeat=2) if x == g[c])

for _ in range(100):
    g += 1
    for y, x in f(10):
        flash(y, x)
    for y, x in f(-1):
        g[y, x] = 0

print(flash.count)

((y + dy, x + dx) for dy, dx in it.product((-1, 0, 1), repeat=2))

This generator yields (0, 0) as one of its elements. Fortunately I can ignore this because we’ve already marked that cell as visited by setting it to -1.

For part 2 it was simple to change for _ in range(100) into for i in it.count(1), and then break and print i when every cell is marked as visited. Unfortunately I initially had an off-by-one error as I wrote for i in it.count().

import itertools as it

import numpy as np


with open('11.in') as f:
    g = np.array([[int(x) for x in y] for y in f.read().splitlines()])


def flash(y, x):
    g[y, x] = -1
    for a, b in ((y + dy, x + dx) for dy, dx in it.product((-1, 0, 1), repeat=2)):
        if 0 <= a < len(g) and 0 <= b < len(g) and -1 != g[a, b]:
            g[a, b] += 1
            if g[a, b] >= 10:
                flash(a, b)

f = lambda x: (c for c in it.product(range(len(g)), repeat=2) if x == g[c])

for i in it.count(1):
    g += 1
    for y, x in f(10):
        flash(y, x)
    if np.all(-1 == g):
        break
    for y, x in f(-1):
        g[y, x] = 0

print(i)

Day 12 #

I love these sorts of maze/graph problems. This time I represented the graph as a dictionary that mapped each node to a set of the nodes it connects to. Not a robust solution, but suitable for this one-off usage.

from collections import defaultdict


with open('12.in') as f:
    lines = [x.split('-') for x in f.read().splitlines()]

m = defaultdict(set)
for a, b in lines:
    m[a].add(b)
    m[b].add(a)

def explore(x, visited: list):
    visited.append(x)
    if x == 'end':
        yield visited
    for path in m[x]:
        if path != 'start' and (path not in visited or path.isupper()):
            yield from explore(path, visited.copy())

print(len(list(explore('start', []))))

I mistakenly thought the order of the nodes that are visited would be important, so I implemented the explore function as a recursive generator that would yield explored paths.

For part 2 I removed the unnecessary complexity, and instead simply counted the possible paths recursively. A flag was added to keep track of whether a small cave had been visited twice yet (or as I named it in the code, recycled):

from collections import defaultdict


with open('12.in') as f:
    lines = [x.split('-') for x in f.read().splitlines()]

m = defaultdict(set)
for a, b in lines:
    m[a].add(b)
    m[b].add(a)

def explore(x, visited: set, recycled_small: bool):
    if x == 'end':
        return 1
    c = 0
    for path in m[x]:
        if path == 'start':
            continue
        elif path.isupper() or path == 'end':
            c += explore(path, visited, recycled_small)
        elif path in visited and not recycled_small:
            c += explore(path, visited, True)
        elif path not in visited:
            c += explore(path, {path} | visited, recycled_small)
    return c

print(explore('start', set(), False))

Day 13 #

This was a fun problem. The challenge of part 1 came from implementing the fold function, which was originally a clunky mess, but I cleaned it up into a neat one-liner. It uses boolean values as an index to choose between two options several times.

with open('13.in') as f:
    points, instructions = (x.split('\n') for x in f.read().split('\n\n'))
    points = [tuple(int(b) for b in a.split(',')) for a in points]
    instructions = [x.split()[-1].split('=') for x in instructions]
    instructions = [(a, int(n)) for a, n in instructions]


def fold(axis, x, points) -> set:
    return {((p[not axis], x - (p[axis] - x))[::(-1, 1)[axis]], p)[p[axis] < x] for p in points}


print(len(fold(instructions[0][0] == 'y', instructions[0][1], points)))

Part 2 followed quickly from my solution to part 1, as it was just asking for the fold function to be applied to its results over the instructions, which is a textbook use-case for a fold, which is provided in Python as functools.reduce.

from functools import reduce


with open('13.in') as f:
    points, instructions = (x.split('\n') for x in f.read().split('\n\n'))
    points = [tuple(int(b) for b in a.split(',')) for a in points]
    instructions = [x.split()[-1].split('=') for x in instructions]
    instructions = [(a, int(n)) for a, n in instructions]


def fold(axis, x, points) -> set:
    return {((p[not axis], x - (p[axis] - x))[::(-1, 1)[axis]], p)[p[axis] < x] for p in points}


def generate_code(points) -> str:
    code = []
    for y in range(6):
        for x in range(45):
            code.append(' █'[(x, y) in points])
        code.append('\n')
    return ''.join(code[:-1])


points = reduce(lambda acc, z: fold(z[0] == 'y', z[1], acc), instructions, points)
print(generate_code(points))

Printing the code in a readable way was just a matter of looping over two large enough ranges (originally I just guessed how big they should be), and building a list of characters to print. I used @ at first, but █ is much more legible.

Day 14 #

As soon as I had read the question it was obvious that part 2 would ask for additional iterations, yet after struggling for a minute to think of an efficient way to solve this I decided I should hurry up and get my first star of the night with a naive approach. Unlike all previous years I was taking the competition somewhat seriously this year. So I arrived at this straightforward solution for part 1:

from collections import Counter
import itertools as it


with open('14.in') as f:
    polymer, rules = f.read().split('\n\n')
    polymer = list(polymer)
    rules = dict((x.split(' -> ') for x in rules.split('\n')))

for _ in range(10):
    i = 1
    for a, b in it.pairwise(polymer.copy()):
        if a + b in rules:
            polymer.insert(i, rules[a + b])
            i += 1
        i += 1

c = Counter(polymer)
print(c.most_common()[0][1] - c.most_common()[-1][1])

As expected, part 2 asked for 40 iterations. Some napkin math tells us that that’s way beyond what can be brute forced, so a more clever approach was required. Fortunately I was mulling the problem over while I wrote my solution to part 1, and was able to put together this efficient solution fairly quickly afterwards:

from collections import Counter


with open('14.in') as f:
    polymer, rules = f.read().split('\n\n')
    polymer = list(polymer)
    rules = dict((x.split(' -> ') for x in rules.split('\n')))

first = polymer[0]
polymer = Counter(polymer[i] + polymer[i + 1] for i in range(len(polymer) - 1))

for _ in range(40):
    c = polymer
    polymer = Counter()
    for a, b in c:
        polymer[a + rules[a + b]] += c[a + b]
        polymer[rules[a + b] + b] += c[a + b]

c = Counter()
c[first] = 1
for x, n in polymer.items():
    c[x[1]] += n

print(c.most_common()[0][1] - c.most_common()[-1][1])

Day 15 #

NetworkX to the rescue!

For those who don’t know, NetworkX is a popular and powerful Python graph (as in graph theory) library, among other things. I began by trying to remember how to implement Dijkstra’s algorithm as I was typing away, but caught myself when I was looking up the algorithm. Why try to re-implement Dijkstra’s algorithm over own graph representation to find the shortest path when I could just use the defacto standard? And so I wrote this for part 1:

import itertools as it

import networkx as nx


with open('15.in') as f:
    grid = [[int(x) for x in y] for y in f.read().splitlines()]

n = len(grid)

g = nx.DiGraph()
for x, y in it.product(range(n), repeat=2):
    for a, b in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        if 0 <= x + a < n and 0 <= y + b < n:
            g.add_edge((x, y), (x + a, y + b), weight=grid[y + b][x + a])

path = nx.shortest_path(g, (0, 0), (n - 1,) * 2, weight="weight")
print(sum(grid[y][x] for x, y in path[1:]))

Most of the work is just going from a list of lists of ints to the graph representation, but there’s nothing special going on there. Once I had the graph constructed, the shortest path was easily obtained, and then I just had to take the sum of the weights along the path, save for the weight of the starting position.

Part 2 was just a matter of enlarging the grid as directed, and then doing what was done for part 1. I used a dictionary to represent the larger grid, but in hindsight, seeing as the grid was a known size, I probably should’ve used a Numpy array. Dictionaries are more appropriate for infinite grids - but no matter, it works fine:

import itertools as it

import networkx as nx


with open('15.in') as f:
    grid = [[int(x) for x in y] for y in f.read().splitlines()]

n = len(grid)

dgrid = {}
for x, y in it.product(range(n * 5), repeat=2):
    dgrid[x, y] = (grid[y % n][x % n] + (x // n) + (y // n))
    if dgrid[x, y] > 9:
        dgrid[x, y] -= 9

g = nx.DiGraph()
for x, y in dgrid:
    for a, b in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        if (x + a, y + b) in dgrid:
            g.add_edge((x, y), (x + a, y + b), weight=dgrid[(x + a, y + b)])

path = nx.shortest_path(g, (0, 0), (n * 5 - 1,) * 2, weight="weight")
print(sum(dgrid[x, y] for x, y in path[1:]))

Day 16 #

Buoyancy Interchange Transmission System, eh? I’m expecting/hoping that this format comes back at least a couple times this year. Otherwise why did I put all this work into implementing this somewhat sprawling schema with a pretty poor parser?

import itertools as it


with open('16.in') as f:
    data = bin(int(f.read(), 16))[2:]
    data = ('0' * (len(data) % 4)) + data


def taketo(predicate, iterable):
    '''Like `itertools.takewhile`, but yields the first element that fails the predicate.'''
    for x in iterable:
        yield x
        if not predicate(x):
            break


def parse(data):
    data = iter(data)
    read = lambda n: ''.join(it.islice(data, n))
    yield int(read(3), 2)
    packet_type = int(read(3), 2)
    if packet_type == 4:
        return int(''.join(y for _, *x in taketo(lambda x: x[0] == '1', zip(*[data]*5)) for y in x), 2)
    if read(1) == '0':
        subpackets = iter(''.join(read(int(read(15), 2))))
        while subpackets.__length_hint__():
            yield from parse(subpackets)
    else:
        for _ in range(int(read(11), 2)):
            yield from parse(data)


print(sum(parse(data)))

My solution is pretty hacky. To advance the data it’s kept as an iterator instead of as a string. This allows us to pass the itertor into a recursive call to parse subpackets, and have those variable length subpackets removed from the caller’s data.

We need to know what length of the data is sometimes, so a little-known method is used: __length_hint__. Documented in PEP 424, this method of some iterators only exists for performance reasons, but for str iterators in particular, it can be used to get the exact remaining length of the string being iterated over without exhausting the iterator. Please do not use this trick in production.

The parse function is implemented as a generator for the version numbers, for no other reason than convenience. Now I need only call sum on the “parsed” data. Obviously this particular hack is amended for part 2.

The following line is interesting, and warrants some explanation:

(y for _, *x in taketo(lambda x: x[0] == '1', zip(*[data]*5)) for y in x)

zip(*[data]*5) provides an iterator over data that advances 5 at a time without exhausting the iterator completely if I break early. The taketo call does just that - breaking when the first bit of the segment of the literal is '0'. Then for _, *x in ... is used to discard the first bit of each segment of the literal, leaving me with tuples of 4 bits. This generator yields y, which is obtained by the inner loop for y in x. This serves to flatten the output.

Next time someone says that Python’s syntax is simple, feel free to show them this. Or show them Python’s (well-documented) grammar.

For part 2 I use Python’s new match-case statement:

import itertools as it
from math import prod


with open('16.in') as f:
    data = bin(int(f.read(), 16))[2:]
    data = ('0' * (len(data) % 4)) + data


def taketo(predicate, iterable):
    '''Like `itertools.takewhile`, but yields the first element that fails the predicate.'''
    for x in iterable:
        yield x
        if not predicate(x):
            break


def parse(data):
    data = iter(data)
    read = lambda n: ''.join(it.islice(data, n))
    read(3) # discard version
    packet_type = int(read(3), 2)
    if packet_type == 4:
        return int(''.join(y for _, *x in taketo(lambda x: x[0] == '1', zip(*[data]*5)) for y in x), 2)
    if read(1) == '0':
        subpackets = iter(''.join(read(int(read(15), 2))))
        parsed = [parse(subpackets) for _ in it.takewhile(lambda _: subpackets.__length_hint__(), it.count())]
    else:
        parsed = [parse(data) for _ in range(int(read(11), 2))]
    match packet_type:
        case 0: return sum(parsed)
        case 1: return prod(parsed)
        case 2: return min(parsed)
        case 3: return max(parsed)
        case 5: return parsed[0] > parsed[1]
        case 6: return parsed[0] < parsed[1]
        case 7: return parsed[0] == parsed[1]

print(parse(data))

Might’ve gone overboard with itertools here, but it’s fun, and that’s one of the main reasons I participate in Advent of Code.

Day 17 #

Yet another brute force solution. I’m sure there’s a better way to solve this, but this is low-effort, and both part 1 and part 2 run in under a second on my computer, thanks in large part to the use of multiprocessing to parallelize the work. I don’t like how I just guessed at what an appropriate range for x, range for y, and the number of iterations were - but not enough to write a better solution at this time.

Part 1:

import itertools as it
import multiprocessing as mp
import re


with open('17.in') as f:
    xa, xb, ya, yb = (int(x) for x in re.findall(r'[-]?\d+', f.read()))

def shoot(dx, dy):
    x = y = max_y = 0
    for _ in range(250):
        x += dx
        y += dy
        max_y = max(max_y, y)
        dx -= dx > 0
        dx += dx < 0
        dy -= 1
        if xa <= x <= xb and ya <= y <= yb:
            return max_y
    return 0

with mp.Pool() as pool:
    print(max(pool.starmap(shoot, it.product(range(300), range(-300, 300)))))

Part 2:

import itertools as it
import multiprocessing as mp
import re


with open('17.in') as f:
    xa, xb, ya, yb = (int(x) for x in re.findall(r'[-]?\d+', f.read()))

def shoot(dx, dy):
    x = y = 0
    for _ in range(250):
        x += dx
        y += dy
        dx -= dx > 0
        dx += dx < 0
        dy -= 1
        if xa <= x <= xb and ya <= y <= yb:
            return True
    return False

with mp.Pool() as pool:
    print(sum(pool.starmap(shoot, it.product(range(300), range(-300, 300)))))

Day 18 #

Today was doubtlessly one of the best Advent of Code problems of this year. What a neat challenge - defining a new discrete compound number system, and then having us implement a strange binary operation over it (addition), and a somewhat less strange unary operation over it (magnitude). Both were a joy to implement.

Parsing the input was made easy by the fact that each line was a valid Python expression, so I was able to use literal_eval to turn it into Python lists of lists and ints.

I decided against using a tree-based representation for the numbers because I figured that would make some things unnecessarily difficult, such as finding the leftmost/rightmost int. Instead a used a comparatively flat representation (generated by the flatten function), which was a list of tuples, each containing an int (i.e. a “regular number” as the question puts it), and its depth in the tree.

Here’s my solution for parts 1 and 2 together, since the bulk of the code is identical between them:

from ast import literal_eval
import itertools as it
from functools import reduce
from typing import List, Optional, Tuple


with open('18.in') as f:
    v = [literal_eval(x) for x in f.read().splitlines()]

SnailfishNumTree = int | List['SnailfishNumTree']
SnailfishNum = List[Tuple[int, int]]

def next_idx(n: SnailfishNum, cond) -> Optional[int]:
    try:
        return next(x for x in range(len(n)) if cond(n[x]))
    except StopIteration:
        return None

def explode(n: SnailfishNum) -> Tuple[SnailfishNum, bool]:
    if (i := next_idx(n, lambda x: x[1] == 4)) is not None:
        if i > 0:           n[i-1] = (n[i-1][0] + n[i][0], n[i-1][1])
        if i + 2 < len(n):  n[i+2] = (n[i+2][0] + n[i+1][0], n[i+2][1])
        return [*n[:i], (0, 3), *([n[i+1]] if i+1 >= len(n) else []), *n[i+2:]], True
    return n, False

def split(n: SnailfishNum) -> Tuple[SnailfishNum, bool]:
    if (i := next_idx(n, lambda x: x[0] >= 10)) is not None:
        return [
            *n[:i],
            (n[i][0] // 2, n[i][1] + 1),
            (-(-n[i][0] // 2), n[i][1] + 1),
            *n[i+1:],
        ], False
    return n, True

def add(a, b):
    n = [(x, depth + 1) for x, depth in (*a, *b)]
    done = False
    while not done:
        n, exploded = explode(n)
        if exploded: continue
        n, done = split(n)
    return n

def magnitude(n: SnailfishNum) -> int:
    for depth in range(max(x for _, x in n), -1, -1):
        while (i := next_idx(n, lambda x: x[1] == depth)) is not None:
            n = [*n[:i], (3 * n[i][0] + 2 * n[i + 1][0], n[i][1] - 1), *n[i+2:]]
    return n[0][0]

def flatten(n: SnailfishNumTree, depth=0):
    for x in n:
        try:
            yield from flatten(x, depth + 1)
        except TypeError:
            yield x, depth

# Part 1:
print(magnitude(reduce(add, [flatten(x) for x in v])))

# Part 2:
pairs = list(it.combinations((list(flatten(x)) for x in v), 2))
print(max(magnitude(add(a, b)) for a, b in (*pairs, *((y, x) for x, y in pairs))))

(-(-n[i][0] // 2) is a neat little trick to take the ceiling of n[i][0] without importing the math module. Not that I would recommend using such a trick for anything other than toy problems like this.

For the most part I’m very satisfied with how this solution turned out, but there are a few bits that bug me. Most of the add function is kinda gross, for instance. I also wish flatten would return a list instead of being a generator. All of these sorts of issues can be easily addressed of course, but not without adding more code, and I’m a proponent of reducing the amount of code used when reasonable.

You’d think that’d be the norm, and yet most code that I look at (that isn’t written by the people I work with who, like me, write lean code) is bloated. Often functions are written such that they can fill a whole pane in my text editor, when they could have identical behaviour and still be perfectly readable if they were written to just be a few lines long or less.

Day 19 #

Another day where part 1 is almost all of the work. Likely the most difficult Advent of Code problem of the year.

For brevity, since part 1 and 2 are so similar, what follows is a modified copy of my solution for part 2 that also prints the answer for part 1:

from collections import deque
import itertools as it


def distances(beacons):
    return [
        sorted(
            sum((a - b) ** 2 for a, b in zip(beacons[i], beacons[j]))
            for j in (x for x in range(len(beacons)) if i != x)
        ) for i in range(len(beacons))
    ]


def align(b1, b2):
    if not (common := {i: j for (i, a), (j, b) in it.product(enumerate(distances(b1)), enumerate(distances(b2)))
                            if sum(a[x] == b[x] for x in range(12)) >= 2}):
        return False
    z = {axis: (m.pop(), flip, rotation) for axis, flip, rotation in it.product(range(3), (1, -1), (0, 1, 2)) if 1 == len(m := {a[axis] - flip * b[rotation] for a, b in ((b1[k], b2[v]) for k, v in common.items())})}
    return list(zip(*z.values()))[0], [[a + b * beacon[c] for a, b, c in z.values()] for beacon in b2]


with open('19.in') as f:
    unaligned = deque([[[int(z) for z in y.split(',')] for y in x.split('\n')[1:]] for x in f.read().split('\n\n')])

aligned = [((0, 0, 0), unaligned.popleft())]
while unaligned and (b2 := unaligned.popleft()):
    try:
        aligned.append(next((r[0], r[1]) for _, b1 in aligned if (r := align(b1, b2))[1]))
    except StopIteration:
        unaligned.append(b2)

# Part 1
print(len({tuple(x) for _, b in aligned for x in b}))

# Part 2
print(max(sum(abs(a - b) for a, b, in zip(p1, p2)) for (p1, _), (p2, _) in it.combinations(aligned, 2)))

The align function takes 2 lists of beacon positions, and returns either the second list of beacons adjusted to use the same coordinate basis as the first list of beacons, or False if it was unable to align them.

We start by choosing the first scanner’s basis as the one we’re going to align all of the others to. This choice is arbitrary. Then we loop over the unaligned lists of beacons and attempt alignment against every aligned list of beacons until we either manage to align it, or run out of aligned lists of beacons to align against.

By the end of this process, given a valid input, every scanner will be represented in the aligned list. For part 2 we also keep track of the positions of the scanners relative to the first scanner in the aligned list. With that info derived, getting the solution for part 1 and 2 is easy.

I golfed the align function a bit. I debated making it a one-liner, which would not be difficult thanks to in-line assignment, but that’s taking it a bit too far, even for me.

Day 20 #

After the recent challenges, day 20 was a refreshing change of pace. Just a simple “evolve a state in an infinite discrete space with a few rules” problem - classic Advent of Code material.

The catch today was that, for my puzzle input at least, all cells beyond the ones I was immediately working with flipped their state at each step. Obviously I can’t store them in the defaultdict that represents the grid, but since this special case only applies for cells that are outside of what the defaultdict covers, all I had to do was initialize each new defaultdict (for the next state) with either lambda: True or lambda: False depending on whether the void beyond what I had already operated on was light or dark on that step.

Here’s my solution for part 2. The only change for part 1 is to evolve the state 2 times instead of 50 times.

from collections import defaultdict
import itertools as it


with open('20.in') as f:
    a, b = f.read().split('\n\n')

enhancements = [x == '#' for x in a]
b = b.split()
d = defaultdict(bool)
d.update({(x, y): b[y][x] == '#' for y in range(len(b)) for x in range(len(b[0]))})

def r(d, i):
    v = [e[i] for e in d]
    return range(min(v) - 1, max(v) + 2)

def step(d, void):
    nd = defaultdict(lambda: void)
    for x, y in it.product(r(d, 0), r(d, 1)):
        q = [d[x + b, y + a] for a, b in it.product((-1, 0, 1), repeat=2)]
        nd[x, y] = enhancements[sum(v << i for i, v in enumerate(reversed(q)))]
    return nd, not void

void = enhancements[0]
for _ in range(50):
    d, void = step(d, void)
print(sum(d.values()))

Day 21 #

Today was a rare case where my solutions for part 1 and part 2 have next to nothing to do with each other, unfortunately.

For part 1 I simply apply the rules of the game in an infinite loop until a player’s score reaches 1000. I used 0 and 1 for the players instead of 1 and 2 for ease of indexing. Like this, I can index into players with p to get the currently active player, and not p to get the other player.

import itertools as it


with open('21.in') as f:
    a, b = (int(x[-2:]) for x in f.read().splitlines())

players = [[a, 0], [b, 0]]
rolls = 0
die = 1
for p in it.cycle((0, 1)):
    rolls += 3
    players[p][0] += 3 + 3 * die
    while players[p][0] > 10: players[p][0] -= 10
    players[p][1] += players[p][0]
    if players[p][1] >= 1000:
        break
    die = 3 + die % 100

print(rolls * players[not p][1])

Part 1 wasn’t very interesting, but part 2 was quite a lot of fun. I used a dynamic programming approach with a cache. The cache works because each game, uniquely identified by the players positions and scores, results in the same number of wins.

The number of wins in the recursive case is a reduction over all of the dice rolls, where we add the number of wins from each recursive call to the total. The tuple(map(sum, zip(w, ... part just adds the tuples returned by the recursive call. The number of wins is tracked by w, which is the accumulator variable for the reduction.

import itertools as it
from functools import cache, reduce


with open('21.in') as f:
    a, b = (int(x[-2:]) for x in f.read().splitlines())


@cache
def f(pa, pb, sa, sb):
    if sa >= 21: return (0, 1)
    if sb >= 21: return (1, 0)
    return reduce(
        lambda w, r: tuple(map(sum, zip(w, reversed(f(pb, (x:=(pa + r) % 10), sb, 1 + sa + x))))),
        (sum(x) for x in it.product(range(1, 4), repeat=3)),
        (0, 0)
    )

print(max(f(a - 1, b - 1, 0, 0)))

Trying to get the recursive case all into a single Python expression was challenging. Two key tricks used where subtracting one from the initial positions, as made the position/score math easier later, and swapping pa with pb and sa with sb on each recursion.

The swapping saves me from having to have a parameter that tracks which player is active, which is how I originally solved it. With that approach I had a nearly identical few lines of code for the recursive step for each player, with a different pair of parameters being modified. The swapping is also why I chose the names pa, pb, sa, and sb, instead of p1, p2, s1, and s2. I was worried I might confuse myself since in the first part the players corresponded to an index, but that worry was unfounded as here we never actually know which player is which - only that the current “player A” is what the recursion above (and below) thinks is “player B”. It’s fortunate that both players have identical rules, such that we can safely disregard which is which.

To account for the recursive call having a flipped perspective as to who is who, we reverse the tuple it returns before performing the addition.

Day 22 #

I thought that the remaining days wouldn’t be all that difficult, but day 22 was rough. Took me a little over 2.5 hours to complete it, so I was up pretty late (as the problems come out at midnight for me).

Part 1 was easy, but it was obvious what part 2 would be since part 1 instructed us to essentially ignore most of the puzzle input. I decided to go ahead and pick up the first start with a naive solution:

import itertools as it
import re


with open('22.in') as f:
    lines = f.read().splitlines()

v = [[int(y) for y in re.findall(r'-?\d+', x)] for x in lines]
w = [x[:2] == 'on' for x in lines]

ranges = [
    (range(xa, xb + 1), range(ya, yb + 1), range(za, zb + 1))
    for xa, xb, ya, yb, za, zb in v
    if all(abs(e) <= 50 for e in (xa, xb, ya, yb, za, zb))
]

print(sum({p: state for r, state in zip(ranges, w) for p in it.product(*r)}.values()))

A more space-efficient solution could’ve been had by using a set to track the points instead of a dict, since the dict keys that are coordinates that are turned off are useless. That said, using a dict lets me easily using just a single line for it, which is nice. The lines are processed in-order, so subsequent entries for any key (e.g. turning a point off) overwrites the previous state.

I originally started part 2 by trying to detect cuboid intersections, and then breaking the stored cuboids into multiple subcuboids that don’t intersect. Like that, these subcuboids would not be counted twice, and could be turned off without affecting anything else. Unfortunately I struggled to implement this for a good long while. Eventually I took a break to clear my head. When I came back I decided to try a new solution that I wasn’t entirely sure would work.

Instead of breaking cuboids into subcuboids, I used a collections.Counter to track whether a cuboid was on (+1) or off (-1). Overlapping regions are handled by the nested for-loop that loops over the previous cuboids. Intersections (assigned to x) are calculated, and checked if they are valid (i.e. if it’s actually an intersection). Then we subtract out whatever the value for the old cuboid that the new cuboid intersects with. Once all of the old cuboids have been checked for intersections, any overlapping regions will have been cancelled out.

from collections import Counter, namedtuple
import re


with open('22.in') as f:
    lines = f.read().splitlines()

v = [[int(y) for y in re.findall(r'-?\d+', x)] for x in lines]
w = [x[:2] == 'on' for x in lines]
Cuboid = namedtuple('Cuboid', ('xa', 'xb', 'ya', 'yb', 'za', 'zb'))

def intersect(a: Cuboid, b: Cuboid) -> Cuboid:
    return Cuboid(
        a.xa if a.xa > b.xa else b.xa,
        a.xb if a.xb < b.xb else b.xb,
        a.ya if a.ya > b.ya else b.ya,
        a.yb if a.yb < b.yb else b.yb,
        a.za if a.za > b.za else b.za,
        a.zb if a.zb < b.zb else b.zb,
    )

cubes = Counter()
for ca, on in ((Cuboid(*c), on) for on, c in zip(w, v)):
    prev = cubes.copy()
    cubes[ca] += on
    for cb, s in prev.items():
        if (x := intersect(ca, cb)) and not (x.xa > x.xb or x.ya > x.yb or x.za > x.zb):
            cubes[x] -= s
print(sum(s * (c.xb - c.xa + 1) * (c.yb - c.ya + 1) * (c.zb - c.za + 1) for c, s in cubes.items()))

Day 23 #

Well that was… different. I have no code to show for day 23, as I didn’t use any. I just moved amphipods around manually as best I could, copying the whole state when I wasn’t sure which move was best, and added up the cost of the moves as I went. I ran into a few annoying off by 1 (or 10/100/1000) errors, but it would’ve surely taken longer to write code to solve this problem.

For many other problems I’d still be at least tempted to write code to solve it after getting the stars for today, but this problem doesn’t seem like it would be much fun to write a solution for. Not awful by any means, but not appealing enough to nerd-snipe me into doing it after I’ve already obtained the stars.

After all, I’m currently on my first real break from work and school in over 5 years. I’ll take the time saved to relax a bit.

Day 24 #

Another no-code day… kinda. Right off the start I wrote some code that could evaluate the input program:

import itertools as it
import multiprocessing as mp


with open('24.in') as f:
    v = [x.split() for x in f.read().splitlines()]

def alu(inputs):
    inputs = iter(inputs)
    state = {x: 0 for x in 'wxyz'}
    def get(x):
        try:
            return int(x)
        except ValueError:
            return state[x]
    ops = {
        'inp': lambda x: state.__setitem__(x, next(inputs)),
        'add': lambda x, y: state.__setitem__(x, get(x) + get(y)),
        'mul': lambda x, y: state.__setitem__(x, get(x) * get(y)),
        'div': lambda x, y: state.__setitem__(x, get(x) // get(y)),
        'mod': lambda x, y: state.__setitem__(x, get(x) % get(y)),
        'eql': lambda x, y: state.__setitem__(x, get(x) == get(y)),
    }
    for op, *args in v:
        ops[op](*args)
    return state

def target(inp):
    if not alu(inp)['z']:
        return int(''.join(str(x) for x in inp))
    return None

with mp.Pool() as pool:
    for r in pool.imap_unordered(target, it.product(range(9, 0, -1), repeat=14)):
        if r is not None:
            print(r)

Nothing too weird there. Just a little program that takes its input as an iterable (non-interactively, unlike the generator I wrote to run INTCODE programs), stores its registers in a dictionary, and uses a dictionary of functions. Maybe I should’ve used a match-case statement now that Python 3.10 is out, but that’s unimportant, since this program is practically useless.

After all - and I realized this early on, but continued for no real reason other than “fun” - testing every 14 digit number (sans zeros) would take way too long. In a more performant language on modern hardware, this approach could be used. That is to say it would certainly finish long before the heat death of the universe, and maybe even within a day, but it would still be terribly slow.

One cheeky optimization that could be employeed to speed this approach up would be to (ab)use AoC’s wrong-answer feedback. If your answer is significantly higher or lower than the expected numeric answer, then it will tell you that the correct answer is lower/higher than yours. Using that you can binary-search the answer space to rapidly rule out large swaths of candidate values, even with the wrong-answer rate-limiting. Then, once you’ve narrowed down the number of candidates by a few orders of magnitude, you can have a program like the one above check for the largest (and later the smallest) valid value.

I had not thought of the above optimization in-the-moment however, and even if I had, I’m not sure I would’ve used it. Instead I took a short break, then dove into the assembly-like puzzle input to figure out what it was doing. Fortunately it wasn’t too complicated. It consisted of 14 mostly-repeated segments which each took in a new input value, and then performed the same operations to it with differing constants.

I manually stepped through the program, keeping track of which values influence which others symbolically. I then set the final z value to 0, and worked backwards from there to find a system of equations for the input values. This system of equations were the rules which determined if a given input was valid or not. From there it was fairly easy to figure out what the largest (and later the smallest) valid values were.

This was certainly an unconventional Advent of Code puzzle, and while it’s far from my favourite, it gets points for novelty.

Day 25 #

A nice and easy puzzle to finish Advent of Code 2021. I appreciate being able to get to sleep at a decent time on Christmas morning. A key realization I had while solving this (thanks to actually reading the problem before getting started) was that we need to operate the east moving sea cucumbers before operating on the south moving ones. That made me think they ought to be stored separately.

We also have no need to store the empty spaces, so I used a set to store each herd instead of lists of lists. I could’ve also used a dictionary that maps from coordinates to their states (i.e. whether it has an east-moving sea cucumber, or a south-moving sea cucumber), but using multiple sets seems more simple. If there were more herds/types of sea cucumbers to consider, a list of sets might’ve been appropriate instead.

It would have been neat if the puzzle input was a list of points for each herd, and the grid they existed in was massive and sparse. A bit of extra challenge, although that would probably best be saved for another night.

import itertools as it

with open('25.in') as f:
    board = f.read().splitlines()

w, h = len(board[0]), len(board)
east = {(x, y) for x, y in it.product(range(w), range(h)) if board[y][x] == '>'}
south = {(x, y) for x, y in it.product(range(w), range(h)) if board[y][x] == 'v'}

def step(east, south):
    cucumbers = east | south
    east = {(x, y) if (p := ((x + 1) % w, y)) in cucumbers else p for x, y in east}
    cucumbers = east | south
    south = {(x, y) if (p := (x, (y + 1) % h)) in cucumbers else p for x, y in south}
    return east, south

for i in it.count(start=1):
    new_east, new_south = step(east, south)
    if new_east == east and new_south == south:
        print(i)
        break
    east, south = new_east, new_south

Originally I had the following code in the step function:

{(x, y) if (p := ((x + 1) % w, y)) in east | south else p for x, y in herd}

But that was extremely slow - it would take multiple minutes on my current hardware to obtain an answer for the full-sized input. The culprit is computing the union east | south within the set comprehension. This causes it to be recomputed for every point. Precomputing it and storing it as the variable cucumbers is a tad clunky, but with how slow the cleaner approach is, and with how much faster precomputing is, it cannot be forgone.

Closing Thoughts #

I began this year’s Advent of Code thinking I’d take it easy, do every problem when I had free time and felt like it. I also thought that I would use Pykdb for many problems. I was wrong on both counts.

On the first night I happened to be awake at midnight, and figured the first problem would be easy, so I should do it right then. That was all it took to get into the competitive spirit. Every night thereafter I stayed up however long it took to solve the problem. Towards the start this was mostly fine - getting to sleep at around 1:00 isn’t so bad. As the month when on and the problems became tougher though, it became a bit of an issue. On several nights I went to sleep past 2:00, and even past 3:00 a couple of times.

Nonetheless, my efforts led to results that mostly satisfied me. I didn’t place on the global leaderboard this year, but I came in first place on the KX leaderboard, and had high placements in every other private leaderboards I participated in. If nothing else, this serves as reassurance that despite not working on these sorts of problems in earnest for a year, I am still able to solve them fairly quickly. Given how tech interviews tend to me, these particular skills may be more practically applicable than they have any right to be.

I used Pykdb a small amount during the earlier days of AoC 2021, but it didn’t stick. Even when I was using it, I often wrote all or almost all of the solution using q, rather than intermixing Python and q. Switching between the languages has a cognitive overhead, as does reasoning about the type-conversions. I’m still trying to make the best out of this failure by finding some improvements I could make to Pykdb such that it’s easier to use, but I haven’t thought of any yet.

Perhaps its not something worth worrying about. After all, this sort of thing is not an anticipated use-case for Pykdb. Still, I remain interested in pairing together general-purpose glue languages with powerful domain-specific languages.

I’m not sure what I can say about the problems that were given this year, other than that I mostly liked them. I’ve heard some complaints, but can’t put much stock into my own comparisons between AoC 2021 and previous years since this is the first year where I both had to wake up in the morning, and yet I stayed up late to solve each problem as they came out. In all past years I either was able to significantly adjust my sleep schedule, or I didn’t solve the problems as they were released.

I don’t think I’ll stay up to solve the problems as they come out for 2022. It brings too much stress and seriousness into what I think ought to be leisurely and fun challenge for myself.