advent of code 2016

day01.py

import numpy as np

def day1(lststr):
    lst = lststr.split(', ')
    dirnow = 0
    posnow = [0,0]
    for k in lst:
        dirletter,num = k[0],int(k[1:])
        if dirletter=='R':
            dirnow -= np.pi/2
        else:
            dirnow += np.pi/2
        posnow = [posnow[0]+num*np.cos(dirnow), posnow[1]+num*np.sin(dirnow)]
    print(np.abs(posnow).sum())


def day1b(lststr):
    lst = lststr.split(', ')
    dirnow = 0
    posnow = [0,0]
    allpos = [posnow]
    for k in lst:
        dirletter,num = k[0],int(k[1:])
        if dirletter=='R':
            dirnow -= np.pi/2
        else:
            dirnow += np.pi/2
        for l in range(num):
            posnow = [np.round(posnow[0]+np.cos(dirnow)), np.round(posnow[1]+np.sin(dirnow))]
            if posnow in allpos:
                print(np.abs(posnow).sum())
                return
            else:
                allpos.append(posnow)
    print('single find:',np.abs(posnow).sum())

day02.py

import numpy as np

def day2(codestr):
    nums = np.arange(1,10).astype(np.int64).reshape(3,3)
    lastind = np.array([1,1])
    code = []
    for codeline in codestr.split('\n'):
        for lett in codeline:
            if lett=='U':
                delta = [-1,0]
            elif lett=='D':
                delta = [1,0]
            elif lett=='R':
                delta = [0,1]
            else:
                delta = [0,-1]
            lastind = np.clip(lastind+delta,0,2)
        code.append(str(nums[tuple(lastind)]))
    return ''.join(code)

def day2b(codestr):
    nums = np.array(list('0010002340567890ABC000D00')).reshape(5,5)
    lastind = np.array([2,0])
    code = []
    for codeline in codestr.split('\n'):
        for lett in codeline:
            if lett=='U':
                delta = [-1,0]
            elif lett=='D':
                delta = [1,0]
            elif lett=='R':
                delta = [0,1]
            else:
                delta = [0,-1]
            tmpind = np.clip(lastind+delta,0,4)
            if nums[tuple(tmpind)]!='0':
                lastind = tmpind
        code.append(nums[tuple(lastind)])
    return ''.join(code)

day03.py

import numpy as np
from itertools import permutations

def day3(sideslist):
    sides = np.fromstring(sideslist,sep=' ').reshape(-1,3)
    return sum(np.all(list(sides[:,k1]+sides[:,k2]>sides[:,k3] for k1,k2,k3 in permutations(range(3))),axis=0))


def day3b(sideslist):
    sides = np.fromstring(sideslist,sep=' ').reshape(-1,3)
    sides = sides.T.reshape(-1,3)
    return sum(np.all(list(sides[:,k1]+sides[:,k2]>sides[:,k3] for k1,k2,k3 in permutations(range(3))),axis=0))

day04.py

mport re
from collections import Counter
    
def isreal(roomstr):
    for c in ['-','[',']']:
        roomstr = roomstr.replace(c,'') 
    name,id,checksum = re.match('([a-z]+)(\d+)([a-z]+)',roomstr).groups()
    freqs = Counter(name).most_common() # 5 here won't do
    freqs =sorted((-l,k) for k,l in freqs)
    newchecksum = ''.join(list(zip(*freqs))[1])[:5]
    return int(id) if checksum==newchecksum else 0


def day4(roomlist):
    return sum(map(isreal,roomlist.split('\n')))

###
    
def caesar(char,shift):
    if char==' ':
        return ' '
    for casefun in str.lower,str.upper:
        if casefun('a') <= char <= casefun('z'):
            return chr(ord(casefun('a')) + (ord(char) - ord(casefun('a')) + shift)%26)

def getrooms(roomlist):
    for roomstr in roomlist.split('\n'):
        if not isreal(roomstr):
            continue
        roomstr_t = roomstr.replace('-',' ')

        name,id,checksum = re.match('([a-zA-Z ]+)(\d+)(\[[a-zA-Z]+\])',roomstr_t).groups()
        yield ''.join(map(lambda char:caesar(char,int(id)),name)),id


def day4b(roomlist):
    parsed_dat = getrooms(roomlist)
    for name,id in parsed_dat:
        if 'pole' in name.lower() or 'object' in name.lower():
            print(name,id)

day05.py

from hashlib import md5

def day5(inp):
    if type(inp)==str:
        inp = bytes(inp,'ascii')
    code = []
    ind = 0
    while True:
        hexhash = md5(inp + str(ind).encode('ascii')).hexdigest()
        if hexhash.startswith('00000'):
            code.append(hexhash[5])
            print(hexhash[5])
        if len(code)==8:
            return ''.join(code)
        ind += 1


def day5b(inp):
    if type(inp)==str:
        inp = bytes(inp,'ascii')
    code = {}
    ind = 0
    while True:
        hexhash = md5(inp + str(ind).encode('ascii')).hexdigest()
        if hexhash.startswith('00000') and hexhash[5].isdigit() and int(hexhash[5]) in range(0,8) and hexhash[5] not in code:
            code[hexhash[5]] = hexhash[6]
            print(hexhash[6])
        if len(code)==8:
            return ''.join(list(zip(*sorted(code.items())))[1])
        ind += 1

day05b_funky.py

from hashlib import md5
import random
import time
import string

inputcode = 'ugkcyxxp' # hardwired

def day5b_funky(inp):
    if type(inp)==str:
        inp = bytes(inp,'ascii')
    code = {}
    ind = 0
    print('Initiating hacking...')
    while True:
        if ind%10000==0:
            funkyprint(code)
        hexhash = md5(inp + str(ind).encode('ascii')).hexdigest()
        if hexhash.startswith('00000') and hexhash[5].isdigit() and int(hexhash[5]) in range(0,8) and hexhash[5] not in code:
            code[hexhash[5]] = hexhash[6]
        if len(code)==8:
            funkyprint(code,True)
            endprint(code)
            return ''.join(list(zip(*sorted(code.items())))[1])
        ind += 1

#def funkyprint(code, done=False): #original
#    output = ''.join(code[str(k)] if str(k) in code else '{:x}'.format(random.choice(range(16))) for k in range(8))
#    print('\r' + output + ' Hacking progress [' + '*'*3*len(code) + ' '*3*(8-len(code)) + '] {:3.0f}%'.format(len(code)/8*100),end='')

def funkyprint(code, done = False): #upgrade by @poke
    output = ''.join(code[str(k)] if str(k) in code else '{:x}'.format(random.choice(range(16))) for k in range(8))
    if not done:
        for _ in range(random.randrange(2)):
            print('\r' + ''.join([random.choice(string.digits + string.ascii_letters + string.punctuation) for _ in range(random.randrange(40, 75))]).ljust(76))
    print('\r' + output + ' Hacking progress [' + '*'*3*len(code) + ' '*3*(8-len(code)) + '] {:3.0f}%'.format(len(code)/8*100),end='')


def endprint(code):
    endcode = ''.join(list(zip(*sorted(code.items())))[1])
    for k in range(20):
        if k%2:
            print('\r\033[1m' + endcode + '\033[0m',end='')
        else:
            print('\r' + endcode,end='')
        time.sleep(0.5)


try:
    day5b_funky(inputcode)
except KeyboardInterrupt:
    pass
finally:
    print('')

day06.py

from collections import Counter

def day6(messages):
    return ''.join(list(map(lambda x:Counter(x).most_common(1)[0][0],zip(*messages.split('\n')))))

def day6b(messages):
    return ''.join(list(map(lambda x:Counter(x).most_common()[-1][0],zip(*messages.split('\n')))))

day07.py

import re

def findpals(mystr,pallen):
    pals = []
    for k in range(len(mystr)-pallen+1):
        if pallen==4 and mystr[k]==mystr[k+3]!=mystr[k+2]==mystr[k+1]:
            pals.append(mystr[k:k+4])
        if pallen==3 and mystr[k]==mystr[k+2]!=mystr[k+1]:
            pals.append(''.join([mystr[k+1],mystr[k],mystr[k+1]]))
    return pals

def day7(inputs):
    goodTLS = 0
    goodSSL = 0
    for inp in inputs.split('\n'):
        parts = re.split('[\[\]]',inp)
        outs = '|||'.join(parts[::2])
        ins = '|||'.join(parts[1::2])
        outabbas = findpals(outs,4)
        inabbas = findpals(ins,4)
        babs = findpals(outs,3)
        if outabbas and not inabbas:
            goodTLS += 1
        if any(bab in ins for bab in babs):
            goodSSL += 1
    print(goodTLS,goodSSL)

day08.py

import numpy as np

def day8(inputs):
    disp = np.zeros((6,50),dtype=bool)
    for inp in inputs.split('\n'):
        if inp.startswith('rect'):
            A,B = map(int,inp.split(' ')[-1].split('x'))
            disp[:B,:A] = 1
        elif inp.startswith('rotate row y='):
            A,B = map(int,inp.split('=')[-1].split(' by '))
            disp[A,:] = np.roll(disp[A,:],B)
        elif inp.startswith('rotate column x='):
            A,B = map(int,inp.split('=')[-1].split(' by '))
            disp[:,A] = np.roll(disp[:,A],B)
    print(disp.sum())
    print('\n'.join(map(''.join,np.where(disp,' * ','   '))))

day09.py

import string
import re

def day9(inp):
    for ws in string.whitespace:
        inp = inp.replace(ws,'')
    out = ''
    while True:
        mark = re.search('\(\d+x\d+\)',inp)
        if not mark:
            break
        m,n = map(int,inp[mark.start()+1:mark.end()-1].split('x'))
        out += inp[:mark.start()] + n*inp[mark.end():mark.end()+m]
        inp = inp[mark.end()+m:]
    out += inp
    print(out)
    return len(out)


def day9b(inp):
    mark = re.search('\(\d+x\d+\)',inp)
    if not mark:
        return len(inp)
    m,n = map(int,inp[mark.start()+1:mark.end()-1].split('x'))
    return mark.start() + n*day9b(inp[mark.end():mark.end()+m]) + day9b(inp[mark.end()+m:])

day10.py

from collections import defaultdict

class Bot():
    def __init__(self,val=None,to=None):
        self.nums = set()
        self.to = {}
        if val is not None:
            self.nums.add(val)
        if to is not None:
            self.to.update(to)
    def instruct(self,to):
        self.to.update(to)
    def give(self,val):
        if val in self.nums or len(self.nums)==2:
            print(self.nums)
            raise Exception("Problem, shouldn't happen!")
        self.nums.add(val)
    def take(self):
        if len(self.nums)<2:
            return None
        tnums = list(self.nums)
        lowto,highto = self.to['low'],self.to['high']
        self.nums.clear()
        return ((min(tnums),lowto),(max(tnums),highto))

class Hive():
    def __init__(self,spec):
        self.bots = defaultdict(Bot)
        self.outs = defaultdict(list)
        self.special = spec

    def parse_inputs(self,inps):
        instructs = []
        rest = []
        for inp in inps.split('\n'):
            if inp.startswith('bot '):
                instructs.append(inp)
            else:
                rest.append(inp)
        self.parse_instructs(instructs)
        self.parse_rest(rest)

    def parse_instructs(self,inps):
        for inp in inps:
            if inp.startswith('value '):
                continue
            else:
                tinp = inp[4:].split(' gives low to ')
                ibot = int(tinp[0])
                lowinp,highinp = tinp[1].split(' and high to ')
                lowhigh = []
                for tinp in lowinp,highinp:
                    if tinp.startswith('output'):
                        lowhigh.append(-int(tinp[7:])-1)
                    else:
                        lowhigh.append(int(tinp[4:]))
                self.bots[ibot].instruct({'low':lowhigh[0], 'high':lowhigh[1]})

    def parse_rest(self,inps):
        for inp in inps:
            if not inp.startswith('value'):
                continue
            else:
                val,ibot = map(int,inp[6:].split(' goes to bot '))
                self.bots[ibot].give(val)
            while True:
                if not self.step_all():
                    break

    def step_all(self):
        didstuff = False
        for ibot,bot in self.bots.items():
            took = bot.take()
            if took:
                didstuff = True
                if {took[0][0],took[1][0]} == self.special:
                    print('bot {} compares numbers {} and {}.'.format(ibot,*self.special))
                for num,to in took:
                    if to<0:
                        self.outs[to].append(num)
                    else:
                        runagain = False
                        if to not in self.bots:
                            # new bot: need to rerun, iterator is corrupted
                            runagain = True
                        self.bots[to].give(num)
                        if runagain:
                            return True
        return didstuff

def day10(inps,spec,part2):
    # spec is a 2-element set that defines which bot to look for
    # part2 is a sequence of output bins, the values of which to multiply
    hive = Hive(spec)
    hive.parse_inputs(inps)
    while True:
        if not hive.step_all():
            prod = 1
            for outbin in part2:
                prod *= hive.outs[-outbin-1][0]
            print('product of output bins '+('{} '*len(part2)).format(*part2) +': {}'.format(prod))
            return

day11_meh.py

# this one runs in finite-but-too-much time
# part 1 input gives a broad upper bound quickly with no cutoff
# sufficiently smaller-than-upper-bound cutoff gives optimal answer in ~hours
#
# it's suboptimal in multiple places, but it'd need a full rewrite to get a scalable solution anyway

from collections import deque, defaultdict
from itertools import combinations
from copy import deepcopy
import re

def parse_inputs(inps):
    elems = {}
    floors = defaultdict(set)
    for ifloor,inp in enumerate(inps.split('\n')):
        for icomp,comppatt in enumerate(('\w+ generator','\w+\-compatible microchip')):
            for compstring in re.findall(comppatt,inp):
                elem = re.split('[ -]',compstring,maxsplit=1)[0]
                if elem not in elems:
                    elems[elem] = len(elems)
                ielem = elems[elem]
                floors[ifloor].add((ielem,2*icomp-1)) # 1 for microchip, -1 for generator
    return floors

def next_levels(levelnow):
    if levelnow==0:
        return [levelnow+1]
    if levelnow==3:
        return [levelnow-1]
    return [levelnow-1,levelnow+1]

def validate_level(items):
    for elem,comp in items:
        # invalid if there is a lone microchip *and* any generator on the level
        if comp==1 and (elem,-comp) not in items:
            # see if there are other generators on the floor
            if any(telem!=elem and tcomp==-1 for telem,tcomp in items):
                return False
    return True

def finalstate(floors):
    if any(len(floors[ifloor])>0 for ifloor in range(3)):
        return False
    return True

def day11(inps,cutoff=-1):
    minpath = 1e100 # initial estimate
    floors = parse_inputs(inps)
    backlog = deque()
    floornow = 0
    numsteps = 0
    history = [(numsteps,floornow,deepcopy(floors))]
    while True:
        # determine possible next steps
        # floor choice first, elevator choice later -> prioritize 2 up, 1 down h/t Antti
        for floornext in next_levels(floornow):
            elevlist = list(combinations(floors[floornow],1))+list(combinations(floors[floornow],2))
            if floornext==floornow-1:
                # append/pop from the right -> append deferred ones first
                elevlist = reversed(elevlist)
            for televator in elevlist:
                # don't put a microchip and another generator in the elevator
                if len(televator)==2 and televator[0][1]+televator[1][1]==0 and televator[0][0]!=televator[1][0]:
                    continue
                elevator = set(televator)
                if validate_level(floors[floornext].union(elevator)) and validate_level(floors[floornow].difference(elevator)):
                    tmpfloors = deepcopy(floors)
                    tmpfloors[floornext].update(elevator)
                    for elev in elevator:
                        tmpfloors[floornow].discard(elev)
                    for numst,floorn,hist in history:
                        # check if we've been there before on a shorter path
                        if floorn==floornext and numst<=numsteps+1 and hist==tmpfloors:
                            break
                    else:
                        backlog.append((numsteps+1,floornext,tmpfloors))

        # now backlog contains all unvisited future paths
        while True:
            if len(backlog)==0:
                # out of future paths, we're done
                print('{} with cutoff {}'.format(minpath,cutoff))
                return
            numsteps,floornow,floors = backlog.pop()
            if numsteps==minpath:
                # no need to go on with this path
                continue
            if finalstate(floors):
                print('finalstate: {}'.format(floors))
                print('found a final state, numsteps={}'.format(numsteps))
                minpath = min(minpath,numsteps)
                continue
            if numsteps==cutoff:
                # next step would bee too long, don't go on with this path
                continue
            break
        # if we're here: we're on a possible path without an end so far --> continue
        history.append((numsteps,floornow,deepcopy(floors)))

day12.py

def day12(inps,cstart=0):
    regs = {k:0 for k in list('abcd')}
    regs['c'] = cstart
    instrs = inps.strip().split('\n')
    i = 0
    while True:
        if i<0 or i==len(instrs):
            print(i,len(instrs))
            print(regs)
            print(regs['a'])
            return
        inst = instrs[i]
        #print(inst)
        tlist = inst.split(' ')
        if tlist[0]=='inc':
            reg = tlist[1]
            regs[reg] += 1
        elif tlist[0]=='dec':
            reg = tlist[1]
            regs[reg] -= 1
        elif tlist[0]=='jnz':
            cond = tlist[1]
            delta = tlist[2]
            if cond in regs:
                cond = regs[cond]
            else:
                cond = int(cond)
            if delta in regs:
                delta = regs[delta]
            else:
                delta = int(delta)
            if cond!=0:
                i += delta
                continue
        elif tlist[0]=='cpy':
            val = tlist[1]
            reg = tlist[2]
            if val in regs:
                val = regs[val]
            else:
                val = int(val)
            regs[reg] = val
        else:
            print('weird input: {}'.format(inst))

        i += 1

day13.py

import numpy as np
from collections import defaultdict
from operator import itemgetter
from scipy import ndimage

def is_valid(x,y,c):
    if x>=0 and y>=0 and bin((x+y)**2+3*x+y+c).count('1')%2==0:
        return True
    return False

# see A* wikipedia
def day13_astar(c,finalpos):
    posnow = (1,1)
    pathlen = 0
    visited = []
    tovisit = []
    visited.append(posnow)
    tovisit.append(posnow)

    prevpos = {}
    gscore = defaultdict(lambda: 1e100)
    fscore = defaultdict(lambda: 1e100)
    gscore[posnow] = 0
    fscore[posnow] = heuristic_cost(posnow,finalpos)

    while len(tovisit)>0:
        posnow = sorted([(pos,fscore[pos]) for pos in tovisit],key=itemgetter(1))[0][0]
        if posnow==finalpos:
            finalpath = reconstruct_path(prevpos,posnow)
            print('found first path with stepnum {}: {}'.format(len(finalpath)-1,finalpath))
            return finalpath
        tovisit.remove(posnow)
        visited.append(posnow)

        xl,yl = posnow
        for xn,yn in (xl+1,yl),(xl-1,yl),(xl,yl+1),(xl,yl-1):
            if not is_valid(xn,yn,c) or (xn,yn) in visited:
                continue
            tentative_gscore = gscore[posnow] + 1
            if (xn,yn) not in tovisit:
                tovisit.append((xn,yn))
            elif tentative_gscore >= gscore[(xn,yn)]:
                # discard path
                continue
            # best path so far
            prevpos[(xn,yn)] = posnow
            gscore[(xn,yn)] = tentative_gscore
            fscore[(xn,yn)] = gscore[posnow] + heuristic_cost((xn,yn),finalpos)
    return 'A* failed :('

def heuristic_cost(posnow,finalpos):
    return abs(finalpos[0]-posnow[0]) + abs(finalpos[1]-posnow[1]) #~ straight line

def reconstruct_path(prevpos,posnow):
    allpath = [posnow]
    while posnow in prevpos:
        posnow = prevpos[posnow]
        allpath.append(posnow)
    return allpath


def day13b(c,stepnum):
    posnow = (1,1)
    maze = np.vectorize(lambda x,y,c=c:is_valid(x,y,c),otypes=[bool])(*np.ogrid[:stepnum+1,:stepnum+1])

    paths = np.zeros((stepnum+1,stepnum+1),dtype=bool)
    paths[posnow] = True
    for k in range(stepnum):
        paths = ndimage.binary_dilation(paths,mask=maze)
        print('number of sites after {} steps: {}'.format(k,paths.sum()))
    print('done with steplen {}.'.format(paths.sum()))