This year I return to Advent of Code, as I did in 2016, 17, and 18. Thank you, Eric Wastl! You'll have to look at the Advent of Code website if you want the full description of each puzzle; this notebook gives only a brief summary.
For each day from 1 to 25, I'll write four pieces of code, each in a separate notebook cell. For example, on day 3:
in3: List[str] = data(3)
: the day's input data, parsed into an appropriate form (here, a list of string lines). Most days the data comes from a file, read via the function data
(which has optional arguments to say how to split the data into sections/records and how to parse each one), but some days the data is so small I just copy and paste it.def day3_1(nums): ...
: a function that takes the day's data as input and returns the answer for Part 1.def day3_2(nums): ...
: a function that takes the day's data as input and returns the answer for Part 2.do(3)
: executes the call day3_1(in3)
. I'll then use the result to hopefully unlock part 2 and define day3_2
, which also gets run when I call do(3)
again. Once I verify both answers, I'll change do(3)
to do(3, 167, 736527114)
to serve as a unit test.Preparations prior to Day 1:
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[Atom]:
"Parse text (with regex `ignore` ignored) into atoms separated by `sep`"
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)
Notes:
day
functions, which all return int
, except day21_2
).quantify(inputs, P)
: How many of your input items have property P?sum(map(F, inputs))
: What is the sum of the result of applying F to each input item?assert
, but far fewer test cases than if I was programming seriously.in1: Set[int] = set(data(1, int))
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)
[787776, 262738554]
1-3 b: cdefg
" meaning that the password must contain 1 to 3 instances of b
; cdefg
is invalid under this policy. How many passwords in your input file are valid according to their policies?b
. How many passwords are valid according to the new interpretation of the policies?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)
[383, 272]
The input file is a map of a field that looks like this:
..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
where each #
is a tree and the pattern in each row implicitly repeats to the right. We'll call a list of row-strings a picture.
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)
[167, 736527114]
The input is a file of passport data that looks like this (each passport is a series of field:value pairs separated from the next passport by a blank line):
ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
byr:1937 iyr:2017 cid:147 hgt:183cm
hcl:#ae17e1 iyr:2013
eyr:2024 ecl:brn pid:760753108 byr:1931 hgt:179cm
byr, ecl, eyr, hcl, hgt, iyr, pid
).valid_fields
).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)
[237, 172]
The input is a list of boarding passes, such as 'FBFBBFFRLR'
. Each boarding pass corrsponds to a seat ID using an encoding where B and F stand for the back and front half of the remaining part of the plane; R and L stand for right and left half of a row. (The encoding is the same as substituting 0 for F or L, and 1 for B or R, and treating the result as a binary number.)
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)
[906, 519]
Each passenger fills out a customs form; passengers are arranged in groups. The "yes" answer are recorded; each person on one line, each group separated by a blank line. E.g.:
abc
ab
ac
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)
[6530, 3323]
There are strict luggage processing rules for what color bags must contain what other bags. For example:
light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
I wasn't quite sure, but it turns out that "light red" and "dark red" are different colors.
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)
[103, 1469]
The puzzle input is a program in an assembly language with three instructions: jmp, acc, nop
. Since there is no conditional branch instruction, a program that executes any instruction twice will infinite loop; terminating programs will execute each instruction at most once.
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
I had to think about what to do for Part 2. Do I need to make a flow graph of where the loops are? That sounds hard. But I soon realized that I can just use brute force—try every alteration of an instruction (there are only 638 instructions and at most one way to alter each instruction), and run each altered program to see if it terminates (that too takes no more than 638 steps each).
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)
[1521, 1016]
Given a list of numbers:
I could do this efficiently in $O(n)$ as in Day 1, but $n$ is so small I'll just use brute force.
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)
[776203571, 104800569]
You are given a bunch of joltage adapters, each with a listed joltage output; each can take an input source that is 1, 2, or 3 jolts lower than the output. There is a charging outlet rated 0 jolts, and you want to chargwe a device that is 3 jolts higher than the maximum adapter.
Note: at first I thought this was a search problem. But then I realized that the only possibility is to increase joltage from source to adapter, so that means the adapters must appear in sorted order. For part 2, some adapters can be left out.
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)
[2346, 6044831973376]
This is a version of Conway's Life, except that:
The world is bounded, not infinite.
Cells (seats) have three states, not two: floor as well as the traditional occupied and empty.
The rules for what changes between occupied and empty in the next generation are different:
L
) and there are no occupied seats adjacent to it, the seat becomes occupied.#
) and four or more seats adjacent to it are also occupied, the seat becomes empty.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)
[2299, 2047]
I have to confess that I "cheated" here: after seeing the problem description for Part 2, I went back and refactored the code for Part 1 in two places:
Layout
: Introduced the crowded
attribute; it had been an inline literal 4
. Also made deltas
an attribute, not a global constant.next_generation
: Changed Layout(seats)
to type(self)(seats)
.There was more refactoring and less reuse in Part 2 than I would have liked, but I don't feel like I made bad choices in Part 1.
Another problem involving interpreting a kind of assembly language, with navigation instructions for a ship.
The difference between Part 1 and Part 2 comes down to the initial value of the heading/waypoint, and whether the N/E/W/S commands alter the location or the waypoint. Everything else is the same between the two parts.
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)
[439, 12385]
A bus with ID d leaves the terminal at times 0, d, 2d, 3d, ... You are given bus IDs and an earliest time you can leave.
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
Here's a brute-force solution for Part 2 that works for the simple test cases:
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
However, it is clear this will be too slow for the real input data. Instead of looking at every multiple of the first number, I'll incrementally update the step
as we go through the numbers. Out of all the puzzles so far, this is the one I had to think most carefully about. For each bus id, we want to find a time where we get that id right, then step the time by a multiple of all the ids encountered so far:
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)
[174, 780601154795940]
Another "interpret assembly code" puzzle, with two different versions of the instructions (which I won't describe here).
A mask is a bit string but with three possible values at each position, 01X
. I could make it into two bitstrings, but I choose to leave it as a str
.
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)
[11884151942312, 2625449018811]
This puzzle involves a game where players speak a new number each turn, based on previous numbers.
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
Part 2 involves no changes, but asks for the 30 millionth number. If it had been 3 million, I'd think "no problem!" If it had been 30 billion, I'd think "I need a more efficient solution!" As it is, I'll run it and see how long it takes:
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
[412, 243]
That's reasonable; I won't bother trying to find a more efficient approach.
The input to this puzzle has three parts: some rules for valid fields; your ticket; and a set of nearby tickets. The puzzle is to figure out what field number corresponds to what field name (class, row, seat, etc.). The input looks like:
class: 1-3 or 5-7
row: 6-11 or 33-44
your ticket:
7,1,14
nearby tickets:
7,3,47
40,4,50
First parse the input file, introducing the class TicketData
to hold the three parts of the input file (the fields, your ticket, and nearby tickets), and the class Sets
for a tuple of ranges or other set-like objects, so that we can easily test a number is an element of any one of a number of possibilities. For Part 1, just go through the ticket values and see which values are not in any range.
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)
For part 2, we're playing a simplified variant of Sudoku:
possible
for any index number in the tickets.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)
[21071, 3429967441937]
Now we are explicitly playing Life, but in three dimensions, not two. I've coded this before; I'll adapt my old version to three dimensions (actually, make it d
dimensions in general). My implementation represents a generation as the set of active cell coordinates.
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)
[291, 1524]
At first I thought I could just apply eval
to each line, but alas, the operation order is non-standard.
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)
[3885386961962, 112899558798666]
A grep-like pattern matcher, where a message is a sequence of characters (all 'a'
or 'b'
) and a pattern I will represent as a list of items, where each item can be a character, a rule number (which is associated with a pattern), or a choice of two or more patterns. The input has two sections: first "rule number: pattern" lines, then messages, one per line.
I will define match
to return the remaining string in the message if part or all of the message is matched, or None
if it fails.
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
For part 2, I coded the two changed rules by hand, taking care to avoid infinite left-recursion:
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)
[190, 311]
You are given a bunch of picture tiles, which can be put together to form a larger picture, where the edges of tiles match their neighbors.
#
pixels are not part of a sea monster (which is a specific shape)?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'))
For Part 1, I can find the corners without knowing where all the other tiles go. It is guaranteed that "the outermost edges won't line up with any other tiles," but all the inside edges will. We'll define edge_count
to count how many times an edge appears on any tile (using a canonical
orientation, because tiles might be flipped). Then the corner tiles are ones that have two edges that have an edge count of 1.
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)
[15670959891893, None]
Family holiday preparations kept me from doing Part 2 on the night it was released, and unfortunately I didn't feel like coming back to it later: it seemed too tedious for too little reward. I thought it was inelegant that a solid block of #
pixels would be considered a sea monster with waves.
This is another Sudoku-like problem, similar to Day 16, involving ingredients and allergens. Crucially, each allergen is found in exactly one ingredient, but a food may not list every allergen. I can reuse the function eliminate_others
, but the rest I need to define here. day21_2
is the only day
function that does not return an int
.
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')
[2282, 'vrzkz,zjsh,hphcb,mbdksj,vzzxl,ctmzsr,rkzqs,zmhnj']
Part 1 is the card game War (here called Combat) with no ties. Part 2 is a more complex recursive version of the game.
Each player holds a deal of cards, which I will represent as a deque
so I can deal from the top and add cards to the bottom.
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)
[31809, 32835]
A game involving moving around some cups that are labelled with positive integers.
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)])
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."
return after(1, play_cups(cupstr, n))
def play_cups(cupstr: str, n=100, maxcup=0):
cups = list(map(int, cupstr))
if maxcup > max(cups):
cups.append(range(max(cups) + 1, maxcup + 1))
current = cups[0][0]
for i in range(n):
picked = pickup(cups, current)
dest = destination(cups, current)
place(cups, picked, dest)
current = clockwise(cups, current)
return 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)])
def day23_2(cupstr):
cups = play_cups(cupstr, 1_000_000, 100_000_000)
do(23, 278659341)
[278659341, None]
For Part 1, I aimed to be very explicit in my code, and the solution works fine for 9 cups and 100 moves (although it did end up being more lines of code than I wanted/expected).
However, my approach would not be efficient enough to do Part 2; thus it was a poor choice. For now I'll skip Part 2; maybe I'll come back to it later. I had an idea for a representation where each entry in cups
is either a list
or a range
of cups; that way we are only breaking up and/or shifting small lists, not million-element lists. A skip list might also be a good approach.
This puzzle involves a hexagonal grid. The input is a list of directions to follow to identify a destination hex tile that should be flipped from white to black. I recall that Amit Patel of Red Blob Games has covered hex grids topic thoroughly; I followed his recommendation to use a (pointy) axial coordinate system.
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)
I'll use binding
to temporarily redefine next_generation
and cell_deltas
to work with this problem; then call life
.
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)
[420, 4206]
This puzzle involves breaking a cryptographic protocol (whose details I won't describe here).
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)
[16881444, None]
Advent of Code suggests that each day's puzzle should run in 15 seconds or less. I met that goal, with days 11 and 15 taking about 8 seconds each, days 22 and 25 about 2 seconds, and the rest if the days (and the overall average) being under a second per day. (However, I skipped Part 2 on days 20 and 23.)
Here's a report. Stars in the first column indicate run times on a log scale: 0 stars for under 1/100 seconds up to 4 stars for 10 seconds or more:
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