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:
    seen.add(freq)
    freq += l[i%len(l)]
    if freq in seen:
        print freq
        break
    i += 1

Part 1

import string

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

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 = [0]*1000000

for l in open('inputs/day3.txt').read().strip().split('\n'):
    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 = [0]*1000000
bad = set()

for l in open('inputs/day3.txt').read().strip().split('\n'):
    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]:
                bad.add(grid[i*1000+j])
                bad.add(a)
            grid[i*1000+j] = a

print set(range(1,a+1)) - bad

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

Part 1

from collections import defaultdict
import re

a = sorted(open('inputs/day4.txt').read().split('\n'))
d = defaultdict(lambda: [0]*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

a = sorted(open('inputs/day4.txt').read().split('\n'))
d = defaultdict(lambda: [0]*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

s = open('inputs/day5.txt').read().strip()

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

s = open('inputs/day5.txt').read().strip()
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:
        visited.add((x,y))
        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())

img voronoi

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

for l in open('inputs/day7.txt').readlines():
    graph[l[5]] += l[36]
    inctr[l[36]] += 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)

for l in open('inputs/day7.txt').readlines():
    graph[l[5]].add(l[36])
    rgraph[l[36]].add(l[5])

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)
    finished.add(x)
    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])
        doing.add(selected)
        heapq.heappush(q, (t+ord(selected)-4, selected))

print q[0][0]

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()[0]

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()[0]

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[0])
n = int(l[6])

class LinkedNode(object):
    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

ptr = LinkedNode(0)
scores = [0]*p

for i in range(1, n+1):
    if i%23:
        ptr = LinkedNode(i,ptr,ptr.nxt).nxt
    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[0])
n = int(l[6])*100

class LinkedNode(object):
    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

ptr = LinkedNode(0)
scores = [0]*p

for i in range(1, n+1):
    if i%23:
        ptr = LinkedNode(i,ptr,ptr.nxt).nxt
    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

stars = map(lambda l:map(int,re.findall(r'\-?\d+',l)), open('inputs/day10.txt').readlines())
n = len(stars)

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

t -= 1
xs=[stars[i][0] + t*stars[i][2] for i in range(n)]
ys=[stars[i][1] + t*stars[i][3] 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

stars = map(lambda l:map(int,re.findall(r'\-?\d+',l)), open('inputs/day10.txt').readlines())
n = len(stars)

prev = 1e99
ymin, ymax = 0, 200000
t = 0
while ymax-ymin < prev:
    t += 1
    prev = ymax-ymin
    ys=[stars[i][1] + t*stars[i][3] 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 :)

img stars


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[0]:
            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[0]:
                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:
    state = list('.'*OFFSET + fi.readline().split()[2]+'.'*OFFSET)
    fi.readline()
    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:
    state = list('.'*OFFSET + fi.readline().split()[2]+'.'*OFFSET)
    fi.readline()
    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[1], tot)

diff = tots[1] - tots[0]
print tots[1] + (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[0])):
        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[2] == 0:
            rockets[i][0] -= 1
        elif rocket[2] == 1:
            rockets[i][1] += 1
        elif rocket[2] == 2:
            rockets[i][0] += 1
        elif rocket[2] == 3:
            rockets[i][1] -= 1
        l,c = rocket[:2]
        if grid[l][c] == '/':
            rockets[i][2] = [1,0,3,2][rocket[2]]
        elif grid[l][c] == '\\':
            rockets[i][2] = [3,2,1,0][rocket[2]]
        elif grid[l][c] == '+':
            if rocket[3] == 0:
                rockets[i][2] -= 1
                rockets[i][2] %= 4
            elif rocket[3] == 2:
                rockets[i][2] += 1
                rockets[i][2] %= 4
            rockets[i][3] += 1
            rockets[i][3] %= 3
        for j in range(len(rockets)):
            if i==j: continue
            if rocket[0] == rockets[j][0] and rocket[1] == rockets[j][1]:
                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[0][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')[0])
        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
            visited.add((l,c))
            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] == '.':
                    visitnext.add((l+dl,c+dc))
                elif (l+dl, c+dc) in targets:
                    solutions.append((l,c))
    return sorted(solutions)[0] if solutions else None


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

nl = len(ogrid)
nc = len(ogrid[0])

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)][1]
                mydict = e
                targets = g.keys()
                targetdict = g
            elif (l,c) in g:
                if not len(e): break
                me = 'G'
                myatk = g[(l,c)][1]
                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)][0], l+dl, c+dc))
            if not reachable: continue
            reachable.sort()
            atk = tuple(reachable[0][1:3])
            targetdict[atk][0] -= myatk
            if targetdict[atk][0] <= 0:
                del targetdict[atk]
                grid[atk[0]][atk[1]] = '.'
        else:
            turn += 1

    score = sum(e[x][0] for x in e) + sum(g[x][0] 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]

ipt = open('inputs/day16.txt').read().split('\n')
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]

ipt = open('inputs/day16.txt').read().split('\n')
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[0]

img stars

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 = []
for l in open('inputs/day17.txt').read().strip().split('\n'):
    a,b,c = map(int, re.findall('-?\\d+', l))
    scans.append((a,a+1,b,c+1) if l[0]=='x' else (b,c+1,a,a+1))

zs = zip(*scans)
minx, maxx = min(zs[0]), max(zs[1])
miny, maxy = min(zs[2]), max(zs[3])

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]:
    srcadd = set()
    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:
                srcadd.add((lx, y))
            if not rtype:
                srcadd.add((rx, y))
    cnt = 0
    for l in grid:
        cnt += l.count('~') + l.count('|')
    cnts.append(cnt)

    sources = sources.union(srcadd)

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.

img stars

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}

ipt = map(lambda s:s.split(), open('inputs/day19.txt').read().strip().split('\n'))
ip = int(ipt[0][1])
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[4]%i, range(1,state[4]+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
Follow me on Twitter to be informed about new posts !