AoC 2021

day01.py

with open("../inputs/2021/day01.input") as f:
    inp = list(map(int, f.readlines()))


def part1(inp):
    return sum(a < b for a, b in zip(inp, inp[1:]))


def part2(inp):
    return sum(a < b for a, b in zip(inp, inp[3:]))


print(f"Part 1: {part1(inp)}")
print(f"Part 2: {part2(inp)}")

day01.rs

pub fn read(inp: &str) -> Vec<usize> {
    inp.trim()
        .split('\n')
        .map(|word| word.parse::<usize>().unwrap())
        .collect()
}

pub fn part1(inp: &[usize]) -> usize {
    inp.iter()
        .zip(inp[1..].iter())
        .filter(|(a, b)| b > a)
        .count()
}

pub fn part2(inp: &[usize]) -> usize {
    inp.iter()
        .zip(inp[3..].iter())
        .filter(|(a, b)| b > a)
        .count()
}

pub fn run() -> (String, String) {
    let inp = include_str!(concat!(env!("CARGO_MANIFEST_DIR"), "/inputs/day01.input"));
    let data = read(inp);
    let a = part1(&data).to_string();
    let b = part2(&data).to_string();
    (a, b)
}

day02.py

F = object()
D = object()


with open("../inputs/2021/day02.input", "r") as f:
    moves = []
    for line in f.read().strip().split("\n"):
        if line[0] == "f":
            moves.append((F, int(line[8:])))
        elif line[0] == "d":
            moves.append((D, int(line[5:])))
        elif line[0] == "u":
            moves.append((D, -int(line[3:])))
        else:
            raise ValueError


def part1(moves):
    h, d = 0, 0
    for (move, n) in moves:
        if move is F:
            h += n
        else:
            d += n
    return h*d


def part2(moves):
    h, d, a = 0, 0, 0
    for (move, n) in moves:
        if move is F:
            h += n
            d += a * n
        else:
            a += n
    return h*d


print(f"Part 1: {part1(moves)}")
print(f"Part 2: {part2(moves)}")

day02.rs

#[derive(Debug)]
pub enum Move {
    F(i32),
    D(i32),
}

fn parse(word: &str) -> Move {
    match word.chars().next() {
        Some('f') => Move::F(word[8..].parse::<i32>().unwrap()),
        Some('d') => Move::D(word[5..].parse::<i32>().unwrap()),
        Some('u') => Move::D(-word[3..].parse::<i32>().unwrap()),
        _ => unreachable!(),
    }
}

pub fn read(inp: &str) -> Vec<Move> {
    inp.trim().split('\n').map(parse).collect()
}

pub fn part1(inp: &[Move]) -> i32 {
    let mut h: i32 = 0;
    let mut d: i32 = 0;
    for m in inp {
        match m {
            Move::F(n) => h += n,
            Move::D(n) => d += n,
        }
    }
    h * d
}

pub fn part2(inp: &[Move]) -> i32 {
    let mut h: i32 = 0;
    let mut a: i32 = 0;
    let mut d: i32 = 0;
    for m in inp {
        match m {
            Move::F(n) => {
                h += n;
                d += a * n;
            }
            Move::D(n) => a += n,
        }
    }
    h * d
}

pub fn run() -> (String, String) {
    let inp = include_str!(concat!(env!("CARGO_MANIFEST_DIR"), "/inputs/day02.input"));
    let data = read(inp);
    (part1(&data).to_string(), part2(&data).to_string())
}

day03.py

with open("../inputs/2021/day03.input") as f:
    inp = [[int(c) for c in line.strip()]
           for line in f.readlines()]


def part1(inp: list[list[int]]) -> int:
    N, n = len(inp), len(inp[0])
    N = (N + 1) // 2
    gamma = sum((c >= N) << (n - i - 1)
                for i, c in enumerate(map(sum, zip(*inp))))
    return gamma * ((1 << n) - 1 - gamma)


def prune(inp: list[list[int]], bit: int, flip: bool) -> int:
    keep = flip ^ (sum(b[bit] for b in inp) >= (len(inp) + 1) // 2)
    filtered = [b for b in inp if b[bit] == keep]
    try:
        x, = filtered
        n = len(x) - 1
        return sum(c << (n - i) for i, c in enumerate(x))
    except ValueError:
        return prune(filtered, bit+1, flip)


def part2(inp: list[list[int]]) -> int:
    return prune(inp, 0, False)*prune(inp, 0, True)


print(f"Part 1: {part1(inp)}")
print(f"Part 2: {part2(inp)}")

day03.rs

const N: usize = 12;

pub fn read(inp: &str) -> Vec<u32> {
    inp.trim()
        .split('\n')
        .map(|word| u32::from_str_radix(word, 2).unwrap())
        .collect()
}

pub fn part1(inp: &[u32]) -> u32 {
    let n = ((inp.len() + 1) / 2) as u32;
    let mut gamma = 0;
    for i in 0..N {
        let mut t = 0;
        for &b in inp {
            t += ((b & (1 << i)) != 0) as u32;
        }
        let b = (t >= n) as u32;
        gamma |= (1 << i) * b;
    }
    gamma * ((1 << N) - 1 - gamma)
}

#[inline]
fn prune(inp: &[u32], mut bit: u32, flip: bool) -> u32 {
    let mut pruned = inp.to_owned();
    while pruned.len() != 1 {
        let t = pruned.iter().filter(|&b| b & bit != 0).count();
        let keep = ((flip as u32) * bit) ^ (if 2 * t >= pruned.len() { bit } else { 0 });
        pruned = pruned
            .into_iter()
            .filter(|&bits| bits & bit == keep)
            .collect();
        bit >>= 1;
    }
    pruned[0]
}

pub fn part2(inp: &[u32]) -> u32 {
    prune(inp, 1 << (N - 1), false) * prune(inp, 1 << (N - 1), true)
}

pub fn run() -> (String, String) {
    let inp = include_str!(concat!(env!("CARGO_MANIFEST_DIR"), "/inputs/day03.input"));
    let data = read(inp);
    let a = part1(&data).to_string();
    let b = part2(&data).to_string();
    (a, b)
}

day04.py

from itertools import product
from operator import lt, gt

N = 5
with open("../inputs/2021/day04.input") as f:
    moves, *boards = f.read().split("\n\n")
    moves = list(map(int, moves.strip().split(",")))
    boards = [list(map(int, board.strip().split()))
              for board in boards]


def time_to_win(board, times):
    col = [0] * N
    row = [0] * N
    for (r, c), n in zip(product(range(N), range(N)),
                         board):
        t = times[n]
        col[c] = max(col[c], t)
        row[r] = max(row[r], t)
    return min(*col, *row)


def solve(moves, boards, cmp, init):
    idx = 0
    win = init
    times = moves[:]
    for i, n in enumerate(moves):
        times[n] = i
    for i, board in enumerate(boards):
        t = time_to_win(board, times)
        if cmp(t, win):
            win = t
            idx = i
    score = sum(b for b in boards[idx] if times[b] > win)
    return score * moves[win]


def part1(moves, boards):
    return solve(moves, boards, lt, len(moves))


def part2(moves, boards):
    return solve(moves, boards, gt, 0)


print(f"Part 1: {part1(moves, boards)}")
print(f"Part 2: {part2(moves, boards)}")

day04.rs

use itertools::Itertools;

const N: usize = 5;
type Board = Vec<u8>;

pub fn read(inp: &str) -> (Vec<u8>, Vec<Board>) {
    let mut s = inp.trim().split("\n\n");

    let moves = s
        .next()
        .unwrap()
        .trim()
        .split(',')
        .map(|word| word.parse::<u8>().unwrap())
        .collect();

    let boards = s
        .map(|board| {
            board
                .trim()
                .split_ascii_whitespace()
                .map(|word| word.parse::<u8>().unwrap())
                .collect()
        })
        .collect();
    (moves, boards)
}

fn time_to_win(board: &[u8], times: &[u8]) -> u8 {
    let mut col = [0; N];
    let mut row = [0; N];
    for ((r, c), &n) in (0..N).cartesian_product(0..N).zip(board.iter()) {
        let t = times[n as usize];
        col[c] = col[c].max(t);
        row[r] = row[r].max(t);
    }
    col.into_iter()
        .min()
        .unwrap_or(0)
        .min(row.into_iter().min().unwrap_or(0))
}

fn solve(inp: &(Vec<u8>, Vec<Board>), cmp: impl Fn(u8, u8) -> bool, init: u8) -> usize {
    let (moves, boards) = inp;
    let mut times = [0u8; 100];
    for (i, &n) in moves.iter().enumerate() {
        times[n as usize] = i as u8;
    }
    let mut idx = 0;
    let mut win = init;
    for (i, board) in boards.iter().enumerate() {
        let t = time_to_win(board, &times);
        if cmp(t, win) {
            win = t;
            idx = i;
        }
    }
    let board = &boards[idx];
    let score = board.iter().fold(0usize, |a, &n| {
        if times[n as usize] > win {
            a + n as usize
        } else {
            a
        }
    });
    score * (moves[win as usize] as usize)
}

pub fn part1(inp: &(Vec<u8>, Vec<Board>)) -> usize {
    solve(inp, |t, win| t < win, u8::MAX)
}

pub fn part2(inp: &(Vec<u8>, Vec<Board>)) -> usize {
    solve(inp, |t, win| t > win, 0)
}

pub fn run() -> (String, String) {
    let inp = include_str!(concat!(env!("CARGO_MANIFEST_DIR"), "/inputs/day04.input"));
    let data = read(inp);
    (part1(&data).to_string(), part2(&data).to_string())
}

day05.py

from collections import Counter
from itertools import zip_longest, chain
from functools import partial

with open("../inputs/2021/day05.input", "r") as f:
    wires = [
        list(chain(*(map(int, x.split(",")) for x in line.split(" -> "))))
        for line in f.readlines()
    ]


def solve(diagonal, wires):
    c = Counter()
    cmp = lambda x: (x > 0) - (x < 0)
    for x1, y1, x2, y2 in wires:
        dx = cmp(x2 - x1)
        dy = cmp(y2 - y1)
        if dx and dy and not diagonal:
            continue
        for x, y in zip_longest(
            range(x1, x2 + dx, dx or 1),
            range(y1, y2 + dy, dy or 1),
            fillvalue=y1 if dx else x1,
        ):
            c[x, y] += 1
    return sum(i > 1 for i in c.values())


part1 = partial(solve, False)
part2 = partial(solve, True)
print(f"{part1(wires)}")
print(f"{part2(wires)}")

day06.py

from collections import deque

with open("../inputs/2021/day06.input", "r") as f:
    ages = list(map(int, f.read().strip().split(",")))


def solve(ages, rounds):
    fish = deque([0] * 9, maxlen=9)
    for a in ages:
        fish[a] += 1
    for _ in range(rounds):
        fish.rotate(-1)
        fish[6] += fish[8]
    return sum(fish)


print(solve(ages, 80))
print(solve(ages, 256))

day07.py

with open("../inputs/2021/day07.input", "r") as f:
    inp = sorted(map(int, f.read().strip().split(",")))


def part1(inp):
    # Probably doesn't work for all inputs
    median = inp[len(inp) // 2]
    return sum(abs(k - median) for k in inp)


def part2(inp):
    # Probably doesn't work for all inputs
    mean = sum(inp) // len(inp)
    return sum((abs(k - mean) * (abs(k - mean) + 1)) // 2 for k in inp)


# Original solutions
def part1_brute_force(inp):
    from collections import Counter

    inp = Counter(inp)
    lo = min(inp)
    hi = max(inp)

    def cost(n) -> int:
        return sum(abs(k - n) * v for k, v in inp.items())

    return min(cost(i) for i in range(lo, hi + 1))


def part2_brute_force(inp):
    from collections import Counter

    inp = Counter(inp)
    lo = min(inp)
    hi = max(inp)

    def cost(n):
        return sum(v * (abs(k - n) * (abs(k - n) + 1)) // 2 for k, v in inp.items())

    return min(cost(i) for i in range(lo, hi + 1))


print(part1(inp))
print(part2(inp))

day08.py

from collections import defaultdict
from itertools import chain

with open("../inputs/2021/day08.input", "r") as f:
    inputs = []
    outputs = []
    data = f.read().strip()
    for line in data.split("\n"):
        i, o = line.strip().split(" | ")
        inputs.append(i.split(" "))
        outputs.append(o.split(" "))


def part1(_, outputs):
    return sum(len(o) in {2, 3, 4, 7} for o in chain(*outputs))


# 0: a b c e f g
# 1: c f
# 2: a c d e g           a
# 3: a c d f g         b   c
# 4: b c d f             d
# 5: a b d f g         e   f
# 6: a b d e f g         g
# 7: a c f
# 8: a b c d e f g
# 9: a b c d f g
def decode(inputs, outputs):
    data = defaultdict(set)
    for digit in inputs:
        data[len(digit)].add(frozenset(digit))
    (one,) = data[2]
    (four,) = data[4]
    (seven,) = data[3]
    eg1, eg2 = set(i - (four | seven) for i in data[5])
    cf1, cf2 = set(i & one for i in data[6])
    (a,) = seven - one
    (c,) = cf1 ^ cf2
    (e,) = eg1 ^ eg2
    (f,) = cf1 & cf2
    (g,) = eg1 & eg2
    (bde1, bde2, bde3) = set(i - (seven | {g}) for i in data[5])
    (d,) = bde1 & bde2 & bde3
    (b,) = four - (seven | {d})
    digits = {}
    digits[frozenset([a, b, c, e, f, g])] = 0
    digits[frozenset([c, f])] = 1
    digits[frozenset([a, c, d, e, g])] = 2
    digits[frozenset([a, c, d, f, g])] = 3
    digits[frozenset([b, c, d, f])] = 4
    digits[frozenset([a, b, d, f, g])] = 5
    digits[frozenset([a, b, d, e, f, g])] = 6
    digits[frozenset([a, c, f])] = 7
    digits[frozenset([a, b, c, d, e, f, g])] = 8
    digits[frozenset([a, b, c, d, f, g])] = 9
    return sum(10 ** i * digits[frozenset(d)] for i, d in enumerate(reversed(outputs)))


def part2(inputs, outputs):
    return sum(decode(*io) for io in zip(inputs, outputs))


print(part1(inputs, outputs))
print(part2(inputs, outputs))

day09.py

from collections import defaultdict
from functools import reduce
from itertools import product
from operator import mul
from typing import Iterable, Mapping

T = tuple[int, int]
M = Mapping[T, int]

with open("../inputs/2021/day09.input", "r") as f:
    data = f.read()
    data = data.strip().split("\n")
    shape = (len(data) + 2, len(data[0].strip()) + 2)
    heights: M = defaultdict(lambda: 9)
    for i, line in enumerate(data):
        for j, c in enumerate(map(int, line.strip())):
            heights[i, j] = c


def neighbours(i: int, j: int) -> Iterable[T]:
    yield from ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))


def minima(heights: M) -> Iterable[T]:
    n, m = map(max, zip(*heights))
    yield from (
        i
        for i in product(range(n + 1), range(m + 1))
        if all(heights[i] < heights[n] for n in neighbours(*i))
    )


def part1(heights: M) -> int:
    return sum(heights[m] + 1 for m in minima(heights))


def size(seed: T, heights: M) -> int:
    found: set[T] = set()
    queue = {seed}
    while queue:
        seed = queue.pop()
        if seed not in found:
            found.add(seed)
            # Restriction that each point is either 9 or belonging to
            # exactly one basin means the termination criterion is
            # heights[c] == 9, and we don't need the additional check
            # that seed < heights[c]
            queue |= set((c for c in neighbours(*seed) if heights[c] < 9))
    return len(found)


def part2(heights: M) -> int:
    return reduce(mul, sorted(size(s, heights) for s in minima(heights))[-3:])


print(part1(heights))
print(part2(heights))

day10.py

from typing import Optional

with open("../inputs/2021/day10.input", "r") as f:
    lines = f.read().strip().split("\n")


match = {"(": ")", "{": "}", "[": "]", "<": ">"}
score1 = {")": 3, "]": 57, "}": 1197, ">": 25137}
score2 = {"(": "1", "[": "2", "{": "3", "<": "4"}


def check(line: str) -> tuple[Optional[int], int]:
    lifo: list[str] = []
    for c in line:
        if c in match:
            lifo.append(c)
        elif not lifo or match[lifo.pop()] != c:
            return score1[c], 0
    return None, int("".join(score2[c] for c in reversed(lifo)), 5)


def part1(lines):
    return sum(c for c, _ in map(check, lines) if c is not None)


def part2(lines):
    scores = [score for c, score in map(check, lines) if c is None]
    return sorted(scores)[len(scores) // 2]


print(part1(lines))
print(part2(lines))

day11.py

from typing import Iterable

Tidx = tuple[int, int]
Toct = dict[Tidx, int]

with open("../inputs/2021/day11.input", "r") as f:
    data = f.read()
    data = data.strip().split("\n")
    octopuses: Toct = {}
    for i, line in enumerate(data):
        for j, c in enumerate(map(int, line.strip())):
            octopuses[i, j] = c
    N, M = map(max, zip(*octopuses))
    N += 1
    M += 1


def neighbours(i: int, j: int) -> Iterable[Tidx]:
    for di, dj in (
        (i - 1, j - 1),
        (i, j - 1),
        (i + 1, j - 1),
        (i - 1, j),
        (i + 1, j),
        (i - 1, j + 1),
        (i, j + 1),
        (i + 1, j + 1),
    ):
        if 0 <= di < N and 0 <= dj < M:
            yield di, dj


def step(octopuses: Toct) -> int:
    for k in octopuses:
        octopuses[k] += 1
    lifo = [k for k, v in octopuses.items() if v > 9]
    seen = set()
    while lifo:
        seed = lifo.pop()
        if seed not in seen:
            seen.add(seed)
            for i in neighbours(*seed):
                octopuses[i] += 1
                if i not in seen and octopuses[i] > 9:
                    lifo.append(i)
    for idx in seen:
        octopuses[idx] = 0
    return len(seen)


def part1(octopuses: Toct) -> int:
    octopuses = octopuses.copy()
    return sum(step(octopuses) for _ in range(100))


def part2(octopuses: Toct) -> int:
    octopuses = octopuses.copy()
    i = 0
    while any(v != 0 for v in octopuses.values()):
        step(octopuses)
        i += 1
    return i


print(part1(octopuses))
print(part2(octopuses))

day12.py

import time
from collections import defaultdict

start = time.time()
with open("../inputs/2021/day12.input", "r") as f:
    nodes = defaultdict(list)
    lines = f.read().strip().split("\n")
    for line in lines:
        a, b = line.split("-")
        if b != "start":
            nodes[a].append(b)
        if a != "start":
            nodes[b].append(a)

print("setup: %.0fus" % ((time.time() - start) * 1e6))


def recurse(head, seen, twice, nodes, cache):
    # Original implementation
    if head == "end":
        return 1
    try:
        return cache[(head, seen, twice)]
    except KeyError:
        pass

    s = sum(
        recurse(
            c,
            seen if c.isupper() else frozenset(seen | {c}),
            twice or c in seen,
            nodes,
            cache,
        )
        for c in nodes[head]
        if not (twice and c in seen)
    )
    return cache.setdefault((head, seen, twice), s)


def part1(nodes):
    return recurse("start", frozenset(), True, nodes, {})


def part2(nodes):
    return recurse("start", frozenset(), False, nodes, {})


print(part1(nodes))
print(part2(nodes))
print("end: %.0fus" % ((time.time() - start) * 1e6))

day13.py

import time

start = time.time()
with open("../inputs/2021/day13.input", "r") as f:
    coords, folds = f.read().strip().split("\n\n")
    coords = [list(map(int, line.split(","))) for line in coords.split("\n")]
    folds = [(int(fold[11] == "y"), int(fold[13:])) for fold in folds.split("\n")]
    inp = (coords, folds)


def solve(coords, folds):
    points = {}
    comp, n = folds[0]
    for coord in coords:
        for comp, n in folds:
            p = coord[comp]
            coord[comp] = p if p < n else p - 2 * (p - n)
        points[tuple(coord)] = "#"
    return points


def part1(inp):
    coords, folds = inp
    return len(solve(coords, folds[:1]))


ALPHABET = {
    " ## \n#  #\n#  #\n####\n#  #\n#  #": "A",
    "### \n#  #\n### \n#  #\n#  #\n### ": "B",
    " ## \n#  #\n#   \n#   \n#  #\n ## ": "C",
    "####\n#   \n### \n#   \n#   \n####": "E",
    "####\n#   \n### \n#   \n#   \n#   ": "F",
    " ## \n#  #\n#   \n# ##\n#  #\n ###": "G",
    "#  #\n#  #\n####\n#  #\n#  #\n#  #": "H",
    " ###\n  # \n  # \n  # \n  # \n ###": "I",
    "  ##\n   #\n   #\n   #\n#  #\n ## ": "J",
    "#  #\n# # \n##  \n# # \n# # \n#  #": "K",
    "#   \n#   \n#   \n#   \n#   \n####": "L",
    " ## \n#  #\n#  #\n#  #\n#  #\n ## ": "O",
    "### \n#  #\n#  #\n### \n#   \n#   ": "P",
    "### \n#  #\n#  #\n### \n# # \n#  #": "R",
    " ###\n#   \n#   \n ## \n   #\n### ": "S",
    "#  #\n#  #\n#  #\n#  #\n#  #\n ## ": "U",
    "#   \n#   \n # #\n  # \n  # \n  # ": "Y",
    "####\n   #\n  # \n #  \n#   \n####": "Z",
}


def part2(inp):
    coords, folds = inp
    points = solve(coords, folds)
    width = 4
    chars = []
    for c in range(8):
        char = "\n".join(
            "".join(
                points.get((i, j), " ")
                for i in range(c * (width + 1), c * (width + 1) + width)
            )
            for j in range(6)
        )
        chars.append(ALPHABET[char])
    return "".join(chars)


print(
    f"Day 13     {part1(inp):<13} {part2(inp):<14} {(time.time() - start)*1e6:>13.0f}"
)

day14.py

import time
from collections import Counter

start = time.time()
with open("../inputs/2021/day14.input", "r") as f:
    data = f.read()
    polymer, lines = data.strip().split("\n\n")
    rules = {}
    for line in lines.split("\n"):
        (a, b), c = line.split(" -> ")
        rules[a, b] = c
    inp = (polymer, rules)


def solve(polymer, rules, reps):
    pairs = Counter(zip(polymer, polymer[1:]))
    counts = Counter(polymer)
    for _ in range(reps):
        newpairs = Counter()
        for (a, b), count in pairs.items():
            c = rules[a, b]
            counts[c] += count
            newpairs[a, c] += count
            newpairs[c, b] += count
            pairs = newpairs
    return max(counts.values()) - min(counts.values())


def part1(inp: tuple[str, dict]):
    return solve(*inp, 10)


def part2(inp: tuple[str, dict]):
    return solve(*inp, 40)


print(
    f"Day 14     {part1(inp):<13} {part2(inp):<14} {(time.time() - start)*1e6:>13.0f}"
)

day15.py

import heapq
import time

start = time.time()
with open("../inputs/2021/day15.input", "r") as f:
    data = f.read().strip()
    inp = []
    for line in data.split("\n"):
        inp.append(list(map(int, line)))


def neighbours(i, j, graph):
    N, M = len(graph), len(graph[0])
    di = [1, 0, -1, 0]
    dj = [0, 1, 0, -1]
    for n in range(4):
        i_ = i + di[n]
        j_ = j + dj[n]
        if 0 <= i_ < N and 0 <= j_ < M:
            yield (i_, j_)


def dijkstra(start, end, graph):
    N, M = len(graph), len(graph[0])
    dist = [[False] * M for _ in range(N)]
    pq = []
    seen = [[False] * M for _ in range(N)]
    i, j = start
    seen[i][j] = True
    heapq.heappush(pq, (1, start))
    while pq:
        d, (vi, vj) = heapq.heappop(pq)
        if dist[vi][vj]:
            continue  # already searched this node.
        if (vi, vj) == end:
            return d - 1
        dist[vi][vj] = d
        for ui, uj in neighbours(vi, vj, graph):
            if not seen[ui][uj]:
                seen[ui][uj] = True
                heapq.heappush(pq, (d + graph[ui][uj], (ui, uj)))


def part1(graph):
    start = (0, 0)
    end = len(graph) - 1, len(graph[0]) - 1
    return dijkstra(start, end, graph)


def replicate(graph):
    nx, ny = len(graph), len(graph[0])

    newgraph = [[None] * ny * 5 for _ in range(nx * 5)]
    for ki in range(nx):
        for kj in range(ny):
            v = graph[ki][kj]
            for i in range(0, 5):
                for j in range(0, 5):
                    kx = ki + i * nx
                    ky = kj + j * ny
                    newval = v + i + j
                    if newval > 9:
                        newval = newval % 9
                    newgraph[kx][ky] = newval
    return newgraph


def part2(graph):
    start = (0, 0)
    graph = replicate(graph)
    end = len(graph) - 1, len(graph[0]) - 1
    return dijkstra(start, end, graph)


print(
    f"Day 15     {part1(inp):<13} {part2(inp):<14} {(time.time() - start)*1e6:>13.0f}"
)

day16.py

import time
from functools import partial, reduce
from operator import eq, gt, lt, mul

start = time.time()
with open("../inputs/2021/day16.input", "r") as f:
    inp = f.read()


def to_chunks(data):
    mapping = {
        "0": "0000",
        "1": "0001",
        "2": "0010",
        "3": "0011",
        "4": "0100",
        "5": "0101",
        "6": "0110",
        "7": "0111",
        "8": "1000",
        "9": "1001",
        "A": "1010",
        "B": "1011",
        "C": "1100",
        "D": "1101",
        "E": "1110",
        "F": "1111",
    }
    return "".join(mapping[c] for c in data)


def parse_version(chunks):
    version = int(chunks[:3], 2)
    return version, chunks[3:]


SUM = 0b000
MUL = 0b001
MIN = 0b010
MAX = 0b011
VAL = 0b100
GT = 0b101
LT = 0b110
EQ = 0b111

OPS = {
    SUM: sum,
    MUL: partial(reduce, mul),
    MIN: min,
    MAX: max,
    GT: lambda v: gt(*v),
    LT: lambda v: lt(*v),
    EQ: lambda v: eq(*v),
}


def parse_type(chunks):
    type = int(chunks[:3], 2)
    return type, chunks[3:]


def parse_literal(chunks):
    value = 0
    while True:
        block = int(chunks[:5], 2)
        chunks = chunks[5:]
        value <<= 4
        value |= block & 0b01111
        if not (block & 0b10000):
            break
    return value, chunks


def parse_operator(chunks):
    typ = int(chunks[:1], 2)
    chunks = chunks[1:]
    if typ == 1:
        npacket = int(chunks[:11], 2)
        chunks = chunks[11:]
        return (typ, npacket), chunks
    elif typ == 0:
        nbit = int(chunks[:15], 2)
        chunks = chunks[15:]
        return (typ, nbit), chunks
    else:
        raise RuntimeError


def parse_packet(chunks):
    version, rest = parse_version(chunks)
    typ, rest = parse_type(rest)
    if typ == VAL:
        value, rest = parse_literal(rest)
        return rest, version, value
    else:
        (length_type, n), rest = parse_operator(rest)
        values = []
        if length_type == 1:
            # Parse a fixed number of packets
            for _ in range(n):
                rest, v, value = parse_packet(rest)
                values.append(value)
                version += v
        else:
            # Parse a fixed number of bits
            sub = rest[:n]
            while sub:
                sub, v, value = parse_packet(sub)
                values.append(value)
                version += v
            rest = rest[n:]
        # Evaluate the values
        value = OPS[typ](values)
    return rest, version, value


def part1(inp):
    return parse_packet(to_chunks(inp))[1]


def part2(inp):
    return parse_packet(to_chunks(inp))[2]


print(
    f"Day 16     {part1(inp):<13} {part2(inp):<14} {(time.time() - start)*1e6:>13.0f}"
)