Advent of Code 2020

01.py

from itertools import combinations

with open("01.txt", 'r') as f:
    nums = [int(line.rstrip()) for line in f]

# 1a
print(next(a * b for a, b in combinations(nums, 2) if a + b == 2020))

# 1b
for a, b, c in combinations(nums, 3):
    if a + b + c == 2020:
        print(a * b * c)
        break

02.py

from operator import xor

data = []
with open("02.txt", 'r') as f:
    for line in f:
        nums, letter, password = line.split()
        data.append((*[int(x) for x in nums.split("-")], letter[0], password))

# 2a
print(sum(n_min <= pwd.count(ltr) <= n_max for n_min, n_max, ltr, pwd in data))

# 2b
num_valid = 0
for pos1, pos2, letter, password in data:
    num_valid += xor(password[pos1 - 1] == letter, password[pos2 - 1] == letter)
print(num_valid)

03.py

with open("03.txt", 'r') as f:
    rows = [line.rstrip() for line in f]

# 3a
print(sum(rows[i][i * 3 % len(rows[i])] == "#" for i in range(len(rows))))

# 3b
slopes = ((1, 1), (3, 1), (5, 1), (7, 1), (1, 2))
width = len(rows[0])
answer = 1
for dx, dy in slopes:
    squares = [rows[i][i * dx // dy % width] for i in range(0, len(rows), dy)]
    answer *= squares.count("#")
print(answer)

04.py

import re

required = ("byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid")
data = []
with open("04.txt", 'r') as f:
    for record in f.read().split("\n\n"):
        data.append(dict(word.split(":") for word in record.split()))

# 4a
print(sum(all(field in passport for field in required) for passport in data))

# 4b
validators = {
    "byr": lambda x: x.isdigit() and 1920 <= int(x) <= 2002,
    "iyr": lambda x: x.isdigit() and 2010 <= int(x) <= 2020,
    "eyr": lambda x: x.isdigit() and 2020 <= int(x) <= 2030,
    "hgt": lambda x: x[-2:] in "cm in" and validators["hgt_" + x[-2:]](x[:-2]),
    "hgt_cm": lambda x: x.isdigit() and 150 <= int(x) <= 193,
    "hgt_in": lambda x: x.isdigit() and 59 <= int(x) <= 76,
    "hcl": lambda x: re.match(r"#[0-9a-f]{6}", x) is not None,
    "ecl": lambda x: x in "amb blu brn gry grn hzl oth",
    "pid": lambda x: x.isdigit() and len(x) == 9
}
num_valid = 0
for passport in data:
    for field in required:
        if field not in passport or not validators[field](passport[field]):
            break
    else:
        num_valid += 1
print(num_valid)

05.py

translation = str.maketrans("FBLR", "0101")
with open("05.txt", 'r') as f:
    seats = [line.rstrip() for line in f]

# 5a
print(max(int(seat.translate(translation), 2) for seat in seats))

# 5b
seat_ids = sorted(int(seat.translate(translation), 2) for seat in seats)
print(sum(range(seat_ids[0], seat_ids[-1] + 1)) - sum(seat_ids))

06.py

from collections import Counter

with open("06.txt", 'r') as f:
    data = [lines.split() for lines in f.read().split("\n\n")]

# 6a
print(sum(len(set("".join(group))) for group in data))

# 6b
num_unanimous = 0
for group in data:
    num_unanimous += list(Counter("".join(group)).values()).count(len(group))
print(num_unanimous)

07.py

import re
from itertools import chain

rules = {}
with open("07.txt", 'r') as f:
    for line in f:
        match = re.match(r"([a-z ]+) bags contain (.+)\.", line)
        rule = {}
        for match2 in re.finditer(r"(\d+) ([a-z ]+) bag", match.group(2)):
            rule[match2.group(2)] = int(match2.group(1))
        rules[match.group(1)] = rule

# 7a
def colors(color):
    return chain(*([x, *colors(x)] for x in rules if color in rules[x]))
print(len(set(colors("shiny gold"))))

# 7b
def bags(color, num=1):
    return sum(num * (v + bags(k, v)) for k, v in rules[color].items())
print(bags("shiny gold"))

08.py

instructions = []
with open("08.txt", 'r') as f:
    for line in f:
        op, arg = line.split()
        instructions.append((op, int(arg)))

# 8a
visited = []
acc = idx = 0
while idx not in visited:
    visited.append(idx)
    op, arg = instructions[idx]
    acc += arg if op == "acc" else 0
    idx += arg if op == "jmp" else 1
print(acc)

# 8b
for i in range(len(instructions)):
    if instructions[i][0] == "acc":
        continue
    visited = []
    acc = idx = 0
    while idx not in visited and idx < len(instructions):
        visited.append(idx)
        op, arg = instructions[idx]
        acc += arg if op == "acc" else 0
        idx += arg if op == ("jmp", "nop")[idx == i] else 1
    if idx == len(instructions):
        break
print(acc)

09.py

with open("09.txt", 'r') as f:
    nums = [int(line.rstrip()) for line in f]

# 9a
for i in range(25, len(nums)):
    prev = nums[i - 25:i]
    if not any(nums[i] - num in prev for num in prev):
        invalid_num = nums[i]
        break
print(invalid_num)

# 9b
for i in range(len(nums) - 1):
    num = nums[i]
    for j in range(i + 1, len(nums)):
        num += nums[j]
        if num >= invalid_num:
            break
    if num == invalid_num:
        break
print(min(nums[i:j]) + max(nums[i:j]))

10.py

from itertools import takewhile

with open("10.txt", 'r') as f:
    nums = [int(line.rstrip()) for line in f]

# 10a
nums.sort()
diffs = [b - a for a, b in zip([0] + nums, nums + [nums[-1] + 3])]
print(diffs.count(1) * diffs.count(3))

# 10b
def adapters(i):
    count = len(list(takewhile(lambda x: x <= nums[i] + 3, nums[i + 1:i + 4])))
    return count, sum(adapters(i + j)[1] for j in range(1, count)) + 1
nums = [0, *nums, nums[-1] + 3]
i = 0
answer = 1
while i < len(nums) - 1:
    count, rec_count = adapters(i)
    i += count
    answer *= rec_count
print(answer)

11.py

from copy import deepcopy
from itertools import product

deltas = ((0, 1), (0, -1), (-1, 0), (1, 0), (1, 1), (-1, 1), (-1, -1), (1, -1))
with open("11.txt", 'r') as f:
    rows = [list(line.rstrip()) for line in f]
def is_occupied(x, y):
    return 0 <= x < len(rows[0]) and 0 <= y < len(rows) and rows[y][x] == "#"

# 11a
def occupied_adj(x, y):
    return sum(is_occupied(x + dx, y + dy) for dx, dy in deltas)
old_rows = deepcopy(rows)
while True:
    new_rows = deepcopy(rows)
    for x, y in product(range(len(rows[0])), range(len(rows))):
        if rows[y][x] == "L" and not occupied_adj(x, y):
            new_rows[y][x] = "#"
        elif rows[y][x] == "#" and occupied_adj(x, y) >= 4:
            new_rows[y][x] = "L"
    if new_rows == rows:
        break
    rows = new_rows
print("".join("".join(row) for row in rows).count("#"))

# 11b
def next_seat(x, y, dx, dy):
    x, y = x + dx, y + dy
    while 0 <= x < len(rows[0]) and 0 <= y < len(rows) and rows[y][x] == ".":
        x, y = x + dx, y + dy
    return x, y
def occupied_adj(x, y):
    return sum(is_occupied(*next_seat(x, y, dx, dy)) for dx, dy in deltas)
rows = old_rows
while True:
    new_rows = deepcopy(rows)
    for x, y in product(range(len(rows[0])), range(len(rows))):
        if rows[y][x] == "L" and not occupied_adj(x, y):
            new_rows[y][x] = "#"
        elif rows[y][x] == "#" and occupied_adj(x, y) >= 5:
            new_rows[y][x] = "L"
    if new_rows == rows:
        break
    rows = new_rows
print("".join("".join(row) for row in rows).count("#"))

12.py

import math

actions = {"N": (0, 1), "S": (0, -1), "E": (1, 0), "W": (-1, 0)}
with open("12.txt", 'r') as f:
    instructions = [(line[0], int(line[1:].rstrip())) for line in f]

# 12a
x = y = theta = 0
for op, arg in instructions:
    if op in actions:
        x, y = x + arg * actions[op][0], y + arg * actions[op][1]
    elif op == "L" or op == "R":
        theta += math.radians(arg) * (-1, 1)[op == "L"]
    elif op == "F":
        x, y = x + arg * math.cos(theta), y + arg * math.sin(theta)
print(round(abs(x) + abs(y)))

# 12b
x = y = 0
x2, y2 = 10, 1
for op, arg in instructions:
    if op in actions:
        x2, y2 = x2 + arg * actions[op][0], y2 + arg * actions[op][1]
    elif op == "L" or op == "R":
        dx, dy = x2 - x, y2 - y
        r, theta = math.sqrt(dx**2 + dy**2), math.atan2(dy, dx)
        theta += math.radians(arg) * (-1, 1)[op == "L"]
        x2, y2 = x + r * math.cos(theta), y + r * math.sin(theta)
    elif op == "F":
        dx, dy = arg * (x2 - x), arg * (y2 - y)
        x, y = x + dx, y + dy
        x2, y2 = x2 + dx, y2 + dy
print(round(abs(x) + abs(y)))

13.py

from functools import reduce

with open("13.txt", 'r') as f:
    timestamp = int(f.readline().rstrip())
    buses = [int(x) if x != "x" else -1 for x in f.readline().split(",")]

# 13a
bus_ids = list(filter(lambda x: x != -1, buses))
times = [timestamp + bus_id - (timestamp % bus_id) for bus_id in bus_ids]
idx = 0
for i in range(1, len(times)):
    if times[i] >= timestamp and times[i] < times[idx]:
        idx = i
print(bus_ids[idx] * (times[idx] - timestamp))

# 13b - https://rosettacode.org/wiki/Chinese_remainder_theorem
def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * pow(p, -1, n_i) * p
    return sum % prod
bus_ids = list(filter(lambda x: x != -1, buses))
print(chinese_remainder(bus_ids, [-buses.index(bus_id) for bus_id in bus_ids]))

14.py

with open("14.txt", 'r') as f:
    data = [line.rstrip().split(" = ") for line in f]
for i, (fst, snd) in enumerate(data):
    if fst.startswith("mem"):
        data[i] = (fst[:3], int(fst[4:-1]), int(snd))

# 14a
mask = "X" * 36
memory = {}
for op, *args in data:
    if op == "mask":
        mask = args[0]
    elif op == "mem":
        value = format(args[1], "036b")
        result = [mask[i] if mask[i] != "X" else value[i] for i in range(36)]
        memory[args[0]] = int("".join(result), 2)
print(sum(memory.values()))

# 14b
mask = "X" * 36
memory = {}
for op, *args in data:
    if op == "mask":
        mask = args[0]
    elif op == "mem":
        address = format(args[0], "036b")
        results = [""]
        for i in range(36):
            results[0] += mask[i] if mask[i] != "0" else address[i]
        while "X" in results[0]:
            idx = results[0].index("X")
            new_results = []
            for address in results:
                new_results.append(address[:idx] + "0" + address[idx + 1:])
                new_results.append(address[:idx] + "1" + address[idx + 1:])
            results = new_results
        for address in results:
            memory[int(address, 2)] = args[1]
print(sum(memory.values()))

15.py

from collections import defaultdict

nums = [int(x) for x in "1,20,11,6,12,0".split(",")]

# 15a
turns = nums[:]
for i in range(len(nums), 2020):
    prev = turns[-1]
    if turns.count(prev) > 1:
        turns.append(turns[-2 - turns[-1::-1].index(prev)::-1].index(prev) + 1)
    else:
        turns.append(0)
print(turns[-1])

# 15b
turns = defaultdict(list, {nums[i]: [i] for i in range(len(nums))})
last_num = nums[-1]
for i in range(len(nums), 30000000):
    history = turns[last_num]
    last_num = (history[-1] - history[-2]) if len(history) > 1 else 0
    turns[last_num].append(i)
print(last_num)