# Advent of Code 2018 - solutions

Here are my solutions to the Advent of Code 2018, updated almost daily with new challenges.

If you are reading this in december 2018, you can join Advent of Code 2018, use the code `433401-91bb9f33` to join my friends leaderboard !

If you are playing the challenge, try not to read any of the solutions to problems you haven’t solved.

The challenge is only for fun and there is nothing to win, so I think it’s ok to publish them while the challenge is running. I might still publish the solutions to the harder problems only after the contest ends.

I will try to come up with simple and/or elegant solutions every day, and I would love to see yours ! Send them my way on Twitter :)

### Part 1

``````print sum(map(int, open('inputs/day1.txt').read().split()))
``````

### Part 2

``````l = map(int, open('inputs/day1.txt').read().split())

seen = set()
freq, i = 0, 0

while True:
freq += l[i%len(l)]
if freq in seen:
print freq
break
i += 1
``````

### Part 1

``````import string

print (sum(any(x.count(c)==2 for c in string.lowercase)for x in l) *
sum(any(x.count(c)==3 for c in string.lowercase) for x in l))
``````

My initial solve used Counter objects, and was more efficient but harder to read.

### Part 2

``````l = open('inputs/day2.txt').read().split()

for i in l:
for j in l:
if sum(a!=b for a,b in zip(i, j)) == 1:
print ''.join(a if a==b else '' for a,b in zip(i, j))
exit(0)
``````

### Part 1

``````import re

grid = *1000000

a,b,c,d,e = map(int,re.findall(r'[\d]+', l))
for i in range(b, b+d):
for j in range(c, c+e):
grid[i*1000+j] += 1

print len(filter(lambda x: x>1, grid))
``````

### Part 2

``````import re

grid = *1000000

a,b,c,d,e = map(int,re.findall(r'[\d]+', l))
for i in range(b, b+d):
for j in range(c, c+e):
if grid[i*1000+j]:
grid[i*1000+j] = a

``````

Today’s solutions are presented to you by Clément!

### Part 1

``````from collections import defaultdict
import re

d = defaultdict(lambda: *60)

def lastNum(s):
return int(re.findall(r"\d+", s)[-1])

for i in range(len(a)):
if "begins shift" in a[i]:
guard = lastNum(a[i])
elif "wakes up" in a[i]:
for j in range(lastNum(a[i-1]), lastNum(a[i])):
d[guard][j] += 1

bestGuard = max(d, key=lambda x: sum(d[x]))
print(bestGuard * d[bestGuard].index(max(d[bestGuard])))
``````

### Part 2

There’s only a 3 byte difference between his solutions !

``````from collections import defaultdict
import re

d = defaultdict(lambda: *60)

def lastNum(s):
return int(re.findall(r"\d+", s)[-1])

for i in range(len(a)):
if "begins shift" in a[i]:
guard = lastNum(a[i])
elif "wakes up" in a[i]:
for j in range(lastNum(a[i-1]), lastNum(a[i])):
d[guard][j] += 1

bestGuard = max(d, key=lambda x: max(d[x]))
print(bestGuard * d[bestGuard].index(max(d[bestGuard])))
``````

### Part 1

``````import string

up = string.uppercase
lo = string.lowercase

r=''
while r!=s:
r=s
for i in range(26):
s=s.replace(up[i]+lo[i], '').replace(lo[i]+up[i], '')

print len(r)
``````

### Part 2

``````import string

up = string.uppercase
lo = string.lowercase

res = len(s)

for i in range(26):
r=''
t=s.replace(lo[i], '').replace(up[i], '')
while r!=t:
r=t
for i in range(26):
t=t.replace(up[i]+lo[i], '').replace(lo[i]+up[i], '')
res=min(res, len(t))

print res
``````

### Part 1

This code generates Manhattan Voronoi by BFS, and generates a nice animation from it.

``````from collections import Counter
from random import randint
from PIL import Image

frame = Image.new('RGB', (400, 400))

l = map(lambda x: map(int, x.split(',')), open('inputs/day6.txt').read().strip().split('\n'))
n = len(l)

colors = [(randint(0,255), randint(0,255), randint(0,255)) for _ in range(n)]

visitnext = {}
cnt = {}
for i, (x,y) in enumerate(l):
visitnext[(x,y)] = i
cnt[i] = 0
visited = set()

i = 0
while visitnext.keys():
visiting = visitnext
visitnext = {}
for x,y in visiting:
for dx, dy in ((-1,0), (1,0), (0,-1), (0,1)):
if 0<=x+dx<400 and 0<=y+dy<400 and (x+dx, y+dy) not in visited:
if (x+dx, y+dy) in visitnext and visitnext[(x+dx, y+dy)] != visiting[(x,y)]:
visitnext[(x+dx, y+dy)] = -1
else:
visitnext[(x+dx, y+dy)] = visiting[(x,y)]

for x,y in visitnext:
root = visitnext[(x,y)]
if root in cnt and (x in (0,399) or y in (0,399)):
del cnt[root]
if root == -1:
frame.putpixel((x,y), (255,255,255))
else:
frame.putpixel((x,y), colors[root])
if root in cnt:
cnt[root] += 1

for x,y in l:
for dx, dy in ((0,0), (-1,0), (1,0), (0,-1), (0,1)):
frame.putpixel((x+dx, y+dy), (0,0,0))
frame.save('frames/%s.png' % str(i).zfill(3))
i += 1

print max(cnt.values())
`````` ### Part 2

``````l = map(lambda x: map(int, x.split(',')), open('inputs/day6.txt').read().strip().split('\n'))
print sum(1 if sum(abs(x - xl) + abs(y - yl) for xl, yl in l) < 10000 else 0 for x in range(360) for y in range(360))
``````

### Part 1

This problem is a simple topological sort, and when given several choices the algorithm always picks the node with the smallest label.

``````import collections

graph = collections.defaultdict(list)
inctr = {chr(i+ord('A')):0 for i in range(26)}

graph[l] += l
inctr[l] += 1

res = ''
for i in range(26):
selected = min(inctr.keys(), key=lambda k:1000*inctr[k]+ord(k))
res += selected
del inctr[selected]
for nxt in graph[selected]:
inctr[nxt] -= 1
print res
``````

### Part 2

This one is pretty complex, but there might be a simple way that I didn’t see.

First, we compute the length of the critical path for each node (longest path from the node to the end). Then, each time a worker is free, we assign it the task with all dependencies completed which has the longest critical path (greedy algorithm).

``````import collections
import heapq

graph = collections.defaultdict(set)
rgraph = collections.defaultdict(set)

critical = collections.defaultdict(int)

for i in range(26):
for j in rgraph:
for k in rgraph[j]:
critical[k] = max(critical[k], critical[j] + ord(j) - 4)

q = [(0, None)] * 5
finished = set()
doing = set()
while len(finished)<26:
t, x = heapq.heappop(q)
if x:doing.remove(x)
while len(q) < 5:
candidates = filter(lambda k:k not in doing and k not in finished and not rgraph[k]-finished, critical)
if not candidates: break
selected = max(candidates, key=lambda k:critical[k])
heapq.heappush(q, (t+ord(selected)-4, selected))

print q
``````

### Part 1

``````l = map(int, open('inputs/day8.txt').read().split())

def parsetree(n=0):
s, pos = 0, n+2
for i in range(l[n]):
val, pos = parsetree(pos)
s += val
return s + sum(l[pos:pos+l[n+1]]), pos + l[n+1]

print parsetree()
``````

### Part 2

``````l = map(int, open('inputs/day8.txt').read().split())

def parsetree(n=0):
if l[n]:
vals, pos = [], n+2
for i in range(l[n]):
val, pos = parsetree(pos)
vals.append(val)
s = sum(vals[i-1] if 0<i<=len(vals) else 0 for i in l[pos:pos+l[n+1]])
return s, pos + l[n+1]
else:
return sum(l[n+2:n+2+l[n+1]]), n + l[n+1] + 2

print parsetree()
``````

### Part 1

The problem is pretty straightforward, we only have to implement the execution loop as it is described.

However, using arrays is not recommended since we have to insert and delete elements in the middle of the data.

What we should use instead is a circular doubly linked list. It supports O(1) insertion and deletion.

As opposed to arrays, linked lists do not easily support random access (which is O(N) for linked lists but O(1) for lists). Luckily, we do not need random access, only sequential access.

``````l = open('inputs/day9.txt').read().split()
p = int(l)
n = int(l)

def __init__(self, val, prev=None, nxt=None):
self.val = val
self.prev = prev or self
self.nxt = nxt or self
self.nxt.prev = self
self.prev.nxt = self

def kill(self):
self.nxt.prev = self.prev
self.prev.nxt = self.nxt
return self.val

scores = *p

for i in range(1, n+1):
if i%23:
else:
ptr = ptr.prev.prev.prev.prev.prev.prev
scores[i%p] += ptr.prev.prev.kill() + i

print max(scores)
``````

### Part 2

Same solution as before, only multiplying the input by 100. Since we are already using an optimized data structure, this scales well.

``````l = open('inputs/day9.txt').read().split()
p = int(l)
n = int(l)*100

def __init__(self, val, prev=None, nxt=None):
self.val = val
self.prev = prev or self
self.nxt = nxt or self
self.nxt.prev = self
self.prev.nxt = self

def kill(self):
self.nxt.prev = self.prev
self.prev.nxt = self.nxt
return self.val

scores = *p

for i in range(1, n+1):
if i%23:
else:
ptr = ptr.prev.prev.prev.prev.prev.prev
scores[i%p] += ptr.prev.prev.kill() + i

print max(scores)
``````

### Part 1

First, we start by finding the time when all stars are aligned. A simple heuristic works – we look at the difference between the highest and the lowest stars, and try to find a local minimum. This local minimum turns out to be our solution.

We then offset the position of each star to move them closer to the origin, then display the resulting stars.

``````import re

n = len(stars)

prev = 1e99
ymin, ymax = 0, 200000
t = 0
while ymax-ymin < prev:
t += 1
prev = ymax-ymin
ys=[stars[i] + t*stars[i] for i in range(n)]
ymin = min(ys)
ymax = max(ys)

t -= 1
xs=[stars[i] + t*stars[i] for i in range(n)]
ys=[stars[i] + t*stars[i] for i in range(n)]
print xs
xs = map(lambda x: x - min(xs), xs)
ys = map(lambda y: y - min(ys), ys)

grid = [[' ' for x in range(max(xs)+1)] for y in range(max(ys)+1)]

for x, y in zip(xs, ys):
grid[y][x] = '#'

for l in grid:
print ''.join(l)
``````

### Part 2

This is the same solution as before, but we only need to print the time, not the stars.

``````import re

n = len(stars)

prev = 1e99
ymin, ymax = 0, 200000
t = 0
while ymax-ymin < prev:
t += 1
prev = ymax-ymin
ys=[stars[i] + t*stars[i] for i in range(n)]
ymin = min(ys)
ymax = max(ys)

print t-1
``````

Here is a nice viz of day 10 as a bonus :) ### Part 1

Naive search is sufficient in complexity there.

``````serial = 5235
best = (0, -1, -1)

for bx in range(1,299):
for by in range(1,299):
tot = 0
for dx in range(3):
for dy in range(3):
x, y = bx + dx, by + dy
tot += (((x+10) * y + serial)*(x+10)/100%10)-5
if tot >= best:
best = (tot, bx, by)

print '%d,%d'%best[1:]
``````

### Part 2

Now we have to get a little smarter, I’m using a dynamic programming approach to the maximum subarray sum problem.

An auxiliary array is computed in O(n²) time, which allows to get the sum of any subarray in O(1) time. We then iterate over 3 variables (x, y, size) to find the maximum in O(n³) time.

I know this solution might look a bit “dark magic”, I don’t have much time today to explain it. Feel free to ask me on Twitter if it interests you :)

``````serial = 5235

dp = [[0 for i in range(301)] for j in range(301)]

for x in range(1,301):
for y in range(1,301):
dp[x][y] = ((((x+10) * y + serial)*(x+10)/100%10)-5
+ dp[x-1][y]
+ dp[x][y-1]
- dp[x-1][y-1])

best = (0, -1, -1, -1)

for x in range(1,301):
for y in range(1,301):
for sz in range(1,300-max(x,y)):
score = (dp[x+sz][y+sz]
- dp[x+sz][y-1]
- dp[x-1][y+sz]
+ dp[x-1][y-1])
if score > best:
best = score, x, y, sz+1
print '%d,%d,%d'%best[1:]
``````

### Part 1

Again - Part 1 is naive implementation, optimizations will come in part 2.

OFFSET is simply the amount of empty cells we add before and after the initial state to ensure trees do not grow outside the array.

``````OFFSET = 3000
tr = {}
with open('inputs/day12.txt', 'rb') as fi:
for i in range(32):
ipt, res = fi.readline().strip().split(' => ')
tr[ipt] = res

for i in range(20):
newstate = ['.','.']
for pos in range(2,len(state)-2):
newstate.append(tr[''.join(state[pos-2:pos+3])])
newstate.append('.')
newstate.append('.')
state = newstate
assert state[0:3] == list('...') and state[-4:-1] == list('...')

tot = 0
for j,x in enumerate(state):
if x == '#':
tot += j-OFFSET

print tot
``````

### Part 2

This is a bit of a dirty hack, I’m pretty sure there are counterexamples to this solution, but it works for me so deal with it ;)

We only compute the first 1000 scores. After a few iterations (about 300 in my case), we can see that the score is on a constant slope (+53 every iteration in my case). By assuming the slope remains constant until iteration 50000000000, we can extrapolate the final score from there.

``````OFFSET = 3000
tr = {}
with open('inputs/day12.txt', 'rb') as fi:
for i in range(32):
ipt, res = fi.readline().strip().split(' => ')
tr[ipt] = res

tots = (0, 0)
for i in range(1000):
newstate = ['.','.']
for pos in range(2,len(state)-2):
newstate.append(tr[''.join(state[pos-2:pos+3])])
newstate.append('.')
newstate.append('.')
state = newstate
assert state[0:3] == list('...') and state[-4:-1] == list('...')

tot = 0
for j,x in enumerate(state):
if x == '#':
tot += j-OFFSET
tots = (tots, tot)

diff = tots - tots
print tots + (50000000000 - 1000) * diff
``````

### Parts 1 and 2

``````grid = map(list, open('inputs/day13.txt').read().rstrip('\n').split('\n'))

rockets = []
for l in range(len(grid)):
for c in range(len(grid)):
if grid[l][c] == '>':
rockets.append([l,c,1,0])
grid[l][c] = '-'
elif grid[l][c] == '<':
rockets.append([l,c,3,0])
grid[l][c] = '-'
elif grid[l][c] == 'v':
rockets.append([l,c,2,0])
grid[l][c] = '|'
elif grid[l][c] == '^':
rockets.append([l,c,0,0])
grid[l][c] = '|'

tick = 0
firstcrash = True
while True:
rockets.sort()
dels = []
tick += 1
for i, rocket in enumerate(rockets):
if rocket == 0:
rockets[i] -= 1
elif rocket == 1:
rockets[i] += 1
elif rocket == 2:
rockets[i] += 1
elif rocket == 3:
rockets[i] -= 1
l,c = rocket[:2]
if grid[l][c] == '/':
rockets[i] = [1,0,3,2][rocket]
elif grid[l][c] == '\\':
rockets[i] = [3,2,1,0][rocket]
elif grid[l][c] == '+':
if rocket == 0:
rockets[i] -= 1
rockets[i] %= 4
elif rocket == 2:
rockets[i] += 1
rockets[i] %= 4
rockets[i] += 1
rockets[i] %= 3
for j in range(len(rockets)):
if i==j: continue
if rocket == rockets[j] and rocket == rockets[j]:
if firstcrash:
firstcrash = False
print rockets[i][1::-1]
dels.append(i)
dels.append(j)
for dl in sorted(dels, reverse=True):
del rockets[dl]
if len(rockets) == 1:
print rockets[1::-1]
break
``````

### Parts 1 and 2

``````ls = '37'
p0 = 0
p1 = 1
seen = set()
while True:
i0, i1 = int(ls[p0]), int(ls[p1])
ls += str(i0 + i1)
p0 += i0 + 1
p0 %= len(ls)
p1 += i1 + 1
p1 %= len(ls)
if '919901' in (ls[-6:], ls[-7:-1]):
print ls[919901:919911]
print len(ls.split('919901'))
break
``````

### Parts 1 and 2

``````import copy

def bfs(sl, sc, targets, grid):
visited = set()
visitnext = set([(sl, sc)])
solutions = []
while len(visitnext) and not solutions:
visiting = visitnext
visitnext = set()
for l,c in visiting:
if (l,c) in visited: continue
for dl, dc in ((-1,0),(1,0),(0,-1),(0,1)):
if (l+dl, c+dc) in visited: continue
if grid[l+dl][c+dc] == '.':
elif (l+dl, c+dc) in targets:
solutions.append((l,c))
return sorted(solutions) if solutions else None

ogrid = map(lambda x:list(x.rstrip()),open('inputs/day15.txt'))

nl = len(ogrid)
nc = len(ogrid)

epower = 3
while True:
grid = copy.deepcopy(ogrid)

e = {}
g = {}

for l in range(nl):
for c in range(nc):
if grid[l][c] == 'E':
e[(l,c)] = [200,epower]
elif grid[l][c] == 'G':
g[(l,c)] = [200,3]

turn = 0
while len(e) and len(g):
for l,c in sorted(e.keys() + g.keys()):
if (l,c) in e:
if not len(g): break
me = 'E'
myatk = e[(l,c)]
mydict = e
targets = g.keys()
targetdict = g
elif (l,c) in g:
if not len(e): break
me = 'G'
myatk = g[(l,c)]
mydict = g
targets = e.keys()
targetdict = e
else:
continue

if not any((l+dl, c+dc) in targets for dl, dc in ((-1,0),(1,0),(0,-1),(0,1))):
mvpos = bfs(l, c, targets, grid)
if mvpos is None: continue
ml, mc = mvpos
backtrack = bfs(ml, mc, [(l,c)], grid)
if backtrack is None:
print me, l, c
for l in grid:
print ''.join(l)
assert backtrack is not None
bl, bc = backtrack
grid[bl][bc] = me
mydict[(bl,bc)] = mydict[(l,c)]
grid[l][c] = '.'
del mydict[(l,c)]

l,c = bl, bc

reachable = []
for dl, dc in ((-1,0),(1,0),(0,-1),(0,1)):
if (l+dl, c+dc) in targets:
reachable.append((targetdict[(l+dl, c+dc)], l+dl, c+dc))
if not reachable: continue
reachable.sort()
atk = tuple(reachable[1:3])
targetdict[atk] -= myatk
if targetdict[atk] <= 0:
del targetdict[atk]
grid[atk][atk] = '.'
else:
turn += 1

score = sum(e[x] for x in e) + sum(g[x] for x in g)

if epower == 3:
print score*turn
if len(e) == 10:
print score*turn
break

epower += 1
``````

### Part 1

``````ops = [lambda reg, a, b: reg[a] + reg[b],
lambda reg, a, b: reg[a] + b,
lambda reg, a, b: reg[a] * reg[b],
lambda reg, a, b: reg[a] * b,
lambda reg, a, b: reg[a] & reg[b],
lambda reg, a, b: reg[a] & b,
lambda reg, a, b: reg[a] | reg[b],
lambda reg, a, b: reg[a] | b,
lambda reg, a, b: a,
lambda reg, a, b: reg[a],
lambda reg, a, b: 1 if a > reg[b] else 0,
lambda reg, a, b: 1 if reg[a] > b else 0,
lambda reg, a, b: 1 if reg[a] > reg[b] else 0,
lambda reg, a, b: 1 if a == reg[b] else 0,
lambda reg, a, b: 1 if reg[a] == b else 0,
lambda reg, a, b: 1 if reg[a] == reg[b] else 0]

i = 0
res = 0
while ipt[i].startswith('Before'):
before = eval(ipt[i].replace('Before:',''))
opcode, a, b, c = map(int, ipt[i+1].split())
after = eval(ipt[i+2].replace('After:',''))
res += int(sum(int(op(list(before), a, b) == after[c]) for op in ops) > 2)
i += 4
print res
``````

### Part 2

``````ops = [lambda reg, a, b: reg[a] + reg[b],
lambda reg, a, b: reg[a] + b,
lambda reg, a, b: reg[a] * reg[b],
lambda reg, a, b: reg[a] * b,
lambda reg, a, b: reg[a] & reg[b],
lambda reg, a, b: reg[a] & b,
lambda reg, a, b: reg[a] | reg[b],
lambda reg, a, b: reg[a] | b,
lambda reg, a, b: a,
lambda reg, a, b: reg[a],
lambda reg, a, b: 1 if a > reg[b] else 0,
lambda reg, a, b: 1 if reg[a] > b else 0,
lambda reg, a, b: 1 if reg[a] > reg[b] else 0,
lambda reg, a, b: 1 if a == reg[b] else 0,
lambda reg, a, b: 1 if reg[a] == b else 0,
lambda reg, a, b: 1 if reg[a] == reg[b] else 0]

i=0
opmap = {}
while ipt[i].startswith('Before'):
before = eval(ipt[i].replace('Before:',''))
opcode, a, b, c = map(int, ipt[i+1].split())
after = eval(ipt[i+2].replace('After:',''))
opset = set(filter(lambda op: op(list(before), a, b) == after[c], ops)) - set(opmap.values())
if len(opset) == 1: opmap[opcode] = opset.pop()
i+=4
i += 2
assert sorted(opmap.keys()) == range(16)

state = [0,0,0,0]
while ipt[i]:
opcode, a, b, c = map(int, ipt[i].split())
state[c] = opmap[opcode](list(state), a, b)
i += 1
print state
`````` ### Parts 1 and 2

This is a pretty straightforward implementation, no big surprises. Our stopping condition is reached when the score does not increase for 10 simulation turns (didn’t work with 1 turn for a reason, might be due to source creation).

``````import re

scans = []
a,b,c = map(int, re.findall('-?\\d+', l))
scans.append((a,a+1,b,c+1) if l=='x' else (b,c+1,a,a+1))

zs = zip(*scans)
minx, maxx = min(zs), max(zs)
miny, maxy = min(zs), max(zs)

grid = [['.' for x in range(maxx - minx + 2)] for y in range(maxy - miny)]

for a,b,c,d in scans:
for x in range(a,b):
for y in range(c,d):
grid[y - miny][x - minx + 1] = '#'

sources = set([(500, miny)])

cnts = []
while len(cnts)<10 or cnts[-1] != cnts[-10]:
for src in sources:
x, y = src
while y+1 < maxy and grid[y - miny + 1][x - minx + 1] not in '#~':
grid[y - miny][x - minx + 1] = '|'
y += 1
grid[y - miny][x - minx + 1] = '|'

if y+1 >= maxy:
continue

lx = x
while True:
grid[y - miny][lx - minx + 1] = '|'
if grid[y - miny + 1][lx - minx + 1] in '.|':
ltype = 0
break
if grid[y - miny][lx - minx] in '#~':
ltype = 1
break
lx -= 1

rx = x
while True:
grid[y - miny][rx - minx + 1] = '|'
if grid[y - miny + 1][rx - minx + 1] in '.|':
rtype = 0
break
if grid[y - miny][rx - minx + 2] in '#~':
rtype = 1
break
rx += 1

if ltype * rtype:
for xi in range(lx, rx+1):
grid[y - miny][xi - minx + 1] = '~'
else:
if not ltype:
if not rtype:
cnt = 0
for l in grid:
cnt += l.count('~') + l.count('|')
cnts.append(cnt)

print cnts[-1]
cnt = 0
for l in grid:
cnt += l.count('~')
print cnt
``````

### Parts 1 and 2

Part 1 is ad-hoc implementation, I surrounded the grid with `x` chars so I don’t have to manage out of bounds checking :)

Part 2 involves a little trick : If a previous board state comes back, it means we are in a loop so it becomes easy to predict future states. Once a loop is detected we simply perform this skip to increase the counter right under 1 billion, and resume execution normally.

``````grid = ['x'*52] + ['x' + l +'x' for l in open('inputs/day18.txt').read().strip().split('\n')] + ['x'*52]

seen = {}

i = 0
while i < 1000000000:
newgrid = ['x'*52]
for l in range(1,51):
newgrid.append('x')
for c in range(1,51):
deltas = ((-1,-1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
nb = [grid[l+dl][c+dc] for dl, dc in deltas]
if grid[l][c] == '.':
newgrid[-1] += '|' if nb.count('|') > 2 else '.'
if grid[l][c] == '|':
newgrid[-1] += '#' if nb.count('#') > 2 else '|'
if grid[l][c] == '#':
newgrid[-1] += '#' if '#' in nb and '|' in nb else '.'
newgrid[-1] += 'x'
newgrid.append('x'*52)
grid = newgrid
res = ''.join(grid)

if res in seen:
cycle = i - seen[res]
i += (999999999-i)/cycle*cycle
seen[res] = i
i += 1
if i==10 : print res.count('|') * res.count('#')

print res.count('|') * res.count('#')
``````

Here is the result of the simulation for the first 600 steps, we can see the loops of length 28 starting around frame 400. ### Parts 1 and 2

In day 19, we have to interpret the provided assembler program. As usual, the first part can be run naively.

However, solving part 2 involves understanding the program. Here is the input function as pseudocode :

``````r4 = f(r0)
r0 = 0
for r5 = 1..r4
r3 = 0
while r5*r3 < r4:
r3++
if r5*r3 == r4
r0 += r5
return r0
``````

The provided program sums all dividers of r4, in an extremely inefficient way (O(r4²) complexity). Since r4 is around 1000 in part 1, we can get to the end in this complexity class, but part 2 needs to be optimized since r4 will be around 10 million.

For simplicity, we still simulate the first part to get r4. As soon as we have the final value for r4, we end the simulation and pipe r4 into our custom divider sum function. The simplified O(N) algorithm is entirely contained in the last line of this solution :

``````opmap = {'addr': lambda reg, a, b: reg[a] + reg[b],
'addi': lambda reg, a, b: reg[a] + b,
'mulr': lambda reg, a, b: reg[a] * reg[b],
'muli': lambda reg, a, b: reg[a] * b,
'banr': lambda reg, a, b: reg[a] & reg[b],
'bani': lambda reg, a, b: reg[a] & b,
'borr': lambda reg, a, b: reg[a] | reg[b],
'bori': lambda reg, a, b: reg[a] | b,
'seti': lambda reg, a, b: a,
'setr': lambda reg, a, b: reg[a],
'gtir': lambda reg, a, b: 1 if a > reg[b] else 0,
'gtri': lambda reg, a, b: 1 if reg[a] > b else 0,
'gtrr': lambda reg, a, b: 1 if reg[a] > reg[b] else 0,
'eqir': lambda reg, a, b: 1 if a == reg[b] else 0,
'eqri': lambda reg, a, b: 1 if reg[a] == b else 0,
'eqrr': lambda reg, a, b: 1 if reg[a] == reg[b] else 0}

ip = int(ipt)
instr = ipt[1:]

state = [1,0,0,0,0,0]
while state[ip] != 1:
opcode, a, b, c = instr[state[ip]]
a, b, c = map(int, (a, b, c))
state[c] = opmap[opcode](state, a, b)
state[ip] += 1

print sum(filter(lambda i:not state%i, range(1,state+1)))
``````

The solution for part 1 is the same, simply set state as `[0,0,0,0,0,0]` instead of `[1,0,0,0,0,0]`.

Written on December 1, 2018