December 2016: Advent of Code Solutions

Peter Norvig

From Dec. 1 to Dec. 25, I will be solving the puzzles that appear each day at Advent of Code. The two-part puzzles are released at midnight EST (9:00PM my time); points are awarded to the first 100 people to solve the day's puzzles. The code shown here basically represents what I did to solve the problem, but slightly cleaned up:

  • On days when I start at 9:00PM and am competing against the clock, I take shortcuts. I use shorter names, because I'm not a fast typer. I run test cases in the Jupyter Notebook, but don't make them into assert statements. Even then, I'm not really competitive with the fastest solvers.
  • On days when I don't start until all the points are gone, what you see here is pretty much exactly what I did, or at least what I ended up with after correcting typos and other errors.

To understand the problems completely, you will have to read the full description in the "Day 1:" link in each day's section header.

Day 0: Getting Ready

On November 30th, I spent some time preparing:

  • I'll import my favorite modules and functions, so I don't have to do it each day.

  • From looking at last year's puzzles, I knew that there would be a data file on many days, so I defined Input to open the file (and for those using this notebook on a remote machine, to fetch the file from the web). My data files are at http://norvig.com/ipython/advent2016/.

  • From working on another puzzle site, Project Euler, I had built up a collection of utility functions, shown below:

In [1]:
# Python 3.x
import re
import numpy as np
import math
import urllib.request

from collections import Counter, defaultdict, namedtuple, deque
from functools   import lru_cache
from itertools   import permutations, combinations, chain, cycle, product, islice
from heapq       import heappop, heappush

def Input(day):
    "Open this day's input file."
    filename = 'advent2016/input{}.txt'.format(day)
    try:
        return open(filename)
    except FileNotFoundError:
        return urllib.request.urlopen("http://norvig.com/ipython/" + filename)

def transpose(matrix): return zip(*matrix)

def first(iterable): return next(iter(iterable))

def nth(iterable, n, default=None):
    "Returns the nth item of iterable, or a default value"
    return next(islice(iterable, n, None), default)

cat = ''.join

Ø   = frozenset() # Empty set
inf = float('inf')
BIG = 10 ** 999

def grep(pattern, lines):
    "Print lines that match pattern."
    for line in lines:
        if re.search(pattern, line):
            print(line)

def groupby(iterable, key=lambda it: it):
    "Return a dic whose keys are key(it) and whose values are all the elements of iterable with that key."
    dic = defaultdict(list)
    for it in iterable:
        dic[key(it)].append(it)
    return dic

def powerset(iterable):
    "Yield all subsets of items."
    items = list(iterable)
    for r in range(len(items)+1):
        for c in combinations(items, r):
            yield c

# 2-D points implemented using (x, y) tuples
def X(point): return point[0]
def Y(point): return point[1]

def neighbors4(point): 
    "The four neighbors (without diagonals)."
    x, y = point
    return ((x+1, y), (x-1, y), (x, y+1), (x, y-1))

def neighbors8(point): 
    "The eight neighbors (with diagonals)."
    x, y = point 
    return ((x+1, y), (x-1, y), (x, y+1), (x, y-1),
            (X+1, y+1), (x-1, y-1), (x+1, y-1), (x-1, y+1))

def cityblock_distance(p, q=(0, 0)): 
    "City block distance between two points."
    return abs(X(p) - X(q)) + abs(Y(p) - Y(q))

def euclidean_distance(p, q=(0, 0)): 
    "Euclidean (hypotenuse) distance between two points."
    return math.hypot(X(p) - X(q), Y(p) - Y(q))

def trace1(f):
    "Print a trace of the input and output of a function on one line."
    def traced_f(*args):
        result = f(*args)
        print('{}({}) = {}'.format(f.__name__, ', '.join(map(str, args)), result))
        return result
    return traced_f

def astar_search(start, h_func, moves_func):
    "Find a shortest sequence of states from start to a goal state (a state s with h_func(s) == 0)."
    frontier  = [(h_func(start), start)] # A priority queue, ordered by path length, f = g + h
    previous  = {start: None}  # start state has no previous state; other states will
    path_cost = {start: 0}     # The cost of the best path to a state.
    while frontier:
        (f, s) = heappop(frontier)
        if h_func(s) == 0:
            return Path(previous, s)
        for s2 in moves_func(s):
            new_cost = path_cost[s] + 1
            if s2 not in path_cost or new_cost < path_cost[s2]:
                heappush(frontier, (new_cost + h_func(s2), s2))
                path_cost[s2] = new_cost
                previous[s2] = s
    return dict(fail=True, front=len(frontier), prev=len(previous))
                
def Path(previous, s): 
    "Return a list of states that lead to state s, according to the previous dict."
    return ([] if (s is None) else Path(previous, previous[s]) + [s])

Some tests/examples for these:

In [2]:
assert tuple(transpose(((1, 2, 3), (4, 5, 6)))) == ((1, 4), (2, 5), (3, 6))
assert first('abc') == first(['a', 'b', 'c']) == 'a'
assert cat(['a', 'b', 'c']) == 'abc'
assert (groupby(['test', 'one', 'two', 'three', 'four'], key=len) 
        == {3: ['one', 'two'], 4: ['test', 'four'], 5: ['three']})

Day 1: No Time for a Taxicab

Given a sequence of moves, such as "R2, L3", which means turn 90° to the right and go forward 2 blocks, then turn 90° left and go 3 blocks, how many blocks do we end up away from the start? I make the following choices:

  • Intersection Points in the city grid will be represented as points on the complex plane.
  • Headings and turns can be represented by unit vectors in the complex plane: if you are heading east (along the positive real axis), then a left turn means you head north, and a right turn means you head south, and in general a left or right turn is a multiplication of your current heading by the North or South unit vectors, respectively.
  • Moves of the form "R53" will be parsed into a (turn, distance) pair, e.g. (South, 53).

To solve the puzzle with the function how_far(moves), I initialize the starting location as the origin and the starting heading as North, and follow the list of moves, updating the heading and location on each step, before returning the distance from the final location to the origin.

In [3]:
Point = complex             
N, S, E, W = 1j, -1j, 1, -1 # Unit vectors for headings

def distance(point): 
    "City block distance between point and the origin."
    return abs(point.real) + abs(point.imag)

def how_far(moves):
    "After following moves, how far away from the origin do we end up?"
    loc, heading = 0, N # Begin at origin, heading North
    for (turn, dist) in parse(moves):
        heading *= turn
        loc += heading * dist
    return distance(loc)

def parse(text):
    "Return a list of (turn, distance) pairs from text of form 'R2, L42, ...'"
    turns = dict(L=N, R=S)
    return [(turns[RL], int(d))
           for (RL, d) in re.findall(r'(R|L)(\d+)', text)]

assert distance(Point(3, 4)) == 7 # City block distance; Euclidean distance would be 5
assert parse('R2, L42') == [(S, 2), (N, 42)]
assert how_far("R2, L3") == 5
assert how_far("R2, R2, R2") == 2
assert how_far("R5, L5, R5, R3") == 12

how_far(Input(1).read())
Out[3]:
250.0

In part two of this puzzle, I have to find the first point that is visited twice. To support that, I keep track of the set of visited points. My first submission was wrong, because I didn't consider that the first point visited twice might be in the middle of a move, not the end, so I added the "for i" loop to iterate over the path of a move, one point at a time.

In [4]:
def visited_twice(text):
    "Following moves in text, find the first location we visit twice, and return the distance to it."
    loc, heading = 0, N # Begin at origin, heading North
    visited = {loc}
    for (turn, dist) in parse(text):
        heading *= turn
        for i in range(dist):
            loc += heading
            if loc in visited:
                return distance(loc)
            visited.add(loc)

assert visited_twice("R8, R4, R4, R8") == 4
assert visited_twice("R8, R4, R4, L8") == None
assert visited_twice("R8, R0, R1") == 7

visited_twice(Input(1).read())
Out[4]:
151.0

Day 2: Bathroom Security

Given instructions in the form of a sequence of Up/Down/Right/Left moves, such as 'ULL', output the keys on the bathroom lock keypad that the instructions correspond to. Start at the 5 key. Representation choices:

  • Keypad: a keypad is an array of strings: keypad[y][x] is a key. The character '.' indicates a location that is off the keypad; by surrounding the keys with a border of off characters, I avoid having to write code that checks to see if we hit the edge.
  • Key: A key is a character other than '.'.
  • Instructions: A sequence of lines of "UDRL" characters, where each line leads to the output of one key.
In [5]:
Keypad = str.split

keypad = Keypad("""
.....
.123.
.456.
.789.
.....
""")

assert keypad[2][2] == '5'

off = '.'

def decode(instructions, x=2, y=2):
    """Follow instructions, keeping track of x, y position, and
    yielding the key at the end of each line of instructions."""
    for line in instructions:
        for C in line:
            x, y = move(C, x, y)
        yield keypad[y][x]

def move(C, x, y):
    "Make the move corresponding to this character (L/R/U/D)"
    if   C == 'L' and keypad[y][x-1] is not off: x -= 1
    elif C == 'R' and keypad[y][x+1] is not off: x += 1
    elif C == 'U' and keypad[y-1][x] is not off: y -= 1
    elif C == 'D' and keypad[y+1][x] is not off: y += 1
    return x, y

assert move('U', 2, 2) == (2, 1)
assert move('U', 2, 1) == (2, 1)
assert cat(decode("ULL RRDDD LURDL UUUUD".split())) == '1985'

cat(decode(Input(2)))
Out[5]:
'97289'

In part two, we have to deal with a different keypad. I won't need any new functions, but I will need to redefine the global variable keypad, and provide decode with the new x and y coordinates of the 5 key:

In [6]:
keypad = Keypad("""
.......
...1...
..234..
.56789.
..ABC..
...D...
.......
""")

assert keypad[3][1] == '5'

cat(decode(Input(2), x=1, y=3))
Out[6]:
'9A7DC'

Day 3: Squares With Three Sides

From a file of numbers, three to a line, count the number that represent valid triangles; that is, numbers that satisfy the triangle inequality.

In [7]:
def is_triangle(sides):
    "Do these side lengths form a valid triangle?"
    x, y, z = sorted(sides)
    return z < x + y

def parse_ints(text): 
    "All the integers anywhere in text."
    return [int(x) for x in re.findall(r'\d+', text)]

triangles = [parse_ints(line) for line in Input(3)]

sum(map(is_triangle, triangles))
Out[7]:
983

In part two, the triangles are denoted not by three sides in the same line, but by three sides in the same column. For example, given the text:

101 301 501
102 302 502
103 303 503
201 401 601
202 402 602
203 403 603

The triangles are:

[101, 102, 103]
[301, 302, 303]
[501, 502, 503]
[201, 202, 203]
[401, 402, 403]
[601, 602, 603]

The task is still to count the number of valid triangles.

In [8]:
def invert(triangles):
    "Take each 3 lines and transpose them."
    for i in range(0, len(triangles), 3):
        yield from transpose(triangles[i:i+3])

sum(map(is_triangle, invert(triangles)))
Out[8]:
1836

Day 4: Security Through Obscurity

Given a list of room names like "aaaaa-bbb-z-y-x-123[abxyz]", consisting of an encrypted name followed by a dash, a sector ID, and a checksum in square brackets, compute the sum of the sectors of the valid rooms. A room is valid if the checksum is the five most common characters, in order (ties listed in alphabetical order).

In [9]:
def parse(line): 
    "Return (name, sector, checksum)."
    return re.match(r"(.+)-(\d+)\[([a-z]+)\]", line).groups()

def sector(line):
    "Return the sector number if valid, or 0 if not."
    name, sector, checksum = parse(line)
    return int(sector) if valid(name, checksum) else 0

def valid(name, checksum):
    "Determine if name is valid according to checksum."
    counts = Counter(name.replace('-', '')) 
    # Note: counts.most_common(5) doesn't work because it breaks ties arbitrarily.
    letters = sorted(counts, key=lambda L: (-counts[L], L))
    return checksum == cat(letters[:5])

assert  parse('aaaaa-bbb-z-y-x-123[abxyz]') == ('aaaaa-bbb-z-y-x', '123', 'abxyz')
assert sector('aaaaa-bbb-z-y-x-123[abxyz]') == 123
assert  valid('aaaaa-bbb-z-y-x', 'abxyz')

sum(map(sector, Input(4)))
Out[9]:
185371

Initially I had a bug: I forgot the name.replace('-', '') to make sure that we don't count hyphens.

In part two, we are asked "What is the sector ID of the room where North Pole objects are stored?" We are told that names are to be decrypted by a shift cipher, shifting each letter forward in the alphabet by the sector number.

In [10]:
def decrypt(line):
    "Decrypt the line (shift the name by sector; discard checksum)."
    name, sector, _ = parse(line)
    return shift(name, int(sector)) + ' ' + sector

def shift(text, N, alphabet='abcdefghijklmnopqrstuvwxyz'):
    "Shift cipher: letters in text rotate forward in alphabet by N places."
    N = N % len(alphabet)
    tr = str.maketrans(alphabet, alphabet[N:] + alphabet[:N])
    return text.translate(tr)

assert shift('hal', 1) == 'ibm'
assert shift('qzmt-zixmtkozy-ivhz', 343) == 'very-encrypted-name'

grep("north", map(decrypt, Input(4)))
northpole-object-storage 984

Day 5: How About a Nice Game of Chess?

This puzzle involves md5 hashes and byte encodings; it took me a while to look up how to do that. What I have to do, for integers starting at 0, is concatenate my door ID string with the integer, get the md5 hex hash, and if the first five digits of the hash are 0, collect the sixth digit; repeat until I have collected eight digits:

In [11]:
import hashlib

door = "ffykfhsq"

def find_password(door):
    "First 8 sixth digits of md5 hashes of door+i that begin with '00000'."
    password = ''
    for i in range(BIG):
        x = hashlib.md5(bytes(door + str(i), 'utf-8')).hexdigest()
        if x.startswith('00000'):
            password += x[5]
            print(i, x, password) # Just to see something happen
            if len(password) == 8: 
                return password

find_password(door)
515840 00000c6c3f533fe4f7b0cb6d851185a8 c
844745 000006a94bb1c9322cbb56dd8564e76e c6
2968550 000006c8c9090315b0fb38154a947c86 c66
4034943 00000970faef6424564944d5e8a59618 c669
5108969 000007b2e0e83dfeade14ebe09f9e6a7 c6697
5257971 00000bc5fdee6506b09262247ceb63f0 c6697b
5830668 0000051079ac6b44fc3a5266a1630d42 c6697b5
5833677 00000537192966c3ee924306195faede c6697b55
Out[11]:
'c6697b55'

In part two, the sixth digit of the hash that starts with '00000' is to be treated as an index that tells where in the password to place the seventh digit of the hash. For example, if the sixth digit is 2 and the seventh digit is a, then place a as the second digit of the final password. Do nothing if the sixth digit is not less than 8, or if a digit has already been placed at that index location.

In [12]:
def find_tougher_password(door):
    "For md5 hashes that begin with '00000', the seventh digit goes in the sixth-digit slot of the password."
    password = [off] * 8
    for i in range(BIG):
        x = hashlib.md5(bytes(door + str(i), 'utf-8')).hexdigest()
        if x.startswith('00000'):
            index = int(x[5], 16)
            if index < 8 and password[index] is off:
                password[index] = x[6]
                print(i, x, cat(password)) # Just to see something happen
            if off not in password:
                return cat(password)

%time find_tougher_password(door)
844745 000006a94bb1c9322cbb56dd8564e76e ......a.
5108969 000007b2e0e83dfeade14ebe09f9e6a7 ......ab
5830668 0000051079ac6b44fc3a5266a1630d42 .....1ab
6497076 0000008239d1bbf480ea541e9da1e494 8....1ab
8962195 00000351ce68ffb449644d4bfa4cee5d 8..5.1ab
23867827 000001c3c28bcbacf0f543a33548ef24 8c.5.1ab
24090051 000004d57fc545f376c09f27383b2c88 8c.5d1ab
26383109 0000023d12c49f028699d4679ba91780 8c35d1ab
CPU times: user 30.4 s, sys: 48.7 ms, total: 30.4 s
Wall time: 30.4 s
Out[12]:
'8c35d1ab'

Day 6: Signals and Noise

Given a file, where each line is a string of letters and every line has the same length, find the most common letter in each column. We can easily do this with the help of Counter.most_common. (Note I use Input(6).read().split() instead of just Input(6) so that I don't get the '\n' at the end of each line.)

In [13]:
counts = [Counter(col) for col in transpose(Input(6).read().split())]
cat(c.most_common(1)[0][0] for c in counts)
Out[13]:
'tsreykjj'

Just to make it clear, here's how we ask for the most common character (and its count) in the first column:

In [14]:
c = counts[0]
c.most_common(1)
Out[14]:
[('t', 24)]

And here is how we pick out the 't' character:

In [15]:
c.most_common(1)[0][0]
Out[15]:
't'

In part two, we ask for the least common character in each column. Easy-peasy:

In [16]:
cat(c.most_common()[-1][0] for c in counts)
Out[16]:
'hnfbujie'

Day 7: Internet Protocol Version 7

Given input lines of the form 'abcd[1234]fghi[56789]zz[0]z', count the number of lines that are a TLS, meaning they have an ABBA outside of square brackets, but no ABBA inside brackets. An ABBA is a 4-character subsequence where the first two letters are the same as the last two, but not all four are the same.

I assume brackets are in proper pairs, and are never nested. Then if I do a re.split on brackets, the even-indexed pieces of the split will be outside the brackets, and the odd-indexed will be inside. For example:

  • Given the line 'abcd[1234]fghi[56789]zz'
  • Split on brackets to get ['abcd', '1234', 'fghi', '56789', 'zz']
  • Outsides of brackets are 'abcd, fghi, zz' at indexes 0, 2, 4.
  • Insides of brackets are '1234, 56789' at indexes 1, 3.
In [17]:
def abba(text):           return any(a == d != b == c for (a, b, c, d) in subsequences(text, 4))
def subsequences(seq, n): return [seq[i:i+n] for i in range(len(seq) + 1 - n)]
def segment(line):        return re.split(r'\[|\]', line)
def outsides(segments):   return ', '.join(segments[0::2])
def insides(segments):    return ', '.join(segments[1::2])
def tls(segments):        return abba(outsides(segments)) and not abba(insides(segments))

sum(tls(segment(line)) for line in Input(7))
Out[17]:
110

Here are some tests:

In [18]:
assert abba('abba') and not abba('aaaa') and not abba('abbc')
assert subsequences('abcdefg', 4) == ['abcd', 'bcde', 'cdef', 'defg']
assert segment('abcd[1234]fghi[56789]zz') == ['abcd', '1234', 'fghi', '56789', 'zz']
assert outsides(['abcd', '1234', 'fghi', '56789', 'zz']) == 'abcd, fghi, zz'
assert insides(['abcd', '1234', 'fghi', '56789', 'zz']) == '1234, 56789'
assert tls(['abba', '123']) 
assert not tls(['bookkeeper', '123']) and not tls(['abba', 'xxyyx'])

In part two, we are asked to count the number of SSL lines: an SSL is when there is an ABA outside brackets, and the corresponding BAB inside brackets. An ABA is a three-character sequence with first and third (but not all three) the same. The corresponding BAB has the first character of the ABA surrounded by two copies of the second character.

In [19]:
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def ssl(segments): 
    "Is there an ABA outside brackets, and the corresponding BAB inside?"
    outs, ins = outsides(segments), insides(segments)
    return any(a+b+a in outs and b+a+b in ins
               for a in alphabet for b in alphabet if a != b)

sum(ssl(segment(line)) for line in Input(7))
Out[19]:
242

Day 8: Two-Factor Authentication

Given an array of pixels on a screen, follow commands that can:

  • Turn on a sub-rectangle of pixels in the upper left corner: rect 3x2
  • Rotate a row of pixels: rotate row y=0 by 4
  • Rotate a column of pixels: rotate column x=1 by 1

Then count the total number of 1 pixels in the screen.

I will use numpy two-dimensional arrays, mostly because of the screen[:, A] notation for getting at a column.

In [20]:
def interpret(cmd, screen):
    "Interpret this command to mutate screen."
    A, B = map(int, re.findall(r'(\d+)', cmd)) # There should be 2 numbers on every command line
    if cmd.startswith('rect'):
        screen[:B, :A] = 1
    elif cmd.startswith('rotate row'):
        screen[A, :] = rotate(screen[A, :], B)
    elif cmd.startswith('rotate col'):
        screen[:, A] = rotate(screen[:, A], B)

def rotate(items, n): return np.append(items[-n:], items[:-n])

def Screen(): return np.zeros((6, 50), dtype=np.int)

def run(commands, screen):
    "Do all the commands and return the final pixel array."
    for cmd in Input(8):
        interpret(cmd, screen)   
    return screen

screen = run(Input(8), Screen())
np.sum(screen)
Out[20]:
128

In part two, we are asked what message is on the screen. I won't try to do OCR; I'll just print the screen and look at the output:

In [21]:
for row in screen:
    print(cat(' @'[pixel] for pixel in row))
@@@@  @@   @@  @@@   @@  @@@  @  @ @   @ @@   @@  
@    @  @ @  @ @  @ @  @ @  @ @  @ @   @@  @ @  @ 
@@@  @  @ @  @ @  @ @    @  @ @@@@  @ @ @  @ @  @ 
@    @  @ @@@@ @@@  @ @@ @@@  @  @   @  @@@@ @  @ 
@    @  @ @  @ @ @  @  @ @    @  @   @  @  @ @  @ 
@@@@  @@  @  @ @  @  @@@ @    @  @   @  @  @  @@  

My answer is EOARGPHYAO.

Day 9: Explosives in Cyberspace

In this puzzle we are asked to decompress text of the form 'A(2x5)BCD', where the '(2x5)' means to make 5 copies of the next 2 characters, yielding 'ABCBCBCBCBCD'. We'll go through the input text, a character at a time, and if a re matcher detects a '(CxR)' pattern, process it; otherwise just collect the character. Note that the C characters that are to be repeated R times are taken literally; even if they contain an embedded '(1x5)'.

In [22]:
matcher = re.compile(r'[(](\d+)x(\d+)[)]').match # e.g. matches "(2x5)" as ('2', '5')

def decompress(s):
    "Decompress string s by interpreting '(2x5)' as making 5 copies of the next 2 characters."
    s = re.sub(r'\s', '', s) # "whitespace is ignored"
    result = []
    i = 0
    while i < len(s):
        m = matcher(s, i)
        if m:
            i = m.end()                # Advance to end of '(CxR)' match
            C, R = map(int, m.groups())
            result.append(s[i:i+C] * R) # Collect the C characters, repeated R times
            i += C                      # Advance past the C characters           
        else:
            result.append(s[i])         # Collect 1 regular character
            i += 1                      # Advance past it
    return cat(result)

len(decompress(Input(9).read()))
Out[22]:
138735

In part two, the copied characters are recursively decompressed. So, given '(8x2)(3x3)ABC', the (8x2) directive picks out the 8 characters '(3x3)ABC', which would then be decompressed to get 'ABCABCABC' and then the 'x2' is applied to get 'ABCABCABCABCABCABC'. However, for this part, we are not asked to actually build up the decompressed string, just to compute its length:

In [23]:
def decompress_length(s):
    """Decompress string s by interpreting '(2x5)' as making 5 copies of the next 2 characters.
    Recursively decompress these next 5 characters. Return the length of the decompressed string."""
    s = re.sub(r'\s', '', s) # "whitespace is ignored"
    length = 0
    i = 0
    while i < len(s):
        m = matcher(s, i)
        if m:
            C, R = map(int, m.groups())
            i = m.end(0)                              # Advance to end of '(CxR)'
            length += R * decompress_length(s[i:i+C]) # Decompress C chars and add to length
            i += C                                    # Advance past the C characters 
        else:
            length += 1                               # Add 1 regular character to length
            i += 1                                    # Advance past it
    return length

decompress_length(Input(9).read())
Out[23]:
11125026826

Here are some tests:

In [24]:
assert decompress('A(2x5)BCD') == 'ABCBCBCBCBCD'
assert decompress('ADVENT') == 'ADVENT'
assert decompress('(3x3)XYZ') == 'XYZXYZXYZ'
assert decompress('(5x4)(3x2)') == '(3x2)(3x2)(3x2)(3x2)'
assert decompress('X(8x2)(3x3)ABCY') == 'X(3x3)ABC(3x3)ABCY'
    
assert decompress_length('(8x2)(3x3)ABC') == 18
assert decompress_length('(25x3)(3x3)ABC(2x3)XY(5x2)PQRSTX(18x9)(3x2)TWO(5x7)SEVEN') == 445
assert decompress_length('(9x999)(2x999)xx') == 999 * 999 * 2 == 1996002

Day 10: Balance Bots

In this puzzle, a fleet of robots exchange some chips from input bins, passing them among themselves, and eventually putting them in output bins. We are given instructions like this:

value 5 goes to bot 2
bot 2 gives low to bot 1 and high to bot 0
value 3 goes to bot 1
bot 1 gives low to output 1 and high to bot 0
bot 0 gives low to output 2 and high to output 0
value 2 goes to bot 2

At first I thought I just had to interpret these instructions sequentially, but then I realized this is actually a data flow problem: whenever a bot acquires two chips, it passes the low number chip to one destination and the high number to another. So my representation choices are:

  • Bots and bins are represented as strings: 'bot 1' and 'output 2'.
  • Chips are represented by ints. (Not strings, because we want 9 to be less than 10).
  • Keep track of which bot currently has which chip(s) with a dict: has['bot 2'] = {5}
  • Keep track of what a bot does when it gets 2 chips with a dict: gives['bot 1'] = ('output 1', 'bot 0')
  • Pull this information from instructions with re.findall. The order of instructions is not important.
  • A function, give, moves a chip to a recipient, and if the recipient now has two chips, that triggers two more give calls.
In [25]:
def bots(instructions, goal={17, 61}):
    "Follow the data flow instructions, and if a bot gets the goal, print it."
    def give(giver, chip, recip):
        "Pass the chip from giver to recipient."
        has[giver].discard(chip)
        has[recip].add(chip)
        chips = has[recip]
        if chips == goal:
            print(recip, 'has', goal)
        if len(chips) == 2:
            give(recip, min(chips), gives[recip][0])
            give(recip, max(chips), gives[recip][1])
            
    has   = defaultdict(set)       # who has what
    gives = {giver: (dest1, dest2) # who will give what
             for (giver, dest1, dest2) 
             in re.findall(r'(bot \d+) gives low to (\w+ \d+) and high to (\w+ \d+)', instructions)}
    for (chip, recip) in re.findall(r'value (\d+) goes to (\w+ \d+)', instructions):
        give('input bin', int(chip), recip)
    return has

has = bots(Input(10).read())
bot 113 has {17, 61}

In part two, we are asked for the product of three output bins:

In [26]:
def out(i): return has['output ' + str(i)].pop()

out(0) * out(1) * out(2)
Out[26]:
12803

Day 11: Radioisotope Thermoelectric Generators

I knew my astar_search function would come in handy! To search for the shortest path to the goal, I need to provide an initial state of the world, a heuristic function (which estimates how many moves away from the goal a state is), and a function that says what states can be reached by moving the elevator up or down, and carrying some stuff. I will make these choices:

  • The state of the world is represented by the State type, which says what floor the elevator is on, and for a tuple of floors, the set of objects that are on the floor. We use frozensets so that a state will be hashable.
  • To figure out what moves can be made, consider both directions for the elevator (up or down); find all combinations of one or two items on each floor, and keep all of those moves, as long as they don't violate the constraint that we can't have a chip on the same floor as an RTG, unless the chip's own RTG is there.
  • To calculate the heuristic, add up the number of floors away each item is from the top floor and divide by two (since a move might carry two items).

Here is my input:

  • The first floor contains a thulium generator, a thulium-compatible microchip, a plutonium generator, and a strontium generator.
  • The second floor contains a plutonium-compatible microchip and a strontium-compatible microchip.
  • The third floor contains a promethium generator, a promethium-compatible microchip, a ruthenium generator, and a ruthenium-compatible microchip.
  • The fourth floor contains nothing relevant.
In [27]:
State = namedtuple('State', 'elevator, floors')

def fs(*items): return frozenset(items)

legal_floors = {0, 1, 2, 3}

def combos(things):
    "All subsets of 1 or 2 things."
    for s in chain(combinations(things, 1), combinations(things, 2)):
        yield fs(*s)

def moves(state):
    "All legal states that can be reached in one move from this state"
    L, floors = state
    for L2 in {L + 1, L - 1} & legal_floors:
        for stuff in combos(floors[L]):
            newfloors = tuple((s | stuff if i == L2 else 
                               s - stuff if i == state.elevator else 
                               s)
                              for (i, s) in enumerate(state.floors))
            if legal_floor(newfloors[L]) and legal_floor(newfloors[L2]):
                yield State(L2, newfloors)

def legal_floor(floor):
    "Floor is legal if no RTG, or every chip has its corresponding RTG."
    rtgs  = any(r.endswith('G') for r in floor)
    chips = [c for c in floor if c.endswith('M')]
    return not rtgs or all(generator_for(c) in floor for c in chips)

def generator_for(chip): return chip[0] + 'G'

def h_to_top(state):
    "An estimate of the number of moves needed to move everything to top."
    total = sum(len(floor) * i for (i, floor) in enumerate(reversed(state.floors)))
    return math.ceil(total / 2) # Can move two items in one move.

Let's try it out on an easy sample problem:

In [28]:
easy  = State(0, (fs('RG'), Ø, fs('RM'), Ø))

astar_search(easy, h_to_top, moves)
Out[28]:
[State(elevator=0, floors=(frozenset({'RG'}), frozenset(), frozenset({'RM'}), frozenset())),
 State(elevator=1, floors=(frozenset(), frozenset({'RG'}), frozenset({'RM'}), frozenset())),
 State(elevator=2, floors=(frozenset(), frozenset(), frozenset({'RG', 'RM'}), frozenset())),
 State(elevator=3, floors=(frozenset(), frozenset(), frozenset(), frozenset({'RG', 'RM'})))]

Now to solve the real problem. The answer we need is the number of elevator moves, which is one less than the path length (because the path includes the initial state).

In [29]:
part1 = State(0, (fs('TG', 'TM', 'PG', 'SG'), fs('PM', 'SM'), fs('pM', 'pG', 'RM', 'RG'), Ø))

%time path = astar_search(part1, h_to_top, moves)
len(path) - 1
CPU times: user 11.9 s, sys: 72.3 ms, total: 12 s
Wall time: 12 s
Out[29]:
31

In part two, we add four more items. Now, in part one there were 10 items, each of which could be on any of the 4 floors, so that's 410 ≈ 1 million states. Adding 4 more items yields ≈ 260 million states. We won't visit every state, but the run time could be around 100 times longer. I think I'll start this running, take the dog for a walk, and come back to see if it worked.

In [30]:
part2 = State(0, (fs('TG', 'TM', 'PG', 'SG', 'EG', 'EM', 'DG', 'DM'), 
                  fs('PM', 'SM'), fs('pM', 'pG', 'RM', 'RG'), Ø))

%time path = astar_search(part2, h_to_top, moves)
len(path) - 1
CPU times: user 14min 34s, sys: 11.4 s, total: 14min 46s
Wall time: 14min 52s
Out[30]:
55

It worked. And it took about 60 times longer. If I wanted to make it more efficient, I would focus on symmetry: when there are two symmetric moves, we only need to consider one. For example, in terms of finding the shortest path, it is the same to move, say {'TG', 'TM'} or {'EG', 'EM'} or {'DG', 'DM'} when they are all on the ground floor.

Day 12: Leonardo's Monorail

This one looks pretty easy: an interpreter for an assembly language with 4 op codes and 4 registers. We start by parsing a line like "cpy 1 a" into a tuple, ('cpy', 1, 'a'). Then to interpret the code, we set the program counter, pc, to 0, and interpret the instruction at code[0], and continue until the pc is past the end of the code:

In [31]:
def interpret(code, regs):
    "Execute instructions until pc goes off the end."
    def val(x): return (regs[x] if x in regs else x)
    pc = 0
    while pc < len(code):
        inst = code[pc]
        op, x, y = inst[0], inst[1], inst[-1]
        pc += 1
        if   op == 'cpy': regs[y] = val(x)
        elif op == 'inc': regs[x] += 1
        elif op == 'dec': regs[x] -= 1
        elif op == 'jnz' and val(x): pc += y - 1
    return regs

def parse(line): 
    "Split line into words, and convert to int where appropriate."
    return tuple((x if x.isalpha() else int(x)) 
                 for x in line.split())

code = [parse(line) for line in Input(12)]

interpret(code, dict(a=0, b=0, c=0, d=0))
Out[31]:
{'a': 318007, 'b': 196418, 'c': 0, 'd': 0}

I had a bug initially: in the jnz instruction, I had pc += y, to do the relative jump, but I forgot the -1 to offset the previous pc += 1.

In part two all we have to do is initialize register c to 1, not 0:

In [32]:
interpret(code, dict(a=0, b=0, c=1, d=0))
Out[32]:
{'a': 9227661, 'b': 5702887, 'c': 0, 'd': 0}

Day 13: A Maze of Twisty Little Cubicles

This is a maze-solving puzzle, where the maze is infinite in the non-negative (x, y) quarter-plane. Each space in that infinite grid is open or closed according to this computation:

Find x*x + 3*x + 2*x*y + y + y*y. Add the office designer's favorite number (your puzzle input). Find the binary representation of that sum; count the number of bits that are 1. If the number of bits that are 1 is even, it's an open space (denoted '.'). If the number of bits that are 1 is odd, it's a wall (denoted '#').

The problem is to find the length of the shortest path to the goal location, (31, 39). So I'll be using astar_search again.

In [33]:
favorite = 1362
goal = (31, 39)

def is_open(location):
    "Is this an open location?"
    x, y = location
    num = x*x + 3*x + 2*x*y + y + y*y + favorite
    return x >= 0 and y >= 0 and bin(num).count('1') % 2 == 0

def open_neighbors(location): return filter(is_open, neighbors4(location))

path = astar_search((1, 1), lambda p: cityblock_distance(p, goal), open_neighbors)
len(path) - 1
Out[33]:
82

Here we see a portion of the maze:

In [34]:
for y in range(30):
    print(cat(('.' if is_open((x, y)) else '#') for x in range(90)))
#..###.#...#..#....##.#...#....#....#..#.#.##...##.##.##.#####.#####.####.#.##..#..#.#.#.#
#.#..#.##.#######.#.#.####.##.###...##.#..#.###...#.#..#.##...#..###....##...##.#.##.#.#..
#..#.#.##.#....##...#..#.####.####...#..#..#..#.#...##......#.....######.#.#...##.##.#..##
##..##.##.#..#...###.#.....#.....##.######....#..###########.####..##....#...#......###..#
..#.##..########.#.#####...#..##.##.#.....##.###.#..#...##.###..#....####.#######.#.#.####
#............###.....#####.#####....#..##..#.###....#....#......#..#.##.#....##.###.###..#
###.##.####...#.##....#..#.#..#.##.####.##....####.###.#.##.##.###......###........#...#..
#.#..#.##.#.#.######..#.##..#.####..#.#######..###..##..#.##.#.##########.#####..#.#.#....
.###......#..#..#..####.###..#..#.#.##..#.......###...#....#....##...#......#####..#..##.#
.####..###.#.##.#.#...#..#.#.##.##......#..####..#.######.#####....#...##.......#.###..#.#
..######.###..###..##.#..###..##.#..##.####...#..##....##.#...#.###.######.######.#.##....
#..##..#.......###.#..###......#.#####..#.#...#...#..#....#...#...###....#.##..##.######..
.......##.##.#.....#....#.##.#.###..#.#.####..##.###########..##.#....##.....#..##..#..##.
#####.#.#.##...###.##...##.#..#..##.##...#######.....##..#######.#########.#.....##.#.#.#.
...##..##.#.###..#.###.#.##.#..#..##.#.....#..#####....#..##..##...#..##.#..##.#..###..##.
.#.###.#..#...#.##...#..#.#..#.......##..#.##..##.#.##.....#.....#..#...###..#......##.#..
##..#..#.######.#####.#..###..##.###.####...#.....#.#.##.#.##.#####...#.####..##.##.#..#.#
....##.#.##..#...##.#.##.####..#.###....#...#..###..#..#..#.#....#.##.#..#######.#..##.#..
##...#.......#......#.....#.###...########.#####.#..##..#..####..##.#.#...##..#..#...#..#.
###.#######.########.##.#.###.##...##..#.#.##..#.#########.##.###.##..###.....##.##.######
.##.#...###.##...#.##.#..#.....##....#.##......#.#..#........#..##.#......##.#.#.##.#...#.
.##.#.....#....#..#.##.#.####.#.#.##..#.#####.##.#..#..#####......###..##..#..##.#..#...##
...###.##.#.###.#.##.###...##..##.#.#......##.#..#.####.....##.##.#####.##..#.#..#####...#
.#..##.#..##..##...#.....#..##.#..#..##..#.##.#.##..#.#..##..#.#....#.#######.#.#....##.##
###....#...###.#...##.#####.#..#..##.#####..###.#.#.#####.###..#.##.##..#...###...##.##.##
.#.##.###.#..#.##.#.###..#..##.#####..........#.##...##.###.##.#.#....#.#.....######.#....
.####..##..#.#.##..#.....#...#.#..#####.##.##.##.#.....#.....#...#.##..###.##..#..#..#..##
...#.#...#..##..##...###.##.##..#..##.#.##.#...#.##..#.#.##.###..#.#.#..##.#.#..#.#.###...
#..##.##..#.###.#.####.#.##.###.#.....#....#.#.######..#.##.#.###..##.#....####..##.#####.
##..#######..#..#.....##.....#..######.##..#..#.....#.##.#..###.##..##.##.#..#.#..#..##.#.

In part two, we're asked how many locations we can reach in 50 moves or less. I'll grab the breadth_first search function from aima-python and modify it to find all the states within N steps:

In [35]:
def count_locations_within(start, N, neighbors):
    "Find how many locations are within N steps from start."
    frontier = deque([start]) # A queue of states
    distance = {start: 0}     # distance to start; also tracks all states seen
    while frontier:
        s = frontier.popleft()
        if distance[s] < N:
            for s2 in neighbors(s):
                if s2 not in distance:
                    frontier.append(s2)
                    distance[s2] = distance[s] + 1
    return len(distance)
                
count_locations_within((1, 1), 50, open_neighbors)
Out[35]:
138

Day 14: One-Time Pad

For this problem I again have to take the md5 hash of a string with increasing integers appended. The puzzle is to find the integer that yields the 64th key, where a hash is a key if:

  • It contains three of the same character in a row, like 777. Only consider the first such triplet in a hash.
  • One of the next 1000 hashes in the stream contains that same character five times in a row, like 77777.

I'll use lru_cache to avoid repeating the hashing of the next 1000.

In [36]:
salt = 'yjdafjpo'

@lru_cache(1001)
def hashval(i): return hashlib.md5(bytes(salt + str(i), 'utf-8')).hexdigest()

def is_key(i):
    "A key has a triple like '777', and then '77777' in one of the next thousand hashval(i)."
    three = re.search(r'(.)\1\1', hashval(i))
    if three:
        five = three.group(1) * 5
        return any(five in hashval(i+delta) for delta in range(1, 1001))
    
def nth_key(N): return nth(filter(is_key, range(BIG)), N)

nth_key(63)
Out[36]:
25427

In part two, we do key stretching, hashing an additional 2016 times. Eeverything else is the same:

In [37]:
@lru_cache(1001)
def hashval(i, stretch=2016): 
    h = hashlib.md5(bytes(salt + str(i), 'utf-8')).hexdigest()
    for i in range(stretch):
        h = hashlib.md5(bytes(h, 'utf-8')).hexdigest()
    return h

%time nth_key(63)
CPU times: user 36.4 s, sys: 314 ms, total: 36.7 s
Wall time: 37 s
Out[37]:
22045

This was my highest-scoring day, finishing #20 on part two.

Day 15: Timing is Everything

In this puzzle rotating discs with a slot in position 0 spin around. We are asked at what time will all the slots be lined up for a capsule to fall through the slots. The capsule takes one time unit to fall through each disc (not clear why it doesn't accelerate as it falls) and the discs spin one position per time unit.

In [38]:
def parse(inputs): 
    "Parse an input string into (disc#, positions, pos) triples."
    return [tuple(map(int, triple))
            for triple in re.findall(r'#(\d+).* (\d+) positions.* (\d+)[.]', inputs)]
    
discs = parse('''
Disc #1 has 13 positions; at time=0, it is at position 1.
Disc #2 has 19 positions; at time=0, it is at position 10.
Disc #3 has 3 positions; at time=0, it is at position 2.
Disc #4 has 7 positions; at time=0, it is at position 1.
Disc #5 has 5 positions; at time=0, it is at position 3.
Disc #6 has 17 positions; at time=0, it is at position 5.
''')

def falls(t, discs):
    "If we drop the capsule at time t, does it fall through all slots?"
    return all((pos + t + d) % positions == 0 
               for (d, positions, pos) in discs)

first(t for t in range(10**100) if falls(t, discs))
Out[38]:
376777
In [39]:
assert discs == [(1, 13, 1), (2, 19, 10), (3, 3, 2), (4, 7, 1), (5, 5, 3), (6, 17, 5)]
assert falls(5, [(1, 5, 4), (2, 2, 1)])

For part two, we add a 7th disc, with 11 positions, at position 0 at time 0:

In [40]:
discs.append((7, 11, 0))

first(t for t in range(7, 10**100, 19) if falls(t, discs))
Out[40]:
3903937

Day 16 Dragon Checksum

Given a bit string of the form '01...', expand it until it fills N bits, then report the checksum.

The rules for expanding:

  • Call the data you have at this point "a".
  • Make a copy of "a"; call this copy "b".
  • Reverse the order of the characters in "b".
  • In "b", replace all instances of 0 with 1 and all 1s with 0.
  • The resulting data is "a", then a single 0, then "b".
  • If this gives N or more bits, take the first N; otherwise repeat the process.

The rules for the checksum:

  • Assume the string is 110010110100
  • Consider each pair: 11, 00, 10, 11, 01, 00.
  • These are same, same, different, same, different, same, producing 110101.
  • The resulting string has length 6, which is even, so we repeat the process.
  • The pairs are 11 (same), 01 (different), 01 (different).
  • This produces the checksum 100, which has an odd length, so we stop.
In [41]:
def expand(a, N):
    "Expand seed `a` until it has length N."
    while len(a) < N:
        b = flip(a[::-1])
        a = a + '0' + b
    return a[:N]

def flip(text, table=str.maketrans('10', '01')): return text.translate(table)

def checksum(a):
    "Compute the checksum of `a` by comparing pairs until len is odd."
    while len(a) % 2 == 0:
        a = cat(('1' if a[i] == a[i+1] else '0') 
                for i in range(0, len(a), 2))
    return a
    
seed = '10010000000110000'

checksum(expand(seed, 272))
Out[41]:
'10010110010011110'

In part two, we take the same seed, but expand it to fill 35Mb of space:

In [42]:
%time checksum(expand(seed, 35651584)) 
CPU times: user 6.17 s, sys: 326 ms, total: 6.49 s
Wall time: 6.54 s
Out[42]:
'01101011101100011'

Day 17 Two Steps Forward

In this puzzle, we move through a 4x4 grid/maze, starting at position (0, 0) and trying to reach (3, 3), but the door from one position to the next is open or not depending on the hash of the path to get there (and my passcode), so doors open and lock themselves as you move around. I'll represent a state as a tuple of (position, path) and use astar_search to find the shortest path to the goal:

In [43]:
passcode = 'awrkjxxr'

openchars = 'bcdef'

grid = set((x, y) for x in range(4) for y in range(4))

start, goal = (0, 0), (3, 3)

def to_goal(state): 
    "City block distance between state's position and goal."
    pos, path = state
    return cityblock_distance(pos, goal)

directions = [(0, 'U', (0, -1)), (1, 'D', (0, 1)), (2, 'L', (-1, 0)), (3, 'R', (1, 0))]

def moves(state):
    "All states reachable from this state."
    (x, y), path = state
    hashx = hashlib.md5(bytes(passcode + path, 'utf-8')).hexdigest()
    for (i, p, (dx, dy)) in directions:
        pos2 = (x+dx, y+dy)
        if hashx[i] in openchars and pos2 in grid:
            yield (pos2, path+p)
    
astar_search((start, ''), to_goal, moves)
Out[43]:
[((0, 0), ''),
 ((1, 0), 'R'),
 ((1, 1), 'RD'),
 ((1, 0), 'RDU'),
 ((2, 0), 'RDUR'),
 ((3, 0), 'RDURR'),
 ((3, 1), 'RDURRD'),
 ((3, 2), 'RDURRDD'),
 ((2, 2), 'RDURRDDL'),
 ((3, 2), 'RDURRDDLR'),
 ((3, 3), 'RDURRDDLRD')]

In part two, we're asked for the longest path to the goal. We have to stop when we reach the goal, but we can make repeated visits to positions along the way, as long as the doors are open. I'll use a depth-first search, and keep track of the longest path length:

In [44]:
def longest_search(state, goal, moves):
    "Find the longest path to goal by depth-first search."
    longest = 0
    frontier = [state]
    while frontier:
        state = (pos, path) = frontier.pop()
        if pos == goal:
            longest = max(longest, len(path))
        else:
            frontier.extend(moves(state))
    return longest
            
longest_search((start, ''), goal, moves)
Out[44]:
526

Day 18 Like a Rogue

Here we have a cellular automaton, where a cell is a "trap" iff the 3 tiles in the row above, (one to the left above, directly above, and one to the right above) are one of the set {'^^.', '.^^', '^..', '..^'}; in other words if the first of the three is different from the last of the three. Given an initial row, we're asked for the count of all the safe tiles in the first 40 rows:

In [45]:
safe, trap = '.', '^'  
initial = '.^^.^^^..^.^..^.^^.^^^^.^^.^^...^..^...^^^..^^...^..^^^^^^..^.^^^..^.^^^^.^^^.^...^^^.^^.^^^.^.^^.^.'

def rows(n, row=initial):
    "The first n rows of tiles (given the initial row)."
    result = [row]
    for i in range(n-1):
        previous = safe + result[-1] + safe
        result.append(cat((trap if previous[i-1] != previous[i+1] else safe)
                          for i in range(1, len(previous) - 1)))
    return result

cat(rows(40)).count(safe)
Out[45]:
1951

Here I reproduce the simple example from the puzzle page:

In [46]:
rows(10, '.^^.^.^^^^')
Out[46]:
['.^^.^.^^^^',
 '^^^...^..^',
 '^.^^.^.^^.',
 '..^^...^^^',
 '.^^^^.^^.^',
 '^^..^.^^..',
 '^^^^..^^^.',
 '^..^^^^.^^',
 '.^^^..^.^^',
 '^^.^^^..^^']

In part two, we just have to run longer (but only a few seconds):

In [47]:
%time cat(rows(400000)).count(safe)
CPU times: user 7.92 s, sys: 90.6 ms, total: 8.01 s
Wall time: 8.08 s
Out[47]:
20002936

Day 19 An Elephant Named Joseph

Elves numbered 1 to N sit in a circle. Each Elf brings a present. Then, starting with the first Elf, they take turns stealing all the presents from the Elf to their left. An Elf with no presents is removed from the circle and does not take turns. So, if N = 5, then:

Elf 1 takes Elf 2's present.
Elf 2 has no presents and is skipped.
Elf 3 takes Elf 4's present.
Elf 4 has no presents and is also skipped.
Elf 5 takes Elf 1's two presents.
Neither Elf 1 nor Elf 2 have any presents, so both are skipped.
Elf 3 takes Elf 5's three presents, ending the game.

Who ends up with all the presents for general case of N? First, I note that I only need to keep track of the Elf number of the remaining elves, I don't need to count how many presents each one has. I see two representation choices:

  • Represent the circle of elves as a list of elf numbers, and everytime an Elf's presents are taken, delete the elf from the list. But this is O(N2), where N = 3 million, so this will be slow.
  • Represent the elves by a range, and instead of deleting elf-by-elf, instead limit the range round-by-round. If there is an even number of elves, then the elf in position 0 takes from position 1; position 2 takes from position 3, and so on, leaving only the even positions, which we denote elves[0::2]. If there is an odd number of elves, then it is the same, except that the last elf takes from the one in position 0, leaving elves[2::2]. Here's the code:
In [48]:
def Elves(N=3018458): return range(1, N+1) 

def winner(elves): return (elves[0] if (len(elves) == 1) else winner(one_round(elves)))

def one_round(elves): return (elves[0::2] if (len(elves) % 2 == 0) else elves[2::2])

assert winner(Elves(5)) == 3

winner(Elves())
Out[48]:
1842613

Here is a cool thing about representing the elves with a range: the total storage is O(1), not O(N). We never need to make a list of 3 million elements. Here we see a trace of the calls to one_round:

In [49]:
one_round = trace1(one_round)
winner(Elves())
one_round(range(1, 3018459)) = range(1, 3018459, 2)
one_round(range(1, 3018459, 2)) = range(5, 3018459, 4)
one_round(range(5, 3018459, 4)) = range(5, 3018461, 8)
one_round(range(5, 3018461, 8)) = range(21, 3018461, 16)
one_round(range(21, 3018461, 16)) = range(53, 3018469, 32)
one_round(range(53, 3018469, 32)) = range(53, 3018485, 64)
one_round(range(53, 3018485, 64)) = range(181, 3018485, 128)
one_round(range(181, 3018485, 128)) = range(437, 3018549, 256)
one_round(range(437, 3018549, 256)) = range(437, 3018677, 512)
one_round(range(437, 3018677, 512)) = range(1461, 3018677, 1024)
one_round(range(1461, 3018677, 1024)) = range(3509, 3019189, 2048)
one_round(range(3509, 3019189, 2048)) = range(7605, 3020213, 4096)
one_round(range(7605, 3020213, 4096)) = range(7605, 3022261, 8192)
one_round(range(7605, 3022261, 8192)) = range(7605, 3022261, 16384)
one_round(range(7605, 3022261, 16384)) = range(7605, 3022261, 32768)
one_round(range(7605, 3022261, 32768)) = range(7605, 3022261, 65536)
one_round(range(7605, 3022261, 65536)) = range(7605, 3022261, 131072)
one_round(range(7605, 3022261, 131072)) = range(269749, 3022261, 262144)
one_round(range(269749, 3022261, 262144)) = range(794037, 3153333, 524288)
one_round(range(794037, 3153333, 524288)) = range(1842613, 3415477, 1048576)
one_round(range(1842613, 3415477, 1048576)) = range(1842613, 3939765, 2097152)
Out[49]:
1842613

In part two the rules have changed, and each elf now takes from the elf across the circle. If there is an even number of elves, take from the elf directly across. Fo example, with 12 elves in a circle (like a clock face), Elf 1 takes from Elf 7. With an odd number of elves, directly across the circle falls between two elves, so choose the one that is earlier in the circle. For example, with 11 elves, Elf 2 takes from the Elf at position 7. Now who ends up with the presents?

This is tougher. I can't think of a simple range expression to describe who gets eliminated in a round. But I can represent the circle as a list and write a loop to eliminate elves one at a time. Again, if I did that with a del statement for each elf, it would be O(N2). But if instead I do one round at a time, replacing each eliminated elf with None in the list, and then filtering out the None values, then each round is only O(N), and sine there will be log(N) rounds, the whole thing is only O(N log(N)). That should be reasonably fast.

It is still tricky to know which elf to eliminate. If there are N elves, then the elf at position i should elminate the one at position i + N // 2. But we have to skip over the already-eliminated spaces; we can do that by keeping track of the number of eliminated elves in the variable eliminated. We also need to keep track of the current value of N, since it will change. And, since I don't want to deal with the headaches of wrapping around the circletconn, I will only deal with the first third of the elves: the first third all eliminate elves in the other two-thirds; if we went more than 1/3 of the way through, we would have to worry about wrapping around. (I had a bug here: at first I just iterated through N // 3. But when N is 2, that does no iteration at all, which is wrong; with two elves, the first should eliminate the other. It turns out it is safe to iterate through ceil(N /3) on each round.)

I will change the Elves function to return a list, not a range. The function winner stays the same. The one_round function is where the work goes:

In [50]:
def Elves(N=3018458): return list(range(1, N+1))

def one_round(elves):
    "The first third of elves eliminate ones across the circle from them; who is left?"
    N = len(elves)
    eliminated = 0
    for i in range(int(math.ceil(N / 3))):
        across = i + eliminated + (N // 2) 
        elves[across] = None
        N -= 1
        eliminated += 1
    return list(filter(None, elves[i+1:] + elves[:i+1]))

assert winner(Elves(5)) == 2

assert one_round(Elves(5)) == [4, 1, 2]

%time winner(Elves())
CPU times: user 1.26 s, sys: 74.7 ms, total: 1.33 s
Wall time: 1.34 s
Out[50]:
1424135

I was worried that this solution might take over a minute to run, but it turns out to only take about a second.

Day 20 Firewall Rules

We are given a list of blocked IP addresses, in the form "2365712272-2390766206", indicating the low and high numbers that are blocked by the firewall. I will parse the numbers into (low, high) pairs (and peek at the first 5 to see if I got it right):

In [51]:
pairs = sorted(map(parse_ints, Input(20)))

pairs[:5]
Out[51]:
[[0, 97802],
 [5682, 591077],
 [591078, 868213],
 [868214, 1216244],
 [1216245, 1730562]]

We are asked what is the lowest non-negative integer that is not blocked. I will generate all the unblocked numbers, and just ask for the first one. To find unblocked numbers, start a counter, i at zero, and increment it past the high value of each range, after yielding any numbers from i to the low value of the range:

In [52]:
def unblocked(pairs):
    "Find the lowest unblocked integer, given the sorted pairs of blocked numbers."
    i = 0
    for (low, high) in pairs:
        yield from range(i, low)
        i = max(i, high + 1)
            
first(unblocked(pairs))   
Out[52]:
4793564

In part two we are asked how many numbers are unblocked:

In [53]:
len(list(unblocked(pairs)))
Out[53]:
146

Day 21 Scrambled Letters and Hash

In this puzzle we are asked to take a password string, scramble it according to a list of instructions, and output the result, which will be a permutation of the original password. This is tedious because there are seven different instructions, but each one is pretty straightforward. I make the following choices:

  • I'll transform password (a str) into pw (a list), because lists are mutable and easier to manipulate. At the end I'll turn it back into a str.
  • I'll define functions rot and swap because they get used multiple times by different instructions.
  • I use the variables A, B to denote the first two integers anywhere in a line. If there is only one integer (or none), then B (and A) get as a default value 0. I accept ill-formed instructions, such as "move 1 to 4" instead of requiring "move position 1 to position 4".
In [54]:
def scramble(password, instructions=list(Input(21)), verbose=False):
    "Scramble the password according to the instructions."
    pw = list(password) 
    def rot(N):     pw[:]        = pw[-N:] + pw[:-N]
    def swap(A, B): pw[A], pw[B] = pw[B], pw[A]  
    for line in instructions:
        words = line.split()
        A, B, = parse_ints(line + ' 0 0')[:2]
        cmd = line.startswith
        if   cmd('swap position'): swap(A, B)
        elif cmd('swap letter'):   swap(pw.index(words[2]), pw.index(words[5]))
        elif cmd('rotate right'):  rot(A)
        elif cmd('rotate left'):   rot(-A)
        elif cmd('reverse'):       pw[A:B+1] = pw[A:B+1][::-1]
        elif cmd('move'):          pw[A:A+1], pw[B:B] = [], pw[A:A+1]
        elif cmd('rotate based'):
            i = pw.index(words[6])
            rot((i + 1 + (i >= 4)) % len(pw))
        if verbose: 
            print(line + ': ' + cat(pw))
    return cat(pw)

scramble('abcdefgh')
Out[54]:
'gcedfahb'

When I ran the first version of this code the answer I got was incorrect, and I couldn't see where I went wrong, so I implemented the test case from the problem description and inspected the results line by line.

In [55]:
test = '''swap position 4 with position 0
swap letter d with letter b
reverse positions 0 through 4
rotate left 1 step
move position 1 to position 4
move position 3 to position 0
rotate based on position of letter b
rotate based on position of letter d'''.splitlines()

scramble('abcde', test, verbose=True)
swap position 4 with position 0: ebcda
swap letter d with letter b: edcba
reverse positions 0 through 4: abcde
rotate left 1 step: bcdea
move position 1 to position 4: bdeac
move position 3 to position 0: abdec
rotate based on position of letter b: ecabd
rotate based on position of letter d: decab
Out[55]:
'decab'

That was enough to show me that I had two bugs (which are fixed above):

  • For "reverse", I thought "positions 0 through 4" meant [0:4], when actually it means [0:5].
  • For "rotate based", in the case where the rotation is longer than the password, I need to take the modulo of the password length.

For part two, the task is to find the password that, when scrambled, yields 'fbgdceah'. I think the puzzle designer was trying to tempt solvers into implementing an unscramble function, which would be another 20 or 30 lines of code. Fortunately, I was too lazy to go down that path. I realized there are only 40 thousand permutations of an 8-character password, so we can just brure force them all (which would be infeasible with a 20-character password):

In [56]:
{cat(p) for p in permutations('fbgdceah') 
 if scramble(p) == 'fbgdceah'}
Out[56]:
{'hegbdcfa'}

Day 22 Grid Computing

We are given a description of files across multiple devices, like this:

[email protected]# df -h
Filesystem              Size  Used  Avail  Use%
/dev/grid/node-x0-y0     92T   70T    22T   76%
/dev/grid/node-x0-y1     86T   65T    21T   75%

For part one, we are asked how many pairs of nodes can viably make a transfer of data. The pair (A, B) is viable if

  • Node A is not empty (its Used is not zero).
  • Nodes A and B are not the same node.
  • The data on node A (its Used) would fit on node B (its Avail).

I'll represent a node as a namedtuple of six integers; the rest is easy:

In [57]:
Node = namedtuple('Node', 'x, y, size, used, avail, pct')

nodes = [Node(*parse_ints(line)) for line in Input(22) if line.startswith('/dev')]

def viable(A, B): return A != B and 0 < A.used < B.avail

sum(viable(A, B) for A in nodes for B in nodes)
Out[57]:
903

In part two, we are asked to move data from the node in the upper right (the one with maximum x value and 0 y value) to the upper left (x=0, y=0). At first I worried about all sorts of complications: could we split the data into two or more pieces, copying different pieces into different nodes, and then recombining them? I spent many minutes thinking about these complications. Eventually, after a more careful reading of the rules, I decided such moves were not allowed, and the answer had to just involve moving the empty square around. So to proceed, we need to find the initial position of the empty node, and the maximum x value, so we know where the data is:

In [58]:
empty = first(node for node in nodes if node.used == 0)
maxx  = max(node.x for node in nodes)

empty, maxx
Out[58]:
(Node(x=35, y=21, size=91, used=0, avail=91, pct=0), 37)

I will also define a dict of {(x, y): node} entries to define the grid, so that I can find the neighbors of a node:

In [59]:
grid = {(node.x, node.y): node 
        for node in nodes}

Let's make sure the nodes look reasonable:

In [60]:
nodes[:5]
Out[60]:
[Node(x=0, y=0, size=92, used=70, avail=22, pct=76),
 Node(x=0, y=1, size=86, used=65, avail=21, pct=75),
 Node(x=0, y=2, size=88, used=73, avail=15, pct=82),
 Node(x=0, y=3, size=91, used=67, avail=24, pct=73),
 Node(x=0, y=4, size=87, used=70, avail=17, pct=80)]

An astar_search seems appropriate. Each state of the search keeps track of the position of the data we are trying to get, and the position of the currently empty node. The heuristic is the city block distance of the data to the origin:

In [61]:
State = namedtuple('State', 'datapos, emptypos')

def distance(state): return cityblock_distance(state.datapos)

def moves(state):
    "Try moving any neighbor we can into the empty position."
    for pos in neighbors4(state.emptypos):
        if pos in grid:
            # Try to move contents of `node` at pos into `empty` at emptypos
            node, empty = grid[pos], grid[state.emptypos]
            if node.used < empty.size:
                newdatapos = (state.emptypos if pos == state.datapos else state.datapos)
                yield State(newdatapos, pos)
                        
path = astar_search(State((maxx, 0), (empty.x, empty.y)), distance, moves)
len(path) - 1
Out[61]:
215

Day 23 Safe Cracking

This day's puzzle is just like Day 12, except there is one more instruction, tgl. I made four mistakes in the process of coding this up:

  • At first I didn't read the part that says register 'a' should initially be 7.
  • I wasn't sure exactly what constitutes an invalid instruction; it took me a few tries to get that right: the only thing that is invalid is a cpy that does not copy into a register.
  • I forgot to subtract one from the pc (again) in the tgl instruction.
  • I forgot that I had parse return instructions as immutable tuples; I had to change that to mutable lists.
In [62]:
def interpret(code, regs):
    "Execute instructions until pc goes off the end."
    def val(x): return (regs[x] if x in regs else x)
    pc = 0
    while 0 <= pc < len(code):
        inst = code[pc]
        op, x, y = inst[0], inst[1], inst[-1]
        pc += 1
        if   op == 'cpy' and y in regs: regs[y] = val(x)
        elif op == 'inc':               regs[x] += 1                  
        elif op == 'dec':               regs[x] -= 1                  
        elif op == 'jnz' and val(x):    pc += val(y) - 1   
        elif op == 'tgl':               toggle(code, pc - 1 + val(x))
    return regs

def toggle(code, i):
    "Toggle the instruction at location i."
    if 0 <= i < len(code): 
        inst = code[i]
        inst[0] = ('dec' if inst[0] == 'inc' else 
                   'inc' if len(inst) == 2 else
                   'cpy' if inst[0] == 'jnz' else 
                   'jnz')

def parse(line): 
    "Split line into words, and convert to int where appropriate."
    return [(x if x.isalpha() else int(x)) 
            for x in line.split()]
In [63]:
text = '''
cpy a b
dec b
cpy a d
cpy 0 a
cpy b c
inc a
dec c
jnz c -2
dec d
jnz d -5
dec b
cpy b c
cpy c d
dec d
inc c
jnz d -2
tgl c
cpy -16 c
jnz 1 c
cpy 84 c
jnz 75 d
inc a
inc d
jnz d -2
inc c
jnz c -5
'''.strip()

code = [parse(line) for line in text.splitlines()]

regs = dict(a=7, b=0, c=0, d=0)

interpret(code, regs)
Out[63]:
{'a': 11340, 'b': 1, 'c': 0, 'd': 0}

In part two, we are told to run the same computation, but with register a set to 12. We are also warned that this will take a long time, and we might consider implementing a multiply instruction, but I was too lazy to make sense of the assembly code, and just let my interpreter run to completion, even if it takes a while.

In [64]:
code = [parse(line) for line in text.splitlines()]

regs = dict(a=12, b=0, c=0, d=0)

%time interpret(code, regs)
CPU times: user 25min 21s, sys: 5.37 s, total: 25min 27s
Wall time: 25min 31s
Out[64]:
{'a': 479007900, 'b': 1, 'c': 0, 'd': 0}

Well, it completed, and gave me the right answer. But I feel like the intent of Advent of Code is like Project Euler: all code should run in about a minute or less. So I don't think this counts as a "real" solution.

Day 24 Air Duct Spelunking

This is another maze-solving problem; it should be easy for my astar_search. First the maze:

In [65]:
maze = tuple(Input(24))

The tricky part is that we have to visit all the digits in the maze, starting at 0, and not necessarily going in order. How many digits are there?

In [66]:
set(cat(maze))
Out[66]:
{'\n', '#', '.', '0', '1', '2', '3', '4', '5', '6', '7'}

OK, there are 8 digits. What is the start square (the square that currently holds a '0')?

In [67]:
zero = first((x, y) for y, row in enumerate(maze) for x, c in enumerate(row) if c == '0')
zero
Out[67]:
(33, 11)

Now I'm ready to go. The state of the search will include the x, y position, and also the digits visited so far, which I can represent as a sorted string (a frozenset would also work):

In [68]:
def h(state):
    "Heuristic: the number of digits not yet visited."
    _, visited = state
    return 8 - len(visited) # Note: 8 == len('01234567')
    
def moves(state):
    "Move to any neighboring square that is not a wall. Track the digits visited."
    pos, visited = state
    for x1, y1 in neighbors4(pos):
        c = maze[y1][x1]
        if c != '#':
            visited1 = (visited if c in visited or c == '.' else cat(sorted(visited + c)))
            yield (x1, y1), visited1

path = astar_search((zero, '0'), h, moves)
len(path) - 1
Out[68]:
448

In part two we need to get the robot back to the start square. I'll do that by creating a new heuristic function that still requires us to collect all the digits, and also measures the distance back to the start (zero) square.

In [69]:
def h2(state):
    "Heuristic: the number of digits not yet visited, plus the distance back to start."
    pos, visited = state
    return 8 - len(visited) + cityblock_distance(pos, zero)

path2 = astar_search((zero, '0'), h2, moves)
len(path2) - 1
Out[69]:
672

Day 25 Clock Signal

This is another assembly language interpreter puzzle. This time there is one more instruction, out, which transmits a signal. We are asked to find the lowest positive integer value for register a that causes the program to output an infinite series of 0, 1, 0, 1, 0, 1, ... signals. Dealing with infinity is difficult, so I'll approximate that by asking: what is the lowest value for register a that causes the program to output at least 100 elements in the 0, 1, 0, 1, 0, 1, ... series, within the first million instructions executed?

To do that, I'll change interpret to be a generator that yields signals, and change it to take an argument saying the number of steps to execute before halting:

In [70]:
def interpret(code, regs, steps=BIG):
    "Execute instructions until pc goes off the end, or until we execute the given number of steps."
    def val(x): return (regs[x] if x in regs else x)
    pc = 0
    for _ in range(steps):
        if not (0 <= pc < len(code)):
            return
        inst = code[pc]
        op, x, y = inst[0], inst[1], inst[-1]
        pc += 1
        if   op == 'cpy' and y in regs: regs[y] = val(x)
        elif op == 'inc':               regs[x] += 1                  
        elif op == 'dec':               regs[x] -= 1                  
        elif op == 'jnz' and val(x):    pc += val(y) - 1   
        elif op == 'tgl':               toggle(code, pc - 1 + val(x))
        elif op == 'out':               yield val(x)

Here is my program, and the function repeats, which returns True if the code repeats with a given value of the register a. Then all we need to do is iterate through integer values for register a until we find one that repeats:

In [71]:
text = '''
cpy a d
cpy 4 c
cpy 633 b
inc d
dec b
jnz b -2
dec c
jnz c -5
cpy d a
jnz 0 0
cpy a b
cpy 0 a
cpy 2 c
jnz b 2
jnz 1 6
dec b
dec c
jnz c -4
inc a
jnz 1 -7
cpy 2 b
jnz c 2
jnz 1 4
dec b
dec c
jnz 1 -4
jnz 0 0
out b
jnz a -19
jnz 1 -21
'''.strip()

code = [parse(line) for line in text.splitlines()]

def repeats(a, code, steps=10**6, minsignals=100):
    "Does this value for register a cause code to repeat `out` signals of 0, 1, 0, 1, ...?"
    signals = interpret(code, dict(a=a, b=0, c=0, d=0), steps)
    expecteds = cycle((0, 1))
    for (i, (signal, expected)) in enumerate(zip(signals, expecteds)):
        if signal != expected:
            return False
    # We'll say "yes" if the code outputs at least a minimum number of 0, 1, ... signals, and nothing else.
    return i >= minsignals
    
first(a for a in range(1, BIG) if repeats(a, code))
Out[71]:
198

That's all folks! Thank you Eric Wastl, that was fun!