Advent of Code 2023 Solutions

All solutions on this page were written by me without reading any hints or solutions.

My solutions aren’t necessarily great, but they did the job and got me the answers.

My suggestion to run these solutions:

$ cat input.txt | ./solution.py

Links to the full challenge specifications are included throughout this document. The original specifications aren’t allowed to be reproduced, so I can’t repost them here.

Day 1 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin

def run(f):
    n = 0
    for s in f.readlines():
        s = [c for c in s if (c in "1234567890")]
        n += int(s[0] + s[-1])
    print(n)

run(stdin)

Part 2 Solution

I found Part 2 to be a pain in the ass because the exact conditions for a word to count as a number weren’t clear.

My first attempt would replace all valid substrings into digits, giving priority to what appears earlier:

#!/usr/bin/env python3 from sys import stdin from math import isinf, inf nums = {str(s) for s in range(10)} tab = { "one": "1", "two": "2", "three": "3", "four": "4", "five": "5", "six": "6", "seven": "7", "eight": "8", "nine": "9", #"zero": "0", } def run(): n = 0 for i, s in enumerate(x.strip() for x in f.readlines()): while True: best_idx = inf best_str = "" for (query, digit) in tab.items(): idx = s.find(query) if idx >= 0 and idx < best_idx: best_idx = idx best_str = query if isinf(best_idx): break s = s.replace(best_str, tab[best_str], 1) s = list(filter(lambda x : x in nums, s)) n += int(s[0] + s[-1]) print(n) run(f)

After a bit more thought, I realized the important thing is probably the first and last actual valid word.

In the interest of getting something done quick, I produced a terribly inelegant solution. Both the #replace first and #replace last blocks of code are near identical and do the same thing, just at different ends of the string. In the case of #replace first, it:

finds the left-most valid substring,
replaces it with a digit (if there is such a substring), then
removes all non-numerical character.

The full solution:

#!/usr/bin/env python3

from sys import stdin
from math import isinf, inf

nums = {str(s) for s in range(10)}
tab = {
    "one": "1",
    "two": "2",
    "three": "3",
    "four": "4",
    "five": "5",
    "six": "6",
    "seven": "7",
    "eight": "8",
    "nine": "9",
    #"zero": "0",
}

def run(f):
    n = 0
    for i, s in enumerate(x.strip() for x in f.readlines()):
        # replace first
        s1 = s
        best_idx = inf
        best_str = ""
        for (query, digit) in tab.items():
            idx = s1.find(query)
            if idx >= 0 and idx < best_idx:
                best_idx = idx
                best_str = query
        if not isinf(best_idx):
            s1 = s1.replace(best_str, tab[best_str], 1)
        s1 = [c for c in s1 if (c in nums)]

        # replace last
        s2 = s
        best_idx = -1
        best_str = ""
        for (query, digit) in tab.items():
            idx = s2.rfind(query)
            if idx >= 0 and idx > best_idx:
                best_idx = idx
                best_str = query
        if best_idx >= 1:
            s2 = s2.replace(best_str, tab[best_str])
        s2 = [c for c in s2 if (c in nums)]

        n += int(s1[0] + s2[-1])
    print(n)

run(stdin)

Day 2 [Spec]

Part 1 Solution

My solution just checks if every number of cubes falls within the limits (R_LIMIT, G_LIMIT, and B_LIMIT).

#!/usr/bin/env python3

from sys import stdin

R_LIMIT = 12
G_LIMIT = 13
B_LIMIT = 14

def run(f):
    solution = 0
    for i, s in enumerate(f.readlines()):
        (title, tail) = s.strip().split(":")
        (_, game_num) = title.split()
        sets = [dict(reversed(y.split()) for y in x.split(",")) for x in tail.split(";")]

        game_is_possible = all(
            (
                int(d.get("red", 0)) <= R_LIMIT
                and int(d.get("green", 0)) <= G_LIMIT
                and int(d.get("blue", 0)) <= B_LIMIT
            )
            for d in sets
        )
        if game_is_possible:
            solution += int(game_num)
    print(solution)

run(stdin)

Part 2 Solution

Straightforward modification that instead just grabs the maximum numbers of red, green, and blue seen within each game.

#!/usr/bin/env python3

from sys import stdin

def run(f):
    solution = 0
    for i, s in enumerate(f.readlines()):
        (title, tail) = s.strip().split(":")
        (_, game_num) = title.split()
        sets = [dict(reversed(y.split()) for y in x.split(",")) for x in tail.split(";")]

        (r, g, b) = (0, 0, 0)
        for d in sets:
            r = max(r, int(d.get("red", 0)))
            g = max(g, int(d.get("green", 0)))
            b = max(b, int(d.get("blue", 0)))
        solution += r * g * b
    print(solution)

run(stdin)

Day 3 [Spec]

Part 1 Solution

This one’s a real mess to look at due to the loop nesting (2D data structures can be a pain like this) and lots of things happening simultaneously.

My approach starts by padding the grid with an extra end column and end row of ".", i.e. the symbol denoting empty space. This simplifies the code since we need to check adjacent cells, and "." will simply be read as nothing.

This padding also takes advantage of Python’s negative indexing, where row[-1] will simply grab the final element of the row (i.e. the final column). For example, if our current location is (1, 0) (row 1, column 0), our adjacent cells will include the negative column: (0, -1), (1, -1), and (2, -1). These negative column numbers will just map to the final column, which will all be ".". In my opinion, this is a nice simplification that means we no longer have to explicitly deal with the edge case within the loop.

The loop itself scans each row for consecutive digits. Every time a digit is found, it updates an accumulator (called num). E.g. if the accumulator is 452 and we read in a new digit 7, the accumulator now becomes 4527. Every time we read in a non-digit, the accumulator is flushed, resetting it to zero.

At the same time, we also scan all adjacent cells for part symbols (*, #, etc.). If it is, then we record the current accumulator as being a part number (is_part_num). That way, by the time the accumulator flushes, we know whether the full number is indeed a part number.

Once again, the "." padding helps us simplify our code to avoid explicitly dealing with an edge case. Since the final column is ".", we will know that any part number still stored in the accumulator will be forced to flush, and thus be included in the solution.

#!/usr/bin/env python3

from sys import stdin
from itertools import product

def run(f):
    solution = 0
    grid = [list(x.strip()) + ["."] for x in f]
    (len1, len2) = (len(grid), len(grid[0]))
    grid.append(["."] * len2)
    for i, row in enumerate(grid):
        (num, is_part_num) = (0, False)
        for j, v in enumerate(row):
            if v.isdigit():
                num = (num * 10) + int(v)
                for i2, j2 in product((i - 1, i, i + 1), (j - 1, j, j + 1)):
                    (i2, j2) = (i2 % len1, j2 % len2)
                    if (not grid[i2][j2].isdigit()) and (grid[i2][j2] != "."):
                        is_part_num = True
            else:
                if is_part_num:
                    solution += num
                (num, is_part_num) = (0, False)
    print(solution)

run(stdin)

Part 2 Solution

We keep a lot of the same tricks as Part 1, but this time, instead of is_part_num, we store a set of adjacent gears (gears) to the current accumulator value. Every time we flush the accumulator, we record every gear we found as being adjacent to the part number (gear_adjs).

Then, we just loop through gear_adjs, summing up gear ratios (x[0] * x[1]) after filtering for gears with exactly two adjacencies (len(x) == 2).

#!/usr/bin/env python3

from sys import stdin
from itertools import product
from collections import defaultdict

def run(f):
    grid = [x.strip() + "." for x in f]
    (len1, len2) = (len(grid), len(grid[0]))
    grid.append("." * len2)
    gear_adjs = defaultdict(list) # "gear adjacencies", {(i, j): [part nums]}
    for i, row in enumerate(grid):
        (num, gears) = (0, set())
        for j, v in enumerate(row):
            if v.isdigit():
                num = (num * 10) + int(v)
                for i2, j2 in product((i - 1, i, i + 1), (j - 1, j, j + 1)):
                    (i2, j2) = (i2 % len1, j2 % len2)
                    if grid[i2][j2] == "*":
                        gears.add((i2, j2))
            else:
                for i2, j2 in gears:
                    gear_adjs[(i2, j2)].append(num)
                (num, gears) = (0, set())
    print(sum(x[0] * x[1] for x in gear_adjs.values() if len(x) == 2))

run(stdin)

Day 4 [Spec]

Part 1 Solution

We just take a set intersection between what’s present on the card and the winning numbers to get the number of winning numbers. Easy!

#!/usr/bin/env python3

from sys import stdin

def run(f):
    solution = 0
    for line in f:
        (_, all_numbers) = line.split(":")
        (card, winning_numbers) = [x.strip().split() for x in all_numbers.strip().split("|")]
        matches = len(set(card) & set(winning_numbers))
        if matches > 0:
            solution += 2 ** (matches - 1)
    print(solution)

run(stdin)

Part 2 Solution

I went for a 1D dynamic programming solution. Each card’s final value is only dependent on cards of higher indices, so we iterate through the list of cards in reverse.

#!/usr/bin/env python3

from sys import stdin

def run(f):
    cards = []
    for line in f:
        (_, all_numbers) = line.split(":")
        (card, winning_numbers) = [x.strip().split() for x in all_numbers.strip().split("|")]
        cards.append(len(set(card) & set(winning_numbers)))

    solution = 0
    for i, v in reversed(list(enumerate(cards))):
        cards[i] = sum(cards[i+1:i+1+cards[i]]) + 1
        solution += cards[i]
    print(solution)

run(stdin)

Day 5 [Spec]

Part 1 Solution

Each X-to-Y map: section is doing basically the same thing, mapping some set of input IDs to some set of output IDs. To avoid code duplication, I wrote ID mapping functionality that is simply reused for each “X-to-Y map:” in the order dictated by maps_order.

#!/usr/bin/env python3

from sys import stdin

maps_order = (
    "seed-to-soil map",
    "soil-to-fertilizer map",
    "fertilizer-to-water map",
    "water-to-light map",
    "light-to-temperature map",
    "temperature-to-humidity map",
    "humidity-to-location map",
)

def run(f):
    sections = [x.split(":") for x in "".join(f.readlines()).split("\n\n")]
    sections = {k.strip(): v.strip() for k, v in sections}

    seeds = [int(x) for x in sections["seeds"].split()]
    del sections["seeds"]

    maps = {k: [[int(y) for y in x.split()] for x in v.split("\n")] for k, v in sections.items()}

    ids = seeds
    for map_name in maps_order:
        ranges = maps[map_name]
        new_ids = []
        for i in ids:
            new_i = i
            for dst, src, rangelen in ranges:
                if (i >= src) and (i < src + rangelen):
                    new_i = dst + (i - src)
                    break
            new_ids.append(new_i)
        ids = new_ids
    print(min(ids))

run(stdin)

Part 2 Solution

To deal with the ranges of seeds, rather than map individual seeds/IDs at a time (as with Part 1), we instead map ranges represented by tuples of starting ID and range length.

Since ID ranges have to occasionally be split, each mapping operation starts with a stack of ID ranges. We pop a range and attempt to map it. If we find a “partial match”, then we map the part that can be mapped, then we push back the unmapped parts back to the stack to be reprocessed.

For example, suppose we have the ID range tuple (7, 4) representing the IDs [7, 8, 9, 10]. This might match with a mapping 31 4 5, which maps the IDs [4, 5, 6, 7, 8] to the IDs [31, 32, 33, 34, 35]. Our ID range tuple only matches on the IDs [7, 8], so we map those two IDs to [34, 35], and the unmatched portion [9, 10] is pushed back to the stack as a new ID range tuple (9, 2).

Now, that was actually an oversimplification. My solution actually cheats a little by always pushing the upper unmatched portion and lower unmatched portion back to the stack, even if the unmatched portions might be zero-length. We just filter for zero-length ID ranges with the if id_len == 0: branch. This means that even if we find a “full match”, we end up pushing two zero-length ranges back to the stack anyway.

For the case where an ID range tuple doesn’t match with any mapping, it just maps like you’d expect.

The grouper() function is taken directly from Itertools Recipes from the official documentation.

#!/usr/bin/env python3

from sys import stdin
from itertools import chain, pairwise, zip_longest

maps_order = (
    "seed-to-soil map",
    "soil-to-fertilizer map",
    "fertilizer-to-water map",
    "water-to-light map",
    "light-to-temperature map",
    "temperature-to-humidity map",
    "humidity-to-location map",
)

# <https://docs.python.org/3/library/itertools.html#itertools-recipes>
def grouper(iterable, n, *, incomplete='fill', fillvalue=None):
    "Collect data into non-overlapping fixed-length chunks or blocks"
    # grouper('ABCDEFG', 3, fillvalue='x') --> ABC DEF Gxx
    # grouper('ABCDEFG', 3, incomplete='strict') --> ABC DEF ValueError
    # grouper('ABCDEFG', 3, incomplete='ignore') --> ABC DEF
    args = [iter(iterable)] * n
    if incomplete == 'fill':
        return zip_longest(*args, fillvalue=fillvalue)
    if incomplete == 'strict':
        return zip(*args, strict=True)
    if incomplete == 'ignore':
        return zip(*args)
    else:
        raise ValueError('Expected fill, strict, or ignore')

def run(f):
    sections = [x.split(":") for x in "".join(f.readlines()).split("\n\n")]
    sections = {k.strip(): v.strip() for k, v in sections}

    seeds = list(grouper((int(x) for x in sections["seeds"].split()), 2))
    del sections["seeds"]

    maps = {k: [[int(y) for y in x.split()] for x in v.split("\n")] for k, v in sections.items()}

    ids = seeds
    for map_name in maps_order:
        ranges = maps[map_name]
        new_ids = []
        while len(ids):
            id_start, id_len = ids.pop()
            if id_len == 0:
                continue
            for dst, src, rangelen in ranges:
                intersect_start = max(id_start, src)
                intersect_end = min(id_start + id_len, src + rangelen)
                if intersect_end > intersect_start:
                    ids.append((id_start, intersect_start - id_start))
                    ids.append((intersect_end, id_start + id_len - intersect_end))
                    new_ids.append((intersect_start + dst - src, intersect_end - intersect_start))
                    break
            else:
                new_ids.append((id_start, id_len))
        ids = new_ids
    print(min((x for (x, _) in ids), default="NONE"))

run(stdin)

Day 6 [Spec]

Part 1 Solution

I just tried every possible button-hold-time and counted the record-breakers.

#!/usr/bin/env python3

from sys import stdin

def run(f):
    sections = [s.split(":") for s in f.readlines()]
    sections = {k.strip(): [int(x) for x in v.strip().split()] for k, v in sections}

    solution = 1
    for time_limit, dist_record in zip(sections["Time"], sections["Distance"]):
        combos = 0
        for hold_time in range(1, time_limit):
            dist_travelled = (time_limit - hold_time) * hold_time
            if dist_travelled > dist_record:
                combos += 1
        solution *= combos

    print(solution)

run(stdin)

Part 2 Solution

Instead of making lists of integers, I joined the integers together with this line:

    sections = {k.strip(): int("".join(v.strip().split())) for k, v in sections}

The full solution:

#!/usr/bin/env python3

from sys import stdin

def run(f):
    sections = [s.split(":") for s in f.readlines()]
    sections = {k.strip(): int("".join(v.strip().split())) for k, v in sections}

    (time_limit, dist_record) = (sections["Time"], sections["Distance"])

    combos = 0
    for hold_time in range(1, time_limit):
        dist_travelled = (time_limit - hold_time) * hold_time
        if dist_travelled > dist_record:
            combos += 1

    print(combos)

run(stdin)

Day 7 [Spec]

Part 1 Solution

I used a list of lists of hands. When filling the inner lists, I map the card symbols to a relative strength integer using label_order. That way, when I sort the inner list, I can just take advantage of the natural sort order where Python can sort tuples by the tuple contents.

>>> from itertools import count
>>> label_order = {c: i for c, i in zip(reversed("AKQJT98765432"), count())}
>>> label_order
{'2': 0, '3': 1, '4': 2, '5': 3, '6': 4, '7': 5, '8': 6, '9': 7, 'T': 8, 'J': 9, 'Q': 10, 'K': 11, 'A': 12}

The inner lists are sorted by natural order before then chained together into a single list all_sorted.

The full solution:

#!/usr/bin/env python3

from sys import stdin
from collections import Counter
from itertools import chain, count

label_order = {c: i for c, i in zip(reversed("AKQJT98765432"), count())}

def run(f):
    hands = [s.split() for s in f.readlines()]

    sorted_hands = [[], [], [], [], [], [], []]
    for labels, bid in hands:
        bid = int(bid)
        cnt = Counter(labels)
        freqs = Counter(cnt.values())

        tup = (tuple(label_order[c] for c in labels), bid)
        if 5 in freqs:
            sorted_hands[6].append(tup)
        elif 4 in freqs:
            sorted_hands[5].append(tup)
        elif 3 in freqs:
            if 2 in freqs:
                sorted_hands[4].append(tup)
            else:
                sorted_hands[3].append(tup)
        elif freqs[2] == 2:
            sorted_hands[2].append(tup)
        elif freqs[2] == 1:
            sorted_hands[1].append(tup)
        else:
            sorted_hands[0].append(tup)

    all_sorted = chain(*(tuple(sorted(lst)) for lst in sorted_hands))
    print(sum(bid * rank for ((_, bid), rank) in zip(all_sorted, count(1))))

run(stdin)

Part 2 Solution

For Part 2, I modified Part 1 to try every possible card that a joker can “mimic”, and taking the best strength.

#!/usr/bin/env python3

from sys import stdin
from collections import Counter
from itertools import chain, count

label_order = {c: i for c, i in zip(reversed("AKQT98765432J"), count())}

def run(f):
    hands = [s.split() for s in f.readlines()]

    sorted_hands = [[], [], [], [], [], [], []]
    for labels, bid in hands:
        bid = int(bid)

        tup = (tuple(label_order[c] for c in labels), bid)
        strength = -1
        for joker_mimic in "AKQT98765432J":
            mimicked = labels.replace("J", joker_mimic)
            print(mimicked)
            cnt = Counter(mimicked)
            freqs = Counter(cnt.values())

            if 5 in freqs:
                strength = max(strength, 6)
            elif 4 in freqs:
                strength = max(strength, 5)
            elif 3 in freqs:
                if 2 in freqs:
                    strength = max(strength, 4)
                else:
                    strength = max(strength, 3)
            elif freqs[2] == 2:
                strength = max(strength, 2)
            elif freqs[2] == 1:
                strength = max(strength, 1)
            else:
                strength = max(strength, 0)
        sorted_hands[strength].append(tup)

    all_sorted = chain(*(tuple(sorted(lst)) for lst in sorted_hands))
    print(sum(bid * rank for ((_, bid), rank) in zip(all_sorted, count(1))))

run(stdin)

Day 8 [Spec]

Part 1 Solution

My solution builds a graph and just follows the instructions until we reach ZZZ.

#!/usr/bin/env python3

from sys import stdin

def run(f):
    (instructions, graph) = f.read().strip().split("\n\n")
    graph = {x[0]: (x[2][1:-1], x[3][:-1]) for x in (s.split() for s in graph.split("\n"))}

    steps = 0
    cur = "AAA"
    while cur != "ZZZ":
        cur = graph[cur][0] if (instructions[steps % len(instructions)] == "L") else graph[cur][1]
        steps += 1
    print(steps)

run(stdin)

Part 2 Failed Brute Force

At each iteration of the loop, I transform a vector of current nodes to a new vector of current nodes. However, I ran it for a few hours (I had to leave my computer anyway lol) and when I got back, it was still running, so it was clear that something smarter was needed.

#!/usr/bin/env python3

from sys import stdin

def run(f):
    (instructions, graph) = f.read().strip().split("\n\n")
    graph = {x[0]: (x[2][1:-1], x[3][:-1]) for x in (s.split() for s in graph.split("\n"))}

    steps = 0
    cur = [x for x in graph.keys() if x[-1] == "A"]
    while any((x[-1] != "Z") for x in cur):
        i = 0 if (instructions[steps % len(instructions)] == "L") else 1
        cur[:] = [graph[x][i] for x in cur]
        steps += 1
        if steps % 1000000 == 0:
            print(steps)
    print(steps)

run(stdin)

Part 2 Solution

Here’s my original full solution:

#!/usr/bin/env python3

from sys import stdin
from itertools import cycle
from math import lcm

def run(f):
    (instructions, graph) = f.read().strip().split("\n\n")
    instructions = [(0 if x == "L" else 1) for x in instructions]
    graph = {x[0]: (x[2][1:-1], x[3][:-1]) for x in (s.split() for s in graph.split("\n"))}

    starts = list({x for x in graph.keys() if x[-1] == "A"})
    cycle_exits = []
    cycle_bounds = []
    for i, start in enumerate(starts):
        seen = {} # {(node, instruction order): step, ...}
        cycle_exits.append([])
        cur = start
        for step, (j, instr) in enumerate(cycle(enumerate(instructions))):
            tup = (cur, j)
            if tup in seen:
                cycle_bounds.append((seen[tup], step))
                break
            if cur[-1] == "Z":
                cycle_exits[-1].append(step)
            seen[tup] = step
            cur = graph[cur][instr]
    print("exits:", cycle_exits)
    print()
    print("bounds:", cycle_bounds)
    print()

    # the rest of this code works only because we know there is only exactly one exit for
    # each cycle
    if any(len(x) != 1 for x in cycle_exits):
        raise RuntimeError()

    # also, we ignore any steps before they all enter a cycle
    offset = max(start for (start, _) in cycle_bounds)
    cycle_lens = [end - start for (start, end) in cycle_bounds]
    first_exit = [x[0] - offset for x in cycle_exits]
    diffs = [cl - fe for cl, fe in zip(cycle_lens, first_exit)]

    print("cycle lengths - first exit:", diffs)
    print()

    # the rest of the code below assumes the same difference!
    if any(x != diffs[0] for x in diffs):
        raise RuntimeError()
    
    print(lcm(*cycle_lens))

run(stdin)

Getting an efficient Part 2 solution was a big pain in the ass. At the moment, I’m not sure of a better approach, but here’s what I did at the time to get that final solution.

To make progress, I started by exploring the graph, first wondering where each individual "**A" starting point went (i.e. the path taken when starting from the individual node) rather than dealing with all the paths at the same time.

My assumption was that we eventually enter a cycle, and within the cycle, there is one or more "**Z" exit points. I wanted to know at what point does each individual path enter a cycle, and where the exit points sit in the cycle. Maybe we can do some fancy math with it?

Here are the results of that exploration work:

exits: [[20803], [23147], [19631], [13771], [17287], [12599]]

bounds: [(3, 20806), (2, 23149), (2, 19633), (2, 13773), (6, 17293), (2, 12601)]

The exits: and bounds: printouts above correspond to these lines in my solution:

    print("exits:", cycle_exits)
    print()
    print("bounds:", cycle_bounds)
    print()

(TODO: Continue this explanation.)

Day 9 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import pairwise

def run(f):
    seqs = [[int(x) for x in s.split()] for s in f.readlines()]

    solution = 0
    for seq in seqs:
        diffs = [seq.copy()]
        while any(x != 0 for x in diffs[-1]):
            diffs.append([b - a for a, b in pairwise(diffs[-1])])
        next_diff = 0
        for i in reversed(range(len(diffs) - 1)):
            next_diff = diffs[i][-1] + next_diff
            diffs[i].append(next_diff)
        solution += diffs[0][-1]
    print(solution)

run(stdin)

Part 2 Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import pairwise

def run(f):
    seqs = [[int(x) for x in s.split()] for s in f.readlines()]

    solution = 0
    for seq in seqs:
        diffs = [list(reversed(seq))] # this is literally the only change
        while any(x != 0 for x in diffs[-1]):
            diffs.append([b - a for a, b in pairwise(diffs[-1])])
        next_diff = 0
        for i in reversed(range(len(diffs) - 1)):
            next_diff = diffs[i][-1] + next_diff
            diffs[i].append(next_diff)
        solution += diffs[0][-1]
    print(solution)

run(stdin)

Day 10 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin, setrecursionlimit
from itertools import chain

CONNECTIONS = {
    (-1,  0): {"S", "|", "L", "J"},
    ( 1,  0): {"S", "|", "7", "F"},
    ( 0, -1): {"S", "-", "J", "7"},
    ( 0,  1): {"S", "-", "L", "F"},
}

def run(f):
    pipemap = [s.strip() + "." for s in f.readlines()]
    pipemap.append("."*len(pipemap[0]))

    start = None
    for row, col in enumerate(s.find("S") for s in pipemap):
        if col >= 0:
            start = (row, col)
            break

    dummy = len(pipemap) * len(pipemap[0])
    distances = [[dummy]*len(pipemap[0]) for _ in range(len(pipemap))]

    setrecursionlimit(dummy)
    def dfs(i, j, dist):
        if distances[i][j] <= dist:
            return
        distances[i][j] = dist
        for (ii, jj), symbols in CONNECTIONS.items():
            if (pipemap[i][j] in symbols) and (pipemap[i + ii][j + jj] in CONNECTIONS[(-ii, -jj)]):
                dfs(i + ii, j + jj, dist + 1)
    dfs(*start, 0)
    print(max(x for x in chain(*distances) if (x < dummy)))

run(stdin)

Part 2 Solution

#!/usr/bin/env python3

from sys import stdin#, setrecursionlimit
from itertools import chain, product

TILE_CONVERTER = {
    (-1,  0): {"S", "|", "L", "J"},
    ( 1,  0): {"S", "|", "7", "F"},
    ( 0, -1): {"S", "-", "J", "7"},
    ( 0,  1): {"S", "-", "L", "F"},
    ( 0,  0): {"S", "|", "-", "L", "J", "F", "7"},
}

def run(f):
    pipemap = [s.strip() for s in f.readlines()]

    start = None
    for i, j in enumerate(s.find("S") for s in pipemap):
        if j >= 0:
            start = (i, j)
            break

    expanded_map = [["."]*(3*len(pipemap[0])) for _ in range(3 * len(pipemap))]
    for i, row in enumerate(pipemap):
        for j, c in enumerate(row):
            if c != ".":
                (i2, j2) = ((i*3) + 1, (j*3) + 1)
                for (i3, j3), symbols in TILE_CONVERTER.items():
                    if c in symbols:
                        expanded_map[i2 + i3][j2 + j3] = "X"
    start = ((start[0]*3) + 1, (start[1]*3) + 1)

    #setrecursionlimit(len(expanded_map) * len(expanded_map[0]))

    print()
    print("\n".join("".join(x) for x in expanded_map))

    # The code below only works because we know for sure that 'S' passes through
    # just one loop and has no ambiguity. This is confirmed by just inspecting
    # the input file visually.

    # Can't do recursion because we'll literally crash CPython lmao
    def floodfill(i, j, to_replace, new_char):
        stack = [(i, j)]
        while len(stack):
            (i, j) = stack.pop()
            if (i < 0) or (j < 0) \
                    or (i >= len(expanded_map)) or (j >= len(expanded_map[0])) \
                    or expanded_map[i][j] not in to_replace:
                continue
            expanded_map[i][j] = new_char
            for ii, jj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                stack.append((i + ii, j + jj))
    floodfill(*start, {"X"}, "Y")
    floodfill(0, 0, {".", "X"}, "Y")

    print("\n".join("".join(x) for x in expanded_map))

    solution = 0
    for i, j in product(range(len(pipemap)), range(len(pipemap[0]))):
        solution += expanded_map[(i*3) + 1][(j*3) + 1] != "Y"
    print()
    print(solution)

run(stdin)

Day 11 [Spec]

Part 1 BFS Solution

My first solution was a very bad and overly complex approach involving repeated BFS, and takes ages to run.

#!/usr/bin/env python3

from sys import stdin
from heapq import heappush, heappop
from itertools import product

def expand_space(galaxymap):
    (rows, cols) = (len(galaxymap), len(galaxymap[0]))
    for row in reversed(range(rows)):
        if all(c == "." for c in galaxymap[row]):
            galaxymap.insert(row, ["."]*len(galaxymap[0]))
    rows = len(galaxymap)
    for col in reversed(range(cols)):
        if all(galaxymap[row][col] == "." for row in range(rows)):
            for lst in galaxymap:
                lst.insert(col, ".")

def sum_paths(galaxymap, pairs_seen, init):
    pq = [(0, *init)]
    seen = set()
    solution = 0
    while len(pq):
        (dist, i, j) = heappop(pq)
        if ((i, j) in seen) or (i < 0) or (j < 0) \
                or (i >= len(galaxymap)) or (j >= len(galaxymap[0])):
            continue
        seen.add((i, j))
        if (galaxymap[i][j] == "#") and ((init, (i, j)) not in pairs_seen):
            solution += dist
            pairs_seen.add((init, (i, j)))
            pairs_seen.add(((i, j), init))
        for ii, jj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            heappush(pq, (dist + 1, i + ii, j + jj))
    return solution

def run(f):
    galaxymap = [list(s.strip()) for s in f.readlines()]
    expand_space(galaxymap)

    solution = 0
    pairs_seen = set()
    for i, j in product(range(len(galaxymap)), range(len(galaxymap[0]))):
        if galaxymap[i][j] == "#":
            galaxymap[i][j] = "."
            solution += sum_paths(galaxymap, pairs_seen, (i, j))
            galaxymap[i][j] = "#"
    print(solution)

run(stdin)

Part 1 “Point List” Mathematical Solution

When I read Part 2, I realized the original approach will scale horribly due to the suddenly massively expanded search space. I decided to start by improving Part 1 to validate a new approach.

The new approach simply involves storing a list of galaxy coordinates (galaxies) then doing math on each coordinate and each pair of coordinates. Much more elegant, and runs so much faster!

#!/usr/bin/env python3

from sys import stdin
from itertools import product, combinations

def run(f):
    galaxymap = [s.strip() for s in f.readlines()]
    galaxies = []
    for i, j in product(range(len(galaxymap)), range(len(galaxymap[0]))):
        if galaxymap[i][j] == "#":
            galaxies.append((i, j))

    empty_rows = [
        i for i in range(len(galaxymap))
        if all(c == "." for c in galaxymap[i])
    ]
    empty_cols = [
        j for j in range(len(galaxymap[0]))
        if all(galaxymap[i][j] == "." for i in range(len(galaxymap)))
    ]

    # Apply expansion
    galaxies = [
        (i + sum(i > ii for ii in empty_rows), j + sum(j > jj for jj in empty_cols))
        for i, j in galaxies
    ]

    print(sum(
        abs(i2 - i1) + abs(j2 - j1)
        for (i1, j1), (i2, j2) in combinations(galaxies, 2)
    ))

run(stdin)

Part 2 Solution

With my faster mathematical solution for Part 1, I made a few modifications to adapt it for Part 2.

I changed the expansion-application to:

# Apply expansion
galaxies = [
    (
        i + (EXPANSION * sum(i > ii for ii in empty_rows)),
        j + (EXPANSION * sum(j > jj for jj in empty_cols)),
    )
    for i, j in galaxies
]

and introducing the constant:

EXPANSION = 1000000 - 1

The full solution:

#!/usr/bin/env python3

from sys import stdin
from itertools import product, combinations

EXPANSION = 1000000 - 1

def run(f):
    galaxymap = [s.strip() for s in f.readlines()]
    galaxies = []
    for i, j in product(range(len(galaxymap)), range(len(galaxymap[0]))):
        if galaxymap[i][j] == "#":
            galaxies.append((i, j))

    empty_rows = [
        i for i in range(len(galaxymap))
        if all(c == "." for c in galaxymap[i])
    ]
    empty_cols = [
        j for j in range(len(galaxymap[0]))
        if all(galaxymap[i][j] == "." for i in range(len(galaxymap)))
    ]

    # Apply expansion
    galaxies = [
        (
            i + (EXPANSION * sum(i > ii for ii in empty_rows)),
            j + (EXPANSION * sum(j > jj for jj in empty_cols)),
        )
        for i, j in galaxies
    ]

    print(sum(
        abs(i2 - i1) + abs(j2 - j1)
        for (i1, j1), (i2, j2) in combinations(galaxies, 2)
    ))

run(stdin)

Day 12 [Spec]

Part 1 Brute Force Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import product

OK = "."
BAD = "#"
UNKNOWN = "?"

def run(f):
    solution = 0
    for s in f.readlines():
        (springs, groups) = s.split()
        springs = list(springs)
        groups = tuple(int(x) for x in groups.split(","))

        num_wildcards = springs.count(UNKNOWN)
        for wildcards in product(OK + BAD, repeat=num_wildcards):
            wildcards = list(wildcards)
            springs2 = springs.copy()
            for i in range(len(springs2)):
                if springs2[i] == UNKNOWN:
                    springs2[i] = wildcards.pop()
            if groups == tuple(len(x) for x in "".join(springs2).replace(".", " ").split()):
                solution += 1
    print(solution)

run(stdin)

Part 1 Backtracking Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import product

OK = "."
BAD = "#"
UNKNOWN = "?"

def run(f):
    solution = 0
    for s in f.readlines():
        (springs, groups) = s.split()
        #springs = list("?".join([springs]*5))
        #groups = tuple(int(x) for x in groups.split(","))*5
        springs = list(springs) + ["."]
        groups = [0] + [int(x) for x in reversed(groups.split(","))]

        subsolution = 0
        def backtrack(i, is_contiguous_bads):
            nonlocal subsolution
            if i == len(springs):
                if (len(groups) == 1) and (groups[0] == 0):
                    subsolution += 1
                return
            elif springs[i] == UNKNOWN:
                springs[i] = OK
                backtrack(i, is_contiguous_bads)
                springs[i] = BAD
                backtrack(i, is_contiguous_bads)
                springs[i] = UNKNOWN
            elif springs[i] == OK:
                if is_contiguous_bads:
                    if groups[-1] != 0:
                        return
                    groups.pop()
                    if len(groups):
                        backtrack(i + 1, False)
                    groups.append(0)
                else:
                    backtrack(i + 1, False)
            else: # springs[1] == BAD
                if is_contiguous_bads and (groups[-1] == 0):
                    return
                groups[-1] -= 1
                backtrack(i + 1, True)
                groups[-1] += 1
        backtrack(0, False)
        solution += subsolution
    print(solution)

run(stdin)

Part 1 Dynamic Programming Solution

#!/usr/bin/env python3

from sys import stdin
from functools import cache
from itertools import product

OK = "."
BAD = "#"
UNKNOWN = "?"

def run(f):
    solution = 0
    for s in f.readlines():
        (springs, groups) = s.split()
        springs = "." + springs
        groups = tuple(int(x) for x in groups.split(","))

        # Returns number of combinations
        # `i` is the beginning of a subarray in `springs`
        # `j` is the beginning of a subarray in `groups`
        #@cache # runs fast enough without it
        def subproblem(i, j):
            if j == len(groups):
                return all((c != BAD) for c in springs[i:])
            elif len(springs) - i < groups[j] + 1:
                return 0 # not enough room
            elif springs[i] == BAD:
                return 0 # must not connect with previous group
            i += 1
            subsolution = 0
            for i in range(i, len(springs) - groups[j] + 1):
                s = springs[i : i + groups[j]]
                if all(c != OK for c in s):
                    subsolution += subproblem(i + groups[j], j + 1)
                if springs[i] == BAD:
                    break
            return subsolution
        solution += subproblem(0, 0)

    print(solution)

run(stdin)

Part 2 Solution

My Part 2 solution is a modified version of my Part 1 dynamic programming solution.

Instead of:

springs = "." + springs
groups = tuple(int(x) for x in groups.split(","))

we instead have:

springs = ["."] + list("?".join([springs]*5))
groups = [int(x) for x in groups.split(",")]*5

and I uncomment the @cache line since subproblem() runs too slow without memoization.

The full solution is thus:

#!/usr/bin/env python3

from sys import stdin
from functools import cache
from itertools import product

OK = "."
BAD = "#"
UNKNOWN = "?"

def run(f):
    solution = 0
    for s in f.readlines():
        (springs, groups) = s.split()
        springs = ["."] + list("?".join([springs]*5))
        groups = [int(x) for x in groups.split(",")]*5

        # Returns number of combinations
        # `i` is the beginning of a subarray in `springs`
        # `j` is the beginning of a subarray in `groups`
        @cache
        def subproblem(i, j):
            if j == len(groups):
                return all((c != BAD) for c in springs[i:])
            elif len(springs) - i < groups[j] + 1:
                return 0 # not enough room
            elif springs[i] == BAD:
                return 0 # must not connect with previous group
            i += 1
            subsolution = 0
            for i in range(i, len(springs) - groups[j] + 1):
                s = springs[i : i + groups[j]]
                if all(c != OK for c in s):
                    subsolution += subproblem(i + groups[j], j + 1)
                if springs[i] == BAD:
                    break
            return subsolution
        solution += subproblem(0, 0)

    print(solution)

run(stdin)

Day 13 [Spec]

Part 1 Solution

My solution starts by assuming all possible lines of reflection are valid. For example, is_horz_reflection is a list of booleans, each element representing a different vertical line of reflection and whether said line is valid.

My solution then visit each cell one-by-one. For each cell, it tries every possible vertical and horizontal line of reflection by checking if the current cell matches the mirror image cell. If the mirror image cell does not match the current cell, then we mark the corresponding line of reflection as impossible.

After checking every cell and every line of reflection, is_horz_refl and is_vert_refl should only contain one True element between them. This corresponds to the one valid line of reflection for the pattern.

#!/usr/bin/env python3

from sys import stdin
from itertools import product

def run(f):
    patterns = [s.split() for s in "".join(f.readlines()).split("\n\n")]

    solution = 0
    for pattern in patterns:
        is_horz_refl = [True]*(len(pattern[0]) - 1)
        is_vert_refl = [True]*(len(pattern) - 1)
        for i, j in product(range(len(pattern)), range(len(pattern[0]))):
            c = pattern[i][j]
            # check horizontal reflections
            for j_midline in range(j, len(pattern[0])):
                j_refl = j_midline + (j_midline - j) + 1
                if j_refl >= len(pattern[0]):
                    break
                elif c != pattern[i][j_refl]:
                    is_horz_refl[j_midline] = False
            # check vertical reflections
            for i_midline in range(i, len(pattern)):
                i_refl = i_midline + (i_midline - i) + 1
                if i_refl >= len(pattern):
                    break
                elif c != pattern[i_refl][j]:
                    is_vert_refl[i_midline] = False
        solution += sum(i + 1 for i, v in enumerate(is_horz_refl) if v)
        solution += sum(i + 1 for i, v in enumerate(is_vert_refl) if v) * 100
    print(solution)

run(stdin)

Part 2 Solution

I mainly modified my Part 1 solution so that we count line-of-reflection breakages for each line of reflection. Thus, we now have:

        horz_refl_breakages = [0]*(len(pattern[0]) - 1)
        vert_refl_breakages = [0]*(len(pattern) - 1)

The full solution:

#!/usr/bin/env python3

from sys import stdin
from itertools import product

def run(f):
    patterns = [s.split() for s in "".join(f.readlines()).split("\n\n")]

    solution = 0
    for pattern in patterns:
        horz_refl_breakages = [0]*(len(pattern[0]) - 1)
        vert_refl_breakages = [0]*(len(pattern) - 1)
        for i, j in product(range(len(pattern)), range(len(pattern[0]))):
            c = pattern[i][j]
            # check horizontal reflections
            for j_midline in range(j, len(pattern[0])):
                j_refl = j_midline + (j_midline - j) + 1
                if j_refl >= len(pattern[0]):
                    break
                elif c != pattern[i][j_refl]:
                    horz_refl_breakages[j_midline] += 1
            # check vertical reflections
            for i_midline in range(i, len(pattern)):
                i_refl = i_midline + (i_midline - i) + 1
                if i_refl >= len(pattern):
                    break
                elif c != pattern[i_refl][j]:
                    vert_refl_breakages[i_midline] += 1
        solution += sum(i + 1 for i, v in enumerate(horz_refl_breakages) if v == 1)
        solution += sum(i + 1 for i, v in enumerate(vert_refl_breakages) if v == 1) * 100
    print(solution)

run(stdin)

Day 14 [Spec]

Part 1 Non-Modifying Two-Pointer Solution

My Part 1 solution is basically a two-pointer solution where I pretend to move the O rocks, but I don’t actually modify the underlying data structure.

#!/usr/bin/env python3

from sys import stdin

def run(f):
    rockmap = [s.strip() for s in f.readlines()]

    solution = 0
    for j in range(len(rockmap[0])):
        empty_i = 0
        for i in range(len(rockmap)):
            c = rockmap[i][j]
            if c == "#":
                empty_i = i + 1
            elif c == "O":
                solution += len(rockmap) - empty_i
                empty_i += 1
    print(solution)

run(stdin)

Part 1 Modifying Two-Pointer Solution

To help me out for Part 2, I modified my original Part 1 solution so that instead of pretending to move the O rocks without modifying the rockmap data structure, we actually do modify it, moving the O rocks to new places, then running a sum() to get the final answer.

#!/usr/bin/env python3

from sys import stdin
from itertools import product

def push_north(rockmap):
    for j in range(len(rockmap[0])):
        empty_i = 0
        for i in range(len(rockmap)):
            c = rockmap[i][j]
            if c == "#":
                empty_i = i + 1
            elif c == "O":
                rockmap[i][j] = "."
                rockmap[empty_i][j] = "O"
                empty_i += 1

def run(f):
    rockmap = [list(s.strip()) for s in f.readlines()]
    push_north(rockmap)
    print(sum(
        len(rockmap) - i
        for i, j in product(range(len(rockmap)), range(len(rockmap[0])))
        if rockmap[i][j] == "O"
    ))

run(stdin)

Part 2 Lazy Solution

Part 2 asks for 1,000,000,000 iterations. Obviously, a brute-force solution shouldn’t scale well for simulating all 1,000,000,000 iterations, with my attempt at brute-force taking 5 seconds to run 100,000 iterations. Extrapolating to 1,000,000,000, it would take 14 hours.

(When I say “iteration”, I mean a single set of four pushes: north, then west, then south, then east.)

The next idea that I tried was the assumption that after enough iterations, we reach a constant state of rockmap (and therefore also the same “load value”). For example, I was thinking maybe we might see load values $\brackets{12, 16, 14, 17, 15, 15, 15, 15, 15, \dots}$ , and the pattern of constant $15$ repeats all the way to infinity. However, when you run the brute-force algorithm on the actual puzzle input and print out the load values, we don’t observe a constant value.

What we instead observe is a cycle of values. For example, maybe we might see load values $\brackets{12, 16, 14, 17, 15, 19, 18, 15, 19, 18, 15, 19, 18, \dots}$ . In this example, we notice the repeating cycle of $\brackets{15, 19, 18}$ .

Based on this observation, I decided to cheat. Using the printouts, I manually identified the following repeating pattern:

[102851, 102834, 102831, 102829, 102827, 102828, 102837]

With only 7 possibilities, I submitted each of them until one of them was right. And it worked!

For completeness, I decided to make an automated solution.

Part 2 Automated Solution

The idea is that we directly calculate intermediate rockmaps and load values while running a cycle detection algorithm on top of it.

To directly calculate intermediate rockmaps, I chose to implement a function that rotates the the entire rockmap 90 degrees clockwise. Though, I could’ve instead just implemented a version of push_north() that just changes direction, or duplicated the push_north() function for each cardinal direction, but rotating the whole map just seemed simpler to me at the time.

Unfortunately, I went into this problem with not a lot of experience with cycle-detection algorithms, so there might be something better. Otherwise, my quick-and-dirty cycle detection algorithm works on the assumption that at the end of an iteration (i.e. after pushing north, then west, then south, then east), if the same rockmap appears a second time, then the sequence between and including the two appearances is a repeating cycle of maps. This is because the map itself contains all information on the state of the system at the particular time step. If state $A$ was previously seen to transition to state $B$ , then when we see state $A$ again, we know it will transition to state $B$ again.

But on the other hand, if we relied on just reading the load values, this cycle detection algorithm would be insufficient. For example, for the sequence of load values $\brackets{1, 2, 1, 3, 1, 2, 1, 3, \dots}$ , the algorithm may mistakenly think that the subsequence $\brackets{1, 2}$ is the repeated subsequence when the actual repeated subsequence is $\brackets{1, 2, 1, 3}$ . In this case, $1$ is not guaranteed to transition to the same load value each time. rockmap states don’t necessarily map one-to-one to load values (i.e. the mapping is not bijective), meaning that two different rockmap states may produce the same load value.

Once the cycle detection algorithm identifies the repeated subsequence, we use a bit of modular arithmetic to index into this repeated subsequence to get the final answer.

My full automated solution:

#!/usr/bin/env python3

from sys import stdin
from itertools import chain, product

TARGET_ITERATIONS = 1000000000

def rotate_grid(rockmap):
    new_map = []
    for j in range(len(rockmap[0])):
        new_row = []
        new_map.append(new_row)
        for i in reversed(range(len(rockmap))):
            new_row.append(rockmap[i][j])
    return new_map

def push_north(rockmap):
    for j in range(len(rockmap[0])):
        empty_i = 0
        for i in range(len(rockmap)):
            c = rockmap[i][j]
            if c == "#":
                empty_i = i + 1
            elif c == "O":
                rockmap[i][j] = "."
                rockmap[empty_i][j] = "O"
                empty_i += 1

def calculate_load(rockmap):
    return sum(
        len(rockmap) - i
        for i, j in product(range(len(rockmap)), range(len(rockmap[0])))
        if rockmap[i][j] == "O"
    )

def run(f):
    rockmap = [list(s.strip()) for s in f.readlines()]
    latest_i = {} # {stringified map: latest iteration}
    history = [] # loads

    dist = 0
    end_iteration = None
    for i in range(TARGET_ITERATIONS):
        for _ in range(4):
            push_north(rockmap)
            rockmap = rotate_grid(rockmap)
        s = "".join(chain(*rockmap))
        history.append(calculate_load(rockmap))
        if s in latest_i:
            dist = i - latest_i[s]
            end_iteration = i
            break
        latest_i[s] = i

    # we assume we actually do find a repeat
    # (not going to bother dealing with the edge case of no periodicity)
    if end_iteration is None:
        raise RuntimeError()

    repeated = history[-dist:] # just get the repeated section
    #print(repeated)
    print(repeated[(TARGET_ITERATIONS - end_iteration - 2) % len(repeated)])

run(stdin)

For completeness, let’s derive the section where I select the correct element of the repeated subsequence:

    repeated = history[-dist:] # just get the repeated section
    #print(repeated)
    print(repeated[(TARGET_ITERATIONS - end_iteration - 2) % len(repeated)])

The important pieces of information we have about the state of the main loop after break statement are:

the length of the repeated subsequence (dist),
the last iteration processed by the main loop (end_iteration), and
the history of load values from each completed iteration of the main loop (history).

Additionally, we also have:

the total number of iterations requested by the problem specification (TARGET_ITERATIONS).

For a concrete example, let’s assume:

\begin{gather*} \texttt{TARGET\_ITERATIONS} = 10 \\ \texttt{dist} = 3 \\ \texttt{end\_iteration} = 4 \end{gather*}

Visually, this looks like this:

All possible iterations:  0 1 2 3 4 5 6 7 8 9
`history`:                a b c d e
`repeated`:                   c d e
`end_iteration`:                  ^

Intuitively, we can overlay the repeated section over the remaining iterations:

0 1 2 3 4 5 6 7 8 9
a b c d e
          c d e
                c d

In this situation, it’s obvious that the final answer is repeated_section[1] since the final iteration (the 9th iteration) will produce load value d, which is the second element of repeated_section, which is index 1.

To derive a general solution, we start by cutting the conceptual array of all possible iterations at end_iteration:

All possible iterations:  0 1 2 3 4 5 6 7 8 9
Remaining iterations:               0 1 2 3 4

`repeated`:                   c d e
`end_iteration`:                  ^

The number of remaining iterations is:

\text{num remaining iterations} = \texttt{TARGET\_ITERATIONS} - \texttt{end\_iteration} - 1

For our concrete example, $\text{num remaining iterations} = 10 - 4 - 1 = 5$ .

Due to zero-indexing, to get solution for $n$ iterations, we must get the $n - 1$ , modulo the size of the repeated sequence.

In code, we might write this out as:

    repeated = history[-dist:] # just get the repeated section
    num_remaining_iterations = TARGET_ITERATIONS - end_iteration - 1
    print(repeated[(num_remaining_iterations - 1) % len(repeated)])

which can then be simplified to remove the num_remaining_iterations variable.

Day 15 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import product

def run(f):
    strs = f.readlines()[0].strip().split(",")

    solution = 0
    for s in strs:
        cur_hash = 0
        for c in s:
            cur_hash = ((cur_hash + ord(c)) * 17) % 256
        solution += cur_hash
    print(solution)

run(stdin)

Part 2 Solution

Such a pain in the ass verbose problem specification in terms of trying to parse out how the algorithm is supposed to work. At least Part 1 was super-simple and easy to skim. Part 2 has relatively many moving parts with the different parts spread out across the problem specification text. The question was obviously designed more as a reading comprehension problem than anything else really.

Along the way, I made two notable misunderstandings of the problem specification:

I originally thought each box held at most one lens. This led to misunderstanding the functionality of the - operation character, particularly the phrase “move any remaining lenses as far forward in the box as they can go without changing their order”. I assumed I was meant to shift the lenses to different boxes.
I originally obtained the box numbers by running the “HASH algorithm” over the entire command string (e.g. running the HASH algorithm over all four characters of rn=1) when it should only be run over the “label” portion of the command string (e.g. for rn=1, the label is rn).

My final solution after resolving all misunderstandings:

#!/usr/bin/env python3

from sys import stdin

def get_box_num(s):
    boxnum = 0
    for c in s:
        boxnum = ((boxnum + ord(c)) * 17) % 256
    return boxnum

def run(f):
    strs = f.readlines()[0].strip().split(",")

    boxes = [[] for _ in range(256)] # [[[label, focal length], ...], ...]
    for s in strs:
        if "-" in s:
            label = s[:-1]
            box = boxes[get_box_num(label)]
            box[:] = [x for x in box if (x[0] != label)]
        else:
            (label, focal_len) = s.split("=")
            box = boxes[get_box_num(label)]
            for tup in box:
                if tup[0] == label:
                    tup[1] = focal_len
                    break
            else:
                box.append([label, focal_len])

    print(sum(
        ((1 + boxnum) * sum(
            (i + 1) * int(focal_len) for i, (label, focal_len) in enumerate(box)
        ))
        for boxnum, box in enumerate(boxes)
    ))

run(stdin)

Day 16 [Spec]

Part 1 Solution

I went for a DFS solution, tracking both position (i and j) and facing direction unit vectors (i_dir and j_dir) at each step of the DFS.

We prevent infinite loops by conceptually keeping a set of (i, j, i_dir, j_dir) tuples. The actual implementation is a 2D grid of sets called seen, where the grid indices are i and j while each set stores the unit direction vectors that have passed through the grid location.

The DFS starts with travel(0, 0, 0, 1), meaning we start at the i=0 and j=0 (i.e. the top-left corner) and travelling in the direction of i_dir=0 and j_dir=1 (i.e. we are travelling in the positive-j direction).

#!/usr/bin/env python3

from sys import stdin, setrecursionlimit
from itertools import chain

def run(f):
    grid = [s.strip() for s in f.readlines()]
    setrecursionlimit(len(grid) * len(grid[0]))

    # grid of sets of unit directional vectors (i, j)
    seen = [[set() for _ in range(len(grid[0]))] for _ in range(len(grid))]

    def travel(i, j, i_dir, j_dir):
        if (i < 0) or (i >= len(grid)) \
                or (j < 0) or (j >= len(grid[0])) \
                or (i_dir, j_dir) in seen[i][j]:
            return
        seen[i][j].add((i_dir, j_dir))
        c = grid[i][j]
        if c == ".":
            travel(i + i_dir, j + j_dir, i_dir, j_dir)
        elif c == "|":
            if j_dir:
                travel(i + 1, j,  1, 0)
                travel(i - 1, j, -1, 0)
            else:
                travel(i + i_dir, j + j_dir, i_dir, j_dir)
        elif c == "-":
            if i_dir:
                travel(i, j + 1, 0,  1)
                travel(i, j - 1, 0, -1)
            else:
                travel(i + i_dir, j + j_dir, i_dir, j_dir)
        elif c == "/":
            travel(i - j_dir, j - i_dir, -j_dir, -i_dir)
        else: # "\"
            travel(i + j_dir, j + i_dir, j_dir, i_dir)
    travel(0, 0, 0, 1)

    print(sum(len(x) > 0 for x in chain(*seen)))

run(stdin)

I didn’t actually write out those elif c = "/": and else: branches like that the first time around. I originally wrote it out explicitly:

        elif c == "/":
            if j_dir == 1:
                travel(i - 1, j, -1, 0)
            elif j_dir == -1:
                travel(i + 1, j, 1, 0)
            elif i_dir == 1:
                travel(i, j - 1, 0, -1)
            else:
                travel(i, j + 1, 0, 1)
        else: # "\"
            if j_dir == 1:
                travel(i + 1, j, +1, 0)
            elif j_dir == -1:
                travel(i - 1, j, -1, 0)
            elif i_dir == 1:
                travel(i, j + 1, 0, 1)
            else:
                travel(i, j - 1, 0, -1)

Only after verifying I got the right answer did I refactor to the final version before moving on to Part 2.

Part 2 Solution

I refactored the Part 1 functionality into a new function calculate_coverage() before running calculate_coverage() on every possible entrypoint into the grid to get the final answer.

#!/usr/bin/env python3

from sys import stdin, setrecursionlimit
from itertools import chain

def calculate_coverage(grid, _i, _j, _i_dir, _j_dir):
    # grid of sets of unit directional vectors (i, j)
    seen = [[set() for _ in range(len(grid[0]))] for _ in range(len(grid))]

    def travel(i, j, i_dir, j_dir):
        if (i < 0) or (i >= len(grid)) \
                or (j < 0) or (j >= len(grid[0])) \
                or (i_dir, j_dir) in seen[i][j]:
            return
        seen[i][j].add((i_dir, j_dir))
        c = grid[i][j]
        if c == ".":
            travel(i + i_dir, j + j_dir, i_dir, j_dir)
        elif c == "|":
            if j_dir:
                travel(i + 1, j,  1, 0)
                travel(i - 1, j, -1, 0)
            else:
                travel(i + i_dir, j + j_dir, i_dir, j_dir)
        elif c == "-":
            if i_dir:
                travel(i, j + 1, 0,  1)
                travel(i, j - 1, 0, -1)
            else:
                travel(i + i_dir, j + j_dir, i_dir, j_dir)
        elif c == "/":
            travel(i - j_dir, j - i_dir, -j_dir, -i_dir)
        else: # "\"
            travel(i + j_dir, j + i_dir, j_dir, i_dir)
    travel(_i, _j, _i_dir, _j_dir)
    return sum(len(x) > 0 for x in chain(*seen))

def run(f):
    grid = [s.strip() for s in f.readlines()]
    setrecursionlimit(len(grid) * len(grid[0]))

    solution = 0
    for i in range(len(grid)): # left edge
        solution = max(solution, calculate_coverage(grid, i, 0, 0, 1))
    for i in range(len(grid)): # right edge
        solution = max(solution, calculate_coverage(grid, i, len(grid[0]) - 1, 0, -1))
    for j in range(len(grid[0])): # top edge
        solution = max(solution, calculate_coverage(grid, 0, j, 1, 0))
    for j in range(len(grid[0])): # bottom edge
        solution = max(solution, calculate_coverage(grid, len(grid) - 1, j, -1, 0))
    print(solution)

run(stdin)

Day 17 [Spec]

Part 1 Solution

I went for a Dijkstra’s algorithm solution. The cost of a path is the “heat loss”, and we further distinguish states not just by position (i and j), but also travelling-direction unit vectors (travel_i and travel_j) and the number of steps made in a straight line (moves).

#!/usr/bin/env python3

from sys import stdin
from math import inf
from heapq import heappush, heappop

def run(f):
    citymap = [s.strip() for s in f.readlines()]
    goal = (len(citymap) - 1, len(citymap[0]) - 1)

    seen = set()
    pq = [(0, 0, 0, 0, 1, 0)]
    def pqpush(cost, i, j, travel_i, travel_j, moves):
        if (0 <= i <= goal[0]) and (0 <= j <= goal[1]):
            heappush(pq, (cost + int(citymap[i][j]), i, j, travel_i, travel_j, moves))

    solution = inf
    while len(pq):
        (cost, i, j, travel_i, travel_j, moves) = heappop(pq)
        if (i, j, travel_i, travel_j, moves) in seen:
            continue
        if (i, j) == goal:
            print(cost)
            return
        seen.add((i, j, travel_i, travel_j, moves))
        if moves < 3:
            pqpush(cost, i + travel_i, j + travel_j, travel_i, travel_j, moves + 1)
        if travel_i:
            pqpush(cost, i, j + 1, 0, 1, 1)
            pqpush(cost, i, j - 1, 0, -1, 1)
        elif travel_j:
            pqpush(cost, i + 1, j, 1, 0, 1)
            pqpush(cost, i - 1, j, -1, 0, 1)
    raise RuntimeError()

run(stdin)

Part 2 Solution

The only modification from my Part 1 solution was the change to this new chunk of code:

        if moves < 10:
            pqpush(cost, i + travel_i, j + travel_j, travel_i, travel_j, moves + 1)
        if 4 <= moves <= 10:
            if travel_i:
                pqpush(cost, i, j + 1, 0, 1, 1)
                pqpush(cost, i, j - 1, 0, -1, 1)
            elif travel_j:
                pqpush(cost, i + 1, j, 1, 0, 1)
                pqpush(cost, i - 1, j, -1, 0, 1)

The full solution:

#!/usr/bin/env python3

from sys import stdin
from math import inf
from heapq import heappush, heappop

print("lmao")

def run(f):
    citymap = [s.strip() for s in f.readlines()]
    goal = (len(citymap) - 1, len(citymap[0]) - 1)

    seen = set()
    pq = [(0, 0, 0, 0, 1, 0)]
    def pqpush(cost, i, j, travel_i, travel_j, moves):
        if (0 <= i <= goal[0]) and (0 <= j <= goal[1]):
            heappush(pq, (cost + int(citymap[i][j]), i, j, travel_i, travel_j, moves))

    solution = inf
    while len(pq):
        (cost, i, j, travel_i, travel_j, moves) = heappop(pq)
        if (i, j, travel_i, travel_j, moves) in seen:
            continue
        if (i, j) == goal:
            print(cost)
            return
        seen.add((i, j, travel_i, travel_j, moves))
        if moves < 10:
            pqpush(cost, i + travel_i, j + travel_j, travel_i, travel_j, moves + 1)
        if 4 <= moves <= 10:
            if travel_i:
                pqpush(cost, i, j + 1, 0, 1, 1)
                pqpush(cost, i, j - 1, 0, -1, 1)
            elif travel_j:
                pqpush(cost, i + 1, j, 1, 0, 1)
                pqpush(cost, i - 1, j, -1, 0, 1)
    raise RuntimeError()

run(stdin)

Day 18 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import product

def run(f):
    digplan = [s.strip().split() for s in f.readlines()]
    digplan = [(_dir, int(_len)) for _dir, _len, _ in digplan]

    dugouts = {(0, 0)} # set of coordinates
    (i, j) = (0, 0)
    for _dir, _len in digplan:
        for _ in range(_len):
            if _dir == "U":
                i -= 1
            elif _dir == "D":
                i += 1
            elif _dir == "L":
                j -= 1
            elif _dir == "R":
                j += 1
            dugouts.add((i, j))

    i_lo_bound = min(i for i, _ in dugouts) - 1
    i_hi_bound = max(i for i, _ in dugouts) + 1
    j_lo_bound = min(j for _, j in dugouts) - 1
    j_hi_bound = max(j for _, j in dugouts) + 1

    nondugout = set()
    to_visit = [(i_lo_bound, j_lo_bound)] # initial coords guaranteed to be outside
    def floodfill_nondugout(i, j):
        if (i < i_lo_bound) or (i > i_hi_bound) \
                or (j < j_lo_bound) or (j > j_hi_bound) \
                or ((i, j) in dugouts) or ((i, j) in nondugout):
            return
        nondugout.add((i, j))
        for ii, jj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            to_visit.append((i + ii, j + jj))
    while len(to_visit):
        floodfill_nondugout(*to_visit.pop())

    print(sum(
        (i, j) not in nondugout
        for i, j in product(range(i_lo_bound, i_hi_bound + 1), range(j_lo_bound, j_hi_bound + 1))
    ))

run(stdin)

Part 2 TODO

I’m still trying to figure Part 2 out!

Day 19 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from collections import defaultdict

def evaluate_destination(raw_rules, part_data):
    for raw_rule in raw_rules:
        if ":" in raw_rule:
            (condition, send_to) = raw_rule.split(":")
            condition = condition.replace("x", str(part_data["x"]))
            condition = condition.replace("m", str(part_data["m"]))
            condition = condition.replace("a", str(part_data["a"]))
            condition = condition.replace("s", str(part_data["s"]))
            if eval(condition):
                return send_to
        else:
            return raw_rule
    raise RuntimeError()

def run(f):
    (workflows, parts) = "".join(f.readlines()).strip().split("\n\n")

    workflows = [s.split("{") for s in workflows.split()]
    workflows = {k: v[:-1].split(",") for k, v in workflows}

    parts = [[x.split("=") for x in s[1:-1].split(",")] for s in parts.split()]
    parts = [{k: int(v) for k, v in x} for x in parts]

    progress = defaultdict(set)
    progress["in"] = set(range(len(parts)))
    
    accepted = []

    while any(len(x) for x in progress.values()):
        progress2 = defaultdict(set)
        for workflow_id, cur_parts in progress.items():
            raw_rules = workflows[workflow_id]
            for part_id in cur_parts:
                send_to = evaluate_destination(raw_rules, parts[part_id])
                if send_to == "A":
                    accepted.append(parts[part_id])
                elif send_to != "R":
                    progress2[send_to].add(part_id)
        progress = progress2

    print(sum(sum(part.values()) for part in accepted))

run(stdin)

Part 2 Solution

#!/usr/bin/env python3

from sys import stdin

LOW_BOUND = 1
HIGH_BOUND = 4001

def new_range():
    return {s: [LOW_BOUND, HIGH_BOUND] for s in "xmas"}
def copy_range(x):
    return {k: v.copy() for k, v in x.items()}
def range_union(a, b): # can return None if empty union
    ret = {k: [max(a[k][0], b[k][0]), min(a[k][1], b[k][1])] for k in a.keys()}
    if any(hi <= lo for lo, hi in ret.values()):
        return None
    return ret

def parse_rules(raw_rules):
    out = []
    cur1 = new_range()
    raw_rules = raw_rules.split(",")
    for raw_rule in raw_rules:
        if ":" in raw_rule:
            (condition, label) = raw_rule.split(":")
            cur2 = copy_range(cur1)
            if "<" in condition:
                (var, boundary) = condition.split("<")
                boundary = int(boundary)
                cur2[var] = [cur1[var][0], boundary]
                cur1[var] = [boundary, cur1[var][1]]
                out.append((label, cur2))
            elif ">" in condition:
                (var, boundary) = condition.split(">")
                boundary = int(boundary)
                cur2[var] = [boundary + 1, cur1[var][1]]
                cur1[var] = [cur1[var][0], boundary + 1]
                out.append((label, cur2))
            else:
                raise RuntimeError("Unexpected operator")

            if (cur1[var][1] <= cur1[var][0]) or (cur2[var][1] <= cur2[var][0]):
                raise RuntimeError("Bad range")
        else:
            out.append((raw_rule, cur1))
    return out

def run(f):
    (workflows, _) = "".join(f.readlines()).strip().split("\n\n")

    workflows = [s.split("{") for s in workflows.split()]
    workflows = {k: parse_rules(v[:-1]) for k, v in workflows}

    accepted_ranges = []

    total_combos = 0
    def dfs(label, cur_range):
        nonlocal total_combos
        for nxt_label, condition_range in workflows[label]:
            union = range_union(cur_range, condition_range)
            if (not union) or (nxt_label == "R"):
                continue
            elif nxt_label == "A":
                accepted_ranges.append(union)
                # reduce is unnecessarily complicated for this, but it works lol
                #total_combos += reduce(
                #    lambda ac, cur: ac * (cur[1] - cur[0]),
                #    union.values(),
                #    1
                #)
                total_combos += (
                    (union["x"][1] - union["x"][0])
                    * (union["m"][1] - union["m"][0])
                    * (union["a"][1] - union["a"][0])
                    * (union["s"][1] - union["s"][0])
                )
            else:
                dfs(nxt_label, union)
    dfs("in", new_range())

    print(total_combos)

run(stdin)

Day 20 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from collections import defaultdict, deque

HI = True
LO = False

UNCATEGORIZED = "."
FLIPFLOP = "%"
CONJ = "&"

def run(f):
    raw_rules = [s.strip().split("->") for s in f.readlines()]
    raw_rules = [(k.strip(), [x.strip() for x in v.strip().split(",")]) for k, v in raw_rules]
    rules = {"output": (UNCATEGORIZED, [])}
    for k, v in raw_rules:
        if k[0] in FLIPFLOP + CONJ:
            module_type = k[0]
            k = k[1:]
        else:
            module_type = UNCATEGORIZED
        rules[k] = (module_type, v)

    # turns out there are modules that don't go anywhere
    dependencies = defaultdict(list)
    for src, (_, dsts) in rules.items():
        for dst in dsts:
            dependencies[dst].append(src)

    cur_states = {k: LO for k in rules.keys()}
    inputs_history = defaultdict(dict)
    conj_input_memory = {
        k: {dep: LO for dep in dependencies[k]}
        for k, v in rules.items() if v[0] == CONJ
    }

    dq = deque()
    (num_lo, num_hi) = (0, 0)
    for i in range(1000):
        dq.append(("button", LO, "broadcaster"))
        while len(dq):
            (src, pulse, dst) = dq.popleft()
            if pulse == HI:
                num_hi += 1
            else:
                num_lo += 1

            if dst not in rules:
                continue
            elif dst in {"broadcaster", "output"}:
                pass
            elif rules[dst][0] == FLIPFLOP:
                if pulse == LO:
                    cur_states[dst] = (cur_states[dst] != True)
                else:
                    continue # "nothing happens"
            elif rules[dst][0] == CONJ:
                conj_input_memory[dst][src] = pulse
                if all((v == HI) for v in conj_input_memory[dst].values()):
                    cur_states[dst] = LO
                else:
                    cur_states[dst] = HI
            else:
                raise RuntimeError()
            dq.extend((dst, cur_states[dst], x) for x in rules[dst][1])
    print(num_lo * num_hi)

run(stdin)

Part 2 TODO

I’m still trying to figure Part 2 out!

Day 21 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin, setrecursionlimit
from itertools import product

setrecursionlimit(10000)

NUM_STEPS = 64

def run(f):
    garden_map = ["#" + s.strip() + "#" for s in f.readlines()]
    garden_map.insert(0, "#"*len(garden_map[0]))
    garden_map.append("#"*len(garden_map[0]))
    (len1, len2) = (len(garden_map), len(garden_map[0]))

    start = None
    for i, j in product(range(len1), range(len2)):
        if garden_map[i][j] == "S":
            start = (i, j)
            break
    if start == None:
        raise RuntimeError()

    seen = set()
    solution = set()
    def bfs(i, j, steps_remaining):
        if ((i, j, steps_remaining) in seen) or (garden_map[i][j] == "#"):
            return
        seen.add((i, j, steps_remaining))
        if steps_remaining == 0:
            solution.add((i, j))
            return
        for ii, jj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            bfs(i + ii, j + jj, steps_remaining - 1)
    bfs(*start, NUM_STEPS)
    print(len(solution))

run(stdin)

Part 2 TODO

I’m still trying to figure Part 2 out!

Day 22 [Spec]

Part 1 TODO

I’m still trying to figure Part 1 out!

Part 2 TODO

Still not up to Part 2!

Day 23 [Spec]

Part 1 TODO

I’m still trying to figure Part 1 out!

Part 2 TODO

Still not up to Part 2!

Day 24 [Spec]

Part 1 Mathematics Discussion

Mathy question! Let’s start with some mathematical analysis.

The simplest starting point to me seems to be to consider the parametric form of the straight line. We’re only dealing with the $x$ and $y$ coordinates, so we’re obviously only dealing with 2D space.

For the hailstone initial position vector $\myvec{p}$ and velocity vector $\myvec{v}$ , we can get the position vector $\myvec{x}\parens{t}$ at time $t$ :

\myvec{x}\parens{t} = \myvec{p} + \myvec{v} t

Positions of the hailstone in the future will happen at $t > 0$ , while positions “in the past” happened at $t < 0$ .

Let’s try to find where two hailstones intersect. We’ll need two equations:

\begin{gather*} \myvec{x}_0 \parens{t_0} = \myvec{p}_0 + \myvec{v}_0 t_0 \tag{d24e1} \\ \myvec{x}_1 \parens{t_1} = \myvec{p}_1 + \myvec{v}_1 t_1 \tag{d24e2} \end{gather*}

We use two separate time variables rather than the same one since we’re only looking if the paths will intersect, not necessarily that the hailstones will actually collide.

The two paths intersect when $\myvec{x}_0 \parens{t_0} = \myvec{x}_1 \parens{t_1}$ , so we can find the $t_0$ and $t_1$ values with:

\myvec{p}_0 + \myvec{v}_0 t_0 = \myvec{p}_1 + \myvec{v}_1 t_1

At this point, it can be helpful to just break it up into component equations, then solve for one of the $t$ variables:

\begin{gather*} \begin{cases} p_{0x} + v_{0x} t_0 = p_{1x} + v_{1x} t_1 \\ p_{0y} + v_{0y} t_0 = p_{1y} + v_{1y} t_1 \end{cases} \tag{d24e3} \\ \begin{cases} t_0 = \frac{p_{1x} - p_{0x} + v_{1x} t_1}{v_{0x}} \\ t_0 = \frac{p_{1y} - p_{0y} + v_{1y} t_1}{v_{0y}} \end{cases} \\ \frac{p_{1x} - p_{0x} + v_{1x} t_1}{v_{0x}} = \frac{p_{1y} - p_{0y} + v_{1y} t_1}{v_{0y}} \\ \frac{p_{1x} - p_{0x}}{v_{0x}} - \frac{p_{1y} - p_{0y}}{v_{0y}} = \frac{v_{1y} t_1}{v_{0y}} - \frac{v_{1x} t_1}{v_{0x}} \\ \frac{p_{1x} - p_{0x}}{v_{0x}} - \frac{p_{1y} - p_{0y}}{v_{0y}} = t_1 \parens{ \frac{v_{1y}}{v_{0y}} - \frac{v_{1x}}{v_{0x}} } \end{gather*}

\begin{align*} t_1 &= \frac{ \frac{p_{1x} - p_{0x}}{v_{0x}} - \frac{p_{1y} - p_{0y}}{v_{0y}} }{ \frac{v_{1y}}{v_{0y}} - \frac{v_{1x}}{v_{0x}} } = \frac{ v_{0y} \frac{p_{1x} - p_{0x}}{v_{0x}} - \parens{p_{1y} - p_{0y}} }{ v_{1y} - v_{0y} \frac{v_{1x}}{v_{0x}} } \\ &= \frac{ v_{0y} \parens{p_{1x} - p_{0x}} - v_{0x} \parens{p_{1y} - p_{0y}} }{ v_{0x} v_{1y} - v_{0y} v_{1x} } \tag{d24e4} \end{align*}

To solve for the other variable $t_0$ , we can simply plug the result of $t_1$ it back into either of the component equations (d24e3). For my Part 1 solution, I will use either of these equations depending on whether the denominators are zero:

\begin{align*} t_0 = \frac{p_{1x} - p_{0x} + v_{1x} t_1}{v_{0x}} \\ t_0 = \frac{p_{1y} - p_{0y} + v_{1y} t_1}{v_{0y}} \end{align*}

TODO: Huh. So if either

v_{0x}

v_{0y}

is zero, that means one of the equations evaluates to an undefined value… intuitively, that makes sense since in one dimension, it will have to be undefined but not in the other dimension. But does that actually make sense mathematically? I should look more into this line of reasoning because I’m not happy with it. Please let me know if there’s a better way of thinking about it!

Since the question is asking for where the paths intersect only considering the future, we can simply check if both $t_0$ and $t_1$ are positive.

Now, we’ll need to consider how we can handle the edge cases of these results.

Intuitively (and assuming the the past also counts as part of the path), these edge cases are:

What if the paths are parallel but never intersect? In this case, the paths will never intersect.
What if paths are exactly the same? In this case, we’d need to check if the intersection region happens for positive $t_0$ and $t_1$ .
What if any velocity is zero?

I quickly checked the input for zero velocities as a sanity check. We found no zero velocities, so we can neglect to look for this edge case. Code snippet used (this code snippet will make sense in the context of my final solution):

def run(f):
    stones = [
        [[int(y.strip()) for y in x.strip().split(",")] for x in s.strip().split("@")]
        for s in f.readlines()
    ]
    if any(all(x == 0 for x in v) for _, v in stones):
        raise RuntimeError(f"We expect no zero velocities.")

If any path is parallel but not the same, we intuitively expect to see no possible solution for $t_0$ or $t_1$ . If the paths are the same, then we expect to see infinite solutions.

A simple method used by a human might be to first check if the denominator of (d24e4) is zero, and if so, try checking if any hailstone’s $t = 0$ position is a solution to the other hailstone’s position equation for $t \ge 0$ . If this is true for either hailstone in the manner described, then we know their future paths intersect, otherwise they don’t.

Let’s try some concrete examples. Suppose we have two lines with a slope of $\frac{y}{x} = 1$ :

\begin{gather*} \myvec{p}_0 = {\begin{pmatrix} 0 \\ 0 \end{pmatrix}} \qquad \myvec{v}_0 = {\begin{pmatrix} 1 \\ 1 \end{pmatrix}} \\ \myvec{p}_1 = {\begin{pmatrix} 2 \\ 2 \end{pmatrix}} \qquad \myvec{v}_1 = {\begin{pmatrix} -1 \\ -1 \end{pmatrix}} \end{gather*}

Using (d24e4), we see we get an undefined result:

t_1 = \frac{ 1 \parens{2 - 0} - 1 \parens{2 - 0} }{ 1 \parens{-1} - 1 \parens{-1} } = \frac{2 - 2}{\parens{-1} - \parens{-1}}

Let’s try solving for $t_1$ if $\myvec{p}_0 = \myvec{x}_1 \parens{t_1}$ . From (d12e2):

\begin{gather*} {\begin{pmatrix} 0 \\ 0 \end{pmatrix}} = {\begin{pmatrix} 2 \\ 2 \end{pmatrix}} + {\begin{pmatrix} -1 \\ -1 \end{pmatrix}} t_1 \end{gather*}

It is trivial to see that this equation is valid and results in $t_1 = 2$ . Since this is positive, we know that $\myvec{p}_0$ is a valid solution for the $\myvec{x}_1$ hailstone for positive $t_1$ .

Part 1 Solution

With all the math sorted out in the previous section, the implementation is actually quite straightforward! We just look at every pair of hailstones and count the intersections.

#!/usr/bin/env python3

from sys import stdin
from itertools import combinations

#LOWER = 7
#UPPER = 27
LOWER = 200000000000000
UPPER = 400000000000000

def paths_intersect_within_bounds(p0, v0, p1, v1):
    denom = (v0[0] * v1[1]) - (v0[1] * v1[0])
    if denom == 0:
        # case 1: parallel lines
        t0_x = (p1[0] - p0[0]) / v0[0]
        t0_y = (p1[1] - p0[1]) / v0[1]
        t1_x = (p0[0] - p1[0]) / v1[0]
        #t1_y = (p0[1] - p1[1]) / v1[1] # don't need this one
        return (t0_x == t0_y) and ((t0_x >= 0) or (t1_x >= 0))
    else:
        # case 2: non-parallel lines
        num = (v0[1] * (p1[0] - p0[0])) - (v0[0] * (p1[1] - p0[1]))
        t1 = num / denom
        i = 0 if v0[0] else 1
        t0 = (p1[i] - p0[i] + (v1[i] * t1)) / v0[i]
        if (t0 < 0) or (t1 < 0):
            return False # Intersection is in the past
        x1 = (p1[0] + (v1[0] * t1), p1[1] + (v1[1] * t1))
        return (LOWER <= x1[0] <= UPPER) and (LOWER <= x1[1] <= UPPER)

def run(f):
    stones = [
        [[int(y.strip()) for y in x.strip().split(",")] for x in s.strip().split("@")]
        for s in f.readlines()
    ]
    if any(all(x == 0 for x in v) for _, v in stones):
        raise RuntimeError(f"We expect no zero velocities.")

    print(sum(paths_intersect_within_bounds(*a, *b) for a, b in combinations(stones, 2)))
    print("Note: You may need to change constants depending on test case.")

run(stdin)

Part 2 Mathematics Discussion

The first approach I will try is to grab any two hailstones and come up with some set of solutions to throw a rock such that it will hit both hailstones. Such a set of solutions may be parameterized in some way to account for every possible way the two hailstones can be hit.

Once we have the set of solutions, we can try introducing another hailstone to somehow narrow down this set of solutions. And as long as there’s only one solution, surely that should be the one solution that works for the full set of hailstones? It may even be possible that we solve this entirely analytically without writing any code.

Let’s try it out!

Same as with Part 1, let’s begin with two hailstone trajectories, though the vectors are now in $\Reals^3$ . We use the same time variable now since we need the actual hailstone position at a point in time.

\begin{gather*} \myvec{x}_0 \parens{t} = \myvec{p}_0 + \myvec{v}_0 t \tag{d24e5} \\ \myvec{x}_1 \parens{t} = \myvec{p}_1 + \myvec{v}_1 t \tag{d24e6} \end{gather*}

The rock trajectory will be defined the same way, but with an $x$ subscript:

\myvec{x}_x \parens{t} = \myvec{p}_x + \myvec{v}_x t \tag{d24e7}

TODO: Haven’t finished this yet!

Part 2 TODO

I’m still trying to figure Part 2 out!

Day 25 [Spec]

Part 1 TODO

Day 25 hasn’t released yet (as of writing)!

Part 2 TODO

Day 25 hasn’t released yet (as of writing)!