2020 Solutions

Imports

Code

import functools
import itertools
import os
import re
import sys
from collections import defaultdict, deque

import numpy as np
import scipy

sys.path.insert(1, os.path.join(sys.path[0], ".."))
import utils

load = utils.year_load(2020)

Day 1: Report Repair

Part 1

Code

data = load(1, "np")
[pair[0] * pair[1] for pair in itertools.product(data, data) if sum(pair) == 2020][0]

Part 2

Code

[
    triple[0] * triple[1] * triple[2]
    for triple in itertools.product(data, data, data)
    if sum(triple) == 2020
][0]

Day 2: Password Philosophy

Part 1

Code

def is_valid(interval, letters, password):
    interval = [int(x) for x in interval.split("-")]
    occurrences = password.count(letters[0])
    return interval[0] <= occurrences <= interval[1]


lines = load(2)
sum([is_valid(*line.split()) for line in lines])

Part 2

Code

from operator import xor


def is_valid(interval, letters, password):
    lower, upper = [int(x) - 1 for x in interval.split("-")]
    return xor(password[lower] == letters[0], password[upper] == letters[0])


sum([is_valid(*line.split()) for line in lines])

Day 3: Toboggan Trajectory

Part 1

Code

data = np.array([[0 if char == "." else 1 for char in line] for line in load(3)])


def count_trees(data, width_change, height_change):
    height, width = data.shape
    result = 0
    for i in range((height - 1) // height_change + 1):
        result += data[i * height_change, (i * width_change) % width]
    return result


count_trees(data, 3, 1)

Part 2

Code

slopes = [[1, 1], [3, 1], [5, 1], [7, 1], [1, 2]]
np.prod([count_trees(data, slope[0], slope[1]) for slope in slopes])

Day 4: Passport Processing

Part 1

Code

data = load(4, "raw")
passports = data.split("\n\n")
passport_dicts = [
    dict(list(map(lambda x: x.split(":"), p.replace("\n", " ").split())))
    for p in passports
]
sum([len(set(p.keys()) - set(["cid"])) == 7 for p in passport_dicts])

Part 2

Code

def validate_key(key, value):
    year_limits = {"byr": [1920, 2002], "eyr": [2020, 2030], "iyr": [2010, 2020]}
    try:
        if key in ["byr", "eyr", "iyr"]:
            minval, maxval = year_limits[key]
            return minval <= int(value) <= maxval
        if key == "hgt":
            value, unit = int(value[:-2]), value[-2:]
            return (unit == "cm" and (150 <= value <= 193)) or (
                unit == "in" and (59 <= value <= 76)
            )
        if key == "hcl":
            return (
                value[0] == "#"
                and len(value) == 7
                and not (set(value[1:]) - set("0123456789abcdef"))
            )
        if key == "ecl":
            return value in ["amb", "blu", "brn", "gry", "grn", "hzl", "oth"]
        if key == "pid":
            test = int(value)
            return len(value) == 9
        return True
    except ValueError:
        return False


def is_valid_passport(p):
    return len(set(p.keys()) - set(["cid"])) == 7 and all(
        [validate_key(key, p[key]) for key in p]
    )


sum([is_valid_passport(p) for p in passport_dicts])

Day 5: Binary Boarding

Part 1

Code

# "BFFFBBFRRR" -> 70, column 7 -> 567
def seat_id(instruction):
    return int(instruction.translate(str.maketrans("BFRL", "1010")), 2)


seat_ids = [seat_id(x) for x in load(5)]
max(seat_ids)

Part 2

Code

(set(range(min(seat_ids), max(seat_ids) + 1)) - set(seat_ids)).pop()

Day 6: Custom Customs

Part 1

Code

data = load(6, "raw")
groups = data.split("\n\n")
sum(len(set(list(group.replace("\n", "")))) for group in groups)

Part 2

Code

sum(
    len(functools.reduce(lambda x, y: set(x) & set(y), (group.splitlines())))
    for group in groups
)

Day 7: Handy Haversacks

Part 1

Nothing super groundbreaking for part one. I thought of using a regex to parse the input, but splitting on commas and then into words works just fine.

Code

data = load(7)
tree = {}
for line in data:
    bag, contents = line.split(" bags contain ")
    if "no other" in contents:
        contents = {}
    else:
        elements = contents.split(", ")
        contents = {
            " ".join(words[1:-1]): int(words[0]) for words in map(str.split, elements)
        }
    tree[bag] = contents


@functools.cache
def contains_gold(key):
    return "shiny gold" in tree[key] or any(contains_gold(child) for child in tree[key])


sum(contains_gold(key) for key in tree)

Part 2

The key thing to remember is to include the bag itself, as well as the bags it contains, when calculating the total. That’s what the “+1” is for in the sum

Code

@functools.cache
def count_bags(bag):
    return sum(tree[bag][key] * (count_bags(key) + 1) for key in tree[bag])


count_bags("shiny gold")

Day 8: Handheld Halting

Part 1

Code

data = [x.split() for x in load(8)]
data = [(x[0], int(x[1])) for x in data]


def terminal_run(program):
    ip, accumulator = 0, 0
    seen = {}
    while ip != len(program):
        if ip in seen:
            return False, accumulator
        seen[ip] = 1
        instruction, operand = program[ip]
        ip += 1
        if instruction == "jmp":
            ip += operand - 1
        if instruction == "acc":
            accumulator += operand
    return True, accumulator


terminal_run(data)[1]

Part 2

Code

instruction_map = {"acc": "acc", "jmp": "nop", "nop": "jmp"}
for idx, instruction in enumerate(data):
    new_instruction = (instruction_map[instruction[0]], instruction[1])
    status, value = terminal_run(data[:idx] + [new_instruction] + data[idx + 1 :])
    if status:
        break
value

Day 9: Encoding Error

Part 1

Code

data = list(load(9, "np"))
end = len(data) - 25
for window_start in range(end):
    target = data[window_start + 25]
    if (
        min(
            map(
                lambda x: abs(target - sum(x)),
                itertools.combinations(data[window_start : window_start + 25], 2),
            )
        )
        != 0
    ):
        break
invalid_number = target
invalid_number

Part 2

Code

start_idx, end_idx = 0, 1
while start_idx < len(data):
    total = sum(data[start_idx:end_idx])
    if total == invalid_number:
        break
    if total < invalid_number:
        end_idx += 1
    if total > invalid_number:
        start_idx += 1
        end_idx = start_idx + 1
min(data[start_idx:end_idx]) + max(data[start_idx:end_idx])

Day 10: Adapter Array

Part 1

Code

data = [0] + sorted((load(10, "np")))
(np.diff(data) == 1).sum() * ((np.diff(data) == 3).sum() + 1)

Part 2

Sorting the values, we see a series of jumps of 1 and jumps of 3. If the value is allowed to jump by at most 3 every time, then we have to include both sides of every jump of 3.

The only interesting thing is then what to do with runs of 1 jumps. In general, we can count the number of ways, \(f\), as follows

\(f(n) = f(n - 1) + g(n-1)\)

The first term comes from saying that we pick the first element, leaving us with a run of length \((n - 1)\), exactly as before. The second comes from saying that we skip the first element, and now have to find the number of ways of choosing for a series of gaps starting with \(2\), followed by \(n - 2\) ones. Similarly

\(g(n - 1) = f(n - 2) + f(n - 3)\)

If we pick the element that resulted in a gap of two, then we just have to choose from a run of n - 2 ones, which is the \(f\) we are looking at. If we don’t pick it, we’ve created a gap of size \(3\) - but then we are forced to pick the next element, leaving us with a run of length \(n - 3\) to distribute.

Putting everything together gives the recurrence

\(f(n) = f(n - 1) + f(n - 2) + f(n - 3)\),

with initial conditions \(f(0) = 1\), \(f(-1) = 0\), \(f(-2) = 0\).

That recurrence can be written in matrix form as

\[ \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{pmatrix}\]

And iterating the function is then just a question of matrix powers

Code

def total_ways(n_ones):
    matrix = np.array([[1, 1, 1], [1, 0, 0], [0, 1, 0]])
    return (np.linalg.matrix_power(matrix, n_ones) @ [1, 0, 0])[0]


np.product(
    [total_ways(len(x)) for x in "".join(str(x) for x in np.diff(data)).split("3")]
)

Day 11: Seating System

Part 1

For the first part, we are taking the convolution of our original grid with a weights array that looks like \[ \begin{pmatrix} 1 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1\\ \end{pmatrix} \] Scipy has nice routines that handle all that indexing for us, so we’ll cheat and use them. The only slight issue is what to do at the edge of the grid, but using a constant value of 0 for any cells that would fall outside the grid works out of the box.

Code

data = np.array([[1 if char == "." else 0 for char in line] for line in load(11)])
mask = np.where(data)
board = np.zeros(data.shape, dtype=int)
new_board = np.ones(board.shape, dtype=int)
new_board[mask] = 0
weights = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
while (board != new_board).any():
    board = new_board.copy()
    convolution = scipy.ndimage.convolve(new_board, weights, mode="constant")
    new_board[np.where(convolution == 0)] = 1
    new_board[np.where(convolution >= 4)] = 0
    new_board[mask] = 0
board.sum()

Part 2

For part 2 I was unable to find a nice way of expressing the condition of “Look for the first grid position in a given direction which is not floor”. That means that I have to manually loop over the grid instead of using the convolution routine - and that really slows down the runtime!

Code

board = np.zeros(data.shape, dtype=int)
new_board = np.ones(board.shape, dtype=int)
new_board[mask] = 0


def update(board):
    new_board = board.copy()
    directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
    for row, col in itertools.product(*[range(x) for x in board.shape]):
        total = 0
        for direction in directions:
            done = False
            new_row, new_col = row, col
            while not done:
                new_row, new_col = new_row + direction[0], new_col + direction[1]
                if (
                    new_row < 0
                    or new_row >= board.shape[0]
                    or new_col < 0
                    or new_col >= board.shape[1]
                ):
                    break
                if not data[new_row, new_col]:
                    done = True
            else:  # no break - so a valid position
                total += board[new_row, new_col]
        if total == 0:
            new_board[row, col] = 1
        if total >= 5:
            new_board[row, col] = 0
    new_board[mask] = 0
    return new_board


while (new_board != board).any():
    board = new_board
    new_board = update(new_board)
new_board.sum()

Day 12: Rain Risk

Part 1

I’ll use the usual trick of modelling the 2d grid as the complex plane.

Code

directions = {"N": 1j, "E": 1, "S": -1j, "W": -1}
turns = {"L": 1j, "R": -1j}
position, direction = 0, 1


def update_state(position, direction, instruction, value, part=1):
    if instruction in directions:
        offset = directions[instruction] * value
        return (
            (position + offset, direction)
            if part == 1
            else (position, direction + offset)
        )
    if instruction in turns:
        return position, direction * turns[instruction] ** (int(value // 90))
    return position + value * direction, direction


instructions = load(12)
for instruction, value in map(lambda x: (x[0], int(x[1:])), instructions):
    position, direction = update_state(position, direction, instruction, value)
int(abs(position.real) + abs(position.imag))

Part 2

Part 2 can be done basically the same way as part 1, with only a small change to the update state function. In part 1, nesw move the ship; in part 2 they move the waypoint. Everything else is the same.

Code

position, waypoint = 0, 10 + 1j
for instruction, value in map(lambda x: (x[0], int(x[1:])), instructions):
    position, waypoint = update_state(position, waypoint, instruction, value, part=2)
int(abs(position.real) + abs(position.imag))

Day 13: Shuttle Search

Part 1

This one looks like a bunch of modular arithmetic. The first one is just whichever bus number n has the smallest -x (mod n)

Code

x = 1006726
buses = (
    "23,x,x,x,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,647,"
    "x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,13,19,x,x,x,x,x,x,x"
    ",x,x,29,x,557,x,x,x,x,x,37,x,x,x,x,x,x,x,x,x,x,17"
)
bus_moduli = [
    (int(_), (-idx) % int(_)) for idx, _ in enumerate(buses.split(",")) if _ != "x"
]
bus_numbers = [n for n, a in bus_moduli]
waits = [-x % bus for bus in bus_numbers]
min(waits) * bus_numbers[np.argmin(waits)]

Part 2

For the second, it’s the Chinese remainder theorem to the rescue. Code shamelessly copied from wikipedia.

Code

from utils import crt

crt(bus_moduli)

Day 14: Docking Data

Part 1

Code

data = [line.split(" = ") for line in load(14)]
result = defaultdict(int)
mask = ""
for operation, operand in data:
    if operation == "mask":
        mask = operand
    else:
        new_operand = "".join(
            [b1 if (b1 != "X") else b2 for b1, b2 in zip(mask, f"{int(operand):036b}")]
        )
        result[operation[4:-1]] = int(new_operand, 2)
sum(result.values())

Code

result = defaultdict(int)
mask = ""
for operation, operand in data:
    if operation == "mask":
        mask = operand
    else:
        operand = int(operand)
        operation = operation[4:-1]
        addresses = [""]
        for b1, b2 in zip(mask, f"{int(operation):036b}"):
            if b1 == "X":
                addresses = [a + "0" for a in addresses] + [a + "1" for a in addresses]
            elif b1 == "1":
                addresses = [a + "1" for a in addresses]
            else:
                addresses = [a + b2 for a in addresses]
        for address in addresses:
            result[int(address, 2)] = operand
sum(result.values())

Day 15: Rambunctious Recitation

Part 1

Code

prefix = load(15, "int")[0]
state = {i: idx + 1 for idx, i in enumerate(prefix[:-1])}
current = prefix[-1]


def update(current, i):
    if current not in state:
        next_n = 0
    else:
        next_n = i - state[current]
    state[current] = i
    return next_n


n_turns = 2020
for i in range(len(prefix), n_turns):
    current = update(current, i)
current

Part 2

30 million is just within range where brute force would be plausible. Let’s try it:

Code

for i in range(n_turns, 30_000_000):
    current = update(current, i)
current

Day 16: Ticket Translation

Part 1

I could do this by trying to merge ranges of valid values. Or I could just instantiate a set with every valid value…

Code

data = load(16, "raw")
rules, own, nearby = data[:-1].split("\n\n")
valid = set()
for rule in rules.split("\n"):
    limits = [int(x) for x in re.findall(r"\d+", rule)]
    for lower, upper in zip(limits[::2], limits[1::2]):
        valid |= set(range(lower, upper + 1))
sum(
    map(
        lambda x: 0 if int(x) in valid else int(x),
        nearby[nearby.index("\n") + 1 :].replace("\n", ",").split(","),
    )
)

Part 2

I’m not entirely surprised that that’s where he went for part 2

Code

ranges = defaultdict(set)
for rule in rules.split("\n"):
    name, _ = rule.split(":")
    limits = [int(x) for x in re.findall(r"\d+", rule)]
    for lower, upper in zip(limits[::2], limits[1::2]):
        ranges[name] |= set(range(lower, upper + 1))
own_ticket = [int(x) for x in own.split("\n")[1].split(",")]
nearby_tickets = [[int(x) for x in line.split(",")] for line in nearby.split("\n")[1:]]
nearby_tickets = np.array([x for x in nearby_tickets if all(y in valid for y in x)])
assignments = [0] * len(own_ticket)
while ranges:
    for column in range(len(assignments)):
        if assignments[column]:
            continue
        candidates = [
            key
            for key in ranges.keys()
            if all(x in ranges[key] for x in nearby_tickets[:, column])
        ]
        if len(candidates) == 1:
            assignments[column] = candidates[0]
            del ranges[candidates[0]]
np.product(
    [
        own_ticket[idx]
        for idx, assignment in enumerate(assignments)
        if "departure" in assignment
    ]
)

Day 17: Conway Cubes

Part 1

This looks like another good time to use scipy’s handy correlate/convolve functions. At some point I should probably learn what the difference between those two is.

Code

data = np.array(
    [[1 if char == "#" else 0 for char in line] for line in load(17)], dtype=int
)


def simulate(data, dimensions=3, ncycles=6):
    weights = np.ones((3,) * dimensions)
    missing_dimensions = dimensions - len(data.shape)
    data = data.reshape(data.shape + (1,) * missing_dimensions)
    data = np.pad(data, ncycles)
    for i in range(ncycles):
        convolution = scipy.ndimage.correlate(data, weights, mode="constant")
        data = (convolution == 3) | ((convolution == 4) & data)
    return data.sum()


simulate(data)

Part 2

Code

simulate(data, 4)

Day 18: Operation Order

Part 1

Code

import string

operators = {"*": lambda x, y: x * y, "+": lambda x, y: x + y}


def find_closing_paren(s):
    assert s[0] == "("
    count = 0
    for idx, char in enumerate(s):
        count += 1 if char == "(" else -1 if char == ")" else 0
        if count == 0:
            return idx + 1


def evaluate(expression, part=1):
    i = 0
    ops = deque()
    operands = deque()
    while i < len(expression):
        char = expression[i]
        if char in "+*":
            ops.append(char)
            i += 1
            continue
        if char == "(":
            delta = find_closing_paren(expression[i:])
            operands.append(evaluate(expression[i + 1 : i + delta - 1], part=part))
            i += delta
        elif char in string.digits:
            operands.append(int(char))
            i += 1

        if part == 2 and ops and ops[-1] == "+":
            ops.pop()
            operands.append(operands.pop() + operands.pop())

    while ops:
        op = ops.popleft()
        operands.appendleft(operators[op](operands.popleft(), operands.popleft()))
    return operands.pop()


lines = [x.replace(" ", "") for x in load(18)]
sum(evaluate(line) for line in lines)

Part 2

The change for part 2 is so small that it can be included in part 1 as a flag

Code

sum(evaluate(line, part=2) for line in lines)

Day 19: Monster Messages

Part 1

Code

data = load(19, "raw")
relations, strings = map(lambda x: x.split("\n"), data.split("\n\n"))
dependencies = {}
rules = {}
for relation in relations:
    lhs, rhs = relation.split(":")
    rules[int(lhs)] = (
        {rhs.replace('"', "").strip()}
        if '"' in rhs
        else {tuple([int(y) for y in x.split()]) for x in rhs.split("|")}
    )

dependencies = {
    x: set().union(*rules[x]) if x not in [54, 20] else set() for x in rules
}


def concat(l1, l2):
    return {s1 + s2 for s1 in l1 for s2 in l2}


def expand(rule, rules, mappings):
    result = set()
    for option in rules[rule]:
        if isinstance(option, str):
            return rules[rule]
        new_elements = (
            mappings[option[0]]
            if len(option) == 1
            else concat(*[mappings[i] for i in option])
        )
        result |= new_elements
    return result


def free_elements(mydict):
    return [x for x in mydict if not mydict[x]]


mappings = {}
while dependencies:
    k1 = free_elements(dependencies)[0]
    mappings[k1] = expand(k1, rules, mappings)
    for k2 in dependencies:
        dependencies[k2].discard(k1)
    del dependencies[k1]
len(list(filter(lambda x: x in mappings[0], strings[:-1])))

Part 2

We have loops now! Analysing the new rules, we see that the system should accept all strings of the form 42^m 13ⁿ, with m > n > 0. Looking at the previous part shows that rule 42 and rule 31 never overlap, and all the strings they match have length 8. That gives the following logic for part 2:

Code

from more_itertools import chunked


def part2(s):
    chunks = ["".join(x).strip() for x in chunked(s, 8)]
    r42, r31 = 0, 0
    while chunks[r42] in mappings[42]:
        r42 += 1
        if r42 == len(chunks):
            break
    while r42 + r31 < len(chunks):
        if chunks[r42 + r31] not in mappings[31]:
            break
        r31 += 1

    return r31 >= 1 and r42 > r31 and r42 + r31 == len(chunks)


sum(part2(s) for s in strings[:-1])

Day 20: Jurassic Jigsaw

Part 1

Code

data = load(20, "raw").split("\n\n")
data[0]
tiles = {}


def edge_hashes(t):
    edges = [
        t[0],
        t[0][::-1],
        t[:, -1],
        t[:, -1][::-1],
        t[-1][::-1],
        t[-1],
        t[:, 0][::-1],
        t[:, 0],
    ]
    return {
        idx: functools.reduce(lambda x, y: 2 * x + y, edge[::-1])
        for idx, edge in enumerate(edges)
    }


def fingerprint(tile):
    return tile, edge_hashes(tile), {v: k for k, v in edge_hashes(tile).items()}


for entry in data:
    header, *tile = entry.split("\n")
    tile = np.array(
        [[1 if char == "#" else 0 for char in line] for line in tile if line],
        dtype="int",
    )
    tile_id = int(re.findall(r"\d+", header)[0])
    tiles[tile_id] = fingerprint(tile)
matches = defaultdict(set)
keys = sorted(tiles.keys())
for x in range(len(keys)):
    for y in range(x + 1, len(keys)):
        if set(tiles[keys[x]][1].values()) & set(tiles[keys[y]][1].values()):
            matches[keys[x]].add(keys[y])
            matches[keys[y]].add(keys[x])
corners = [x for x in matches if len(matches[x]) == 2]
np.product(corners)

Part 2

Direct inspection shows that there are no false matches in the edge pairings, so we can proceed to place all the tiles without taking that into account. We’ll start by placing the tiles in the correct location without worrying about their orientation, and then rotate and flip them afterwards.

There are eight possible ways to fill the board (four different corners to put in the top left, and then for each of those, two different choices for how to flip around the main diagonal), so we’ll arbitrarily pick one of them.

We’ll start by placing a corner piece in the top left, and then one of its neighbors below it.

When we place a tile, we mark the candidates for its unplaced neighbors: these are the intersection of whatever candidates were there before, and the unplaced matches of the current tile. We also remove the current tile as a candidate from any other open location, since it’s just been placed. Whenever a location has only one candidate, we can place that, and proceed until the whole board is filled.

Code

corner = corners[0]
match = next(iter(matches[corner]))
locations = defaultdict(lambda: set(keys))
placed = set()


def place(tile, location):
    locations[location] = tile
    placed.add(tile)
    x, y = location
    if x < 11 and isinstance(locations[x + 1, y], set):
        locations[x + 1, y] &= matches[tile] - placed
    if y < 11 and isinstance(locations[x, y + 1], set):
        locations[x, y + 1] &= matches[tile] - placed
    to_place = []
    for location in locations:
        if isinstance(locations[location], set):
            locations[location].discard(tile)
            if len(locations[location]) == 1:
                to_place.append(location)
    for placement in to_place:
        if isinstance(locations[placement], set):
            place(next(iter(locations[placement])), placement)


place(corner, (0, 0))
place(match, (1, 0))
coords = np.zeros((12, 12), dtype=int)
for location in locations:
    coords[location] = locations[location]

With that out of the way, we need to orient the tiles correctly. We start by making sure the top left corner is oriented correctly, and then we match all of the other tiles to that structure.

For each row in the grid, we match the first cell to the first cell in the row above, and then we match all the other cells to the neighbor to their left.

Code

# start off by making sure that the right hand side matches
overlap = [
    tiles[coords[0, 0]][2][key]
    for key in set(tiles[coords[0, 0]][2].keys()) & set(tiles[coords[0, 1]][2].keys())
][0]
delta = (((overlap - overlap % 2) - 2) // 2) % 4
if delta:
    tile = np.rot90(tiles[coords[0, 0]][0], -delta)
    tiles[coords[0, 0]] = fingerprint(tile)
# Then check if the bottom of the tile is the one that matches [1, 0]. If not, flip it vertically.
overlap = [
    tiles[coords[0, 0]][2][key]
    for key in set(tiles[coords[0, 0]][2].keys()) & set(tiles[coords[1, 0]][2].keys())
][0]
if overlap // 2 != 2:
    tile = tile[::-1]
    tiles[coords[0, 0]] = fingerprint(tile)

All the edges are labelled (not well, but they are labelled). To be oriented correctly, the 7 edge on a tile should match the 2 edge on the tile to its left, and/or the 0 edge on a tile should match the 5 edge on the tile above it.

Code

for y in range(12):
    for x in range(12):
        if not x and not y:
            continue
        tile = tiles[coords[y, x]][0]
        if not x:
            old_edge = 5
            target = 0
            comparison = (y - 1, x)
        else:
            old_edge = 2
            target = 7
            comparison = (y, x - 1)
        value = tiles[coords[comparison]][1][old_edge]
        current = tiles[coords[y, x]][2][value]
        if (target - current) % 2:
            tile = tile.T
            current = 7 - current
        rotation = (current - target) // 2
        tile = np.rot90(tile, rotation)
        tiles[coords[y, x]] = fingerprint(tile)

We can now reconstruct the board, and go hunting for the sea monsters. The convolve/correlate functions are handy here as well, since we’re looking for an area where all of a subset of the neighboring cells are lit up. So we correlate with that mask, and check which correlations have the full set.

The following code will fail if any of the sea monsters overlap, but luckily they don’t.

Code

board = np.zeros((8 * 12, 8 * 12), dtype=int)
for y in range(12):
    for x in range(12):
        board[y * 8 : (y + 1) * 8, x * 8 : (x + 1) * 8] = tiles[coords[y, x]][0][
            1:-1, 1:-1
        ]
pattern = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1],
    [0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0],
]

total = np.sum(pattern)
monsters = 0
for reflection in range(2):
    for rotation in range(4):
        convolution = scipy.ndimage.correlate(board, pattern, mode="constant")
        monsters += (convolution == total).sum()
        board = np.rot90(board)
    board = board.T
board.sum() - monsters * 15

Day 21: Allergen Assessment

Part 1

Nice and easy one today, with just a bit of set intersection logic

Code

counts = defaultdict(int)
mappings = {}
for line in load(21):
    ingredients, allergens = [
        x.split() for x in line[:-2].replace(",", "").split("(contains")
    ]
    for ingredient in ingredients:
        counts[ingredient] += 1
    for allergen in allergens:
        if allergen in mappings:
            mappings[allergen] &= set(ingredients)
        else:
            mappings[allergen] = set(ingredients)
potential_allergens = set().union(*mappings.values())
sum(counts[x] for x in counts if x not in potential_allergens)

Part 2

And part 2 isn’t much harder. Any allergens which have only one matching ingredient are fixed; and this ingredient can then be removed from all the other allergens. And then it’s a question of continuing until we have the full map

Code

assignments = {}
assignable = {x for x in mappings if len(mappings[x]) == 1}
while mappings:
    key = assignable.pop()
    value = mappings[key].pop()
    del mappings[key]
    assignments[key] = value
    for mapping in mappings:
        mappings[mapping].discard(value)
        if len(mappings[mapping]) == 1:
            assignable.add(mapping)
print(",".join(assignments[x] for x in sorted(list(assignments.keys()))))

Day 22: Crab Combat

Part 1

Code

p1, p2 = map(deque, np.array(load(22, "int")).reshape(2, -1)[:, 1:])
while p1 and p2:
    c1, c2 = p1[0], p2[0]
    p1.rotate(-1)
    p2.rotate(-1)
    winner, loser = (p1, p2) if (c1 > c2) else (p2, p1)
    winner.append(loser.pop())
result = p1 if p1 else p2
(np.array(result) * (np.arange(len(result)) + 1)[::-1]).sum()

Part 2

A fairly straightforward recursive implementation of the requirements

Code

p1, p2 = map(deque, np.array(load(22, "int")).reshape(2, -1)[:, 1:])


def play(p1, p2):
    seen = set()
    while p1 and p2:
        hashed = (tuple(p1), tuple(p2))
        if hashed in seen:
            return 1, 0
        seen.add(hashed)
        c1, c2 = p1[0], p2[0]
        p1.rotate(-1)
        p2.rotate(-1)
        if c1 < len(p1) and c2 < len(p2):
            new_p1 = deque(list(p1)[:c1])
            new_p2 = deque(list(p2)[:c2])
            recursive_battle = play(new_p1, new_p2)
            winner, loser = (p1, p2) if recursive_battle[0] else (p2, p1)
        else:
            winner, loser = (p1, p2) if (c1 > c2) else (p2, p1)
        winner.append(loser.pop())
    return p1, p2


result = play(p1, p2)
result = result[0] if result[0] else result[1]
(np.array(result) * np.arange(1, len(result) + 1)[::-1]).sum()

Day 23: Crab Cups

Part 1

Code

data = [int(x) for x in "583976241"]
s = deque(data)
l = len(s)
for _ in range(100):
    target = (s[0] - 2) % l + 1
    s.rotate(-1)
    pickup = [s.popleft() for i in range(3)]
    while target in pickup:
        target = (target - 2) % l + 1

    count = 0
    while s[0] != target:
        s.rotate(-1)
        count += 1
    s.rotate(-1)
    for value in pickup[::-1]:
        s.appendleft(value)
    s.rotate(count + 1)
while s[0] != 1:
    s.rotate()
s.popleft()
"".join(str(x) for x in s)

Part 2

This approach is way too slow for part 2. Instead, we can build an implicit linked list in a numpy array, so that a[node] = next node for all nodes. To make that work with zero based indexing we relabel all the nodes. A single step can now be accomplished by just updating three array elements: the next pointer of the current node, the next pointer of the destination node, and the next pointer of the last of the moved elements.

Code

initial_state = data + list(range(10, 1_000_001))
a = np.zeros(len(initial_state), dtype=int)
minval = min(initial_state)
for c, n in zip(initial_state, initial_state[1:] + [initial_state[0]]):
    a[c - 1] = n - 1
current = a[-1]
for _ in range(10_000_000):
    to_move = [a[current], a[a[current]], a[a[a[current]]]]
    destination = current - 1
    while destination < 0 or destination in to_move:
        destination -= 1
        if destination < 0:
            destination = 999_999
    # next pointer of current is the one after the moved ones
    a[current] = a[to_move[-1]]
    # The next one after the moved three is the one after the destination
    a[to_move[-1]] = a[destination]
    # After the destination comes the first of the moved ones
    a[destination] = to_move[0]
    # And we move to the next node
    current = a[current]
(a[0] + 1) * (a[a[0]] + 1)

Day 24: Lobby Layout

Part 1

Code

vectors = {
    "e": (1, 0),
    "ne": (1, 1),
    "nw": (0, 1),
    "w": (-1, 0),
    "sw": (-1, -1),
    "se": (0, -1),
}
current = ""
terminals = "ew"
tiles = defaultdict(bool)
for s in load(24):
    result = []
    for char in s:
        current += char
        if char in terminals:
            result.append(vectors[current])
            current = ""
    coords = tuple(np.array(result).sum(axis=0))
    tiles[coords] ^= 1
np.sum(list(tiles.values()))

Part 2

This is a fairly simple convolution problem again. We’ll be working in the basis defined above, and in that basis, the neighbors are as given in the vectors dictionary. So the array of weights is the one below.

Code

keys = list(tiles.keys())
weights = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]
border = 100
size = 2 * border + np.max(keys) - np.min(keys)
board = np.zeros((size, size), dtype=int)
for x, y in tiles:
    board[x + size // 2, y + size // 2] = tiles[x, y]
for i in range(100):
    neighbors = scipy.ndimage.correlate(board, weights, mode="constant")
    flips = ((board == 0) & (neighbors == 2)) | (
        (board == 1) & ((neighbors == 0) | (neighbors > 2))
    )
    board = (board + flips) % 2
board.sum()

Day 25: Combo Breaker

Code

d = 14222596
c = 4057428
s1, s2 = 0, 0
f = 7
v = 1
mod = 20201227
i = 0
while not s1 or not s2:
    v = v * f % mod
    i += 1
    if v == d and not s1:
        s1 = i
    if v == c and not s2:
        s2 = i
r1 = 1
for i in range(s1):
    r1 = r1 * c % mod
r1