<jupyter_start><jupyter_text>Day 0: Imports and Utility Functions<jupyter_code>%matplotlib inline
import matplotlib.pyplot as plt

import os
import re
import numpy as np
import random
import string
import collections, itertools
from collections import Counter, defaultdict, namedtuple, deque, OrderedDict
from functools   import lru_cache, reduce
from statistics  import mean, median, mode, stdev, variance
from itertools   import (permutations, combinations, groupby, 
                         islice, repeat,cycle, chain, product, zip_longest, takewhile, dropwhile, count as count_from)
from heapq       import heappush, heappop, heapify
from operator    import iand, ior, ilshift, irshift
from bisect      import bisect_left, bisect_right
def cityblock_distance(P, Q):
    "Compute the manhattan distance between P and Q."
    return sum(abs(p - q) for p, q in zip(P, Q))
def always(value):
    return (lambda *args : value)
assert(always(1)(1, 2, 3) == 1)
def Astar(start, move_func, h_func, cost_func=always(1)):
    "Find the shortest sequence of states from start to a goal state (where h_func(s) == 0)."
    frontier = [(h_func(start), start)] # a priority queue, ordered by f = g + h
    previous = {start : None}
    path_cost = {start : 0}             # the cost of the best path to a state
    Path = lambda s : ([] if (s is None) else Path(previous[s]) + [s])
    while frontier:
        (f, s) = heappop(frontier)
        if h_func(s) == 0:
            return Path(s)
        for s2 in move_func(s):
            g = path_cost[s] + cost_func(s, s2)
            if s2 not in path_cost or g < path_cost[s2]:
                heappush(frontier, (g + h_func(s2), s2))
                path_cost[s2] = g
                previous[s2] = s<jupyter_output><empty_output><jupyter_text>Day 1: Chronal Calibration<jupyter_code>cnt = 0
with open('inputs/day1.txt') as f:
    for line in f:
        cnt += int(line.strip())
print(cnt)
cnt = 0
visited = {0}
with open('inputs/day1.txt') as f:
    for line in cycle(f):
        cnt += int(line.strip())
        if cnt in visited:
            print(cnt)
            break
        else:
            visited.add(cnt)<jupyter_output>73272<jupyter_text>Day 2: Inventory Management System<jupyter_code>twices = threes = 0
with open('inputs/day2.txt') as f:
    lines = f.readlines()
    twices = sum(any(line.count(ch) == 2 for ch in string.ascii_lowercase) for line in lines)
    threes = sum(any(line.count(ch) == 3 for ch in string.ascii_lowercase) for line in lines)
    pairs = [(line1, line2) for line1, line2 in combinations(lines, 2) if sum(ch1 != ch2 for ch1, ch2 in zip(line1, line2)) == 1]
    line1, line2 = pairs[0]
    print(''.join([ch1 for ch1, ch2 in zip(line1, line2) if ch1 == ch2]))
print(twices * threes)<jupyter_output>fvstwblgqkhpuixdrnevmaycd

8715<jupyter_text>Day 3: No Matter How You Slice It<jupyter_code>rects = []
with open('inputs/day3.txt') as f:
    #1 @ 335,861: 14x10
    for line in f:
        _, _, a, b = line.split()
        left, top = tuple(map(int, a[:-1].split(',')))
        w, h = tuple(map(int, b.split('x')))
        rects.append((top, left, top + h, left + w))
print(rects[0])
counter = Counter()
for x1, y1, x2, y2 in rects:
    for x in range(x1, x2):
        for y in range(y1, y2):
            counter[x, y] += 1
print(sum(value > 1 for value in counter.values()))
for i, (a, b, c, d) in enumerate(rects, 1):
    for j, (aa, bb, cc, dd) in enumerate(rects, 1):
        if i == j: continue
        if not (cc <= a or c <= aa or dd <= b or d <= bb):
            break
    else:
        print(i)<jupyter_output>625<jupyter_text>Day 4: Repose Record<jupyter_code>sleeps = defaultdict(Counter) # Guard ID to --> counter
GuardID = None 
low = 0
with open('inputs/day4.txt') as f:
    for line in sorted(f):
        time = line[12:17]
        h, m = time.split(':')
        h, m = int(h), int(m)
        content = line[18:].strip()
        if content.startswith('Guard'):
            _, GuardID, *_ = content.split()
        elif content == 'falls asleep':
            low = m
        else:
            assert(content == 'wakes up')
            for i in range(low, m):
                sleeps[GuardID][i] += 1
name = max(sleeps, key=lambda x : sum(sleeps[x].values()))
max(sleeps[name], key=lambda x : sleeps[name][x]) * int(name[1:])
name = max(sleeps, key=lambda x : max(sleeps[x].values()))
int(name[1:]) * max(sleeps[name], key=lambda x : sleeps[name][x])<jupyter_output><empty_output><jupyter_text>Day 5: Alchemical Reduction<jupyter_code>with open('inputs/day5.txt') as f:
    line = f.read()
dis = abs(ord('a') - ord('A'))
# line = "dabAcCaCBAcCcaDA"
def polymer_reaction(line, remove=''):
    line = re.sub('[{}]'.format(remove), '', line)
    stack = []
    for o in map(ord, line):
        if not stack or abs(stack[-1] - o) != dis:
            stack.append(o)
        else:
            stack.pop()
    return len(stack)
L = len(line)
for t in string.ascii_lowercase:
    temp = polymer_reaction(line, remove=t+t.upper())
    if temp < L:
        L = temp
print(L)<jupyter_output>5698<jupyter_text>Day 6: Chronal Coordinates<jupyter_code>coords = np.loadtxt('inputs/day6.txt', dtype=np.int64, delimiter=', ')
xmin, xmax = coords[:, 0].min(), coords[:, 0].max()
ymin, ymax = coords[:, 1].min(), coords[:, 1].max()
coords[:, 0] -= xmin
coords[:, 1] -= ymin
n = xmax - xmin + 1
m = ymax - ymin + 1
grid = [['.'] * n for _ in range(m)]
queue = collections.deque()
for idx, (y, x) in enumerate(coords):
    grid[x][y] = (idx, 0)
    queue.append((x, y, idx, 0))
while queue:
    size = len(queue)
    for _ in range(size):
        i, j, root, dis = queue.popleft()
        for newi, newj in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
            if 0 <= newi < m and 0 <= newj < n:
                if grid[newi][newj] == '.':
                    grid[newi][newj] = (root, dis + 1)
                    queue.append((newi, newj, root, dis + 1))
                else:
                    parent, cur_dis = grid[newi][newj]
                    if cur_dis == dis + 1 and root != parent:
                        grid[newi][newj] = ('#', dis + 1)
                    elif cur_dis > dis + 1:
                        grid[newi][newj] = (root, dis + 1)
                        queue.append((newi, newj, root, dis + 1))
def is_valid(i, j, m, n):
    return i > 0 and i < m - 1 and j > 0 and j < n - 1
counter = defaultdict(list)
for i in range(m):
    for j in range(n):
        root, _ = grid[i][j]
        counter[root].append((i, j))
max(len(counter[x]) for x in counter if all(is_valid(i, j, m, n) for i, j in counter[x]))
coords = np.loadtxt('inputs/day6.txt', dtype=np.int64, delimiter=', ')
xmin, xmax = coords[:, 0].min(), coords[:, 0].max()
ymin, ymax = coords[:, 1].min(), coords[:, 1].max()
coords[:, 0] -= xmin
coords[:, 1] -= ymin
n = xmax - xmin + 1
m = ymax - ymin + 1
print(m, n)
cnt = 0
for i in range(m):
    for j in range(n):
        if sum(abs(x - i) + abs(y - j) for x, y in coords) <= 10000:
            cnt += 1
print(cnt)<jupyter_output>35928<jupyter_text>Day 7: The Sum of Its Parts<jupyter_code>sucs = defaultdict(set)
pres = defaultdict(set)
nodes = set()
with open('inputs/day7.txt', 'r') as f:
    for line in f:
        _, start, *_, end, _, _ = line.split()
        nodes.add(start)
        nodes.add(end)
        sucs[start].add(end)
        pres[end].add(start)
frees = nodes - pres.keys()
pq = list(frees)
heapify(pq)
ans = ''
while pq:
    node = heappop(pq)
    ans += node
    for nei in sucs[node]:
        if len(pres[nei]) == 1:
            pres.pop(nei)
            heappush(pq, nei)
        elif len(pres[nei]) > 1:
            pres[nei].remove(node)
print(ans)
sucs = defaultdict(set)
pres = defaultdict(set)
nodes = set()
with open('inputs/day7.txt', 'r') as f:
    for line in f:
        _, start, *_, end, _, _ = line.split()
        nodes.add(start)
        nodes.add(end)
        sucs[start].add(end)
        pres[end].add(start)
frees = nodes - pres.keys()
pq = list(frees)
frees = list(frees)
heapify(frees)
heapify(pq)
starts = defaultdict(int)
for node in frees:
    starts[node] = 0
ends = defaultdict(int)
works = dict(zip(string.ascii_uppercase, range(61, 87)))
# works = dict(zip(string.ascii_uppercase, range(1, 27)))
workers = [0] * 5 # 2
heapify(workers)
ans = ''
while pq:
    while frees:
        node = heappop(frees)
        worker_t = heappop(workers)
        worker_t = max(worker_t, starts[node])
        ends[node] = worker_t + works[node]
        heappush(workers, worker_t + works[node])
    node = heappop(pq)
    ans += node
    for nei in sucs[node]:
        if len(pres[nei]) == 1:
            pres.pop(nei)
            heappush(pq, nei)
            heappush(frees, nei)
            starts[nei] = max(ends[node], starts.get(nei, 0))
        elif len(pres[nei]) > 1:
            pres[nei].remove(node)
            starts[nei] = max(ends[node], starts.get(nei, 0))
print(max(ends.values()))<jupyter_output>848<jupyter_text>Day 8: Memory Maneuver<jupyter_code>with open('inputs/day8.txt', 'r') as f:
    items = f.read().split()
# items = "2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2".split()
data = iter(map(int, items))
def traverse_tree():
    cnt = 0
    nchilds = next(data)
    nmetas = next(data)
    for _ in range(nchilds):
        cnt += traverse_tree()
    for _ in range(nmetas):
        cnt += next(data)
    return cnt
print(traverse_tree())    
with open('inputs/day8.txt', 'r') as f:
    items = f.read().split()
# items = "2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2".split()
data = iter(map(int, items))
def traverse_tree_new():
    cnt = 0
    nchilds = next(data)
    nmetas = next(data)
    children = []
    for _ in range(nchilds):
        children.append(traverse_tree_new())
    metas = []
    for _ in range(nmetas):
        temp = next(data)
        metas.append(temp)
        cnt += temp
    if nchilds == 0:
        return cnt
    else:
        cnt = 0
        for idx in metas:
            if 0 <= idx - 1 < nchilds:
                cnt += children[idx - 1]
        return cnt
print(traverse_tree_new())<jupyter_output>25981<jupyter_text>Day 9: <NAME>476 players; last marble is worth 71431 points<jupyter_code>n, m = 476, 71431
players = [[0] for _ in range(n)]
lst = [0]
cur = 0
for idx, player in enumerate(cycle(players), 1):
    if idx % 23 != 0:
        place = (cur + 1) % len(lst) + 1
        lst.insert(place, idx)
        cur = place
    else:
        player[0] += idx
        cur -= 7
        if cur < 0:
            cur += len(lst)
        player[0] += lst[cur]
        old_cur = cur
        if old_cur + 1 == len(lst):
            cur = 0
        else:
            cur = old_cur
        del lst[old_cur]
    if idx == m:
        break
print(max(item[0] for item in players))
class Node:
    def __init__(self, val, prev=None, nxt=None):
        self.val = val
        self.prev = prev
        self.next = nxt
n, m = 476, 71431 * 100
players = [[0] for _ in range(n)]
node = Node(0)
node.prev = node
node.next = node
root = node
cur = node
for idx, player in enumerate(cycle(players), 1):
    if idx % 23 != 0:
        cur = cur.next
        node = Node(idx)
        node.next = cur.next
        node.prev = cur
        cur.next = node
        node.next.prev = node
        cur = node
    else:
        player[0] += idx
        for _ in range(6):
            cur = cur.prev
        player[0] += cur.prev.val
        cur.prev = cur.prev.prev
        cur.prev.next = cur
    if idx == m:
        break
print(max(item[0] for item in players))
# while True:
#     print(root.val, end=' ')
#     root = root.next
#     if root.val == 0:
#         break<jupyter_output>3066307353<jupyter_text>Day 10: The Stars Align<jupyter_code>points, vs = [], []
with open('inputs/day10.txt', 'r') as f:
    for line in f:
        line = line.strip()
        x, y = re.split(',\s+', line[line.index('<') + 1: line.index('>')])
        vx, vy = re.split(',\s+', line[line.rindex('<') + 1:-1])
        points.append([int(x), int(y)])
        vs.append([int(vx), int(vy)])
def compute_box(points):
    xmin = points[:, 0].min()
    xmax = points[:, 0].max()
    ymin = points[:, 1].min()
    ymax = points[:, 1].max()
    return ymax - ymin + xmax - xmin
points = np.array(points)
points_copy = points.copy()
vs = np.array(vs)
min_box = compute_box(points) 
step = 0
for i in range(1, 40000):
    points += vs
    b = compute_box(points)
    if b < min_box:
        min_box = b
        step = i
step
points_copy += step * vs
plt.figure(figsize=(25, 10))
plt.plot(points_copy[:, 0], 200 - points_copy[:, 1], 'r*')<jupyter_output><empty_output><jupyter_text>Day 11: Chronal Charge<jupyter_code>def fuel_power(x, y, serial=7672):
    rack = x + 10
    power = rack * y + serial
    power *= rack
    ten = (power // 100) % 10
    return ten - 5
assert(fuel_power(122, 79, 57) == -5)
assert(fuel_power(217, 196, 39) == 0)
assert(fuel_power(101, 153, 71) == 4)
from itertools import accumulate
grid = np.zeros((300, 300), dtype=np.int64)
for x in range(1, 301):
    for y in range(1, 301):
        grid[y-1, x-1] = fuel_power(x, y, serial=7672)
acc = np.zeros((301, 301), dtype=np.int64)
for i in range(1, 301):
    for j in range(1, 301):
        acc[i, j] = grid[i - 1, j - 1] + acc[i - 1, j] + acc[i, j - 1] - acc[i - 1, j - 1]

def compute_power(x, y, size):
    # x, y to x + size - 1, y + size - 1
    return acc[x + size, y + size] + acc[x, y] - acc[x, y + size] - acc[x + size, y]
# y, x = max([(x, y) for x in range(300 - 2) for y in range(300 - 2)], key=lambda point: sum(grid[point[0] + i, point[1] + j] for i in range(3) for j in range(3)))
# y, x = max([(x, y) for x in range(300 - 2) for y in range(300 - 2)], key=lambda point: grid[point[0]:point[0] + 3, point[1]:point[1] + 3].sum())
# print(x + 1, y + 1)
size = 3
y, x = max(((x, y) for x in range(300 - size + 1)
                  for y in range(300 - size + 1)),
                  key=lambda point:compute_power(*point, size))
print(x + 1, y + 1)
max_power = float('-inf')
rx, ry, rsize = None, None, None
for size in range(1, 301):
    powers = [(compute_power(x, y, size), (x, y)) 
              for x in range(300 - size + 1) 
              for y in range(300 - size + 1)]
    power, (x, y) = max(powers)
    if power > max_power:
        rx = y + 1
        ry = x + 1
        rsize = size
        max_power = power
print(rx, ry, rsize)<jupyter_output>234 197 14<jupyter_text>Day 12: Subterranean Sustainability<jupyter_code>with open('inputs/day12.txt', 'r') as f:
    lines = f.readlines()
state = lines[0][len("initial state: "):].strip()
positions = {i for i, ch in enumerate(state) if ch == '#'}
rules = set()
for line in lines[2:]:
    a, b = line.strip().split(' => ')
    if b == '#':
        rules.add(tuple(a))
positions_back = positions.copy()
def next_gen(rules, positions):
    start, end = min(positions), max(positions)
    ans = set()
    for i in range(start - 3, end + 4):
        five = tuple('#' if (i + di) in positions else '.' for di in range(-2, 3))
        if five in rules:
            ans.add(i)
    return ans
for _ in range(20):
    positions = next_gen(rules,positions)
print(sum(positions))
# positions = positions_back.copy()
# i = 0
# while i < 400:
#     i += 1
#     pre = sum(positions)
#     positions = next_gen(rules, positions)
#     print("{}: {} {}".format(i, sum(positions) - pre, sum(positions)))
print((50_000_000_000 - 101) * 59 + 7557)<jupyter_output>2950000001598<jupyter_text>Day 13: Mine Cart Madness<jupyter_code>with open('inputs/day13.txt', 'r') as f:
    lines = [line.rstrip('\n') for line in f]
graph = {}
carts = {}
lens = []
d = {'>' : '-', '<' : '-', '^' : '|', 'v' : '|'}
for i, line in enumerate(lines):
    lens.append(len(line))
    for j, ch in enumerate(line):
        graph[i, j] = ch
        if ch in ('^', 'v', '>', '<'):
            carts[i, j] = [ch, 0]
dirs = {'>' : (0, 1), '<' : (0, -1), '^' : (-1, 0), 'v' : (1, 0)}
# also need to think about update ...
# 0, 1, 2 means left, straight, right
lefts = {'>' : '^', '<' : 'v', '^' : '<', 'v' : '>'}
straights = {'>' : '>', '<' : '<', '^' : '^', 'v' : 'v'}
rights = {'>' : 'v', '<' : '^', '^' : '>', 'v' : '<'}
turns = [lefts, straights, rights]
# corners
corners = {'/' : {'^' : '>', '<' : 'v', '>' : '^', 'v' : '<'},
           '\\' : {'>' : 'v', '^' : '<', 'v' : '>', '<' : '^'},
          }
while True:
    temp = {}
    positions = set(carts.keys())
    done = False
    for i, j in sorted(carts):
        positions.remove((i, j))
        ch, t = carts[i, j]
        if graph[i, j] == '+':
            ch = turns[t][ch]
            t += 1
            if t == 3:
                t = 0
        di, dj = dirs[ch]
        newi, newj = i + di, j + dj
        if (newi, newj) in positions:
            print(newi, newj)
            done = True
            break
        if graph[newi, newj] in ('/', '\\'):
            ch = corners[graph[newi, newj]][ch]
        temp[newi, newj] = [ch, t]
        positions.add((newi, newj))
    if done:
        break
    carts = temp
graph = {}
carts = {}
lens = []
d = {'>' : '-', '<' : '-', '^' : '|', 'v' : '|'}
for i, line in enumerate(lines):
    lens.append(len(line))
    for j, ch in enumerate(line):
        graph[i, j] = ch
        if ch in ('^', 'v', '>', '<'):
            carts[i, j] = [ch, 0]
while True:
    temp = {}
    if len(carts) == 1:
        print(carts)
        break
    positions = set(carts.keys())
    removed = set()
    for i, j in sorted(carts):
        if (i, j) in removed:
            continue
        positions.remove((i, j))
        ch, t = carts[i, j]
        if graph[i, j] == '+':
            ch = turns[t][ch]
            t += 1
            if t == 3:
                t = 0
        di, dj = dirs[ch]
        newi, newj = i + di, j + dj
        if (newi, newj) in positions:
            removed.add((newi, newj))
#             print(newi, newj)
            continue
        if graph[newi, newj] in ('/', '\\'):
            ch = corners[graph[newi, newj]][ch]
        temp[newi, newj] = [ch, t]
        positions.add((newi, newj))
    carts = temp
    for item in removed:
        if item in carts:
            del carts[item]<jupyter_output>{(111, 53): ['^', 2]}<jupyter_text>Day 14: Chocolate Charts<jupyter_code>def scoreboard(a, b):
    lst = [a, b]
    cur1, cur2 = 0, 1
    yield lst
    while True:
        val = lst[cur1] + lst[cur2]
        if val > 9:
            lst.append(1)
            yield lst
        lst.append(val % 10)
        yield lst
        cur1 = (cur1 + 1 + lst[cur1]) % len(lst)
        cur2 = (cur2 + 1 + lst[cur2]) % len(lst)
# Part 1
n = 598701
score_gen = scoreboard(3, 7)
while True:
    lst = next(score_gen)
    if len(lst) == n + 10:
        break
print(''.join(map(str, lst[-10:])))
find = [5, 9, 8, 7, 0, 1]
n = len(find)
score_gen = scoreboard(3, 7)
while True:
    lst = next(score_gen)
    if len(lst) >= n and lst[-n:] == find:
        print(len(lst) - n)
        break<jupyter_output>20331097<jupyter_text>Day 15: Beverage Bandits  Day 16: Chronal Classification<jupyter_code>def addr(rs, A, B, C):
    rs[C] = rs[A] + rs[B]
def addi(rs, A, B, C):
    rs[C] = rs[A] + B
def mulr(rs, A, B, C):
    rs[C] = rs[A] * rs[B]
def muli(rs, A, B, C):
    rs[C] = rs[A] * B
def banr(rs, A, B, C):
    rs[C] = rs[A] & rs[B]
def bani(rs, A, B, C):
    rs[C] = rs[A] & B
def borr(rs, A, B, C):
    rs[C] = rs[A] | rs[B]
def bori(rs, A, B, C):
    rs[C] = rs[A] | B
def setr(rs, A, B, C):
    rs[C] = rs[A]
def seti(rs, A, B, C):
    rs[C] = A
def gtir(rs, A, B, C):
    if A > rs[B]:
        rs[C] = 1
    else:
        rs[C] = 0
def gtri(rs, A, B, C):
    if rs[A] > B:
        rs[C] = 1
    else:
        rs[C] = 0
def gtrr(rs, A, B, C):
    if rs[A] > rs[B]:
        rs[C] = 1
    else:
        rs[C] = 0
def eqir(rs, A, B, C):
    if A == rs[B]:
        rs[C] = 1
    else:
        rs[C] = 0
def eqri(rs, A, B, C):
    if rs[A] == B:
        rs[C] = 1
    else:
        rs[C] = 0
def eqrr(rs, A, B, C):
    if rs[A] == rs[B]:
        rs[C] = 1
    else:
        rs[C] = 0
def valid(func, before, ops, after):
    _, A, B, C = ops
    func(before, A, B, C)
    return before == after
funcs = [addr, addi, mulr, muli, banr, bani, borr, bori,
         setr, seti, gtir, gtri, gtrr, eqir, eqri, eqrr]
cnt = 0
op_num_map = [set(range(16)) for _ in range(16)]
with open('inputs/day16.txt', 'r') as f:
    lines = f.readlines()
    for i in range(0, 3260, 4):
        sample = lines[i : i + 4]
        before = sample[0].strip()
        ops = list(map(int, sample[1].strip().split()))
        after = sample[2].strip()
        before = eval(before[before.find('[') - 1:])
        after = eval(after[after.find('[') - 1:])
        if sum(valid(func, before[:], ops, after[:]) for func in funcs) >= 3: # change arguments
            cnt += 1
        op_num = ops[0]
        op_num_map[op_num] = {num for num in op_num_map[op_num] if valid(funcs[num], before[:], ops, after[:])}
print(cnt)
m = {}
done = False
while not done:
    done = True
    for i, item in enumerate(op_num_map):
        if len(item) == 1:
            x = item.pop()
            m[i] = x
            print(x)
            for j in range(len(op_num_map)):
                op_num_map[j].discard(x)
            done = False
            break
print(m)
rs = [0, 0, 0, 0]
with open('inputs/day16-part2.txt', 'r') as f:
    for line in f:
        op, A, B, C = list(map(int, line.strip().split()))
        funcs[m[op]](rs, A, B, C)
print(rs[0])<jupyter_output>706<jupyter_text>Day 17: Reservoir Research  Day 18: Settlers of The North Pole<jupyter_code>with open('inputs/day18.txt', 'r') as f:
    area = [list(line.strip()) for line in f]
def neighbors(m, n, i, j):
    for di in (-1, 0, 1):
        for dj in (-1, 0, 1):
            if di == dj == 0:
                continue
            newi, newj = i + di, j + dj
            if 0 <= newi < m and 0 <= newj < n:
                yield newi, newj
import copy
def update_area(area):
    m, n = len(area), len(area[0])
    ans = copy.deepcopy(area)
    for i, row in enumerate(area):
        for j, val in enumerate(row):
            if val == '.':
                new_val = '.'
                cnt = 0
                for newi, newj in neighbors(m, n, i, j):
                    if area[newi][newj] == '|':
                        cnt += 1
                        if cnt >= 3:
                            new_val = '|'
                            break
            elif val == '|':
                new_val = '|'
                cnt = 0
                for newi, newj in neighbors(m, n, i, j):
                    if area[newi][newj] == '#':
                        cnt += 1
                        if cnt >= 3:
                            new_val = '#'
                            break
            else: # val == '#'
                new_val = '.'
                adj_tree = False
                adj_lumber = False
                for newi, newj in neighbors(m, n, i, j):
                    if area[newi][newj] == '#':
                        adj_lumber = True
                    if area[newi][newj] == '|':
                        adj_tree = True
                    if adj_tree and adj_lumber:
                        new_val = '#'
                        break
            ans[i][j] = new_val
    return ans
cur_area = copy.deepcopy(area)
for _ in range(10):
    cur_area = update_area(cur_area)
print(sum(ch == '|' for row in cur_area for ch in row)
     *sum(ch == '#' for row in cur_area for ch in row))
def encode_area(area):
    return reduce(operator.add, [''.join(row) for row in area])
cur_area = copy.deepcopy(area)
period = None
seen = {}
for i in range(1000):
    code = encode_area(cur_area)
    if code in seen:
        print('{} repeats {}'.format(i, seen[code]))
        cur_idx = i
        period = i - seen[code]
        break
    else:
        seen[code] = i
    cur_area = update_area(cur_area)
# print(period)
# print(cur_idx)
for j in range((1000000000 - cur_idx) % period):
    cur_area = update_area(cur_area)
print(sum(ch == '|' for row in cur_area for ch in row)
     *sum(ch == '#' for row in cur_area for ch in row))<jupyter_output>597 repeats 569
190512<jupyter_text>Day 19: Go With The Flow<jupyter_code>funcs = dict(addr=addr, addi=addi, mulr=mulr, muli=muli, banr=banr, bani=bani, borr=borr, bori=bori,
          setr=setr, seti=seti, gtir=gtir, gtri=gtri, gtrr=gtrr, eqir=eqir, eqri=eqri, eqrr=eqrr)
with open('inputs/day19.txt', 'r') as f:
    program = [[int(x) if x.isdigit() else x
                for x in line.strip().split()]
                for line in f]
print(program)
# def eqrr(rs, A, B, C):
#     if rs[A] == rs[B]:
#         rs[C] = 1
#     else:
#         rs[C] = 0
def run(registers, program, funcs, verbose=False):
    assert(program[0][0] == '#ip')
    ip = program[0][1]
    ins_reg = ip
    program = program[1:]
    n = len(program)
    while 0 <= registers[ip] < n:
        op, A, B, C = program[registers[ip]]
        funcs[op](registers, A, B, C)
        registers[ip] += 1
    return registers[0]
registers = [0] * 6
run(registers, program, funcs, False)<jupyter_output><empty_output><jupyter_text>Day 20: A Regular Map<jupyter_code># how to build the map
# string = "^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$" # this is created by a DFS, so we can simulate it with stack
def build_distance_graph(string):
    dirs = dict(W=(1, 0), E=(-1, 0), N=(0, -1), S=(0, 1))
    distances = defaultdict(int)
    x = y = pre_x = pre_y = 0
    positions = []
    for ch in string[1:-1]:
        if ch == '(':
            positions.append((x, y))
        elif ch == '|':
            x, y = positions[-1]
        elif ch == ')':
            x, y = positions.pop()
        else:
            dx, dy = dirs[ch]
            x, y = x + dx, y + dy
            if distances[x, y] != 0:
                distances[x, y] = min(distances[x, y], 1 + distances[pre_x, pre_y])
            else:
                distances[x, y] = 1 + distances[pre_x, pre_y]
        pre_x, pre_y = x, y
    return distances
# string = "^WNE$"
# string = "^ENWWW(NEEE|SSE(EE|N))$"
# string = "^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$"
with open('inputs/day20.txt', 'r') as f:
    string = f.read().strip()
distances = build_distance_graph(string)
print(max(distances.values()))
print(sum(v >= 1000 for v in distances.values()))<jupyter_output>8566<jupyter_text>[Day 22: Mode Maze](https://adventofcode.com/2018/day/22)depth: 5616target: 10,785<jupyter_code>@lru_cache(None)
def geologic_idx(mouth, target, depth, x, y):
    "Compute the geologic index of (x, y)."
    if (x, y) in (mouth, target):
        return 0
    elif y == 0:
        return x * 16807
    elif x == 0:
        return y * 48271
    else:
        return (erosion_level(mouth, target, depth, x - 1, y) 
                * erosion_level(mouth, target, depth, x, y - 1))

@lru_cache(None)
def erosion_level(mouth, target, depth, x, y):
    "Compute erosion level of (x, y)."
    geo = geologic_idx(mouth, target, depth, x, y)
    return (geo + depth) % 20183

def region_type(mouth, target, depth, x, y):
    "Compute region type (0, 1, 2)."
    return erosion_level(mouth, target, depth, x, y) % 3

def risk_sum(mouth, target, depth):
    "Compute risk level."
    mx, my = mouth
    tx, ty = target
    return sum(region_type(mouth, target, depth, x, y)
                for x in range(mx, tx + 1, 1)
                for y in range(my, ty + 1, 1))
mouth = 0, 0
target = 10, 785
depth = 5616
assert(risk_sum((0, 0), (10, 10), 510) == 114)
print(risk_sum(mouth, target, depth))
# this is a A* search problem
# state: ((x, y), tool)
# move_func
# cost_func
# h_func
# 'G' : gear, 'T' : torch, 'N' : Neither
# 'G', 'T', 'N'
# ['GT', 'GN', 'TN']

def cost_func(s1, s2):
    p1, t1 = s1
    p2, t2 = s2
    return cityblock_distance(p1, p2) + 7 * (t1 != t2)

def h_func(state, target):
    p, t = state
    return cityblock_distance(p, target) + (t != 'T') * 7 

def move_func(state, mouth, target, depth):
    tools = ['GT', 'GN', 'TN']
    (x, y), t = state
    xmax, ymax = target
    ans = []
    r_type = region_type(mouth, target, depth, x, y)
    for newt in tools[r_type]:
        if newt != t:
            ans.append(((x, y), newt))
    for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
        newx, newy = x + dx, y + dy
        if newx >= 0 and newy >= 0:
            r_type = region_type(mouth, target, depth, newx, newy)
            if t in tools[r_type]:
                ans.append(((newx, newy), t))
    return ans
# Astar(start, move_func, h_func, cost_func=always(1))
mouth = 0, 0
target = 10, 785
depth = 5616
# target = 10, 10
# depth = 510
start = (mouth, 'T')
from functools import partial
path = Astar(start, partial(move_func, mouth=mouth, target=target, depth=depth), partial(h_func, target=target), cost_func)
print(sum(cost_func(s1,s2) for s1, s2 in zip(path, path[1:])))<jupyter_output>1070<jupyter_text>[Day 23: Experimental Emergency Teleportation](https://adventofcode.com/2018/day/23)<jupyter_code>Nanobot = namedtuple('Nanobot', 'x, y, z, r')
nanobots = []
with open('inputs/day23.txt', 'r') as f:
    for line in f:
        nums = re.findall(r'-?\d+', line)
        nanobots.append(Nanobot(*map(int, nums)))
idx = max(range(len(nanobots)), key=lambda i : nanobots[i].r)
print(sum(cityblock_distance(nanobots[idx][:3], nanobots[i][:3]) <= nanobots[idx].r
          for i in range(len(nanobots))))
# compute the intersect of circles
# try all possible x, y, zs.
xs = [nanobot.x for nanobot in nanobots]
print(max(xs), min(xs))
def best_location(nanobots):
    "Find the best location that within range of most nanobots"
    xs = [nanobot.x for nanobot in nanobots]
    ys = [nanobot.y for nanobot in nanobots]
    zs = [nanobot.z for nanobot in nanobots]
    box_size = 1
    while box_size < max(xs) - min(xs):
        box_size *= 2
    while True:
        mx_cnt = 0
        best_loc = None
        best_dis_to_zero = float('inf')
        for x in range(min(xs), max(xs) + 1, box_size):
            for y in range(min(ys), max(ys) + 1, box_size):
                for z in range(min(zs), max(zs) + 1, box_size):
                    cnt = 0
                    for nx, ny, nz, r in nanobots:
                        dist = cityblock_distance((x, y, z), (nx, ny, nz))
                        if (dist - r) // box_size <= 0:
                            cnt += 1
                    if cnt > mx_cnt:
                        mx_cnt = cnt
                        best_loc = x, y, z
                        best_dis_to_zero = abs(x) + abs(y) + abs(z)
                    elif cnt == mx_cnt and abs(x) + abs(y) + abs(z) < best_dis_to_zero:
                        best_loc = x, y, z
                        best_dis_to_zero = abs(x) + abs(y) + abs(z)
        if box_size == 1:
            return best_loc, mx_cnt
        else:
            x, y, z = best_loc
            xs = [x - box_size, x + box_size]
            ys = [y - box_size, y + box_size]
            zs = [z - box_size, z + box_size]
            box_size //= 2
(x, y, z), mx_cnt = best_location(nanobots)
print(abs(x) + abs(y) + abs(z))<jupyter_output>105370773<jupyter_text>[Day 25: Four-Dimensional Adventure](https://adventofcode.com/2018/day/25)<jupyter_code>coords = np.loadtxt('inputs/day25.txt', dtype=np.int64, delimiter=',')
def build_graph(coords, max_dist=3):
    "Build a graph represented by adjacent list whose edge is <= max_dist."
    n = len(coords)
    graph = {i : [] for i in range(n)}
    for i in range(n):
        for j in range(i + 1, n):
            if cityblock_distance(coords[i, :], coords[j, :]) <= max_dist:
                graph[i].append(j)
                graph[j].append(i)
    return graph
def number_of_connected_components(graph):
    "Compute the number of connected components of a graph."
    visited = {i : False for i in graph}
    def dfs(start):
        "Conduct DFS starts from start on a graph."
        stack = [start]
        visited[start] = True
        while stack:
            node = stack.pop()
            for nei in graph[node]:
                if not visited[nei]:
                    visited[nei] = True
                    stack.append(nei)
    cnt = 0
    for i in visited:
        if not visited[i]:
            dfs(i)
            cnt += 1
    return cnt
graph = build_graph(coords, max_dist=3)
print(number_of_connected_components(graph))<jupyter_output>377
{'fraction_non_alphanumeric': 0.16148358605354993, 'fraction_numerical': 0.02853525215404095, 'mean_word_length': 2.2330271565495208, 'pattern_counts': {'":': 0, '<': 119, '<?xml version=': 0, '>': 109, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '22', 'dir': 'jupyter-structured-clean-dedup', 'id': '229024', 'license': 'MIT', 'n_tokens_mistral': 12810, 'n_tokens_neox': 12016, 'n_words': 3386, 'path': '2018/AoC-2018-Python.ipynb', 'repo_name': 'zhangyaqi1989/Advent-of-Code', 'size': '32387'}