from __future__ import annotations
from collections import Counter, defaultdict, namedtuple, deque
from itertools import permutations, combinations, product, chain
from functools import lru_cache, reduce
from typing import Dict, Tuple, Set, List, Iterator, Optional, Union, Sequence
from contextlib import contextmanager
import operator
import math
import ast
import sys
import re
def data(day: int, parser=str, sep='\n') -> list:
"Split the day's input file into sections separated by `sep`, and apply `parser` to each."
with open(f'data/advent2020/input{day}.txt') as f:
sections = f.read().rstrip().split(sep)
return list(map(parser, sections))
def do(day, *answers) -> List[int]:
"E.g., do(3) returns [day3_1(in3), day3_2(in3)]. Verifies `answers` if given."
g = globals()
got = []
for part in (1, 2):
fname = f'day{day}_{part}'
if fname in g:
got.append(g[fname](g[f'in{day}']))
if len(answers) >= part:
assert got[-1] == answers[part - 1], (
f'{fname}(in{day}) got {got[-1]}; expected {answers[part - 1]}')
else:
got.append(None)
return got
Number = Union[float, int]
Atom = Union[Number, str]
Char = str # Type used to indicate a single character
cat = ''.join
flatten = chain.from_iterable
def quantify(iterable, pred=bool) -> int:
"Count the number of items in iterable for which pred is true."
return sum(1 for item in iterable if pred(item))
def first(iterable, default=None) -> object:
"Return first item in iterable, or default."
return next(iter(iterable), default)
def prod(numbers) -> Number:
"The product of an iterable of numbers."
return reduce(operator.mul, numbers, 1)
def dot(A, B) -> Number:
"The dot product of two vectors of numbers."
return sum(a * b for a, b in zip(A, B))
def ints(text: str) -> Tuple[int]:
"Return a tuple of all the integers in text."
return mapt(int, re.findall('-?[0-9]+', text))
def lines(text: str) -> List[str]:
"Split the text into a list of lines."
return text.strip().splitlines()
def mapt(fn, *args):
"Do map(fn, *args) and make the result a tuple."
return tuple(map(fn, *args))
def atoms(text: str, ignore=r'', sep=None) -> Tuple[Union[int, str]]:
"Parse text into atoms separated by sep, with regex ignored."
text = re.sub(ignore, '', text)
return mapt(atom, text.split(sep))
def atom(text: str, types=(int, str)):
"Parse text into one of the given types."
for typ in types:
try:
return typ(text)
except ValueError:
pass
@contextmanager
def binding(**kwds):
"Bind global variables within a context; revert to old values on exit."
old_values = {k: globals()[k] for k in kwds}
try:
globals().update(kwds)
yield # Stuff within the context gets run here.
finally:
globals().update(old_values)
in1: Set[int] = set(data(1, int))
Execution Error
FileNotFoundError: [Errno 2] No such file or directory: 'data/advent2020/input1.txt'
def day1_1(nums):
"Find 2 distinct numbers that sum to 2020, and return their product."
return first(x * y
for x in nums
for y in nums & {2020 - x}
if x != y)
def day1_2(nums):
"Find 3 distinct numbers that sum to 2020, and return their product."
return first(x * y * z
for x, y in combinations(nums, 2)
for z in nums & {2020 - x - y}
if x != z != y)
do(1, 787776, 262738554)
Policy = Tuple[int, int, Char, str]
def parse_password_policy(line: str) -> Policy:
"Given '1-3 b: cdefg', return (1, 3, 'b', 'cdefg')."
a, b, L, pw = re.findall(r'[^-:\s]+', line)
return (int(a), int(b), L, pw)
in2: List[tuple] = data(2, parse_password_policy)
def valid_password(policy) -> bool:
"Does policy's pw have between a and b instances of letter L?"
a, b, L, pw = policy
return a <= pw.count(L) <= b
def day2_1(policies): return quantify(policies, valid_password)
def day2_2(policies): return quantify(policies, valid_password_2)
def valid_password_2(policy) -> bool:
"Does line's pw have letter L at position a or b (1-based), but not both?"
a, b, L, pw = policy
return (L == pw[a - 1]) ^ (L == pw[b - 1])
do(2, 383, 272)
Picture = List[str]
in3: Picture = data(3)
def day3_1(picture, dx=3, dy=1, tree='#'):
"How many trees are on the coordinates on the slope dy/dx?"
return quantify(row[(dx * y) % len(row)] == tree
for y, row in enumerate(picture[::dy]))
def day3_2(picture):
"What is the product of the number of trees on these five slopes?"
def t(dx, dy): return day3_1(picture, dx, dy)
return t(1, 1) * t(3, 1) * t(5, 1) * t(7, 1) * t(1, 2)
do(3, 167, 736527114)
Passport = dict # e.g. {'iyr': '2013', ...}
def parse_passport(text: str) -> Passport:
"Make a dict of the 'key:val' entries in text."
return Passport(re.findall(r'([a-z]+):([^\s]+)', text))
assert parse_passport('''a:1 b:two\nsee:3''') == {'a': '1', 'b': 'two', 'see': '3'}
in4: List[Passport] = data(4, parse_passport, '\n\n') # Passports are separated by blank lines
required_fields = {'byr', 'ecl', 'eyr', 'hcl', 'hgt', 'iyr', 'pid'}
def day4_1(passports): return quantify(passports, required_fields.issubset)
def day4_2(passports): return quantify(passports, valid_passport_fields)
def valid_passport_fields(passport) -> bool:
'''Validate fields according to the following rules:
byr (Birth Year) - four digits; at least 1920 and at most 2002.
iyr (Issue Year) - four digits; at least 2010 and at most 2020.
eyr (Expr. Year) - four digits; at least 2020 and at most 2030.
hgt (Height) - a number followed by either cm or in:
If cm, the number must be at least 150 and at most 193.
If in, the number must be at least 59 and at most 76.
hcl (Hair Color) - a '#' followed by exactly six characters 0-9 or a-f.
ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth.
pid (Passport ID) - a nine-digit number, including leading zeroes.
cid (Country ID) - ignored, missing or not.'''
return all(field in passport and field_validator[field](passport[field])
for field in required_fields)
field_validator = dict(
byr=lambda v: 1920 <= int(v) <= 2002,
iyr=lambda v: 2010 <= int(v) <= 2020,
eyr=lambda v: 2020 <= int(v) <= 2030,
hcl=lambda v: re.match('#[0-9a-f]{6}$', v),
ecl=lambda v: re.match('(amb|blu|brn|gry|grn|hzl|oth)$', v),
pid=lambda v: re.match('[0-9]{9}$', v),
hgt=lambda v: ((v.endswith('cm') and 150 <= int(v[:-2]) <= 193) or
(v.endswith('in') and 59 <= int(v[:-2]) <= 76)))
do(4, 237, 172)
ID = int # A type
def seat_id(seat: str, table=str.maketrans('FLBR', '0011')) -> ID:
"Treat a seat description as a binary number; convert to int."
return ID(seat.translate(table), base=2)
assert seat_id('FBFBBFFRLR') == 357
in5: List[ID] = data(5, seat_id)
day5_1 = max # Find the maximum seat id.
def day5_2(ids):
"The one missing seat id."
[missing] = set(range(min(ids), max(ids))) - set(ids)
return missing
do(5, 906, 519)
Group = List[str]
in6: List[Group] = data(6, lines, sep='\n\n')
def day6_1(groups):
"For each group, compute the number of letters that ANYONE got. Sum them."
return sum(len(set(cat(group)))
for group in groups)
def day6_2(groups):
"For each group, compute the number of letters that EVERYONE got. Sum them."
return sum(len(set.intersection(*map(set, group)))
for group in groups)
do(6, 6530, 3323)
Bag = str
BagRules = Dict[Bag, Dict[Bag, int]] # {outer: {inner: count, ...}, ...}
def parse_bag_rule(line: str) -> Tuple[Bag, Dict[Bag, int]]:
"Return (outer_bag, {inner_bag: num, ...})"
line = re.sub(' bags?|[.]', '', line) # Remove redundant info
outer, inner = line.split(' contain ')
return outer, dict(map(parse_inner, inner.split(', ')))
def parse_inner(text) -> Tuple[Bag, int]:
"Return the color and number of inner bags."
n, bag = text.split(maxsplit=1)
return bag, (0 if n == 'no' else int(n))
assert parse_inner('3 muted gray') == ('muted gray', 3)
assert (dict([parse_bag_rule("shiny gold bags contain 4 bright blue bags")])
== {'shiny gold': {'bright blue': 4}})
in7: BagRules = dict(data(7, parse_bag_rule))
def day7_1(rules, target='shiny gold'):
"How many colors of bags can contain the target color bag?"
@lru_cache(None)
def contains(bag, target) -> bool:
"Does this bag contain the target (perhaps recursively)?"
contents = rules.get(bag, {})
return (target in contents
or any(contains(inner, target) for inner in contents))
return quantify(contains(bag, target) for bag in rules)
def num_contained_in(rules, target='shiny gold') -> int:
"How many bags are contained (recursively) in the target bag?"
return sum(n + n * num_contained_in(rules, inner)
for (inner, n) in rules[target].items() if n > 0)
day7_2 = num_contained_in
do(7, 103, 1469)
Instruction = Tuple[str, int] # e.g. ('jmp', +4)
Program = List[Instruction]
in8: Program = data(8, atoms)
def day8_1(program):
"Execute the program until it loops; then return accum."
pc = accum = 0
executed = set() # Set of instruction addresses executed so far
while True:
if pc in executed:
return accum
executed.add(pc)
opcode, arg = program[pc]
pc += 1
if opcode == 'acc':
accum += arg
if opcode == 'jmp':
pc = pc - 1 + arg
def day8_2(program):
"Return the accumulator from the first altered program that terminates."
programs = altered_programs(program)
return first(accum for (terminates, accum) in map(run_program, programs)
if terminates)
def altered_programs(program, other=dict(jmp='nop', nop='jmp')) -> Iterator[Program]:
"All ways to swap a nop for a jmp or vice-versa."
for i, (opcode, arg) in enumerate(program):
if opcode in other:
yield [*program[:i], (other[opcode], arg), *program[i + 1:]]
def run_program(program) -> Tuple[bool, int]:
"Run the program until it loops or terminates; return (terminates, accum)"
pc = accum = 0
executed = set() # Set of instruction addresses executed so far
while 0 <= pc < len(program):
if pc in executed:
return False, accum # program loops
executed.add(pc)
opcode, arg = program[pc]
pc += 1
if opcode == 'acc':
accum += arg
if opcode == 'jmp':
pc = pc - 1 + arg
return True, accum # program terminates
do(8, 1521, 1016)
in9: List[int] = data(9, int)
def day9_1(nums, p=25):
"""Find the first number in the list of numbers (after a preamble of p=25 numbers)
which is not the sum of two of the p numbers before it."""
return first(x for i, x in enumerate(nums)
if i > p and x not in twosums(nums[i-p:i]))
def twosums(nums): return map(sum, combinations(nums, 2))
def day9_2(nums, target=day9_1(in9)):
"Find a contiguous subsequence of nums that sums to target; add their max and min."
subseq = find_subseq(nums, target)
return max(subseq) + min(subseq)
def find_subseq(nums, target) -> Optional[deque]:
"Find a contiguous subsequence of nums that sums to target."
subseq = deque()
total = 0
for x in nums:
if total < target:
subseq.append(x)
total += x
if total == target and len(subseq) >= 2:
return subseq
while total > target:
total -= subseq.popleft()
return None
do(9, 776203571, 104800569)
in10: List[int] = data(10, int) # Input is the joltage of each adapter
def day10_1(jolts):
"""Arrange the joltages in order; count the number of each size difference;
return the product of 1- and 3-jolt differences."""
jolts = [0] + sorted(jolts) + [max(jolts) + 3]
diffs = Counter(jolts[i + 1] - jolts[i]
for i in range(len(jolts) - 1))
assert {1, 2, 3}.issuperset(diffs)
return diffs[1] * diffs[3]
def day10_2(jolts): return arrangements(tuple(sorted(jolts)), 0)
@lru_cache(None)
def arrangements(jolts, prev) -> int:
"The number of arrangements that go from prev to the end of `jolts`."
first, rest = jolts[0], jolts[1:]
if first - prev > 3:
return 0
elif not rest:
return 1
else:
return (arrangements(rest, first) + # Use first
arrangements(rest, prev)) # Skip first
assert arrangements((3, 6, 9, 12), 0) == 1
assert arrangements((3, 6, 9, 13), 0) == 0
assert arrangements((1, 2, 3, 4), 0) == 7
do(10, 2346, 6044831973376)
in11: List[str] = data(11)
floor, empty, occupied, off = ".L#?"
Contents = Char # The contents of each location is one of the above 4 characters
class Layout(list):
"A layout of seats (occupied or not) and floor space."
crowded = 4
deltas = ((-1, -1), (0, -1), (1, -1),
(-1, 0), (1, 0),
(-1, +1), (0, +1), (1, +1))
def next_generation(self) -> Layout:
"The next generation, according to the rules."
seats = (cat(self.next_generation_at(x, y) for x in range(len(self[y])))
for y in range(len(self)))
return type(self)(seats)
def next_generation_at(self, x, y) -> Contents:
"The contents of location (x, y) in the next generation."
old = self[y][x]
N = self.neighbors(x, y).count(occupied)
return (occupied if old is empty and N == 0 else
empty if old is occupied and N >= self.crowded else
old)
def neighbors(self, x, y) -> List[Contents]:
"The contents of the 8 neighboring locations."
return [self.at(x + dx, y + dy) for dx, dy in self.deltas]
def count(self, kind: Contents) -> int: return cat(self).count(kind)
def at(self, x, y) -> Contents:
"The contents of location (x, y): empty, occupied, floor, or off?"
if 0 <= y < len(self) and 0 <= x < len(self[y]):
return self[y][x]
else:
return off
def run(self) -> Layout:
"Run until equilibrium."
new = self
while True:
new, old = new.next_generation(), new
if new == old:
return new
def day11_1(seats): return Layout(seats).run().count(occupied)
def day11_2(seats): return Layout2(seats).run().count(occupied)
class Layout2(Layout):
"A layout of seats (occupied or not) and floor space, with new rules."
crowded = 5
def neighbors(self, x, y) -> List[Contents]:
"The contents of the nearest visible seat in each of the 8 directions."
return [self.visible(x, dx, y, dy) for dx, dy in self.deltas]
def visible(self, x, dx, y, dy) -> Contents:
"The contents of the first visible seat in direction (dx, dy)."
for i in range(1, sys.maxsize):
x += dx; y += dy
if not (0 <= y < len(self) and 0 <= x < len(self[y])):
return off
if self[y][x] is not floor:
return self[y][x]
do(11, 2299, 2047)
in12: List[Instruction] = data(12, lambda line: (line[0], int(line[1:])))
Point = Heading = Tuple[int, int]
directions = dict(N=(0, 1), E=(1, 0), S=(0, -1), W=(-1, 0))
def navigate(instructions, loc=(0, 0), heading=directions['E']) -> Point:
"Follow instructions to change ship's loc and heading; return final loc."
for op, n in instructions:
if op == 'R': heading = turn(n, *heading)
elif op == 'L': heading = turn(-n, *heading)
elif op == 'F': loc = go(n, *loc, *heading)
else: loc = go(n, *loc, *directions[op])
return loc
def turn(degrees, x, y) -> Heading:
"Turn `degrees` from the current (x, y) heading."
return (x, y) if degrees % 360 == 0 else turn(degrees - 90, y, -x)
def go(n, x, y, dx, dy) -> Point:
"Go n steps in the (dx, dy) direction from (x, y)."
return (x + n * dx, y + n * dy)
def manhatten_distance(point) -> int: return sum(map(abs, point))
def day12_1(instructions): return manhatten_distance(navigate(instructions))
def navigate2(instructions, loc=(0, 0), way=(10, 1)) -> Point:
"Follow updated instructions to change ship's loc and waypoint; return final loc."
for op, n in instructions:
if op == 'R': way = turn(n, *way)
elif op == 'L': way = turn(-n, *way)
elif op == 'F': loc = go(n, *loc, *way)
else: way = go(n, *way, *directions[op])
return loc
def day12_2(instructions): return manhatten_distance(navigate2(instructions))
do(12, 439, 12385)
x = 0
in13: Tuple[ID] = (29,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,577,
x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,23,x,x,x,x,x,x,x,601,x,x,x,x,x,
x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37)
def day13_1(ids, start=1000001):
"Find the id of the earliest bus after start; return id * wait."
ids = set(ids) - {x}
id = min(ids, key=lambda id: wait(id, start))
return id * wait(id, start)
def wait(id, t):
"How long you have to wait from t for bus id."
return 0 if t % id == 0 else id - t % id
def day13_2(ids):
"Find the time where all the buses arrive at the right offsets."
schedule = {t: id for t, id in enumerate(ids) if id != x}
step = schedule[0]
return first(t for t in range(0, sys.maxsize, step)
if all(wait(schedule[i], t) == i for i in schedule))
assert day13_2((7,13,x,x,59,x,31,19)) == 1068781
assert day13_2((1789,37,47,1889)) == 1202161486
def day13_2(ids):
"Find the time where all the buses arrive at the right offsets."
time = 0
step = 1
schedule = {t: id for t, id in enumerate(ids) if id != x}
for t in schedule:
while wait(schedule[t], time + t):
time += step
step *= schedule[t]
return time
do(13, 174, 780601154795940)
def parse_docking(line: str) -> tuple:
"Parse 'mask = XX10' to ('mask', 'XX10') and 'mem[8] = 11' to (8, 11)"
if line.startswith('mask'):
return ('mask', line.split()[-1])
else:
return ints(line)
in14 = data(14, parse_docking)
Memory = Dict[int, int]
def run_docking(program) -> Memory:
"Execute the program and return memory."
mask = bin36(0)
mem = defaultdict(int)
for addr, val in program:
if addr == 'mask':
mask = val
else:
mem[addr] = int(cat(m if m in '01' else v
for m, v in zip(mask, bin36(val))),
base=2)
return mem
def bin36(i) -> str: return f'{i:036b}'
assert bin36(255 + 2 ** 20) == '000000000000000100000000000011111111'
def day14_1(program): return sum(run_docking(program).values())
def day14_2(program): return sum(run_docking2(program).values())
def run_docking2(program) -> Memory:
"Execute the program using version 2 instructions and return memory."
mask = bin36(0)
mem = defaultdict(int)
for addr, val in program:
if addr == 'mask':
mask = val
else:
addr = cat(a if m == '0' else '1' if m == '1' else '{}'
for m, a in zip(mask, bin36(addr)))
for bits in product('01', repeat=addr.count('{')):
mem[int(addr.format(*bits), base=2)] = val
return mem
do(14, 11884151942312, 2625449018811)
in15 = 10,16,6,0,1,17
def day15_1(starting: Tuple[int], nth=2020) -> int:
"Return the nth (1-based) number spoken."
last = starting[-1]
# `spoken` is a mapping of {number: turn_when_last_spoken}
spoken = defaultdict(int, {n: t for t, n in enumerate(starting[:-1])})
for t in range(len(starting), nth):
new = 0 if last not in spoken else t - 1 - spoken[last]
spoken[last] = t - 1
last = new
return last
assert day15_1((0, 3, 6), 2020) == 436
def day15_2(starting): return day15_1(starting, nth=30_000_000)
%time do(15, 412, 243)
CPU times: user 7.31 s, sys: 114 ms, total: 7.42 s
Wall time: 7.42 s
TicketData = namedtuple('TicketData', 'fields, your, nearby')
Ticket = ints # A ticket is a tuple of ints
class Sets(tuple):
"A tuple of set-like objects (such as ranges); supports `in`."
def __contains__(self, item): return any(item in s for s in self)
def parse_ticket_sections(fieldstr: str, your: str, nearby: str) -> TicketData:
return TicketData(fields=dict(map(parse_ticket_line, fieldstr)),
your=Ticket(your[1]),
nearby=[Ticket(line) for line in nearby[1:]])
def parse_ticket_line(line: str) -> Tuple[str, Sets]:
"Parse 'row: 10-20 or 30-40' to ('row', Sets((range(10, 21), range(30, 41))))."
field = line.split(':')[0]
a, b, c, d = ints(line.replace('-', ' '))
return field, Sets((range(a, b + 1), range(c, d + 1)))
in16 = parse_ticket_sections(*data(16, lines, sep='\n\n'))
def day16_1(ticket_data):
"The sum of the invalid entries in the nearby tickets."
ranges = Sets(ticket_data.fields.values())
return sum(v for ticket in ticket_data.nearby for v in ticket
if v not in ranges)
def valid_ticket(ticket, ranges) -> bool: return all(v in ranges for v in ticket)
def decode_tickets(ticket_data) -> Dict[str, int]:
"Return a mapping of {field_name: field_number} (index into ticket)."
fields, your, nearby = ticket_data
ranges = Sets(ticket_data.fields.values())
valid = [t for t in nearby + [your] if valid_ticket(t, ranges)]
possible = {i: set(fields) for i in range(len(your))}
while any(len(possible[i]) > 1 for i in possible):
for field_name, i in invalid_fields(valid, fields):
possible[i] -= {field_name}
if len(possible[i]) == 1:
eliminate_others(possible, i)
return {field: i for i, [field] in possible.items()}
def invalid_fields(valid, fields) -> Iterable[Tuple[str, int]]:
"Yield (field_name, field_number) for all invalid fields."
return ((field_name, i) for ticket in valid for i in range(len(ticket))
for field_name in fields
if ticket[i] not in fields[field_name])
def eliminate_others(possible, i):
"Eliminate possible[i] from all other possible[j]."
for j in possible:
if j != i:
possible[j] -= possible[i]
def day16_2(ticket_data):
"The product of the 6 fields that start with 'departure'."
code = decode_tickets(ticket_data)
return prod(ticket_data.your[code[field]]
for field in code if field.startswith('departure'))
do(16, 21071, 3429967441937)
in17: Picture = lines('''
##.#....
...#...#
.#.#.##.
..#.#...
.###....
.##.#...
#.##..##
#.####..
''')
Cell = Tuple[int,...]
def day17_1(picture, d=3, n=6):
"How many cells are active in the nth generation?"
return len(life(parse_cells(picture, d), n))
def parse_cells(picture, d=3, active='#') -> Set[Cell]:
"Convert a 2-d picture into a set of d-dimensional active cells."
return {(x, y, *(0,) * (d - 2))
for (y, row) in enumerate(picture)
for x, cell in enumerate(row) if cell is active}
def life(cells, n) -> Set[Cell]:
"Play n generations of Life."
for g in range(n):
cells = next_generation(cells)
return cells
def next_generation(cells) -> Set[Cell]:
"""The set of live cells in the next generation."""
return {cell for cell, count in neighbor_counts(cells).items()
if count == 3 or (count == 2 and cell in cells)}
@lru_cache()
def cell_deltas(d: int):
return set(filter(any, product((-1, 0, +1), repeat=d)))
def neighbor_counts(cells) -> Dict[Cell, int]:
"""A Counter of the number of live neighbors for each cell."""
return Counter(flatten(map(neighbors, cells)))
def neighbors(cell) -> List[cell]:
"All adjacent neighbors of cell in three dimensions."
return [tuple(map(operator.add, cell, delta))
for delta in cell_deltas(len(cell))]
def day17_2(picture): return day17_1(picture, d=4)
do(17, 291, 1524)
def parse_expr(line) -> tuple:
"Parse an expression: '2 + 3 * 4' => (2, '+', 3, '*', 4)."
return ast.literal_eval(re.sub('([+*])', r",'\1',", line))
in18 = data(18, parse_expr)
operators = {'+': operator.add, '*': operator.mul}
def evaluate(expr) -> int:
"Evaluate an expression under left-to-right rules."
if isinstance(expr, int):
return expr
else:
a, op, b, *rest = expr
x = operators[op](evaluate(a), evaluate(b))
return x if not rest else evaluate((x, *rest))
def day18_1(exprs): return sum(map(evaluate, exprs))
def evaluate2(expr) -> int:
"Evaluate an expression under addition-first rules."
if isinstance(expr, int):
return expr
elif '*' in expr:
i = expr.index('*')
return evaluate2(expr[:i]) * evaluate2(expr[i + 1:])
else:
return sum(evaluate2(x) for x in expr if x is not '+')
def day18_2(exprs): return sum(map(evaluate2, exprs))
do(18, 3885386961962, 112899558798666)
Message = str # A string we are trying to match, e.g. "ababba"
Choice = tuple # A choice of any of the elements, e.g. Choice(([5, 6], [7]))
Pattern = List[Union[Char, int, Choice]]
def parse_messages(rules, messages) -> Tuple[Dict[int, Pattern], List[Message]]:
"Return a dict of {rule_number: pattern} and a list of messages."
return dict(map(parse_rule, rules)), messages
def parse_rule(line):
"Parse '1: 2 3' => (1, [2, 3]); '4: 5, 6 | 7' => (4, Choice(([5, 6], [7])))."
n, *rhs = atoms(line.replace(':', ' ').replace('"', ' '))
if '|' in rhs:
i = rhs.index('|')
rhs = [Choice((rhs[:i], rhs[i + 1:]))]
return n, rhs
in19 = parse_messages(*data(19, lines, sep='\n\n'))
def day19_1(inputs):
"How many messages completely match rule 0?"
rules, messages = inputs
return quantify(match(rules[0], msg, rules) == ''
for msg in messages)
def match(pat, msg, rules) -> Optional[Message]:
"If a prefix of msg matches pat, return remaining str; else None"
if pat and not msg: # Failed to match whole pat
return None
elif not pat: # Matched whole pat
return msg
elif pat[0] == msg[0]: # Matched first char; continue
return match(pat[1:], msg[1:], rules)
elif isinstance(pat[0], int): # Look up the rule number
return match(rules[pat[0]] + pat[1:], msg, rules)
elif isinstance(pat[0], Choice): # Match any of the choices
for choice in pat[0]:
m = match(choice + pat[1:], msg, rules)
if m is not None:
return m
return None
def day19_2(inputs):
"How many messages completely match rule 0, with new rules 8 and 11?"
rules, messages = inputs
rules2 = {**rules, 8: [42, maybe(8)], 11: [42, maybe(11), 31]}
return day19_1((rules2, messages))
def maybe(n): return Choice(([], [n]))
do(19, 190, 311)
def jigsaw_tiles(sections: List[List[str]]) -> Dict[ID, Picture]:
"Return a dict of {tile_id: tile_picture}."
return {first(ints(header)): tile
for (header, *tile) in sections}
in20 = jigsaw_tiles(data(20, lines, sep='\n\n'))
Edge = str
def day20_1(tiles: Dict[ID, Picture]):
"The product of the ID's of the 4 corner tiles."
edge_count = Counter(canonical(e) for id in tiles for e in edges(tiles[id]))
is_outermost = lambda edge: edge_count[canonical(edge)] == 1
is_corner = lambda tile: quantify(edges(tile), is_outermost) == 2
corners = [id for id in tiles if is_corner(tiles[id])]
return prod(corners)
def edges(tile) -> Iterable[Edge]:
"The 4 edges of a tile."
for i in (0, -1):
yield tile[i] # top/bottom
yield cat(row[i] for row in tile) # left/right
def canonical(edge) -> Edge: return min(edge, edge[::-1])
do(20, 15670959891893)
Ingredient = str
Allergen = str
Food = namedtuple('Food', 'I, A') # I for set of ingredients; A for set of allergens
def parse_food(line) -> Food:
"Parse 'xtc wkrp (contains fish, nuts)' => Food({'xtc', 'wkrp'}, {'fish', 'nuts'})"
ingredients, allergens = line.split('(contains')
return Food(set(atoms(ingredients)), set(atoms(allergens, ignore='[,)]')))
in21 = data(21, parse_food)
def day21_1(foods):
"How many times does an ingredient with an allergen appear?"
bad = bad_ingredients(foods)
allergens = set(flatten(bad.values()))
return sum(len(food.I - allergens) for food in foods)
def bad_ingredients(foods) -> Dict[Allergen, Set[Ingredient]]:
"A dict of {allergen: {set_of_ingredients_it_could_be}}; each set should have len 1."
all_I = set(flatten(food.I for food in foods))
all_A = set(flatten(food.A for food in foods))
possible = {a: set(all_I) for a in all_A}
while any(len(possible[a]) > 1 for a in possible):
for food in foods:
for a in food.A:
possible[a] &= food.I
if len(possible[a]) == 1:
eliminate_others(possible, a)
return possible
def day21_2(foods) -> str:
"What are the bad ingredients, sorted by the allergen name that contains them?"
bad = bad_ingredients(in21)
return ','.join(first(bad[a]) for a in sorted(bad))
do(21, 2282, 'vrzkz,zjsh,hphcb,mbdksj,vzzxl,ctmzsr,rkzqs,zmhnj')
Deal = Union[tuple, deque] # Cards are a tuple on input; a deque internally
Deals = Tuple[Deal, Deal] # Cards are split into two piles for the two players.
in22: Deals = (
(12,40,50,4,24,15,22,43,18,21,2,42,27,36,6,31,35,20,32,1,41,14,9,44,8),
(30,10,47,29,13,11,49,7,25,37,33,48,16,5,45,19,17,26,46,23,34,39,28,3,38))
def day22_1(deals): return combat_score(combat(deals))
def combat(deals: Deals) -> Deals:
"Given two deals, play Combat and return the final deals (one of which will be empty)."
deals = mapt(deque, deals)
while all(deals):
topcards = mapt(deque.popleft, deals)
winner = 0 if topcards[0] > topcards[1] else 1
deals[winner].extend(sorted(topcards, reverse=True))
return deals
def combat_score(deals: Deals) -> int:
"The winner's cards, each multiplied by their reverse index number, and summed."
winning = deals[0] or deals[1]
return dot(winning, range(len(winning), 0, -1))
def day22_2(deals): return combat_score(recursive_combat(deals))
def recursive_combat(deals: Deals) -> Deals:
"A game of Recursive Combat."
deals = mapt(deque, deals)
previously = set()
while all(deals):
if seen(deals, previously):
return (deals[0], ())
topcards = mapt(deque.popleft, deals)
if all(len(deals[p]) >= topcards[p] for p in (0, 1)):
deals2 = [tuple(deals[p])[:topcards[p]] for p in (0, 1)]
result = recursive_combat(deals2)
winner = 0 if result[0] else 1
else:
winner = 0 if topcards[0] > topcards[1] else 1
deals[winner].extend([topcards[winner], topcards[1 - winner]])
return deals
def seen(deals, previously) -> bool:
"Return True if we have seen this pair of deals previously; else just remember it."
hasht = mapt(tuple, deals)
if hasht in previously:
return True
else:
previously.add(hasht)
return False
do(22, 31809, 32835)
in23 = '872495136'
Cup = int # The label on a cup (not the index of the cup in the list of cups)
def day23_1(cupstr: str, n=100):
"Return the int representing the cups, in order, after cup 1; resulting from n moves."
cups = list(map(int, cupstr))
current = cups[0]
for i in range(n):
picked = pickup(cups, current)
dest = destination(cups, current)
place(cups, picked, dest)
current = clockwise(cups, current)
return after(1, cups)
def pickup(cups, current) -> List[Cup]:
"Return the 3 cups clockwise of current; remove them from cups."
i = cups.index(current)
picked, cups[i+1:i+4] = cups[i+1:i+4], []
extra = 3 - len(picked)
if extra:
picked += cups[:extra]
cups[:extra] = []
return picked
def destination(cups, current) -> Cup:
"The cup with label one less than current, or max(cups)."
return max((c for c in cups if c < current), default=max(cups))
def clockwise(cups, current) -> Cup:
"The cup one clockwise of current."
return cups[(cups.index(current) + 1) % len(cups)]
def place(cups, picked, dest):
"Put `picked` after `dest`"
i = cups.index(dest) + 1
cups[i:i] = picked
def after(cup, cups) -> int:
"All the cups after `cup`, in order."
i = cups.index(cup) + 1
string = cat(map(str, cups + cups))
return int(string[i:i+len(cups)])
do(23, 278659341)
in24 = data(24)
def day24_1(lines: List[str]):
"How many tiles are flipped an odd number of times?"
counts = Counter(map(follow_hex, lines))
return quantify(counts[tile] % 2 for tile in counts)
hexdirs = dict(e=(1, 0), w=(-1, 0), ne=(1, -1), sw=(-1, 1), se=(0, 1), nw=(0, -1))
def parse_hex(line) -> List[str]: return re.findall('e|w|ne|sw|se|nw', line)
def follow_hex(directions: str):
"What (x, y) location do you end up at after following directions?"
x, y = 0, 0
for dir in parse_hex(directions):
dx, dy = hexdirs[dir]
x += dx
y += dy
return (x, y)
assert parse_hex('wsweesene') == ['w', 'sw', 'e', 'e', 'se', 'ne']
assert follow_hex('eeew') == (2, 0)
def day24_2(lines: List[str], days=100):
"How many tiles are black after 100 days of Life?"
counts = Counter(map(follow_hex, lines))
blacks = {tile for tile in counts if counts[tile] % 2}
with binding(next_generation=next_generation24,
cell_deltas=cell_deltas24):
return len(life(blacks, 100))
def next_generation24(cells) -> Set[Cell]:
"The set of live cells in the next generation."
counts = neighbor_counts(cells)
return ({c for c in cells if counts[c] in (1, 2)} |
{c for c in counts if c not in cells and counts[c] == 2})
@lru_cache()
def cell_deltas24(d) -> Iterable[Cell]:
"The neighbors are the 6 surrounding hex squares."
return hexdirs.values()
do(24, 420, 4206)
in25 = 1965712, 19072108
def transform(subj) -> Iterator[int]:
"A stream of transformed values, according to the protocol."
val = 1
while True:
val = (val * subj) % 20201227
yield val
def day25_1(keys):
"Find the loopsize for the first key; transform the other key that number of times."
loopsize = first(i for i, val in enumerate(transform(7)) if val == keys[0])
return first(val for i, val in enumerate(transform(keys[1])) if i == loopsize)
do(25, 16881444)
import time
def timing(days=range(1, 26)):
"Report on timing of `do(day)` for all days."
print(' Day Secs. Answers')
print(' === ===== =======')
for day in days:
t0 = time.time()
answers = do(day)
t = time.time() - t0
if answers != [None, None]:
stars = '*' * int(3 + math.log(t, 10))
print(f'{stars:>4} {day:2} {t:6.3f} {answers}')
%time timing()
Day Secs. Answers
=== ===== =======
1 0.000 [787776, 262738554]
2 0.000 [383, 272]
3 0.000 [167, 736527114]
4 0.001 [237, 172]
5 0.000 [906, 519]
6 0.001 [6530, 3323]
7 0.001 [103, 1469]
8 0.008 [1521, 1016]
9 0.003 [776203571, 104800569]
10 0.000 [2346, 6044831973376]
*** 11 8.271 [2299, 2047]
12 0.001 [439, 12385]
13 0.000 [174, 780601154795940]
* 14 0.063 [11884151942312, 2625449018811]
*** 15 7.480 [412, 243]
** 16 0.145 [21071, 3429967441937]
** 17 0.273 [291, 1524]
18 0.005 [3885386961962, 112899558798666]
** 19 0.262 [190, 311]
20 0.001 [15670959891893, None]
21 0.001 [2282, 'vrzkz,zjsh,hphcb,mbdksj,vzzxl,ctmzsr,rkzqs,zmhnj']
*** 22 2.246 [31809, 32835]
23 0.000 [278659341, None]
** 24 0.724 [420, 4206]
*** 25 1.827 [16881444, None]
CPU times: user 21.3 s, sys: 62.1 ms, total: 21.3 s
Wall time: 21.3 s