========================================
The elves are running low on wrapping paper, and so they need to submit an order for more. They have a list of the dimensions (length l, width w, and height h) of each present, and only want to order exactly as much as they need. Fortunately, every present is a box (a perfect right rectangular prism), which makes calculating the required wrapping paper for each gift a little easier: find the surface area of the box, which is 2lw
The elves are also running low on ribbon. Ribbon is all the same width, so they only have to worry about the length they need to order, which they would again like to be exact. They have a list of the dimensions (length l, width w, and height h) of each present, and only want to order exactly as much as they need. Fortunately, every present is a box (a perfect right rectangular prism). The ribbon required to wrap a present is the shortest distance around its sides, or the smallest perimeter of any one face. Each present also requires a bow made out of ribbon as well; the feet of ribbon required for the perfect bow is equal to the cubic feet of volume of the present. Don't ask how they tie the bow, though; they'll never tell. For example:
In [3]:
#problem 2 part 1 & 2
with open("problem2.txt", "r") as ins:
array = []
for line in ins:
array.append(line)
big_surface = 0
all_ribbons =0
for wl in array:
wl = wl.split('x')
wl = [int(x) for x in wl]
surface = 2 * wl[0] * wl[1] + 2 * wl[1] * wl[2] + 2 * wl[2] * wl[0]
wl = sorted(wl)
small_side = wl[0] * wl[1]
bow = wl[0] * wl[1] * wl[2]
ribbons = wl[0] + wl[0] + wl[1] + wl[1]
big_surface = big_surface + surface + small_side
all_ribbons = all_ribbons + bow + ribbons
print('Whole surface is:', big_surface, 'elves would also need this much of ribbon:', all_ribbons)
=====================
Santa was hoping for a white Christmas, but his weather machine's "snow" function is powered by stars, and he's fresh out! To save Christmas, he needs you to collect fifty stars by December 25th.
Collect stars by helping Santa solve puzzles. Two puzzles will be made available on each day in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!
Here's an easy puzzle to warm you up.
Santa is trying to deliver presents in a large apartment building, but he can't find the right floor - the directions he got are a little confusing. He starts on the ground floor (floor 0) and then follows the instructions one character at a time.
An opening parenthesis, (, means he should go up one floor, and a closing parenthesis, ), means he should go down one floor.
The apartment building is very tall, and the basement is very deep; he will never find the top or bottom floors.
For example:
(()) and ()() both result in floor 0.
((( and (()(()( both result in floor 3.
))((((( also results in floor 3.
()) and ))( both result in floor -1 (the first basement level).
))) and )())()) both result in floor -3.
To what floor do the instructions take Santa?
Your puzzle answer was 280. --- Part Two ---
Now, given the same instructions, find the position of the first character that causes him to enter the basement (floor -1). The first character in the instructions has position 1, the second character has position 2, and so on.
For example:
) causes him to enter the basement at character position 1.
()()) causes him to enter the basement at character position 5.
What is the position of the character that causes Santa to first enter the basement?
Your puzzle answer was 1797.
In [33]:
#problem 1 part 2 # find the instruction first leading into basement
floor = 0
with open('problem1.txt', 'r') as ins:
for i, char in enumerate(ins.read(), 1):
if char == '(':
floor += 1
else:
floor -= 1
if floor < 0:
break
print(i)
=============================================
Santa is delivering presents to an infinite two-dimensional grid of houses. He begins by delivering a present to the house at his starting location, and then an elf at the North Pole calls him via radio and tells him where to move next. Moves are always exactly one house to the north (^), south (v), east (>), or west (<). After each move, he delivers another present to the house at his new location. However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. For example:
Last year, Santa delivered presents to an infinite two-dimensional grid of houses. He began by delivering a present to the house at his starting location, and then an elf at the North Pole called him via radio and told him where to move next. Moves are always exactly one house to the north (^), south (v), east (>), or west (<). After each move, he delivered another present to the house at his new location. However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. This year, to speed up the process, Santa creates a robot version of himself, Robo-Santa, to deliver presents with him. Santa and Robo-Santa start at the same location (delivering two presents to the same starting house), then take turns moving based on instructions from the elf, who is eggnoggedly reading from the same script as the previous year. For example:
In [ ]:
#problem 3 part 2
# The number of people (or robots) delivering
n = 2
# Add a set of coordinates for each person.
coords = [(0,0)] * n
# Keep track of the houses we've visited
houses = set([(0,0)])
with open('prob3.txt') as f:
chars = f.read()
# 'Partition' the list into sets of instructions of length n
chunks = [chars[i:i+n] for i in range(0, len(chars), n)]
# For each set of instructions
for chunk in chunks:
for i, instruction in enumerate(chunk):
# Get the current coordinates for each person for each instruction
x, y = coords[i]
# Adjust position
if instruction == '^':
y -= 1
elif instruction == '>':
x += 1
elif instruction == 'v':
y += 1
elif instruction == '<':
x -= 1
# Add new house
houses.add((x,y))
# Store position for next round
coords[i] = (x, y)
# Count up all the houses.
print(len(houses))
=============================================
Santa needs help figuring out which strings in his text file are naughty or nice. A nice string is one with all of the following properties:
Realizing the error of his ways, Santa has switched to a better model of determining whether a string is naughty or nice. None of the old rules apply, as they are all clearly ridiculous. Now, a nice string is one with all of the following properties:
In [31]:
#http://adventofcode.com/
#PROBLEM 5
import re
p1 = re.compile('(.*[aeiou].*){3,}') #3 vowels
p2 = re.compile("([a-z])\\1") # double letters
p3 = re.compile("ab|cd|pq|xy") #none of these
with open("problem5.txt", 'r') as ins:
print(len([l for l in ins
if (not p3.search(l)) and p1.search(l) and p2.search(l)]))
p4 = re.compile("([a-z][a-z]).*\\1")
p5 = re.compile("([a-z])[a-z]\\1")
with open('problem5.txt', 'r') as f:
print(len([l for l in f if p4.search(l) and p5.search(l)]))
=============================
Because your neighbors keep defeating you in the holiday house decorating contest year after year, you've decided to deploy one million lights in a 1000x1000 grid. Furthermore, because you've been especially nice this year, Santa has mailed you instructions on how to display the ideal lighting configuration. Lights in your grid are numbered from 0 to 999 in each direction; the lights at each corner are at 0,0, 0,999, 999,999, and 999,0. The instructions include whether to turn on, turn off, or toggle various inclusive ranges given as coordinate pairs. Each coordinate pair represents opposite corners of a rectangle, inclusive; a coordinate pair like 0,0 through 2,2 therefore refers to 9 lights in a 3x3 square. The lights all start turned off. To defeat your neighbors this year, all you have to do is set up your lights by doing the instructions Santa sent you in order. For example:
You just finish implementing your winning light pattern when you realize you mistranslated Santa's message from Ancient Nordic Elvish. The light grid you bought actually has individual brightness controls; each light can have a brightness of zero or more. The lights all start at zero.
In [32]:
#problem 6
import re
p6_re = re.compile("([0-9]+)") # get all coordinates
lights_on = set()
with open("protblem6.txt", "r") as ins:
for line in ins:
x1, y1, x2, y2 = [int(x) for x in p6_re.findall(line)] ## get ranges
if line.startswith("turn on"):
for x in range(x1, x2+1):
for y in range(y1, y2+1):
lights_on.add((x,y))
elif line.startswith("toggle"):
for x in range(x1, x2+1):
for y in range(y1, y2+1):
if (x,y) in lights_on:
lights_on.remove((x,y))
else:
lights_on.add((x,y))
elif line.startswith("turn off"):
for x in range(x1, x2+1):
for y in range(y1, y2+1):
if (x,y) in lights_on:
lights_on.remove((x,y))
print(len(lights_on)) #part 1
import re
from collections import defaultdict
# This regex pulls out all contiguous numbers from a line.
r = re.compile("([0-9]+)")
# Keep track of lights as a dict with 0 as a default value.
lights = defaultdict(int)
with open('protblem6.txt') as f:
for line in f:
# Get the ranges from the instruction via regex
x1, y1, x2, y2 = [int(x) for x in r.findall(line)]
# For each instruction, iterate over the range and do the right thing.
if line.startswith('toggle'):
for x in range(x1, x2 + 1):
for y in range(y1, y2 + 1):
# Toggle: Add two to existing brightness
lights[(x,y)] = lights[(x,y)] + 2
elif line.startswith('turn off'):
for x in range(x1, x2 + 1):
for y in range(y1, y2 + 1):
# Turn off: Remove one from existing brightness, but not below 0
lights[(x,y)] = max(lights[(x,y)] - 1, 0)
elif line.startswith('turn on'):
for x in range(x1, x2 + 1):
for y in range(y1, y2 + 1):
# Turn on: Add one to existing brightness
lights[(x,y)] = lights[(x,y)] + 1
# Count up total brightness
print((sum(lights.values()))) #part 2
=============================
This year, Santa brought little Bobby Tables a set of wires and bitwise logic gates! Unfortunately, little Bobby is a little under the recommended age range, and he needs help assembling the circuit. Each wire has an identifier (some lowercase letters) and can carry a 16-bit signal (a number from 0 to 65535). A signal is provided to each wire by a gate, another wire, or some specific value. Each wire can only get a signal from one source, but can provide its signal to multiple destinations. A gate provides no signal until all of its inputs have a signal. The included instructions booklet describe how to connect the parts together: x AND y -> z means to connect wires x and y to an AND gate, and then connect its output to wire z. For example:
Now, take the signal you got on wire a, override wire b to that signal, and reset the other wires (including wire a). What new signal is ultimately provided to wire a?
In [33]:
#problem 7
import re
get_cmd = re.compile("[A-Z]+")
get_args = re.compile("[a-z0-9]+")
# Store functions by their name
funcs = {
'AND': lambda a,b: a & b,
'OR': lambda a,b: a | b,
'LSHIFT': lambda a,b: a << b,
'RSHIFT': lambda a,b: a >> b,
'NOT': lambda a: ~a,
}
# Look up symbol, and its definition recursively, saving the results in
# the wires dict.
def resolve(symbol):
if isinstance(symbol, int):
return symbol
value = wires[symbol]
if not isinstance(value, tuple):
return value
# Value must be a tuple (command, args)
command, args = value
if not command:
# If no command, it must be a simple assignment
result = resolve(args[0])
# store result
wires[symbol] = result
return result
else:
resolved_args = [resolve(x) for x in args]
result = funcs[command](*resolved_args)
# store result
wires[symbol] = result
return result
wires = {}
with open('problem7.txt', 'r') as f:
for line in f:
# Parse the command
command = get_cmd.search(line)
# Get all the arguments via regex
args = get_args.findall(line)
# Convert numeric arguments to integers
args = [int(x) if x.isdigit() else x for x in args]
# Get result of search if we found anything
if command:
command = command.group()
# Get the storage location of the command
to_wire = args.pop()
# Store it
wires[to_wire] = (command, tuple(args))
#print(resolve('a')) #part 1
initial_wires = wires.copy()
result_a = resolve('a')
# Reset to initial state, but with 'b' changed.
wires = initial_wires
wires['b'] = result_a
print(resolve('a'))
In [ ]:
import sys
# Main
print(sum([len(line.strip()) - len(eval(line)) for line in open('problem8.txt')]))
print(sum([line.strip().count('\\') + line.strip().count('"') + 2 for line in open('problem8.txt')]))
============================
Every year, Santa manages to deliver all of his presents in a single night. This year, however, he has some new locations to visit; his elves have provided him the distances between every pair of locations. He can start and end at any two (different) locations he wants, but he must visit each location exactly once. What is the shortest distance he can travel to achieve this? For example, given the following distances:
The next year, just to show off, Santa decides to take the route with the longest distance instead. He can still start and end at any two (different) locations he wants, and he still must visit each location exactly once. For example, given the distances above, the longest route would be 982 via (for example) Dublin -> London -> Belfast. What is the distance of the longest route?
In [34]:
#problem 9
from itertools import permutations
distances = {}
places = set()
with open('problem9.txt', 'r') as f:
for line in f:
parts = line.split(' ')
frm, _, to, _, amount = parts
amount = int(amount.strip())
distances[frm, to] = distances[to, frm] = amount
places.add(frm)
places.add(to)
possibilities = permutations(places)
totals = []
for route in possibilities:
total = 0
for i, frm in enumerate(route):
if i == len(route) -1:
break
to = route[i+1]
total += distances[(frm, to)]
totals.append(total)
print(min(totals))
print(max(totals))
=============================
Today, the Elves are playing a game called look-and-say. They take turns making sequences by reading aloud the previous sequence and using that reading as the next sequence. For example, 211 is read as "one two, two ones", which becomes 1221 (1 2, 2 1s). Look-and-say sequences are generated iteratively, using the previous value as input for the next step. For each step, take the previous value, and replace each run of digits (like 111) with the number of digits (3) followed by the digit itself (1). For example:
Now, starting again with the digits in your puzzle input, apply this process 50 times. What is the length of the new result?
In [35]:
#problem 10
import re
# This is a little complicated, we find a digit and capture all of its
# repetitions, in the second capture group we have the single digit itself
rep_digits = re.compile(r'((\d)\2*)')
looknsay = '3113322113'
for i in range(0,5):
new_looknsay = ''
for match, character in rep_digits.findall(looknsay):
new_looknsay += str(len(match))
new_looknsay += character
looknsay = new_looknsay
print(looknsay)
print(len(looknsay))
========================
Santa's previous password expired, and he needs help choosing a new one. To help him remember his new password after the old one expires, Santa has devised a method of coming up with a password based on the previous one. Corporate policy dictates that passwords must be exactly eight lowercase letters (for security reasons), so he finds his new password by incrementing his old password string repeatedly until it is valid. Incrementing is just like counting with numbers: xx, xy, xz, ya, yb, and so on. Increase the rightmost letter one step; if it was z, it wraps around to a, and repeat with the next letter to the left until one doesn't wrap around. Unfortunately for Santa, a new Security-Elf recently started, and he has imposed some additional password requirements:
Santa's password expired again. What's the next one?
In [36]:
#problem 11
import re
# Magic ASCII number
A = 97
# Can't have these
bad = re.compile(r'i|o|l')
# Must have two pairs
pairs = re.compile(r'([a-z])\1.*([a-z])\2')
# Check if we have a sequence of type 'abc'
def has_sequence(password):
# Switch chars to numbers
nums = list(map(ord, password))
# This checks if the current three are a run
has_run = lambda a,b,c: a == b - 1 and b == c - 1
# This maps our has_run on offset sequences and let's us know if anythin
# makes a run.
return any(map(has_run, nums, nums[1:], nums[2:]))
def get_next_char(c):
# Reduce number to 0-26 range, then add 1
base_num = ord(c) - A + 1
# Convert back to char, keeping within 0-26, then add back up to [a-z] range
return chr((base_num % 26) + A)
def increment_string(s):
if not s:
return ''
next_char = get_next_char(s[-1:])
# If we overflow, recursively overflow on earlier substrings
if next_char == 'a':
return increment_string(s[:-1]) + 'a'
next_string = s[:-1] + next_char
return next_string
# Checks against all required predicates
def is_valid(password):
return (has_sequence(current_password)
and pairs.search(current_password)
and not bad.search(current_password))
current_password = 'hxbxwxba'
while not is_valid(current_password):
current_password = increment_string(current_password)
print(current_password) #part 1
current_password = increment_string(current_password)
while not is_valid(current_password):
current_password = increment_string(current_password)
print(current_password) #part 2
============================
Santa's Accounting-Elves need help balancing the books after a recent order. Unfortunately, their accounting software uses a peculiar storage format. That's where you come in. They have a JSON document which contains a variety of things: arrays ([1,2,3]), objects ({"a":1, "b":2}), numbers, and strings. Your first job is to simply find all of the numbers throughout the document and add them together. For example:
In [37]:
#problem 12
import re
p12 = re.compile(r'(-?\d+)') #find numbers
#part 1
print(sum([sum(int(x) for x in p12.findall(line)) for line in open('problem12.txt')]))
#part 2
import json
with open('problem12.txt') as file:
filter_red = lambda x: {} if 'red' in x.values() else x
inp = json.load(file, object_hook=filter_red)
def sum_numbers_in_json(json):
if isinstance(json, int):
return json
elif isinstance(json, list):
return sum(sum_numbers_in_json(x) for x in json)
elif isinstance(json, dict):
return sum(sum_numbers_in_json(x) for x in json.values())
return 0
print(sum_numbers_in_json(inp))
In years past, the holiday feast with your family hasn't gone so well. Not everyone gets along! This year, you resolve, will be different. You're going to find the optimal seating arrangement and avoid all those awkward conversations.
You start by writing up a list of everyone invited and the amount their happiness would increase or decrease if they were to find themselves sitting next to each other person. You have a circular table that will be just big enough to fit everyone comfortably, and so each person will have exactly two neighbors.
For example, suppose you have only four attendees planned, and you calculate their potential happiness as follows:
Alice would gain 54 happiness units by sitting next to Bob. Alice would lose 79 happiness units by sitting next to Carol. Alice would lose 2 happiness units by sitting next to David. Bob would gain 83 happiness units by sitting next to Alice. Bob would lose 7 happiness units by sitting next to Carol. Bob would lose 63 happiness units by sitting next to David. Carol would lose 62 happiness units by sitting next to Alice. Carol would gain 60 happiness units by sitting next to Bob. Carol would gain 55 happiness units by sitting next to David. David would gain 46 happiness units by sitting next to Alice. David would lose 7 happiness units by sitting next to Bob. David would gain 41 happiness units by sitting next to Carol.
Then, if you seat Alice next to David, Alice would lose 2 happiness units (because David talks so much), but David would gain 46 happiness units (because Alice is such a good listener), for a total change of 44.
If you continue around the table, you could then seat Bob next to Alice (Bob gains 83, Alice gains 54). Finally, seat Carol, who sits next to Bob (Carol gains 60, Bob loses 7) and David (Carol gains 55, David gains 41). The arrangement looks like this:
+41 +46
+55 David -2 Carol Alice +60 Bob +54 -7 +83
After trying every other seating arrangement in this hypothetical scenario, you find that this one is the most optimal, with a total change in happiness of 330.
What is the total change in happiness for the optimal seating arrangement of the actual guest list?
Your puzzle answer was 709. --- Part Two ---
In all the commotion, you realize that you forgot to seat yourself. At this point, you're pretty apathetic toward the whole thing, and your happiness wouldn't really go up or down regardless of who you sit next to. You assume everyone else would be just as ambivalent about sitting next to you, too.
So, add yourself to the list, and give all happiness relationships that involve you a score of 0.
What is the total change in happiness for the optimal seating arrangement that actually includes yourself?
Your puzzle answer was 668.
In [43]:
#problem 13
import re
from collections import defaultdict
from itertools import permutations
person = re.compile(r'[A-Z][a-z]')
value = re.compile(r'-?\d+')
lose = re.compile(r'lose')
people = set()
mapping = defaultdict(int)
sorted_tuple = lambda x, y: tuple(sorted((x,y)))
with open('problem13.txt', 'r') as ins:
for line in ins:
sitter, neighbour = person.findall(line)
diff = int(value.search(line).group())
if lose.search(line):
diff = -diff
people.add(sitter)
# Just get the total difference for the pair of people.
mapping[sorted_tuple(sitter, neighbour)] += diff
totals = []
for p in permutations(people):
total = 0
for i, person in enumerate(p):
# Just need each person and their previous person
total += mapping[sorted_tuple(p[i-1], p[i]) ]
totals.append(total)
print(max(totals))
============================
This year is the Reindeer Olympics! Reindeer can fly at high speeds, but must rest occasionally to recover their energy. Santa would like to know which of his reindeer is fastest, and so he has them race.
Reindeer can only either be flying (always at their top speed) or resting (not moving at all), and always spend whole seconds in either state.
For example, suppose you have the following Reindeer:
Comet can fly 14 km/s for 10 seconds, but then must rest for 127 seconds.
Dancer can fly 16 km/s for 11 seconds, but then must rest for 162 seconds.
After one second, Comet has gone 14 km, while Dancer has gone 16 km. After ten seconds, Comet has gone 140 km, while Dancer has gone 160 km. On the eleventh second, Comet begins resting (staying at 140 km), and Dancer continues on for a total distance of 176 km. On the 12th second, both reindeer are resting. They continue to rest until the 138th second, when Comet flies for another ten seconds. On the 174th second, Dancer flies for another 11 seconds.
In this example, after the 1000th second, both reindeer are resting, and Comet is in the lead at 1120 km (poor Dancer has only gotten 1056 km by that point). So, in this situation, Comet would win (if the race ended at 1000 seconds).
Given the descriptions of each reindeer (in your puzzle input), after exactly 2503 seconds, what distance has the winning reindeer traveled?
Your puzzle answer was 2696. --- Part Two ---
Seeing how reindeer move in bursts, Santa decides he's not pleased with the old scoring system.
Instead, at the end of each second, he awards one point to the reindeer currently in the lead. (If there are multiple reindeer tied for the lead, they each get one point.) He keeps the traditional 2503 second time limit, of course, as doing otherwise would be entirely ridiculous.
Given the example reindeer from above, after the first second, Dancer is in the lead and gets one point. He stays in the lead until several seconds into Comet's second burst: after the 140th second, Comet pulls into the lead and gets his first point. Of course, since Dancer had been in the lead for the 139 seconds before that, he has accumulated 139 points by the 140th second.
After the 1000th second, Dancer has accumulated 689 points, while poor Comet, our old champion, only has 312. So, with the new scoring system, Dancer would win (if the race ended at 1000 seconds).
Again given the descriptions of each reindeer (in your puzzle input), after exactly 2503 seconds, how many points does the winning reindeer have?
Your puzzle answer was 1084.
In [41]:
#problem 14
#part 1
import re
p14 = re.compile("([0-9]+)")
max_dist = []
with open('problem14.txt', 'r') as ins:
for line in ins:
# Get the speed and times from the instruction via regex
speed, duration, rest = [int(x) for x in p14.findall(line)]
time = 2503
traveled = 0
while time > 0:
if time >= duration:
traveled += (speed * duration)
time = time - (duration + rest)
else:
traveled += (speed * time)
time = time - time
max_dist.append(traveled)
print(max(max_dist))
In [42]:
#part 2
import re
import copy
p14 = re.compile("([0-9]+)")
dist_after_s = [0,0,0,0,0,0,0,0,0]
data = []
l = []
time = 2503
with open('problem14.txt', 'r') as ins:
for line in ins:
hl = []
speed, duration, rest = [int(x) for x in p14.findall(line)]
hl.append(speed), hl.append(duration), hl.append(rest)
data.append(hl[:])
datac = copy.deepcopy(data)
while time > 0:
for i in range(len(data)):
if data[i][1] > 0:
dist_after_s[i] += data[i][0]
data[i][1]-=1
elif data[i][1] == 0 and data[i][2] > 0:
data[i][2]-=1
if data[i][1] == 0 and data[i][2] == 0:
data[i][1] = datac[i][1]
data[i][2] = datac[i][2]
time -= 1
l.append(dist_after_s.index(max(dist_after_s))) # in each step append the index to a list with the max value for this step
print((max(set(l), key=l.count)),l.count(max(set(l), key=l.count))) # find the most common index nad # of it
=================================
Today, you set out on the task of perfecting your milk-dunking cookie recipe. All you have to do is find the right balance of ingredients. Your recipe leaves room for exactly 100 teaspoons of ingredients. You make a list of the remaining ingredients you could use to finish the recipe (your puzzle input) and their properties per teaspoon:
"""Solve Day 15/Part 2 of the AdventOfCode
=================================
Your cookie recipe becomes wildly popular! Someone asks if you can make another recipe that has exactly 500 calories per cookie (so they can use it as a meal replacement). Keep the rest of your award-winning process the same (100 teaspoons, same ingredients, same scoring system).
For example, given the ingredients above, if you had instead selected 40 teaspoons of butterscotch and 60 teaspoons of cinnamon (which still adds to 100), the total calorie count would be 408 + 603 = 500. The total score would go down, though: only 57600000, the best you can do in such trying circumstances.
Given the ingredients in your kitchen and their properties, what is the total score of the highest-scoring cookie you can make with a calorie total of 500?
"""
In [27]:
import re
import operator
import collections
Ingredient = collections.namedtuple(
'Ingredient',
'name capacity durability flavor texture calories',
)
p15 = re.compile(
r'(\w+): '
r'capacity (-?\d+), '
r'durability (-?\d+), '
r'flavor (-?\d+), '
r'texture (-?\d+), '
r'calories (-?\d+)'
)
ingredients = []
with open('problem15.txt', 'r') as ins:
for line in ins:
match = p15.match(line)
(name, capacity, durability, flavour, texture, calories) = match.groups()
ingredient = Ingredient(
name,
int(capacity),
int(durability),
int(flavour),
int(texture),
int(calories),)
ingredients.append(ingredient)
def score_ingredients(ingredients, counts):
total = 1
total *= max(0, sum(count * i.capacity for i, count in zip(ingredients, counts)))
total *= max(0, sum(count * i.durability for i, count in zip(ingredients, counts)))
total *= max(0, sum(count * i.flavor for i, count in zip(ingredients, counts)))
total *= max(0, sum(count * i.texture for i, count in zip(ingredients, counts)))
return total
def count_combinations(num_ingredients, total_amount, index=0, counts=None):
"""Yield all combinations for the counts of each ingredient
>>> list(count_combinations(2, 3))
[[0, 3], [1, 2], [2, 1], [3, 0]]
"""
if counts is None:
counts = [0] * num_ingredients
if index == len(counts) - 1:
counts[index] = total_amount
yield counts[:]
return
for i in range(total_amount + 1):
counts[index] = i
remaining = total_amount - i
yield from count_combinations(num_ingredients, remaining, index + 1, counts)
def find_best_combination(ingredients, total_amount):
"""Find the combination of ingredients that gives the highest score
>>> ingredients = [
... Ingredient("Butterscotch", -1, -2, 6, 3, 8),
... Ingredient("Cinnamon", 2, 3, -2, -1, 3),
... ]
>>> find_best_combination(ingredients, 100)
(62842880, [44, 56])
"""
best_score = 0
best_counts = None
for counts in count_combinations(len(ingredients), total_amount):
score = score_ingredients(ingredients, counts)
if score > best_score:
best_score = score
best_counts = counts
return (best_score, best_counts)
score, counts = find_best_combination(ingredients, 100)
print(score)
#part 2 starts here
def get_calories(ingredients, counts):
"""Determine the number of calories based on the counts
>>> ingredients = [
... part_1.Ingredient("Butterscotch", -1, -2, 6, 3, 8),
... part_1.Ingredient("Cinnamon", 2, 3, -2, -1, 3),
... ]
>>> get_calories(ingredients, [40, 60])
500
"""
return sum(count * i.calories for i, count in zip(ingredients, counts))
def find_best_combination(ingredients, total_amount, calories):
"""Find the combination of ingredients that gives the highest score
with the given number of calories.
>>> ingredients = [
... part_1.Ingredient("Butterscotch", -1, -2, 6, 3, 8),
... part_1.Ingredient("Cinnamon", 2, 3, -2, -1, 3),
... ]
>>> find_best_combination(ingredients, 100, 500)
(57600000, [40, 60])
"""
best_score = 0
best_counts = None
for counts in count_combinations(len(ingredients), total_amount):
if get_calories(ingredients, counts) != calories:
continue
score = score_ingredients(ingredients, counts)
if score > best_score:
best_score = score
best_counts = counts
return (best_score, best_counts)
score, counts = find_best_combination(ingredients, 100, 500)
print(score)
--- Day 16: Aunt Sue ---
Your Aunt Sue has given you a wonderful gift, and you'd like to send her a thank you card. However, there's a small problem: she signed it "From, Aunt Sue".
You have 500 Aunts named "Sue".
So, to avoid sending the card to the wrong person, you need to figure out which Aunt Sue (which you conveniently number 1 to 500, for sanity) gave you the gift. You open the present and, as luck would have it, good ol' Aunt Sue got you a My First Crime Scene Analysis Machine! Just what you wanted. Or needed, as the case may be.
The My First Crime Scene Analysis Machine (MFCSAM for short) can detect a few specific compounds in a given sample, as well as how many distinct kinds of those compounds there are. According to the instructions, these are what the MFCSAM can detect:
children, by human DNA age analysis.
cats. It doesn't differentiate individual breeds.
Several seemingly random breeds of dog: samoyeds, pomeranians, akitas, and vizslas.
goldfish. No other kinds of fish.
trees, all in one group.
cars, presumably by exhaust or gasoline or something.
perfumes, which is handy, since many of your Aunts Sue wear a few kinds.
In fact, many of your Aunts Sue have many of these. You put the wrapping from the gift into the MFCSAM. It beeps inquisitively at you a few times and then prints out a message on ticker tape:
children: 3 cats: 7 samoyeds: 2 pomeranians: 3 akitas: 0 vizslas: 0 goldfish: 5 trees: 3 cars: 2 perfumes: 1
You make a list of the things you can remember about each Aunt Sue. Things missing from your list aren't zero - you simply don't remember the value.
What is the number of the Sue that got you the gift?
--- Part Two ---
As you're about to send the thank you note, something in the MFCSAM's instructions catches your eye. Apparently, it has an outdated retroencabulator, and so the output from the machine isn't exact values - some of them indicate ranges.
In particular, the cats and trees readings indicates that there are greater than that many (due to the unpredictable nuclear decay of cat dander and tree pollen), while the pomeranians and goldfish readings indicate that there are fewer than that many (due to the modial interaction of magnetoreluctance).
What is the number of the real Aunt Sue?
In [9]:
import collections
import re
class Sue(object):
def __init__(self, number, traits):
self.number = number
self.traits = traits
@classmethod
def from_line(cls, line):
(number, rest) = re.match(r'Sue (\d+): (.*)', line).groups()
traits = {}
for (name, value) in re.findall(r'(\w+): (\d+)', rest):
traits[name] = int(value)
return cls(int(number), traits)
def compatible(master_sue, sue):
assert len(master_sue.traits) >= len(sue.traits)
for trait in sue.traits.keys():
if master_sue.traits[trait] != sue.traits[trait]:
return False
return True
def compatible(master_sue, sue):
for trait in sue.traits.keys():
if master_sue.traits[trait] != sue.traits[trait]:
return False
return True
with open('problem16.txt', 'r') as ins:
sues = [Sue.from_line(line) for line in ins]
master_traits = {
"children": 3,
"cats": 7,
"samoyeds": 2,
"pomeranians": 3,
"akitas": 0,
"vizslas": 0,
"goldfish": 5,
"trees": 3,
"cars": 2,
"perfumes": 1,
}
master_sue = Sue(-1, master_traits)
for compatible_sue in filter(lambda x: compatible(master_sue, x), sues):
print(compatible_sue.number)
In [1]:
import collections
import re
class Sue(object):
def __init__(self, number, traits):
self.number = number
self.traits = traits
@classmethod
def from_line(cls, line):
(number, rest) = re.match(r'Sue (\d+): (.*)', line).groups()
traits = {}
for (name, value) in re.findall(r'(\w+): (\d+)', rest):
traits[name] = int(value)
return cls(int(number), traits)
def compatible(master_sue, sue):
assert len(master_sue.traits) >= len(sue.traits)
for trait in sue.traits.keys():
if master_sue.traits[trait] != sue.traits[trait]:
return False
return True
def compatible(master_sue, sue):
assert len(master_sue.traits) >= len(sue.traits)
for trait in sue.traits.keys():
master_value = master_sue.traits[trait]
sue_value = sue.traits[trait]
if trait == "cats" or trait == "trees":
if not master_value < sue_value:
return False
elif trait == "pomeranians" or trait == "goldfish":
if not master_value > sue_value:
return False
else:
if master_sue.traits[trait] != sue.traits[trait]:
return False
return True
with open('problem16.txt', 'r') as ins:
sues = [Sue.from_line(line) for line in ins]
master_traits = {
"children": 3,
"cats": 7,
"samoyeds": 2,
"pomeranians": 3,
"akitas": 0,
"vizslas": 0,
"goldfish": 5,
"trees": 3,
"cars": 2,
"perfumes": 1,
}
master_sue = Sue(-1, master_traits)
for compatible_sue in filter(lambda x: compatible(master_sue, x), sues):
print(compatible_sue.number)
The elves bought too much eggnog again - 150 liters this time. To fit it all into your refrigerator, you'll need to move it into smaller containers. You take an inventory of the capacities of the available containers.
For example, suppose you have containers of size 20, 15, 10, 5, and 5 liters. If you need to store 25 liters, there are four ways to do it:
15 and 10
20 and 5 (the first 5)
20 and 5 (the second 5)
15, 5, and 5
Filling all containers entirely, how many different combinations of containers can exactly fit all 150 liters of eggnog?
--- Part Two ---
While playing with all the containers in the kitchen, another load of eggnog arrives! The shipping and receiving department is requesting as many containers as you can spare.
Find the minimum number of containers that can exactly fit all 150 liters of eggnog. How many different ways can you fill that number of containers and still hold exactly 150 litres?
In the example above, the minimum number of containers was two. There were three ways to use that many containers, and so the answer there would be 3.
In [13]:
import itertools
def get_combinations(container_sizes, target_amount):
"""Yield each combination of containers that holds the given amount
>>> list(get_combinations([20, 15, 10, 5, 5], 25))
[(20, 5), (20, 5), (15, 10), (15, 5, 5)]
"""
for i in range(len(container_sizes)):
for combination in itertools.combinations(container_sizes, i):
if sum(combination) == target_amount:
yield combination
with open('problem17.txt', 'r') as f:
container_sizes = [int(line) for line in f]
combinations = get_combinations(container_sizes, 150)
num_combinations = sum(1 for _ in combinations)
print(num_combinations)
combinations1 = list(get_combinations(container_sizes, 150))
min_containers = min(len(x) for x in combinations1)
num_combinations = sum(1 for x in combinations1 if len(x) == min_containers)
print(num_combinations)
--- Day 18: Like a GIF For Your Yard ---
After the million lights incident, the fire code has gotten stricter: now, at most ten thousand lights are allowed. You arrange them in a 100x100 grid.
Never one to let you down, Santa again mails you instructions on the ideal lighting configuration. With so few lights, he says, you'll have to resort to animation.
Start by setting your lights to the included initial configuration (your puzzle input). A # means "on", and a . means "off".
Then, animate your grid in steps, where each step decides the next configuration based on the current one. Each light's next state (either on or off) depends on its current state and the current states of the eight lights adjacent to it (including diagonals). Lights on the edge of the grid might have fewer than eight neighbors; the missing ones always count as "off".
For example, in a simplified 6x6 grid, the light marked A has the neighbors numbered 1 through 8, and the light marked B, which is on an edge, only has the neighbors marked 1 through 5:
1B5... 234... ...... ..123. ..8A4. ..765.
The state a light should have next is based on its current state (on or off) plus the number of neighbors that are on:
A light which is on stays on when 2 or 3 neighbors are on, and turns off otherwise.
A light which is off turns on if exactly 3 neighbors are on, and stays off otherwise.
All of the lights update simultaneously; they all consider the same current state before moving to the next.
Here's a few steps from an example configuration of another 6x6 grid:
Initial state: .#.#.# ...##.
..#...
After 1 step: ..##.. ..##.# ...##. ......
After 2 steps: ..###. ...... ..###. ...... .#.... .#....
After 3 steps: ...#.. ...... ...#.. ..##.. ...... ......
After 4 steps: ...... ...... ..##.. ..##.. ...... ......
After 4 steps, this example has four lights on.
In your grid of 100x100 lights, given your initial configuration, how many lights are on after 100 steps?
--- Part Two ---
You flip the instructions over; Santa goes on to point out that this is all just an implementation of Conway's Game of Life. At least, it was, until you notice that something's wrong with the grid of lights you bought: four lights, one in each corner, are stuck on and can't be turned off. The example above will actually run like this:
Initial state:
...##.
..#...
After 1 step:
...##. ......
After 2 steps:
.#.##. ...##. .#..##
After 3 steps:
..##.# ......
After 4 steps:
...#.. .##...
After 5 steps:
.##..# .##... .##...
After 5 steps, this example now has 17 lights on.
In your grid of 100x100 lights, given your initial configuration, but with the four corners always in the on state, how many lights are on after 100 steps?
In [17]:
import numpy as np
class Grid(object):
def __init__(self, initial_grid):
self.grid = initial_grid
@classmethod
def from_file(cls, fileobj):
grid = [
[
c == "#"
for c in line.strip()
]
for line in fileobj
]
np_grid = np.zeros((2+len(grid), 2+len(grid[0])), dtype=bool)
np_grid[1:-1, 1:-1] = grid
return cls(np_grid)
def __repr__(self):
"""x
>>> lines = [".#.#.#", "...##.", "#....#", "..#...", "#.#..#", "####.."]
>>> grid = Grid.from_file(lines)
>>> grid
.#.#.#
...##.
#....#
..#...
#.#..#
####..
"""
return "\n".join(''.join("#" if val else "." for val in row[1:-1]) for row in self.grid[1:-1])
def step(self):
"""x
>>> lines = [".#.#.#", "...##.", "#....#", "..#...", "#.#..#", "####.."]
>>> grid = Grid.from_file(lines)
>>> grid.step()
>>> grid
..##..
..##.#
...##.
......
#.....
#.##..
"""
previous = self.grid.copy()
for row in range(1, previous.shape[0]-1):
for col in range(1, previous.shape[1]-1):
current = previous[row, col]
neighbors = np.sum(previous[row-1:row+2, col-1:col+2]) - current
if current:
self.grid[row, col] = neighbors == 2 or neighbors == 3
else:
self.grid[row, col] = neighbors == 3
def count_lights(self):
return np.sum(self.grid)
with open('problem18.txt', 'r') as f:
grid = Grid.from_file(f)
for _ in range(100):
grid.step()
lights = grid.count_lights()
print(lights)
class ModifiedGrid(Grid):
def __init__(self, initial_grid):
"""x
>>> lines = [".#.#.#", "...##.", "#....#", "..#...", "#.#..#", "####.."]
>>> grid = ModifiedGrid.from_file(lines)
>>> grid
##.#.#
...##.
#....#
..#...
#.#..#
####.#
"""
Grid.__init__(self, initial_grid)
self.turn_on_corners()
def turn_on_corners(self):
self.grid[1, 1] = True
self.grid[-2, 1] = True
self.grid[-2, -2] = True
self.grid[1, -2] = True
def step(self):
"""x
>>> lines = [".#.#.#", "...##.", "#....#", "..#...", "#.#..#", "####.."]
>>> grid = ModifiedGrid.from_file(lines)
>>> grid.step()
>>> grid
#.##.#
####.#
...##.
......
#...#.
#.####
"""
self.turn_on_corners()
Grid.step(self)
self.turn_on_corners()
with open('problem18.txt', 'r') as f:
grid = ModifiedGrid.from_file(f)
for _ in range(100):
grid.step()
lights = grid.count_lights()
print(lights)
--- Day 19: Medicine for Rudolph ---
Rudolph the Red-Nosed Reindeer is sick! His nose isn't shining very brightly, and he needs medicine.
Red-Nosed Reindeer biology isn't similar to regular reindeer biology; Rudolph is going to need custom-made medicine. Unfortunately, Red-Nosed Reindeer chemistry isn't similar to regular reindeer chemistry, either.
The North Pole is equipped with a Red-Nosed Reindeer nuclear fusion/fission plant, capable of constructing any Red-Nosed Reindeer molecule you need. It works by starting with some input molecule and then doing a series of replacements, one per step, until it has the right molecule.
However, the machine has to be calibrated before it can be used. Calibration involves determining the number of molecules that can be generated in one step from a given starting point.
For example, imagine a simpler machine that supports only the following replacements:
H => HO H => OH O => HH
Given the replacements above and starting with HOH, the following molecules could be generated:
HOOH (via H => HO on the first H).
HOHO (via H => HO on the second H).
OHOH (via H => OH on the first H).
HOOH (via H => OH on the second H).
HHHH (via O => HH).
So, in the example above, there are 4 distinct molecules (not five, because HOOH appears twice) after one replacement from HOH. Santa's favorite molecule, HOHOHO, can become 7 distinct molecules (over nine replacements: six from H, and three from O).
The machine replaces without regard for the surrounding characters. For example, given the string H2O, the transition H => OO would result in OO2O.
Your puzzle input describes all of the possible replacements and, at the bottom, the medicine molecule for which you need to calibrate the machine. How many distinct molecules can be created after all the different ways you can do one replacement on the medicine molecule?
--- Part Two ---
Now that the machine is calibrated, you're ready to begin molecule fabrication.
Molecule fabrication always begins with just a single electron, e, and applying replacements one at a time, just like the ones during calibration.
For example, suppose you have the following replacements:
e => H e => O H => HO H => OH O => HH
If you'd like to make HOH, you start with e, and then make the following replacements:
e => O to get O
O => HH to get HH
H => OH (on the second H) to get HOH
So, you could make HOH after 3 steps. Santa's favorite molecule, HOHOHO, can be made in 6 steps.
How long will it take to make the medicine? Given the available replacements and the medicine molecule in your puzzle input, what is the fewest number of steps to go from e to the medicine molecule?
In [22]:
import re
import itertools
class Replacements(object):
def __init__(self):
self.replacements = list()
def add(self, line):
"""x
>>> r = Replacements()
>>> r.add('H => OH')
>>> r.replacements
[('H', 'OH')]
"""
(before, after) = line.split(' => ')
self.replacements.append((before, after))
def possiblities_for(self, molecule):
"""x
>>> r = Replacements()
>>> r.add('H => HO')
>>> r.add('H => OH')
>>> r.add('O => HH')
>>> list(r.possiblities_for('HOH'))
['HOOH', 'HOHO', 'OHOH', 'HOOH', 'HHHH']
"""
for (before, after) in self.replacements:
indices = [i.start() for i in re.finditer(before, molecule)]
for index in indices:
yield molecule[:index] + after + molecule[index+len(before):]
with open('problem19.txt', 'r') as f:
replacements = Replacements()
for line in f:
line = line.strip()
if line == "":
break
replacements.add(line)
molecule = f.readline()
possiblities = replacements.possiblities_for(molecule)
unique_count = len(set(possiblities))
print(unique_count)
def number_of_steps(molecule):
"""x
>>> number_of_steps("ABCDE")
4
>>> number_of_steps("ARnBRnCRnDRnEArArArAr")
4
>>> number_of_steps("ARnBRnCYDArYERnFYGArAr")
3
"""
# Thanks https://www.reddit.com/r/adventofcode/comments/3xflz8/day_19_solutions/cy4etju
elements = [el.group() for el in re.finditer(r'[A-Z][a-z]?', molecule)]
rn_or_ar = [el for el in elements if el == 'Rn' or el == 'Ar']
y_elements = [el for el in elements if el == 'Y']
steps = len(elements) - len(rn_or_ar) - 2*len(y_elements) - 1
return steps
with open('problem19.txt', 'r') as f:
for line in f:
line = line.strip()
if line == "":
break
pass
molecule = f.readline()
steps = number_of_steps(molecule)
print(steps)
--- Day 20: Infinite Elves and Infinite Houses ---
To keep the Elves busy, Santa has them deliver some presents by hand, door-to-door. He sends them down a street with infinite houses numbered sequentially: 1, 2, 3, 4, 5, and so on.
Each Elf is assigned a number, too, and delivers presents to houses based on that number:
The first Elf (number 1) delivers presents to every house: 1, 2, 3, 4, 5, ....
The second Elf (number 2) delivers presents to every second house: 2, 4, 6, 8, 10, ....
Elf number 3 delivers presents to every third house: 3, 6, 9, 12, 15, ....
There are infinitely many Elves, numbered starting with 1. Each Elf delivers presents equal to ten times his or her number at each house.
So, the first nine houses on the street end up like this:
House 1 got 10 presents. House 2 got 30 presents. House 3 got 40 presents. House 4 got 70 presents. House 5 got 60 presents. House 6 got 120 presents. House 7 got 80 presents. House 8 got 150 presents. House 9 got 130 presents.
The first house gets 10 presents: it is visited only by Elf 1, which delivers 1 * 10 = 10 presents. The fourth house gets 70 presents, because it is visited by Elves 1, 2, and 4, for a total of 10 + 20 + 40 = 70 presents.
What is the lowest house number of the house to get at least as many presents as the number in your puzzle input?
Your puzzle input is 34000000.
--- Part Two ---
The Elves decide they don't want to visit an infinite number of houses. Instead, each Elf will stop after delivering presents to 50 houses. To make up for it, they decide to deliver presents equal to eleven times their number at each house.
With these changes, what is the new lowest house number of the house to get at least as many presents as the number in your puzzle input?
In [25]:
import math
import itertools
class Houses(object):
def __init__(self):
pass
def get_number_of_presents(self, house_number):
"""x
>>> h = Houses()
>>> h.get_number_of_presents(1)
10
>>> h.get_number_of_presents(2)
30
>>> h.get_number_of_presents(3)
40
>>> h.get_number_of_presents(4)
70
"""
result = 0
for elf in self.elves_delivering_to(house_number):
result += self.presents_per_elf(elf)
return result
def elves_delivering_to(self, house_number):
for divisor in divisors_for(house_number):
yield divisor
def presents_per_elf(self, elf):
return 10 * elf
def divisors_for(number):
"""x
>>> sorted(list(divisors_for(6)))
[1, 2, 3, 6]
"""
yield 1
if number != 1:
yield number
for divisor in range(2, 1+math.floor(math.sqrt(number))):
if number % divisor == 0:
quotient = number // divisor
yield divisor
if quotient != divisor:
yield number // divisor
present_threshold = int(34000000)
houses = Houses()
for house_number in itertools.count():
if houses.get_number_of_presents(house_number) >= present_threshold:
break
print(house_number)
class ModifiedHouses(Houses):
def __init__(self):
pass
def elves_delivering_to(self, house_number):
for divisor in divisors_for(house_number):
if house_number > 50 * divisor:
continue
yield divisor
def presents_per_elf(self, elf):
return 11 * elf
houses = ModifiedHouses()
for house_number in itertools.count():
if houses.get_number_of_presents(house_number) >= present_threshold:
break
print(house_number)
--- Day 21: RPG Simulator 20XX ---
Little Henry Case got a new video game for Christmas. It's an RPG, and he's stuck on a boss. He needs to know what equipment to buy at the shop. He hands you the controller.
In this game, the player (you) and the enemy (the boss) take turns attacking. The player always goes first. Each attack reduces the opponent's hit points by at least 1. The first character at or below 0 hit points loses.
Damage dealt by an attacker each turn is equal to the attacker's damage score minus the defender's armor score. An attacker always does at least 1 damage. So, if the attacker has a damage score of 8, and the defender has an armor score of 3, the defender loses 5 hit points. If the defender had an armor score of 300, the defender would still lose 1 hit point.
Your damage score and armor score both start at zero. They can be increased by buying items in exchange for gold. You start with no items and have as much gold as you need. Your total damage or armor is equal to the sum of those stats from all of your items. You have 100 hit points.
Here is what the item shop is selling:
Weapons: Cost Damage Armor Dagger 8 4 0 Shortsword 10 5 0 Warhammer 25 6 0 Longsword 40 7 0 Greataxe 74 8 0
Armor: Cost Damage Armor Leather 13 0 1 Chainmail 31 0 2 Splintmail 53 0 3 Bandedmail 75 0 4 Platemail 102 0 5
Rings: Cost Damage Armor Damage +1 25 1 0 Damage +2 50 2 0 Damage +3 100 3 0 Defense +1 20 0 1 Defense +2 40 0 2 Defense +3 80 0 3
You must buy exactly one weapon; no dual-wielding. Armor is optional, but you can't use more than one. You can buy 0-2 rings (at most one for each hand). You must use any items you buy. The shop only has one of each item, so you can't buy, for example, two rings of Damage +3.
For example, suppose you have 8 hit points, 5 damage, and 5 armor, and that the boss has 12 hit points, 7 damage, and 2 armor:
The player deals 5-2 = 3 damage; the boss goes down to 9 hit points.
The boss deals 7-5 = 2 damage; the player goes down to 6 hit points.
The player deals 5-2 = 3 damage; the boss goes down to 6 hit points.
The boss deals 7-5 = 2 damage; the player goes down to 4 hit points.
The player deals 5-2 = 3 damage; the boss goes down to 3 hit points.
The boss deals 7-5 = 2 damage; the player goes down to 2 hit points.
The player deals 5-2 = 3 damage; the boss goes down to 0 hit points.
In this scenario, the player wins! (Barely.)
You have 100 hit points. The boss's actual stats are in your puzzle input. What is the least amount of gold you can spend and still win the fight?
--- Part Two ---
Turns out the shopkeeper is working with the boss, and can persuade you to buy whatever items he wants. The other rules still apply, and he still only has one of each item.
What is the most amount of gold you can spend and still lose the fight?
In [30]:
import itertools
class Item(object):
def __init__(self, item_type, name, cost, damage, armor):
self.item_type = item_type
self.name = name
self.cost = cost
self.damage = damage
self.armor = armor
def __eq__(self, other):
return self.item_type == other.item_type and self.name == other.name
def __le__(self, other):
if self.item_type < other.item_type:
return True
if self.name < other.name:
return True
return False
def __repr__(self):
return "Item(name={!r})".format(self.name)
def __str__(self):
return "{}".format(self.name)
def is_weapon(self):
return self.item_type == "weapon"
def is_armor(self):
return self.item_type == "armor"
def is_ring(self):
return self.item_type == "ring1" or self.item_type == "ring2"
store_items = [
Item("weapon", "Dagger", 8, 4, 0),
Item("weapon", "Shortsword", 10, 5, 0),
Item("weapon", "Warhammer", 25, 6, 0),
Item("weapon", "Longsword", 40, 7, 0),
Item("weapon", "Greataxe", 74, 8, 0),
Item("armor", "Leather", 13, 0, 1),
Item("armor", "Chainmail", 31, 0, 2),
Item("armor", "Splintmail", 53, 0, 3),
Item("armor", "Bandedmail", 75, 0, 4),
Item("armor", "Platemail", 102, 0, 5),
Item("ring1", "Damage +1", 25, 1, 0),
Item("ring1", "Damage +2", 50, 2, 0),
Item("ring1", "Damage +3", 100, 3, 0),
Item("ring1", "Defense +1", 20, 0, 1),
Item("ring1", "Defense +2", 40, 0, 2),
Item("ring1", "Defense +3", 80, 0, 3),
Item("ring2", "Damage +1", 25, 1, 0),
Item("ring2", "Damage +2", 50, 2, 0),
Item("ring2", "Damage +3", 100, 3, 0),
Item("ring2", "Defense +1", 20, 0, 1),
Item("ring2", "Defense +2", 40, 0, 2),
Item("ring2", "Defense +3", 80, 0, 3),
]
class Character(object):
def __init__(self, hit_points, damage, armor):
self.hit_points = hit_points
self.damage = damage
self.armor = armor
@classmethod
def from_items(cls, hit_points, items):
damage = 0
armor = 0
for item in items:
damage += item.damage
armor += item.armor
return cls(hit_points, damage, armor)
@classmethod
def from_lines(cls, lines):
hit_points = None
damage = None
armor = None
for line in lines:
(attribute, value) = line.split(':')
if attribute == "Hit Points":
hit_points = int(value)
elif attribute == "Damage":
damage = int(value)
elif attribute == "Armor":
armor = int(value)
return cls(hit_points, damage, armor)
def copy(self):
return Character(self.hit_points, self.damage, self.armor)
def attack(self, other):
other.hit_points -= max(1, self.damage - other.armor)
def is_living(self):
return self.hit_points > 0
def item_combinations(size):
for combination in itertools.combinations(store_items, size):
# Exactly 1 weapon
num_weapons = sum(x.is_weapon() for x in combination)
if num_weapons != 1:
continue
# No more than 1 armor
num_armors = sum(x.is_armor() for x in combination)
if num_armors > 1:
continue
# No more than 2 rings
num_rings = sum(x.is_ring() for x in combination)
if num_rings > 2:
continue
# Rings must be distinct
num_distinct_rings = len(set(x.name for x in combination if x.is_ring()))
if num_distinct_rings != num_rings:
continue
yield combination
def all_item_combinations():
for size in range(5):
yield from item_combinations(size)
def determine_winner(player, boss):
"""True if player wins, False otherwise"""
while True:
player.attack(boss)
if not boss.is_living():
return True
boss.attack(player)
if not player.is_living():
return False
with open('problem21.txt', 'r') as f:
boss = Character.from_lines(f)
player_hit_points = 100
winning_items = [] #part 1
losing_items = [] #part 2
for items in all_item_combinations():
player = Character.from_items(player_hit_points, items)
if determine_winner(player.copy(), boss.copy()):
winning_items.append(items) #part 1
if not determine_winner(player.copy(), boss.copy()):
losing_items.append(items) #part 2
min_cost = min(sum(x.cost for x in items) for items in winning_items)
print(min_cost) #part1
max_cost = max(sum(x.cost for x in items) for items in losing_items)
print(max_cost) #part2
--- Day 22: Wizard Simulator 20XX ---
Little Henry Case decides that defeating bosses with swords and stuff is boring. Now he's playing the game with a wizard. Of course, he gets stuck on another boss and needs your help again.
In this version, combat still proceeds with the player and the boss taking alternating turns. The player still goes first. Now, however, you don't get any equipment; instead, you must choose one of your spells to cast. The first character at or below 0 hit points loses.
Since you're a wizard, you don't get to wear armor, and you can't attack normally. However, since you do magic damage, your opponent's armor is ignored, and so the boss effectively has zero armor as well. As before, if armor (from a spell, in this case) would reduce damage below 1, it becomes 1 instead - that is, the boss' attacks always deal at least 1 damage.
On each of your turns, you must select one of your spells to cast. If you cannot afford to cast any spell, you lose. Spells cost mana; you start with 500 mana, but have no maximum limit. You must have enough mana to cast a spell, and its cost is immediately deducted when you cast it. Your spells are Magic Missile, Drain, Shield, Poison, and Recharge.
Magic Missile costs 53 mana. It instantly does 4 damage.
Drain costs 73 mana. It instantly does 2 damage and heals you for 2 hit points.
Shield costs 113 mana. It starts an effect that lasts for 6 turns. While it is active, your armor is increased by 7.
Poison costs 173 mana. It starts an effect that lasts for 6 turns. At the start of each turn while it is active, it deals the boss 3 damage.
Recharge costs 229 mana. It starts an effect that lasts for 5 turns. At the start of each turn while it is active, it gives you 101 new mana.
Effects all work the same way. Effects apply at the start of both the player's turns and the boss' turns. Effects are created with a timer (the number of turns they last); at the start of each turn, after they apply any effect they have, their timer is decreased by one. If this decreases the timer to zero, the effect ends. You cannot cast a spell that would start an effect which is already active. However, effects can be started on the same turn they end.
For example, suppose the player has 10 hit points and 250 mana, and that the boss has 13 hit points and 8 damage:
-- Player turn --
-- Boss turn --
-- Player turn --
-- Boss turn --
Now, suppose the same initial conditions, except that the boss has 14 hit points instead:
-- Player turn --
-- Boss turn --
-- Player turn --
-- Boss turn --
-- Player turn --
-- Boss turn --
-- Player turn --
-- Boss turn --
-- Player turn --
-- Boss turn --
You start with 50 hit points and 500 mana points. The boss's actual stats are in your puzzle input. What is the least amount of mana you can spend and still win the fight? (Do not include mana recharge effects as "spending" negative mana.)
--- Part Two ---
On the next run through the game, you increase the difficulty to hard.
At the start of each player turn (before any other effects apply), you lose 1 hit point. If this brings you to or below 0 hit points, you lose.
With the same starting stats for you and the boss, what is the least amount of mana you can spend and still win the fight?
In [34]:
import enum
import sys
import random
class Boss(object):
def __init__(self, hit_points, damage):
self.hit_points = hit_points
self.damage = damage
def copy(self):
return Boss(self.hit_points, self.damage)
class Player(object):
def __init__(self, hit_points, mana, armor=0):
self.hit_points = hit_points
self.mana = mana
self.armor = armor
def copy(self):
return Player(self.hit_points, self.mana, self.armor)
class Effect(object):
def __init__(self, effect_type, duration, cost):
self.effect_type = effect_type
self.duration = duration
self.cost = cost
def copy(self):
return Effect(self.effect_type, self.duration, self.cost)
def __eq__(self, other):
return self.effect_type == other.effect_type
EffectType = enum.Enum('EffectType', 'MagicMissile Drain Shield Poison Recharge')
RechargeEffect = Effect(EffectType.Recharge, duration=5, cost=229)
PoisonEffect = Effect(EffectType.Poison, duration=6, cost=173)
ShieldEffect = Effect(EffectType.Shield, duration=6, cost=113)
DrainEffect = Effect(EffectType.Drain, duration=0, cost=73)
MagicMissileEffect = Effect(EffectType.MagicMissile, duration=0, cost=53)
effects = [
RechargeEffect,
PoisonEffect,
ShieldEffect,
DrainEffect,
MagicMissileEffect,
]
def find_solution(boss, player, current_spells=None, players_turn=True):
if current_spells is None:
current_spells = []
for effect in current_spells:
if effect == PoisonEffect:
boss.hit_points -= 3
if effect == RechargeEffect:
player.mana += 101
effect.duration -= 1
if effect.duration <= 0:
if effect == ShieldEffect:
player.armor = 0
current_spells = [x for x in current_spells if x.duration > 0]
if boss.hit_points <= 0:
return 0
if player.hit_points <= 0:
return float('inf')
if players_turn:
possible = [x for x in effects if x not in current_spells and x.cost <= player.mana]
if len(possible) == 0:
return float('inf')
chosen = random.choice(possible)
player.mana -= chosen.cost
if chosen == MagicMissileEffect:
boss.hit_points -= 4
elif chosen == DrainEffect:
boss.hit_points -= 2
player.hit_points += 2
elif chosen == ShieldEffect:
player.armor = 7
return chosen.cost + find_solution(boss, player, current_spells + [chosen.copy()], False)
else:
player.hit_points -= max(1, boss.damage - player.armor)
return find_solution(boss, player, current_spells, True)
with open('problem22.txt', 'r') as f:
boss_hit_points = int(f.readline().split(': ')[-1])
boss_damage = int(f.readline().split(': ')[-1])
player_hit_points = 50
player_mana = 500
boss = Boss(boss_hit_points, boss_damage)
player = Player(player_hit_points, player_mana)
lowest_cost_win = float('inf')
for _ in range(30 * 1000 * 1000):
cost = find_solution(boss.copy(), player.copy())
if cost < lowest_cost_win:
import sys; print("Cost = {}".format(cost), file=sys.stderr)
lowest_cost_win = cost
print(lowest_cost_win)
In [48]:
from collections import defaultdict
import itertools
__author__ = 'david'
spells = [
# mana, damage, heal, shield, att, mana, duration
(53, 4, 0, 0, 0, 0, 0),
(73, 2, 2, 0, 0, 0, 0),
(113, 0, 0, 7, 0, 0, 6),
(173, 0, 0, 0, 3, 0, 6),
(229, 0, 0, 0, 0, 101, 5)
]
best = 1000000000000
def iterate(total, depth, timers, mana, shield, health, ehealth):
global spells, best, edamage
# See if we're dead
if health <= 0:
return
elif ehealth <= 0:
# We won! see if the mana cost was good
if total < best:
best = total
return
# Process the timers
for k, v in timers.items():
if k[4]:
ehealth -= k[4]
elif k[3] and v == 0:
shield -= k[3]
elif k[5]:
mana += k[5]
# Get rid of all the expired timers
timers = {k: v - 1 for k, v in timers.items() if v > 0}
# See if anyone died
if ehealth <= 0:
# We won! see if the mana cost was good
if total < best:
best = total
return
if depth % 2 == 0:
# Hard mode, we lose a health
health -= 1
if health <= 0:
return
# Figure out the valid spells
valid = [s for s in spells if s not in timers and s[0] <= mana]
for s in valid:
# Try casting each spell
ntimers = {k: v for k, v in timers.items()}
if not s[-1]:
# instant spell
nehealth = ehealth - s[1]
nhealth = health + s[2]
nshield = shield
else:
nehealth = ehealth
nhealth = health
nshield = shield + s[3]
ntimers[s] = s[-1] - 1
# print "CASTING:", s
iterate(total + s[0], depth + 1, ntimers, mana - s[0], nshield, nhealth, nehealth)
else:
# The boss goes, inflict the damage
health -= max(1, edamage - shield)
iterate(total, depth + 1, timers, mana, shield, health, ehealth)
edamage = 9
iterate(0, 0, {}, mana=500, shield=0, health=50, ehealth=51)
print(best)
--- Day 23: Opening the Turing Lock ---
Little Jane Marie just got her very first computer for Christmas from some unknown benefactor. It comes with instructions and an example program, but the computer itself seems to be malfunctioning. She's curious what the program does, and would like you to help her run it.
The manual explains that the computer supports two registers and six instructions (truly, it goes on to remind the reader, a state-of-the-art technology). The registers are named a and b, can hold any non-negative integer, and begin with a value of 0. The instructions are as follows:
hlf r sets register r to half its current value, then continues with the next instruction.
tpl r sets register r to triple its current value, then continues with the next instruction.
inc r increments register r, adding 1 to it, then continues with the next instruction.
jmp offset is a jump; it continues with the instruction offset away relative to itself.
jie r, offset is like jmp, but only jumps if register r is even ("jump if even").
jio r, offset is like jmp, but only jumps if register r is 1 ("jump if one", not odd).
All three jump instructions work with an offset relative to that instruction. The offset is always written with a prefix + or - to indicate the direction of the jump (forward or backward, respectively). For example, jmp +1 would simply continue with the next instruction, while jmp +0 would continuously jump back to itself forever.
The program exits when it tries to run an instruction beyond the ones defined.
For example, this program sets a to 2, because the jio instruction causes it to skip the tpl instruction:
inc a jio a, +2 tpl a inc a
What is the value in register b when the program in your puzzle input is finished executing? --- Part Two ---
The unknown benefactor is very thankful for releasi-- er, helping little Jane Marie with her computer. Definitely not to distract you, what is the value in register b after the program is finished executing if register a starts as 1 instead?
In [39]:
import re
class Program(object):
def __init__(self, instructions):
self.instructions = instructions
self.state = State()
def step(self):
pc = self.state.program_counter
if pc >= len(self.instructions):
return False
instruction = self.instructions[pc]
instruction.step(self.state)
return True
class State(object):
def __init__(self):
self.registers = [0] * 2
self.program_counter = 0
class Instruction(object):
def step(self, state):
raise NotImplementedError()
class Half(Instruction):
def __init__(self, register_number):
self.register_number = register_number
def step(self, state):
state.registers[self.register_number] //= 2
state.program_counter += 1
class Triple(Instruction):
def __init__(self, register_number):
self.register_number = register_number
def step(self, state):
state.registers[self.register_number] *= 3
state.program_counter += 1
class Increment(Instruction):
def __init__(self, register_number):
self.register_number = register_number
def step(self, state):
state.registers[self.register_number] += 1
state.program_counter += 1
class Jump(Instruction):
def __init__(self, offset):
self.offset = offset
def step(self, state):
state.program_counter += self.offset
class JumpIfEven(Instruction):
def __init__(self, register_number, offset):
self.register_number = register_number
self.offset = offset
def step(self, state):
if state.registers[self.register_number] % 2 == 0:
state.program_counter += self.offset
else:
state.program_counter += 1
class JumpIfOne(Instruction):
def __init__(self, register_number, offset):
self.register_number = register_number
self.offset = offset
def step(self, state):
if state.registers[self.register_number] == 1:
state.program_counter += self.offset
else:
state.program_counter += 1
def parse_instruction(line):
register_mapping = { 'a': 0, 'b': 1 }
match = re.match(r'hlf ([a-z])', line)
if match:
return Half(register_mapping[match.group(1)])
match = re.match(r'tpl ([a-z])', line)
if match:
return Triple(register_mapping[match.group(1)])
match = re.match(r'inc ([a-z])', line)
if match:
return Increment(register_mapping[match.group(1)])
match = re.match(r'jmp ([+-]\d+)', line)
if match:
return Jump(int(match.group(1)))
match = re.match(r'jie ([a-z]), ([+-]\d+)', line)
if match:
return JumpIfEven(register_mapping[match.group(1)], int(match.group(2)))
match = re.match(r'jio ([a-z]), ([+-]\d+)', line)
if match:
return JumpIfOne(register_mapping[match.group(1)], int(match.group(2)))
raise ValueError("Could not parse '{}'".format(line))
with open('problem23.txt', 'r') as f:
instructions = []
for line in f:
instructions.append(parse_instruction(line))
program = Program(instructions)
while program.step():
pass
register_b = program.state.registers[1]
print(register_b)
with open('problem23.txt', 'r') as f:
instructions = []
instructions.append(parse_instruction('inc a'))
for line in f:
instructions.append(parse_instruction(line))
program = Program(instructions)
while program.step():
pass
register_b = program.state.registers[1]
print(register_b)
--- Day 24: It Hangs in the Balance ---
It's Christmas Eve, and Santa is loading up the sleigh for this year's deliveries. However, there's one small problem: he can't get the sleigh to balance. If it isn't balanced, he can't defy physics, and nobody gets presents this year.
No pressure.
Santa has provided you a list of the weights of every package he needs to fit on the sleigh. The packages need to be split into three groups of exactly the same weight, and every package has to fit. The first group goes in the passenger compartment of the sleigh, and the second and third go in containers on either side. Only when all three groups weigh exactly the same amount will the sleigh be able to fly. Defying physics has rules, you know!
Of course, that's not the only problem. The first group - the one going in the passenger compartment - needs as few packages as possible so that Santa has some legroom left over. It doesn't matter how many packages are in either of the other two groups, so long as all of the groups weigh the same.
Furthermore, Santa tells you, if there are multiple ways to arrange the packages such that the fewest possible are in the first group, you need to choose the way where the first group has the smallest quantum entanglement to reduce the chance of any "complications". The quantum entanglement of a group of packages is the product of their weights, that is, the value you get when you multiply their weights together. Only consider quantum entanglement if the first group has the fewest possible number of packages in it and all groups weigh the same amount.
For example, suppose you have ten packages with weights 1 through 5 and 7 through 11. For this situation, some of the unique first groups, their quantum entanglements, and a way to divide the remaining packages are as follows:
Group 1; Group 2; Group 3 11 9 (QE= 99); 10 8 2; 7 5 4 3 1 10 9 1 (QE= 90); 11 7 2; 8 5 4 3 10 8 2 (QE=160); 11 9; 7 5 4 3 1 10 7 3 (QE=210); 11 9; 8 5 4 2 1 10 5 4 1 (QE=200); 11 9; 8 7 3 2 10 5 3 2 (QE=300); 11 9; 8 7 4 1 10 4 3 2 1 (QE=240); 11 9; 8 7 5 9 8 3 (QE=216); 11 7 2; 10 5 4 1 9 7 4 (QE=252); 11 8 1; 10 5 3 2 9 5 4 2 (QE=360); 11 8 1; 10 7 3 8 7 5 (QE=280); 11 9; 10 4 3 2 1 8 5 4 3 (QE=480); 11 9; 10 7 2 1 7 5 4 3 1 (QE=420); 11 9; 10 8 2
Of these, although 10 9 1 has the smallest quantum entanglement (90), the configuration with only two packages, 11 9, in the passenger compartment gives Santa the most legroom and wins. In this situation, the quantum entanglement for the ideal configuration is therefore 99. Had there been two configurations with only two packages in the first group, the one with the smaller quantum entanglement would be chosen.
What is the quantum entanglement of the first group of packages in the ideal configuration?
--- Part Two ---
That's weird... the sleigh still isn't balancing.
"Ho ho ho", Santa muses to himself. "I forgot the trunk".
Balance the sleigh again, but this time, separate the packages into four groups instead of three. The other constraints still apply.
Given the example packages above, this would be some of the new unique first groups, their quantum entanglements, and one way to divide the remaining packages:
11 4 (QE=44); 10 5; 9 3 2 1; 8 7 10 5 (QE=50); 11 4; 9 3 2 1; 8 7 9 5 1 (QE=45); 11 4; 10 3 2; 8 7 9 4 2 (QE=72); 11 3 1; 10 5; 8 7 9 3 2 1 (QE=54); 11 4; 10 5; 8 7 8 7 (QE=56); 11 4; 10 5; 9 3 2 1
Of these, there are three arrangements that put the minimum (two) number of packages in the first group: 11 4, 10 5, and 8 7. Of these, 11 4 has the lowest quantum entanglement, and so it is selected.
Now, what is the quantum entanglement of the first group of packages in the ideal configuration?
In [42]:
import itertools
# Heavily based on
# https://www.reddit.com/r/adventofcode/comments/3y1s7f/day_24_solutions/cy9srkh
def generate_partitions(weights, num_partitions, first_call=True,
expected_sum=None):
if expected_sum is None:
expected_sum = sum(weights) / num_partitions
if num_partitions == 1:
return sum(weights) == expected_sum
for length in range(1, len(weights)):
for first_partition in itertools.combinations(weights, length):
if sum(first_partition) != expected_sum:
continue
remaining = list(set(weights) - set(first_partition))
if not generate_partitions(remaining, num_partitions - 1, False, expected_sum):
continue
product = 1
for weight in first_partition:
product *= weight
return product
return False
with open('problem24.txt', 'r') as f:
weights = sorted([int(line) for line in f])
minimum_qe = generate_partitions(weights, 3)
print(minimum_qe)
minimum_qe = generate_partitions(weights, 4)
print(minimum_qe)
--- Day 25: Let It Snow ---
Merry Christmas! Santa is booting up his weather machine; looks like you might get a white Christmas after all.
The weather machine beeps! On the console of the machine is a copy protection message asking you to enter a code from the instruction manual. Apparently, it refuses to run unless you give it that code. No problem; you'll just look up the code in the--
"Ho ho ho", Santa ponders aloud. "I can't seem to find the manual."
You look up the support number for the manufacturer and give them a call. Good thing, too - that 49th star wasn't going to earn itself.
"Oh, that machine is quite old!", they tell you. "That model went out of support six minutes ago, and we just finished shredding all of the manuals. I bet we can find you the code generation algorithm, though."
After putting you on hold for twenty minutes (your call is very important to them, it reminded you repeatedly), they finally find an engineer that remembers how the code system works.
The codes are printed on an infinite sheet of paper, starting in the top-left corner. The codes are filled in by diagonals: starting with the first row with an empty first box, the codes are filled in diagonally up and to the right. This process repeats until the infinite paper is covered. So, the first few codes are filled in in this order:
| 1 2 3 4 5 6
---+---+---+---+---+---+---+
1 | 1 3 6 10 15 21
2 | 2 5 9 14 20
3 | 4 8 13 19
4 | 7 12 18
5 | 11 17
6 | 16
For example, the 12th code would be written to row 4, column 2; the 15th code would be written to row 1, column 5.
The voice on the other end of the phone continues with how the codes are actually generated. The first code is 20151125. After that, each code is generated by taking the previous one, multiplying it by 252533, and then keeping the remainder from dividing that value by 33554393.
So, to find the second code (which ends up in row 2, column 1), start with the previous value, 20151125. Multiply it by 252533 to get 5088824049625. Then, divide that by 33554393, which leaves a remainder of 31916031. That remainder is the second code.
"Oh!", says the voice. "It looks like we missed a scrap from one of the manuals. Let me read it to you." You write down his numbers:
| 1 2 3 4 5 6 ---+---------+---------+---------+---------+---------+---------+ 1 | 20151125 18749137 17289845 30943339 10071777 33511524 2 | 31916031 21629792 16929656 7726640 15514188 4041754 3 | 16080970 8057251 1601130 7981243 11661866 16474243 4 | 24592653 32451966 21345942 9380097 10600672 31527494 5 | 77061 17552253 28094349 6899651 9250759 31663883 6 | 33071741 6796745 25397450 24659492 1534922 27995004
"Now remember", the voice continues, "that's not even all of the first few numbers; for example, you're missing the one at 7,1 that would come before 6,2. But, it should be enough to let your-- oh, it's time for lunch! Bye!" The call disconnects.
Santa looks nervous. Your puzzle input contains the message on the machine's console. What code do you give the machine?
In [54]:
from collections import defaultdict
world = defaultdict(dict)
world[1][1] = 20151125
last = world[1][1]
for diagonal in range(2, 6056):
r = diagonal
c = 1
while c < diagonal + 1:
world[r][c] = (last * 252533) % 33554393
last = world[r][c]
if r == 2978 and c == 3083:
print(last)
r -= 1
c += 1
In [ ]: