#### IMPORTS %matplotlib inline import matplotlib.pyplot as plt import re from collections import Counter, defaultdict, namedtuple, deque from itertools import chain, cycle, product, islice, count as count_from from functools import lru_cache, total_ordering from dataclasses import dataclass #### CONSTANTS infinity = float('inf') bignum = 10 ** 100 #### FILE INPUT AND PARSING def Input(day, line_parser=str.strip, file_template='data/advent2018/input{}.txt'): "For this day's input file, return a tuple of each line parsed by `line_parser`." return mapt(line_parser, open(file_template.format(day))) def integers(text): "A tuple of all integers in a string (ignore other characters)." return mapt(int, re.findall(r'-?\d+', text)) #### UTILITY FUNCTIONS def mapt(fn, *args): "Do a map, and make the results into a tuple." return tuple(map(fn, *args)) def first(iterable, default=None): "Return first item in iterable, or default." return next(iter(iterable), default) def nth(iterable, n): return next(islice(iter(iterable), n, n+1)) cat = ''.join def rangei(start, end, step=1): """Inclusive, range from start to end: rangei(a, b) = range(a, b+1).""" return range(start, end + 1, step) def quantify(iterable, pred=bool): "Count how many items in iterable have pred(item) true." return sum(map(pred, iterable)) def multimap(items): "Given (key, val) pairs, return {key: [val, ....], ...}." result = defaultdict(list) for (key, val) in items: result[key].append(val) return result

assert _ == 466, 'Day 1.1'

# Part 2 def partial_sums(nums): "The sums of each prefix of nums." total = 0 for n in nums: total += n yield total def seen_before(items): "The first item that appears twice." seen = set() for item in items: if item in seen: return item seen.add(item) seen_before(partial_sums(cycle(input1)))

assert _ == 750, 'Day 1.2'

input2 = Input(2) def numwith(ids, n): return quantify(ids, lambda s: n in Counter(s).values()) numwith(input2, 2) * numwith(input2, 3)

assert _ == 8118, 'Day 2.1'

# Part 2 def diff(A, B): return sum(a != b for a, b in zip(A, B)) def common(A, B): return cat(a for a,b in zip(A, B) if a == b) common(*[i for i in input2 if any(diff(i, x) == 1 for x in input2)])

assert _ == 'jbbenqtlaxhivmwyscjukztdp', 'Day 2.2'

input3 = Input(3, integers) def claimed(claims): "For each square inch position (x, y), how many claims claimed it?" C = Counter() for (id, x, y, w, h) in claims: C += Counter(product(range(x, x+w), range(y, y+h))) return C def value_ge(dic, threshold): "How many items in dic have a value >= threshold?" return quantify(dic[x] >= threshold for x in dic) value_ge(claimed(input3), 2)

assert _ == 103806, 'Day 3.1'

# Part 2 def claimed2(claims): "Which claim has only positions that are claimed by nobody else?" C = claimed(claims) for (id, x, y, w, h) in claims: if all(C[pos] == 1 for pos in product(range(x, x+w), range(y, y+h))): return id claimed2(input3)

assert _ == 625, 'Day 3.2'

example4 = '''[1518-11-01 00:00] Guard #10 begins shift [1518-11-01 00:05] falls asleep [1518-11-01 00:25] wakes up [1518-11-01 00:30] falls asleep [1518-11-01 00:55] wakes up [1518-11-01 23:58] Guard #99 begins shift [1518-11-02 00:40] falls asleep [1518-11-02 00:50] wakes up [1518-11-03 00:05] Guard #10 begins shift [1518-11-03 00:24] falls asleep [1518-11-03 00:29] wakes up [1518-11-04 00:02] Guard #99 begins shift [1518-11-04 00:36] falls asleep [1518-11-04 00:46] wakes up [1518-11-05 00:03] Guard #99 begins shift [1518-11-05 00:45] falls asleep [1518-11-05 00:55] wakes up'''.splitlines() def parse_record(text): "Return date, minutes, opcode action, and argument." text = re.sub('[][#:]', ' ', text) day, hour, mins, opcode, arg, *rest = text.split() return day, int(mins), opcode, arg mapt(parse_record, example4)

def timecard(log): "Return {guard: {day: [asleep_range, ...]}}." records = sorted(map(parse_record, log)) sleep = defaultdict(lambda: defaultdict(list)) # sleep[guard][day] = [minute, ...] for day, mins, opcode, arg in records: if opcode == 'Guard': guard = int(arg) elif opcode == 'falls': falls = mins elif opcode == 'wakes': wakes = mins sleep[guard][day].extend(range(falls, wakes)) else: error() return sleep timecard(example4)[99] # Guard 99's sleep record

def sleepiest_guard(sleep): "Which guard sleeps the most minutes?" return max(sleep, key=lambda guard: sum(map(len, sleep[guard].values()))) def sleepiest_minute(guard, sleep): "In which minute is this guard asleep the most?" def times_asleep(m): return sum(m in mins for mins in sleep[guard].values()) return max(range(60), key=times_asleep) def repose(lines): "The ID of the sleepiest guard times that guard's sleepiest minute." sleep = timecard(lines) guard = sleepiest_guard(sleep) minute = sleepiest_minute(guard, sleep) return guard * minute repose(Input(4))

assert _ == 143415, 'Day 4.1'

# Part 2 def repose2(lines): """Of all guards, which guard is most frequently asleep on the same minute? What is the ID of the guard you chose multiplied by the minute you chose?""" sleep = timecard(lines) c = Counter((guard, minute) for guard in sleep for minute in chain(*sleep[guard].values())) [((guard, minute), _)] = c.most_common(1) return guard * minute repose2(Input(4))

assert _ == 49944, 'Day 4.2'

input5 = cat(Input(5)) alphabet = 'abcdefghijklmnopqrstuvwxyz' ALPHABET = alphabet.upper() OR = '|'.join reaction = OR(OR([c + C, C + c]) for c, C in zip(alphabet, ALPHABET)) def reduction(text): "Remove all cC or Cc pairs, and repeat." while True: text, n = re.subn(reaction, '', text) if n == 0: return text reduction('dabAcCaCBAcCcaDA')

len(reduction(input5))

assert _ == 10180, 'Day 5.1'

# Part 2 def shortest(items): return min(items, key=len) def reduction2(text): """What is the length of the shortest polymer you can produce by removing all units of exactly one type and fully reacting the result?""" return shortest(reduction(re.sub(c, '', text, flags=re.I)) for c in alphabet) len(reduction2(input5))

assert _ == 5668, 'Day 5.2'

input6 = Input(6, integers) def closest_to(point, points): "Which of `points` is closest to `point`? Return None if tie." p1, p2 = sorted(points, key=lambda p: distance(p, point))[:2] return p1 if distance(p1, point) < distance(p2, point) else None def X(point): return point[0] def Y(point): return point[1] def distance(p, q): return abs(X(p) - X(q)) + abs(Y(p) - Y(q)) def maxval(dic): return max(dic.values()) def closest_counts(points, margin=100): "What is the size of the largest area of closest points that isn't infinite?" assert len(points) > 1 xside = range(-margin, max(map(X, points)) + margin) yside = range(-margin, max(map(Y, points)) + margin) box = product(xside, yside) # counts[point] = number of grid points in box that are closest to point counts = Counter(closest_to(p, points) for p in box) # Now delete the counts that are suspected to be infinite: for p in perimeter(xside, yside): c = closest_to(p, points) if c in counts: del counts[c] return counts def perimeter(xside, yside): "The perimeter of a box with these sides." return chain(((xside[0], y) for y in yside), ((xside[-1], y) for y in yside), ((x, yside[0]) for x in xside), ((x, yside[-1]) for x in xside)) closest_counts([(1, 1), (1, 6), (8, 3), (3, 4), (5, 5), (8, 9)])

maxval(closest_counts(input6))

assert _ == 3010, 'Day 6.1'

# Part 2 def total_distance(point, points): "Total distance of this point to all the `points`." return sum(distance(point, c) for c in points) def neighborhood(points, dist=10000): """What is the size of the region containing all locations which have a total distance to all given points of less than `dist`?""" maxx = max(x for x,y in points) maxy = max(y for x,y in points) box = product(range(maxx + 1), range(maxy + 1)) return quantify(box, lambda p: total_distance(p, points) < dist)

neighborhood(Input(6, integers))

assert _ == 48034, 'Day 6.2'

def parse_instruction(line): return re.findall(' ([A-Z]) ', line) parse_instruction('Step B must be finished before step A can begin.')

input7 = Input(7, parse_instruction) def order(pairs): "Yield steps in order, respecting (before, after) pairs; break ties lexically." steps = {step for pair in pairs for step in pair} # Steps remaining to be done prereqs = multimap((A, B) for [B, A] in pairs) # prereqs[A] = [B, ...] def ready(step): return all(pre not in steps for pre in prereqs[step]) while steps: step = min(filter(ready, steps)) steps.remove(step) yield step cat(order(input7))

assert _ == 'ABGKCMVWYDEHFOPQUILSTNZRJX', 'Day 7.1'

# Part 2 def schedule(pairs, workers=5): "Return a {step:endtime} map for best schedule, given a number of `workers`." steps = {step for pair in pairs for step in pair} # Steps remaining to be done prereqs = multimap((A, B) for (B, A) in pairs) # prereqs[A] = [B, ...] endtime = {step: infinity for step in steps} # endtime[step] = time it will be completed for t in count_from(0): # Assign available steps to free workers def ready(step): return all(endtime[p] < t for p in prereqs[step]) available = filter(ready, steps) for step in sorted(available)[:workers]: endtime[step] = t + 60 + ord(step) - ord('A') steps.remove(step) workers -= 1 # Discover if any workers become free this time step workers += quantify(endtime[step] == t for step in endtime) # Return answer once all steps have been scheduled if not steps: return endtime

schedule(input7)

maxval(schedule(input7)) + 1

assert _ == 898, 'Day 7.2'

input8 = integers(cat(Input(8))) Tree = namedtuple('Tree', 'kids, metadata') def tree(nums): """A node consists of the numbers: [k, n, (k child nodes)..., (n metadata values)...].""" k, n = nums.popleft(), nums.popleft() return Tree([tree(nums) for _ in range(k)], [nums.popleft() for _ in range(n)]) example8 = tree(deque((2, 3, 0, 3, 10, 11, 12, 1, 1, 0, 1, 99, 2, 1, 1, 2))) tree8 = tree(deque(input8))

def sum_metadata(tree): "What is the sum of all metadata entries in a tree?" return sum(tree.metadata) + sum(map(sum_metadata, tree.kids)) sum_metadata(example8)

sum_metadata(tree8)

assert _ == 48443, 'Day 8.1'

def value(tree): """What is the value of the root node? Value of tree with no kids is sum of metadata; Otherwise metadata are 1-based indexes into kids; sum up their values.""" if not tree.kids: return sum(tree.metadata) else: return sum(value(tree.kids[i - 1]) for i in tree.metadata if i <= len(tree.kids))

value(example8)

value(tree8)

assert _ == 30063, 'Day 8.2'

players, marbles = integers('448 players; last marble is worth 71628 points') def play(players, marbles, verbose=False): "Add `marbles` to `circle`, rotating according to rules and scoring every 23 marbles." circle = deque([0]) scores = Counter() for m in rangei(1, marbles): player = (m - 1) % players + 1 if m % 23: circle.rotate(-1) circle.append(m) else: circle.rotate(+7) scores[player] += circle.pop() + m circle.rotate(-1) if verbose: print(player, list(circle)) return scores play(9, 25, True)

maxval(play(players, marbles))

assert _ == 394486, 'Day 9.1'

maxval(play(players, marbles * 100))

assert _ == 3276488008, 'Day 9.2'

Light = namedtuple('Light', 'x, y, dx, dy') input10 = Input(10, lambda line: Light(*integers(line))) def configuration(t, lights=input10): "The positions of the lights at time t." return {(L.x + t * L.dx, L.y + t * L.dy) for L in lights} def bounds(points): "Return xmin, xmax, ymin, ymax of the bounding box." return (min(map(X, points)), max(map(X, points)), min(map(Y, points)), max(map(Y, points))) def extent(points): "Area of bounding box." xmin, xmax, ymin, ymax = bounds(points) return (xmax - xmin) * (ymax - ymin) def localmin(sequence, key): "Iterate through sequence, when key(item) starts going up, return previous item." prevscore = infinity for item in sequence: score = key(item) if prevscore < score: return prev prev, prevscore = item, score def lightshow(points, chars='.#'): "Print out the locations of the points." xmin, xmax, ymin, ymax = bounds(points) for y in rangei(ymin, ymax): print(cat(chars[(x, y) in points] for x in rangei(xmin, xmax)))

configurations = map(configuration, count_from(0)) lights = localmin(configurations, key=extent) lightshow(lights)

# Part 2 next(t for t in count_from(1) if configuration(t) == lights)

assert _ == 10605

serial = input11 = 6303 def power_level(point): "Follow the rules for power level." id = X(point) + 10 level = (id * Y(point) + serial) * id return (level // 100) % 10 - 5 def total_power(topleft, width=3): "Total power in the square with given topleft corner and width." x, y = topleft square = product(range(x, x + width), range(y, y + width)) return sum(map(power_level, square)) def maxpower(bounds=300, width=3): "Return (power, topleft, width) of square within `bounds` of maximum power." toplefts = product(rangei(1, bounds - width), repeat=2) return max((total_power(topleft, width), topleft, width) for topleft in toplefts) maxpower()

assert _[1] == (243, 27), 'Day 11.1'

# Part 2 def summed_area(side, key): "A summed-area table." I = defaultdict(int) for x, y in product(side, side): I[x, y] = key((x, y)) + I[x, y - 1] + I[x - 1, y] - I[x - 1, y - 1] return I def total_power(topleft, width=3, I=summed_area(rangei(1, 300), power_level)): "Total power in square with given topleft corner and width (from `I`)." x, y = topleft xmin, ymin, xmax, ymax = x - 1, y - 1, x + width - 1, y + width - 1 return I[xmin, ymin] + I[xmax, ymax] - I[xmax, ymin] - I[xmin, ymax] # Make sure we get the same answer for the Part 1 problem assert maxpower() == (30, (243, 27), 3)

max(maxpower(width=w) for w in range(300))

assert _[1] + _[2:] == (284, 172, 12), 'Day 11.2'

def Plants(row): "Convert '#..#.#' => {0, 3, 5}" return {i for i, c in enumerate(row) if c == '#'} input12 = Input(12, str.split) plants = Plants(input12[0][-1]) rules = {rule[0]: rule[-1] for rule in input12 if '=>' in rule} def grow(plants=plants, rules=rules): "Grow plants using rules, yielding each generation (including 0th)." while True: yield plants extent = rangei(min(plants) - 3, max(plants) + 3) plants = {i for i in extent if lives(plants, i, rules)} def lives(plants, i, rules): "Does pot i live in next generation, according to rules?" neighborhood = cat('.#'[j in plants] for j in rangei(i - 2, i + 2)) return rules[neighborhood] == '#' sum(nth(grow(), 20))

assert _ == 1447, 'Day 12.1'

# Part 2 gens = list(islice(grow(), 200)) plt.plot(mapt(len, gens), label='x');

plt.plot(mapt(sum, gens));

[sum(plants) for plants in gens[100:103]]

def nth_plant_sum(n, k=100): "The sum of plants in the nth generation, assuming linear growth after k generations." a, b = map(sum, islice(grow(), k, k + 2)) return a + (n - k) * (b - a) nth_plant_sum(50 * 10 ** 9)

assert _ == 1050000000480, 'Day 12.2'

[len(g) for g in gens[-3:]]

gens[100]

dict(zip(range(6), grow(plants={1, 2, 3})))

Point = complex def X(point): return point.real if isinstance(point, complex) else point[0] def Y(point): return point.imag if isinstance(point, complex) else point[1] # Headings: HU, HD, HR, HL = Head up, down, right, left # Turns: TL, TR, TS, TB = Turn left, right, straight, backwards HU = TL = Point(0, -1) HD = TR = -TL HR = TS = Point(1, 0) HL = TB = -TS headings = {'>': HR, '<': HL, '^': HU, 'v': HD} inverse_headings = dict((headings[ch], ch) for ch in headings) assert HU * TR == HR and TR ** 4 == TL ** 4 == TS and HR * TB == HL and HU == -HD and TR == -TL

@dataclass class Cart: name: str pos: Point heading: Point turns: object @dataclass class World: grid: tuple carts: list def __init__(self, lines): table = str.maketrans('<>^v', '--||') names = cycle(alphabet) self.grid = [line.translate(table) for line in lines] self.carts = [Cart(next(names), Point(x, y), headings[h], cycle((TL, TS, TR))) for (y, line) in enumerate(lines) for (x, h) in enumerate(line) if h in headings] def __getitem__(self, point): return self.grid[int(Y(point))][int(X(point))] def show(self): "Print a representation of the world." for y, line in enumerate(self.grid): for x, ch in enumerate(line): cart = first(c for c in self.carts if c.pos == Point(x, y)) ch = inverse_headings[cart.heading] if cart else ch print(ch, end='') print() print()

def madmad(world, show=False): "Simulate the mine cart madness until a collision." while True: if show: world.show() for cart in sorted(world.carts, key=lambda c: (Y(c.pos), X(c.pos))): cart.heading *= turn(cart, world) cart.pos += cart.heading if collision(cart, world): if show: world.show() return cart.pos def turn(cart, world): "Which way should the cart turn (depends on character it is on)." ch = world[cart.pos] if ch == '+': return next(cart.turns) if ch == '/': return (TR if cart.heading in (HU, HD) else TL) if ch == '\\': return (TR if cart.heading in (HR, HL) else TL) else: return TS def collision(cart, world): "Has this cart collided with any other cart?" return any(cart.pos == other.pos for other in world.carts if other is not cart)

example = r''' /->-\ | | /----\ | /-+--+-\ | | | | | v | \-+-/ \-+--/ \------/ '''.strip().splitlines() madmad(World(example), True)

madmad(World(Input(13)))