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 PST); 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:
assert statements. Even then, I'm not really competitive with the fastest solvers.To understand the problems completely, you will have to read the full description in the "Day 1:" link in each day's section header.
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 the function 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:
# 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:
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']})
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:
North or South unit vectors, respectively."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.
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())
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.
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())
151.0
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[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.'.'."UDRL" characters, where each line leads to the output of one key.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)))
'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:
keypad = Keypad("""
.......
...1...
..234..
.56789.
..ABC..
...D...
.......
""")
assert keypad[3][1] == '5'
cat(decode(Input(2), x=1, y=3))
'9A7DC'
From a file of numbers, three to a line, count the number that represent valid triangles; that is, numbers that satisfy the triangle inequality.
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))
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.
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)))
1836
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).
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)))
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.
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
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:
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
'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.
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
'8c35d1ab'
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.)
counts = [Counter(col) for col in transpose(Input(6).read().split())]
cat(c.most_common(1)[0][0] for c in counts)
'tsreykjj'
Just to make it clear, here's how we ask for the most common character (and its count) in the first column:
c = counts[0]
c.most_common(1)
[('t', 24)]
And here is how we pick out the 't' character:
c.most_common(1)[0][0]
't'
In part two, we ask for the least common character in each column. Easy-peasy:
cat(c.most_common()[-1][0] for c in counts)
'hnfbujie'
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:
'abcd[1234]fghi[56789]zz'['abcd', '1234', 'fghi', '56789', 'zz']'abcd, fghi, zz' at indexes 0, 2, 4.'1234, 56789' at indexes 1, 3.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))
110
Here are some tests:
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.
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))
242
Given an array of pixels on a screen, follow commands that can:
rect 3x2rotate row y=0 by 4rotate column x=1 by 1Then 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.
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 commands:
interpret(cmd, screen)
return screen
screen = run(Input(8), Screen())
np.sum(screen)
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:
for row in screen:
print(cat(' @'[pixel] for pixel in row))
@@@@ @@ @@ @@@ @@ @@@ @ @ @ @ @@ @@ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @@ @ @ @ @@@ @ @ @ @ @ @ @ @ @ @@@@ @ @ @ @ @ @ @ @ @ @@@@ @@@ @ @@ @@@ @ @ @ @@@@ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @@@@ @@ @ @ @ @ @@@ @ @ @ @ @ @ @@
My answer is EOARGPHYAO.
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)'.
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()))
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:
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())
11125026826
Here are some tests:
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
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:
'bot 1' and 'output 2'.has['bot 2'] = {5}gives['bot 1'] = ('output 1', 'bot 0')re.findall. The order of instructions is not important.give, moves a chip to a recipient, and if the recipient now has two chips, that triggers two more give calls.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:
def out(i): return has['output ' + str(i)].pop()
out(0) * out(1) * out(2)
12803
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:
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.Here is my input:
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:
easy = State(0, (fs('RG'), Ø, fs('RM'), Ø))
astar_search(easy, h_to_top, moves)
[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).
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
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.
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
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.
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:
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))
{'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:
interpret(code, dict(a=0, b=0, c=1, d=0))
{'a': 9227661, 'b': 5702887, 'c': 0, 'd': 0}
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.
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
82
Here we see a portion of the maze:
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:
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)
138
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:
I'll use lru_cache to avoid repeating the hashing of the next 1000.
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)
25427
In part two, we do key stretching, hashing an additional 2016 times. Eeverything else is the same:
@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
22045
This was my highest-scoring day, finishing #20 on part two.
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.
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(BIG) if falls(t, discs))
376777
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. I coud go through all the possible times, just as in part one, but I see a way to get a 19-fold speedup: Disc #2 is the largest, with 19 positions, so we only need consider every 19 values of t. But what is the first one to consider? Disc @2 starts at position 10, so to get back to position 0, we have to release at t=7, because 10 + 2 + 7 = 19 = 0 mod 19. So we will iterate t over range(7, BIG, 19):
discs.append((7, 11, 0))
first(t for t in range(7, BIG, 19) if falls(t, discs))
3903937
Given a bit string of the form '01...', expand it until it fills N bits, then report the checksum.
The rules for expanding:
The rules for the checksum:
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))
'10010110010011110'
In part two, we take the same seed, but expand it to fill 35Mb of space:
%time checksum(expand(seed, 35651584))
CPU times: user 6.17 s, sys: 326 ms, total: 6.49 s Wall time: 6.54 s
'01101011101100011'
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:
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)
[((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:
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)
526
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:
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)
1951
Here I reproduce the simple example from the puzzle page:
rows(10, '.^^.^.^^^^')
['.^^.^.^^^^', '^^^...^..^', '^.^^.^.^^.', '..^^...^^^', '.^^^^.^^.^', '^^..^.^^..', '^^^^..^^^.', '^..^^^^.^^', '.^^^..^.^^', '^^.^^^..^^']
In part two, we just have to run longer (but only a few seconds):
%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
20002936
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:
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:
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())
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:
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)
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:
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
1424135
I was worried that this solution might take over a minute to run, but it turns out to only take about a second.
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 sort them by the low number first (and peek at the first 5 to see if I got it right):
pairs = sorted(map(parse_ints, Input(20)))
pairs[:5]
[[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. (Why do it that way? Because it feels like unblocked is the fundamental issue of the problem, and we already have a function to compute first; there's no need for a first_unblocked function that conflates two ideas.) 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:
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))
4793564
In part two we are asked how many numbers are unblocked:
len(list(unblocked(pairs)))
146
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:
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.rot and swap because they get used multiple times by different instructions.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".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')
'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.
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
'decab'
That was enough to show me that I had two bugs (which are fixed above):
"reverse", I thought "positions 0 through 4" meant [0:4], when actually it means [0:5]."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 brute force them all (which would be infeasible with a 20-character password):
{cat(p) for p in permutations('fbgdceah')
if scramble(p) == 'fbgdceah'}
{'hegbdcfa'}
We are given a description of files across a grid computing cluster, like this:
root@ebhq-gridcenter# 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
I'll represent a node as a namedtuple of six integers; the rest is easy:
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)
903
That worked, but let's make sure the nodes look reasonable:
nodes[:5]
[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)]
In part two, we are asked to move data from the node in the upper right (the one with maximum x value and y=0) 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:
empty = first(node for node in nodes if node.used == 0)
maxx = max(node.x for node in nodes)
empty, maxx
(Node(x=35, y=21, size=91, used=0, avail=91, pct=0), 37)
I will also define the grid as a dict of {(x, y): node} entries (which will enable me to find neighbors of a node):
grid = {(node.x, node.y): node
for node in nodes}
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:
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
215
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:
'a' should initially be 7.the only thing that is invalid is a cpy that does not copy into a register.
pc (again!) in the tgl instruction.parse return instructions as immutable tuples; I had to change that to mutable lists.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()]
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)
{'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.
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
{'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.
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?
set(cat(maze))
{'\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')?
zero = first((x, y) for y, row in enumerate(maze) for x, c in enumerate(row) if c == '0')
zero
(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):
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
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.
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
672
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:
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:
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))
198
That's all folks! Thank you Eric Wastl, that was fun!