Advent of Code 2024 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

pairs = [tuple(map(int, s.split())) for s in stdin.readlines()]

(a, b) = (sorted([x[0] for x in pairs]), sorted([x[1] for x in pairs]))
print(sum(abs(x - y) for (x, y) in zip(a, b)))

Part 2 Solution

#!/usr/bin/env python3

from sys import stdin
from collections import Counter

pairs = [tuple(map(int, s.split())) for s in stdin.readlines()]

cnt = Counter(x[1] for x in pairs)
print(sum(x[0] * cnt[x[0]] for x in pairs))

---

Day 2 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import pairwise

reports = [[int(x) for x in s.split()] for s in stdin.readlines()]
reports = [r for r in reports if (r == sorted(r) or r == sorted(r, reverse=True))]
print(sum(all(0 < abs(a - b) < 4 for a, b in pairwise(r)) for r in reports))

Part 2 Solution

My first solution:

In an attempt to make a more compact solution, I reimplemented with a lambda:

#!/usr/bin/env python3

from sys import stdin
from itertools import pairwise

is_safe = lambda r: (r == sorted(r) or r == sorted(r, reverse=True)) \
    and all(0 < abs(a - b) < 4 for a, b in pairwise(r))

reports = [[int(x) for x in s.split()] for s in stdin.readlines()]
print(sum(any(is_safe(r[:i] + r[i+1:]) for i in range(len(r) + 1)) for r in reports))

---

Day 3 [Spec]

Part 1 Solution

I cheated by using eval() rather than parsing out the mul() myself:

#!/usr/bin/env python3

from sys import stdin
from re import findall
from operator import mul

lines = "".join(stdin.readlines())
print(sum(eval(s) for s in findall(r"mul\([0-9]{1,3},[0-9]{1,3}\)", lines)))

Part 2 Solution

My first solution, retaining the use of eval():

My attempt at making a more compact solution:

#!/usr/bin/env python3

from sys import stdin
from re import findall
from operator import mul

lines = "".join(stdin.readlines())

solution = 0
do_mul = True
for s, do, _ in findall(r"(mul\([0-9]{1,3},[0-9]{1,3}\))|(do\(\))|(don't\(\))", lines):
    if not s:
        do_mul = do
    elif do_mul:
        solution += eval(a)
print(solution)

---

Day 4 [Spec]

Part 1 Solution

My first attempt gets the right solution, but the approach is quite ugly:

#!/usr/bin/env python3

from sys import stdin

arr1 = [s.strip() for s in stdin.readlines()]
arr2 = ["".join(arr1[i][j] for i in range(len(arr1))) for j in range(len(arr1[0]))]
if len(arr2) > len(arr1):
    (arr1, arr2) = (arr2, arr1)
(len1, len2) = (len(arr1), len(arr1[0]))

arr1b = [" "*len2]*len1 + arr1 + [" "*len2] + list(reversed(arr1)) + [" "*len2]*len1
arr3 = ["".join(arr1b[x + i][i] for i in range(len2)) for x in range((len1 * 3) + 1)]
print(sum(s.count("XMAS") + s.count("SAMX") for s in arr1 + arr2 + arr3))

(Yes, I’m just trying to make meme solutions. That’s why it’s so ugly lol.)

Alternative, nicer solution that just indexes into the existing graph:

#!/usr/bin/env python3

from sys import stdin
from itertools import product

arr = [s.strip() + "." for s in stdin.readlines()]
arr.append("."*len(arr[0]))

def found(i, j, di, dj, pos):
    return (pos == 4) or ((arr[i][j] == "XMAS"[pos]) and found(i+di, j+dj, di, dj, pos+1))

it = product(range(len(arr)), range(len(arr[0])), [-1, 0, 1], [-1, 0, 1])
print(sum(found(i, j, di, dj, 0) for i, j, di, dj in it if (di != 0 or dj != 0)))

Part 2 Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import product

arr = [s.strip() for s in stdin.readlines()]

def found(i, j):
    return arr[i+1][j+1] == "A" \
        and "SSMMSSM".count(arr[i][j] + arr[i+2][j] + arr[i+2][j+2] + arr[i][j+2])
print(sum(found(i, j) for i, j in product(range(len(arr) - 2), range(len(arr[0]) - 2))))

---

Day 5 [Spec]

Part 1 Solution

Things are getting a bit tough to make meme solutions, so I went for whatever works this time around. This got me the right answer quickly:

But its runtime was pretty terrible. Doesn’t matter though since solutions aren’t timed. It only took a couple seconds anyway.

In preparation for Part 2, I converted the rules to a dict:

More-compact solution:

#!/usr/bin/env python3

from sys import stdin
from itertools import product, combinations

rules, updates = "".join(stdin.readlines()).strip().split("\n\n")
rules = [s.split("|") for s in rules.split()]
updates = [s.split(",") for s in updates.split()]
print(sum(
    int(update[len(update) >> 1]) for update in updates
    if not any((x, y) == (b, a) for (x, y), (a, b) in product(rules, combinations(update, 2)))
))

Part 2 Solution

Naive topological sort since it’s easier and it ran fast enough for this problem anyway:

More-compact (and honestly more-readable) solution that takes advantage of built-in sort:

#!/usr/bin/env python3

from sys import stdin
from itertools import combinations
from functools import cmp_to_key
from collections import defaultdict

_rules, updates = "".join(stdin.readlines()).strip().split("\n\n")
rules = defaultdict(set)
for a, b in (s.split("|") for s in _rules.split()):
    rules[int(a)].add(int(b))
updates = [[int(x) for x in s.split(",")] for s in updates.split()]

key_fn = cmp_to_key(lambda a, b: 1 if (a in rules[b]) else -1)
print(sum(
    sorted(update, key=key_fn)[len(update) >> 1] for update in updates
    if any((a in rules[b]) for a, b in combinations(update, 2))
))

---

Day 6 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import chain

grid = [list(s.strip()) + [" "] for s in stdin.readlines()]
grid.append([" "]*len(grid[0]))
(i, j, di, dj) = (None, None, -1, 0)
for _i, lst in enumerate(grid):
    for _j, v in enumerate(lst):
        if v == "^":
            (i, j) = (_i, _j)
            break

while grid[i][j] != " ":
    grid[i][j] = "X"
    if grid[i + di][j + dj] == "#":
        (di, dj) = (dj, -di)
    (i, j) = (i + di, j + dj)
print(sum((x == "X") for x in chain(*grid)))

A technically more compact solution, but I think it’s too unnecessarily unreadable:

Part 2 Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import chain

DIRS = {"U": "R", "R": "D", "D": "L", "L": "U"}

grid = [list(s.strip()) + [" "] for s in stdin.readlines()]
grid.append([" "]*len(grid[0]))
(si, sj, d, di, dj) = (None, None, "U", -1, 0)  # s = "start", d = "direction"
for _i, lst in enumerate(grid):
    for _j, v in enumerate(lst):
        if v == "^":
            (si, sj) = (_i, _j)
            break

(i, j) = (si, sj)
possible_positions = set()
while grid[i][j] != " ":
    if grid[i + di][j + dj] == "#":
        (di, dj, d) = (dj, -di, DIRS[d])
    possible_positions.add((i, j))
    (i, j) = (i + di, j + dj)
possible_positions.discard((si, sj))

def has_cycle(bi, bj):  # b = "barrier position"
    if grid[bi][bj] == " ":
        raise RuntimeError()
    grid2 = [lst.copy() for lst in grid]
    grid2[bi][bj] = "#"
    (i, j, d, di, dj) = (si, sj, "U", -1, 0)
    while True:
        while grid2[i + di][j + dj] == "#":
            (di, dj, d) = (dj, -di, DIRS[d])
        if grid2[i + di][j + dj] == " ":
            break
        if grid2[i][j] == d:
            return True
        grid2[i][j] = d
        (i, j) = (i + di, j + dj)
    return False
print(sum(has_cycle(bi, bj) for bi, bj in possible_positions))

We could technically make the solution more compact by using the same thing we did for Part 1, but again, it makes it unnecessarily unreadable to me.

---

Day 7 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from functools import reduce
from itertools import product
from operator import add, mul

arr = [s.split(":") for s in stdin.readlines()]
arr = [(int(lhs), [int(x) for x in rhs.split()]) for lhs, rhs in arr]
print(sum(
    lhs for lhs, rhs in arr
    if any(
        reduce((lambda ac, cur: cur[0](ac, cur[1])), zip(ops, rhs), 0) == lhs
        for ops in product([add], *([[add, mul]] * (len(rhs) - 1)))
    )
))

Part 2 Solution

#!/usr/bin/env python3

from sys import stdin
from functools import reduce
from itertools import product
from operator import add, mul

conc = lambda a, b: int(str(a) + str(b))

arr = [s.split(":") for s in stdin.readlines()]
arr = [(int(lhs), [int(x) for x in rhs.split()]) for lhs, rhs in arr]
print(sum(
    lhs for lhs, rhs in arr
    if any(
        reduce((lambda ac, cur: cur[0](ac, cur[1])), zip(ops, rhs), 0) == lhs
        for ops in product([add], *([[add, mul, conc]] * (len(rhs) - 1)))
    )
))

---

Day 8 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from collections import defaultdict
from itertools import chain, combinations

grid = [s.strip() for s in stdin.readlines()]
antennae = defaultdict(list)
for i, s in enumerate(grid):
    for j, v in enumerate(s):
        if v != ".":
            antennae[v].append((i, j))

antinodes = set()
for (i1, j1), (i2, j2) in chain(*(combinations(v, 2) for k, v in antennae.items())):
    antinodes.add((i2 + i2 - i1, j2 + j2 - j1))
    antinodes.add((i1 - (i2 - i1), j1 - (j2 - j1)))
print(sum((0 <= i < len(grid) and 0 <= j < len(grid[0])) for i, j in antinodes))

Part 2 Solution

#!/usr/bin/env python3

from sys import stdin
from collections import defaultdict
from itertools import chain, combinations

grid = [s.strip() for s in stdin.readlines()]
antennae = defaultdict(list)
for i, s in enumerate(grid):
    for j, v in enumerate(s):
        if v != ".":
            antennae[v].append((i, j))

antinodes = set()
for (i1, j1), (i2, j2) in chain(*(combinations(v, 2) for k, v in antennae.items())):
    (i, j, di, dj) = (i2, j2, i2 - i1, j2 - j1)
    while (0 <= i < len(grid) and 0 <= j < len(grid[0])):
        antinodes.add((i, j))
        (i, j) = (i + di, j + dj)
    (i, j) = (i1, j1)
    while (0 <= i < len(grid) and 0 <= j < len(grid[0])):
        antinodes.add((i, j))
        (i, j) = (i - di, j - dj)
print(len(antinodes))

---

Day 9 [Spec]

Part 1 Solution

#!/usr/bin/env python3

from sys import stdin
from itertools import chain

diskmap = stdin.readline().strip()

disk = list(chain(*([None if (i % 2) else (i >> 1)]*int(v) for i, v in enumerate(diskmap))))
i = 0
while i < len(disk):
    if disk[i] is None:
        while disk[-1] is None:
            disk.pop()
        disk[i] = disk.pop()
    i += 1
print(sum(i * v for i, v in enumerate(disk)))

Part 2 Solution

I attempted a Heap-based solution initially, but kept running into issues. In the end, I realized that my heap-based idea always assumes that you will always take the left-most of the largest contiguous sequence. For example, suppose you need to reallocate ID=2 here:

00..111....22

The actual correct answer here is to move it between the 0 and 1:

0022111......

However, my heap-based solution will place it after the 1 because that’s how the heap is sorted:

00..11122....

I reimplemented using a much more naive algorithm. It takes quite a fair while to run, but it got me my answer:

#!/usr/bin/env python3

from sys import stdin

diskmap = [int(x) for x in stdin.readline().strip()]

disk = []   # [ID, ...]
allocs = [] # [(ID, position, length), ...]
for i, v in enumerate(diskmap):
    if i % 2:
        disk += [None]*v
    elif v != 0:
        allocs.append((i >> 1, len(disk), v))
        disk += [i >> 1]*v

for a_id, a_pos, a_len in reversed(allocs):
    (empty_pos, empty_size) = (0, 0)
    for i, v in enumerate(disk[:a_pos]):
        if v is None:
            empty_size += 1
        else:
            (empty_pos, empty_size) = (i + 1, 0)
        if empty_size == a_len:
            for i in range(a_pos, a_pos + a_len):
                disk[i] = None
            for i in range(empty_pos, empty_pos + a_len):
                disk[i] = a_id
            break

print(sum(i * v for i, v in enumerate(disk) if (v is not None)))

---

Day 10 [Spec]

Part 1 Solution

I skimmed the problem specification and accidentally solved Part 2 first.

When I reread the problem, I realized what Part 1 was actually asking me for, which brings me to my first correct solution for Part 1:

#!/usr/bin/env python3

from sys import stdin

tmap = [[int(c) for c in s.strip()] + [11] for s in stdin.readlines()]
tmap.append([11]*len(tmap[0]))

def dfs(i, j, expected):
    if tmap[i][j] != expected:
        return set()
    if expected == 9:
        return {(i, j)}
    partial = set()
    for _i, _j in ((i + di, j + dj) for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]):
        partial |= dfs(_i, _j, expected + 1)
    return partial

print(sum(sum(len(dfs(i, j, 0)) for j, c in enumerate(s)) for i, s in enumerate(tmap)))

I made an attempt at making a more-compact solution, but it ends up quite unnecessarily unreadable:

Part 2 Solution

By the time I got to Part 2, I didn’t have to do anything because I already accidentally wrote it for Part 1!

#!/usr/bin/env python3

from sys import stdin

tmap = [[int(c) for c in s.strip()] + [11] for s in stdin.readlines()]
tmap.append([11]*len(tmap[0]))

def dfs(i, j, expected):
    if tmap[i][j] != expected:
        return 0
    if expected == 9:
        return 1
    it = ((i + di, j + dj) for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)])
    return sum(dfs(_i, _j, expected + 1) for _i, _j in it)

print(sum(sum(dfs(i, j, 0) for j, c in enumerate(s)) for i, s in enumerate(tmap)))

I made some attempts at writing a more-compact solution, but it really sacrifices readability and actually bloats the logic a bit:

---

Day 11 [Spec]

Part 1 Solution

I went for a naive simulation solution:

#!/usr/bin/env python3

from sys import stdin

BLINKS = 25

stones = [int(x) for x in stdin.readline().split()]
for _ in range(BLINKS):
    for i in reversed(range(len(stones))):
        if stones[i] == 0:
            stones[i] = 1
        elif len(str(stones[i])) % 2:
            stones[i] *= 2024
        else:
            s = str(stones[i])
            (left, right) = (int(s[:(len(s) >> 1)]), int(s[(len(s) >> 1):]))
            stones[i] = right
            stones.insert(i, left)

print(len(stones))

Part 2 Solution

Part 1 runs far too slow.

In hindsight, this is obviously solveable with dp:

#!/usr/bin/env python3

from sys import stdin
from functools import cache

BLINKS = 75

@cache
def count_stones(num, blinks):
    if blinks == 0:
        return 1
    elif num == 0:
        return count_stones(1, blinks - 1)
    elif len(str(num)) % 2:
        return count_stones(num * 2024, blinks - 1)
    else:
        s = str(num)
        (left, right) = (int(s[:(len(s) >> 1)]), int(s[(len(s) >> 1):]))
        return count_stones(left, blinks - 1) + count_stones(right, blinks - 1)

stones = [int(x) for x in stdin.readline().split()]
print(sum(count_stones(v, BLINKS) for v in stones))