Untitled Python Project

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)

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)

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()