--- Day 1: Report Repair ---
After saving Christmas five years in a row, you've decided to take a vacation at a nice resort on a tropical island. Surely, Christmas will go on without you.
The tropical island has its own currency and is entirely cash-only. The gold coins used there have a little picture of a starfish; the locals just call them stars. None of the currency exchanges seem to have heard of them, but somehow, you'll need to find fifty of these coins by the time you arrive so you can pay the deposit on your room.
To save your vacation, you need to get all fifty stars by December 25th.
Collect stars by solving 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!
Before you leave, the Elves in accounting just need you to fix your expense report (your puzzle input); apparently, something isn't quite adding up.
Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.
For example, suppose your expense report contained the following:
1721 979 366 299 675 1456
In this list, the two entries that sum to
299. Multiplying them together produces
1721 * 299 = 514579, so the correct answer is 514579.
Of course, your expense report is much larger. Find the two entries that sum to 2020; what do you get if you multiply them together?
itertools.combinations is what we want here!
Have you seen a list comprehension before?
possible improvements: break the loop early when it finds the first result; try a pure numpy way
--- Part Two ---
The Elves in accounting are thankful for your help; one of them even offers you a starfish coin they had left over from a past vacation. They offer you a second one if you can find three numbers in your expense report that meet the same criteria.
Using the above example again, the three entries that sum to
675. Multiplying them together produces the answer,
In your expense report, what is the product of the three entries that sum to
%timeit to run a line several times to test the speed (words with a
% are line magics)
If you have already created a numpy array with the combinations, it can be done very fast. The slow part is the creation of all the combinations and creating the numpy array.
%%time shows the execution time of the cell (words with
%% are cell magics)
--- Day 2: Password Philosophy ---
Your flight departs in a few days from the coastal airport; the easiest way down to the coast from here is via toboggan.
The shopkeeper at the North Pole Toboggan Rental Shop is having a bad day. "Something's wrong with our computers; we can't log in!" You ask if you can take a look.
Their password database seems to be a little corrupted: some of the passwords wouldn't have been allowed by the Official Toboggan Corporate Policy that was in effect when they were chosen.
To try to debug the problem, they have created a list (your puzzle input) of passwords (according to the corrupted database) and the corporate policy when that password was set.
For example, suppose you have the following list:
1-3 a: abcde 1-3 b: cdefg 2-9 c: ccccccccc
Each line gives the password policy and then the password. The password policy indicates the lowest and highest number of times a given letter must appear for the password to be valid. For example,
1-3 a means that the password must contain
a at least
1 time and at most
In the above example,
2 passwords are valid. The middle password,
cdefg, is not; it contains no instances of
b, but needs at least
1. The first and third passwords are valid: they contain one
a or nine
c, both within the limits of their respective policies.
How many passwords are valid according to their policies?
Can be loaded directly with numpy, but this doesn't really make sense when it is not numeric data
readlines is a convenient file method to read all the lines in a file as a list
Now clean each line for convenience later: remove the trailing
\n newline character, remove the unnecessary colon, and split apart into lists
Loop through each line, using the string method, count, to check the occurrences of the given letter.
optimisations: process the lines as they are read in. Not holding onto all that data would be important if there were too many passwords to check
--- Part Two ---
While it appears you validated the passwords correctly, they don't seem to be what the Official Toboggan Corporate Authentication System is expecting.
The shopkeeper suddenly realizes that he just accidentally explained the password policy rules from his old job at the sled rental place down the street! The Official Toboggan Corporate Policy actually works a little differently.
Each policy actually describes two positions in the password, where
1 means the first character,
2 means the second character, and so on. (Be careful; Toboggan Corporate Policies have no concept of "index zero"!) Exactly one of these positions must contain the given letter. Other occurrences of the letter are irrelevant for the purposes of policy enforcement.
Given the same example list from above:
1-3 a: abcdeis valid: position
1contains a and position
1-3 b: cdefgis invalid: neither position
2-9 c: cccccccccis invalid: both position
How many passwords are valid according to the new interpretation of the policies?
--- Day 3: Toboggan Trajectory ---
With the toboggan login problems resolved, you set off toward the airport. While travel by toboggan might be easy, it's certainly not safe: there's very minimal steering and the area is covered in trees. You'll need to see which angles will take you near the fewest trees.
Due to the local geology, trees in this area only grow on exact integer coordinates in a grid. You make a map (your puzzle input) of the open squares (
.) and trees (
#) you can see. For example:
..##....... #...#...#.. .#....#..#. ..#.#...#.# .#...##..#. ..#.##..... .#.#.#....# .#........# #.##...#... #...##....# .#..#...#.#
These aren't the only trees, though; due to something you read about once involving arboreal genetics and biome stability, the same pattern repeats to the right many times:
..##.........##.........##.........##.........##.........##....... ---> #...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#.. .#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#. ..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.# .#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#. ..#.##.......#.##.......#.##.......#.##.......#.##.......#.##..... ---> .#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....# .#........#.#........#.#........#.#........#.#........#.#........# #.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#... #...##....##...##....##...##....##...##....##...##....##...##....# .#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.# --->
You start on the open square (
.) in the top-left corner and need to reach the bottom (below the bottom-most row on your map).
The toboggan can only follow a few specific slopes (you opted for a cheaper model that prefers rational numbers); start by counting all the trees you would encounter for the slope right 3, down 1:
From your starting position at the top-left, check the position that is right 3 and down 1. Then, check the position that is right 3 and down 1 from there, and so on until you go past the bottom of the map.
The locations you'd check in the above example are marked here with
O where there was an open square and X where there was a tree:
..##.........##.........##.........##.........##.........##....... ---> #..O#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#.. .#....X..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#. ..#.#...#O#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.# .#...##..#..X...##..#..#...##..#..#...##..#..#...##..#..#...##..#. ..#.##.......#.X#.......#.##.......#.##.......#.##.......#.##..... ---> .#.#.#....#.#.#.#.O..#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....# .#........#.#........X.#........#.#........#.#........#.#........# #.##...#...#.##...#...#.X#...#...#.##...#...#.##...#...#.##...#... #...##....##...##....##...#X....##...##....##...##....##...##....# .#..#...#.#.#..#...#.#.#..#...X.#.#..#...#.#.#..#...#.#.#..#...#.# --->
In this example, traversing the map using this slope would cause you to encounter
Starting at the top-left corner of your map and following a slope of right 3 and down 1, how many trees would you encounter?
--- Part Two ---
Time to check the rest of the slopes - you need to minimize the probability of a sudden arboreal stop, after all.
Determine the number of trees you would encounter if, for each of the following slopes, you start at the top-left corner and traverse the map all the way to the bottom:
Right 1, down 1. Right 3, down 1. (This is the slope you already checked.) Right 5, down 1. Right 7, down 1. Right 1, down 2.
In the above example, these slopes would find 2, 7, 3, 4, and 2 tree(s) respectively; multiplied together, these produce the answer 336.
What do you get if you multiply together the number of trees encountered on each of the listed slopes?
--- Day 4: Passport Processing ---
You arrive at the airport only to realize that you grabbed your North Pole Credentials instead of your passport. While these documents are extremely similar, North Pole Credentials aren't issued by a country and therefore aren't actually valid documentation for travel in most of the world.
It seems like you're not the only one having problems, though; a very long line has formed for the automatic passport scanners, and the delay could upset your travel itinerary.
Due to some questionable network security, you realize you might be able to solve both of these problems at the same time.
The automatic passport scanners are slow because they're having trouble detecting which passports have all required fields. The expected fields are as follows:
byr (Birth Year) iyr (Issue Year) eyr (Expiration Year) hgt (Height) hcl (Hair Color) ecl (Eye Color) pid (Passport ID) cid (Country ID)
Passport data is validated in batch files (your puzzle input). Each passport is represented as a sequence of key:value pairs separated by spaces or newlines. Passports are separated by blank lines.
Here is an example batch file containing four passports:
ecl:gry pid:860033327 eyr:2020 hcl:#fffffd byr:1937 iyr:2017 cid:147 hgt:183cm iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884 hcl:#cfa07d byr:1929 hcl:#ae17e1 iyr:2013 eyr:2024 ecl:brn pid:760753108 byr:1931 hgt:179cm hcl:#cfa07d eyr:2025 pid:166559648 iyr:2011 ecl:brn hgt:59in
The first passport is valid - all eight fields are present. The second passport is invalid - it is missing hgt (the Height field).
The third passport is interesting; the only missing field is cid, so it looks like data from North Pole Credentials, not a passport at all! Surely, nobody would mind if you made the system temporarily ignore missing cid fields. Treat this "passport" as valid.
The fourth passport is missing two fields, cid and byr. Missing cid is fine, but missing any other field is not, so this passport is invalid.
According to the above rules, your improved system would report 2 valid passports.
Count the number of valid passports - those that have all required fields. Treat cid as optional. In your batch file, how many passports are valid?
Figure out how to turn each passport into a dictionary
--- Part Two ---
The line is moving more quickly now, but you overhear airport security talking about how passports with invalid data are getting through. Better add some data validation, quick!
You can continue to ignore the cid field, but each other field has strict rules about what values are valid for automatic validation:
byr (Birth Year) - four digits; at least 1920 and at most 2002. iyr (Issue Year) - four digits; at least 2010 and at most 2020. eyr (Expiration Year) - four digits; at least 2020 and at most 2030. hgt (Height) - a number followed by either cm or in: If cm, the number must be at least 150 and at most 193. If in, the number must be at least 59 and at most 76. hcl (Hair Color) - a # followed by exactly six characters 0-9 or a-f. ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth. pid (Passport ID) - a nine-digit number, including leading zeroes. cid (Country ID) - ignored, missing or not.
Your job is to count the passports where all required fields are both present and valid according to the above rules. Here are some example values:
byr valid: 2002 byr invalid: 2003 hgt valid: 60in hgt valid: 190cm hgt invalid: 190in hgt invalid: 190 hcl valid: #123abc hcl invalid: #123abz hcl invalid: 123abc ecl valid: brn ecl invalid: wat pid valid: 000000001 pid invalid: 0123456789
Here are some invalid passports:
eyr:1972 cid:100 hcl:#18171d ecl:amb hgt:170 pid:186cm iyr:2018 byr:1926 iyr:2019 hcl:#602927 eyr:1967 hgt:170cm ecl:grn pid:012533040 byr:1946 hcl:dab227 iyr:2012 ecl:brn hgt:182cm pid:021572410 eyr:2020 byr:1992 cid:277 hgt:59cm ecl:zzz eyr:2038 hcl:74454a iyr:2023 pid:3556412378 byr:2007 Here are some valid passports: pid:087499704 hgt:74in ecl:grn iyr:2012 eyr:2030 byr:1980 hcl:#623a2f eyr:2029 ecl:blu cid:129 byr:1989 iyr:2014 pid:896056539 hcl:#a97842 hgt:165cm hcl:#888785 hgt:164cm byr:2001 iyr:2015 cid:88 pid:545766238 ecl:hzl eyr:2022 iyr:2010 hgt:158cm hcl:#b6652a ecl:blu byr:1944 eyr:2021 pid:093154719
Count the number of valid passports - those that have all required fields and valid values. Continue to treat cid as optional. In your batch file, how many passports are valid?
--- Day 5: Binary Boarding ---
You board your plane only to discover a new problem: you dropped your boarding pass! You aren't sure which seat is yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport control.
You write a quick program to use your phone's camera to scan all of the nearby boarding passes (your puzzle input); perhaps you can find your seat through process of elimination.
Instead of zones or groups, this airline uses binary space partitioning to seat people. A seat might be specified like
F means "front",
B means "back",
L means "left", and
R means "right".
The first 7 characters will either be
B; these specify exactly one of the 128 rows on the plane (numbered
127). Each letter tells you which half of a region the given seat is in. Start with the whole list of rows; the first letter indicates whether the seat is in the front (
63) or the back (
127). The next letter indicates which half of that region the seat is in, and so on until you're left with exactly one row.
For example, consider just the first seven characters of
Start by considering the whole range, rows 0 through 127. F means to take the lower half, keeping rows 0 through 63. B means to take the upper half, keeping rows 32 through 63. F means to take the lower half, keeping rows 32 through 47. B means to take the upper half, keeping rows 40 through 47. B keeps rows 44 through 47. F keeps rows 44 through 45. The final F keeps the lower of the two, row 44.
The last three characters will be either L or R; these specify exactly one of the 8 columns of seats on the plane (numbered 0 through 7). The same process as above proceeds again, this time with only three steps. L means to keep the lower half, while R means to keep the upper half.
For example, consider just the last 3 characters of FBFBBFFRLR:
Start by considering the whole range, columns 0 through 7. R means to take the upper half, keeping columns 4 through 7. L means to take the lower half, keeping columns 4 through 5. The final R keeps the upper of the two, column 5.
So, decoding FBFBBFFRLR reveals that it is the seat at row 44, column 5.
Every seat also has a unique seat ID: multiply the row by 8, then add the column. In this example, the seat has ID 44 * 8 + 5 = 357.
Here are some other boarding passes:
BFFFBBFRRR: row 70, column 7, seat ID 567. FFFBBBFRRR: row 14, column 7, seat ID 119. BBFFBBFRLL: row 102, column 4, seat ID 820.
As a sanity check, look through your list of boarding passes. What is the highest seat ID on a boarding pass?
Let's generalise that a bit more to do columns too
--- Part Two ---
Ding! The "fasten seat belt" signs have turned on. Time to find your seat.
It's a completely full flight, so your seat should be the only missing boarding pass in your list. However, there's a catch: some of the seats at the very front and back of the plane don't exist on this aircraft, so they'll be missing from your list as well.
Your seat wasn't at the very front or back, though; the seats with IDs +1 and -1 from yours will be in your list.
What is the ID of your seat?
A nicer option is to use sets
The cleverer way...
The seat ID codes are actually just binary representations if you map (F, B) to (0, 1) and (L, R) to (0, 1) !
--- Day 6: Custom Customs ---
As your flight approaches the regional airport where you'll switch to a much larger plane, customs declaration forms are distributed to the passengers.
The form asks a series of 26 yes-or-no questions marked
z. All you need to do is identify the questions for which anyone in your group answers "yes". Since your group is just you, this doesn't take very long.
However, the person sitting next to you seems to be experiencing a language barrier and asks if you can help. For each of the people in their group, you write down the questions for which they answer "yes", one per line. For example:
abcx abcy abcz
In this group, there are 6 questions to which anyone answered "yes": a, b, c, x, y, and z. (Duplicate answers to the same question don't count extra; each question counts at most once.)
Another group asks for your help, then another, and eventually you've collected answers from every group on the plane (your puzzle input). Each group's answers are separated by a blank line, and within each group, each person's answers are on a single line. For example:
abc a b c ab ac a a a a b
This list represents answers from five groups:
- The first group contains one person who answered "yes" to 3 questions: a, b, and c.
- The second group contains three people; combined, they answered "yes" to 3 questions: a, b, and c.
- The third group contains two people; combined, they answered "yes" to 3 questions: a, b, and c.
- The fourth group contains four people; combined, they answered "yes" to only 1 question, a.
- The last group contains one person who answered "yes" to only 1 question, b.
In this example, the sum of these counts is 3 + 3 + 3 + 1 + 1 = 11.
For each group, count the number of questions to which anyone answered "yes". What is the sum of those counts?
sets can be used to identify unique elements in a list
--- Part Two ---
As you finish the last group's customs declaration, you notice that you misread one word in the instructions:
You don't need to identify the questions to which anyone answered "yes"; you need to identify the questions to which everyone answered "yes"!
Using the same example as above:
abc a b c ab ac a a a a b
This list represents answers from five groups:
- In the first group, everyone (all 1 person) answered "yes" to 3 questions: a, b, and c.
- In the second group, there is no question to which everyone answered "yes".
- In the third group, everyone answered yes to only 1 question, a. Since some people did not answer "yes" to b or c, they don't count.
- In the fourth group, everyone answered yes to only 1 question, a.
- In the fifth group, everyone (all 1 person) answered "yes" to 1 question, b.
In this example, the sum of these counts is 3 + 0 + 1 + 1 + 1 = 6.
For each group, count the number of questions to which everyone answered "yes". What is the sum of those counts?
--- Day 7: Handy Haversacks ---
You land at the regional airport in time for your next flight. In fact, it looks like you'll even have time to grab some food: all flights are currently delayed due to issues in luggage processing.
Due to recent aviation regulations, many rules (your puzzle input) are being enforced about bags and their contents; bags must be color-coded and must contain specific quantities of other color-coded bags. Apparently, nobody responsible for these regulations considered how long they would take to enforce!
For example, consider the following rules:
light red bags contain 1 bright white bag, 2 muted yellow bags. dark orange bags contain 3 bright white bags, 4 muted yellow bags. bright white bags contain 1 shiny gold bag. muted yellow bags contain 2 shiny gold bags, 9 faded blue bags. shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags. dark olive bags contain 3 faded blue bags, 4 dotted black bags. vibrant plum bags contain 5 faded blue bags, 6 dotted black bags. faded blue bags contain no other bags. dotted black bags contain no other bags.
These rules specify the required contents for 9 bag types. In this example, every
faded blue bag is empty, every
vibrant plum bag contains 11 bags (5
faded blue and 6
dotted black), and so on.
You have a
shiny gold bag. If you wanted to carry it in at least one other bag, how many different bag colors would be valid for the outermost bag? (In other words: how many colors can, eventually, contain at least one
shiny gold bag?)
In the above rules, the following options would be available to you:
bright whitebag, which can hold your
shiny goldbag directly.
muted yellowbag, which can hold your
shiny goldbag directly, plus some other bags.
dark orangebag, which can hold
muted yellowbags, either of which could then hold your
light redbag, which can hold
muted yellowbags, either of which could then hold your
So, in this example, the number of bag colors that can eventually contain at least one
shiny gold bag is
How many bag colors can eventually contain at least one
shiny gold bag? (The list of rules is quite long; make sure you get all of it.)
Now we can pull out information like this...
(I really need to learn regex...)
Can we construct a class that holds this information for every bag...
Now we have a data structure that can contain the full stack of contents of a particular bag color!
(and so on going deeper...)
Let's create a list of all the bags
I added the
.dig_for_gold() method that recursively searches the bags and returns
True if it finds a
shiny gold bag at some point.
Finally got it!
--- Part Two ---
It's getting pretty expensive to fly these days - not because of ticket prices, but because of the ridiculous number of bags you need to buy!
Consider again your
shiny gold bag and the rules from the above example:
faded bluebags contain
dotted blackbags contain
vibrant plumbags contain
11other bags: 5
faded bluebags and 6
dark olivebags contain
7other bags: 3
faded bluebags and 4
So, a single
shiny gold bag must contain 1
dark olive bag (and the 7 bags within it) plus 2
vibrant plum bags (and the 11 bags within each of those):
1 + 1*7 + 2 + 2*11 =
Of course, the actual rules have a small chance of going several levels deeper than this example; be sure to count all of the bags, even if the nesting becomes topologically impractical!
Here's another example:
shiny gold bags contain 2 dark red bags. dark red bags contain 2 dark orange bags. dark orange bags contain 2 dark yellow bags. dark yellow bags contain 2 dark green bags. dark green bags contain 2 dark blue bags. dark blue bags contain 2 dark violet bags. dark violet bags contain no other bags.
In this example, a
single shiny gold bag must contain
126 other bags.
How many individual bags are required inside your single shiny gold bag?
Adjust the class from before to instead count bags...
This the number of bags within a gold bag, plus the gold bag itself
so the answer is 12414
That hurt my brain
Your flight to the major airline hub reaches cruising altitude without incident. While you consider checking the in-flight menu for one of those drinks that come with a little umbrella, you are interrupted by the kid sitting next to you.
Their handheld game console won't turn on! They ask if you can take a look.
You narrow the problem down to a strange infinite loop in the boot code (your puzzle input) of the device. You should be able to fix it, but first you need to be able to run the code in isolation.
The boot code is represented as a text file with one instruction per line of text. Each instruction consists of an operation (
nop) and an argument (a signed number like
accincreases or decreases a single global value called the accumulator by the value given in the argument. For example,
acc +7would increase the accumulator by 7. The accumulator starts at
0. After an
accinstruction, the instruction immediately below it is executed next.
jmpjumps to a new instruction relative to itself. The next instruction to execute is found using the argument as an offset from the
jmpinstruction; for example,
jmp +2would skip the next instruction,
jmp +1would continue to the instruction immediately below it, and
jmp -20would cause the instruction 20 lines above to be executed next.
nopstands for No OPeration - it does nothing. The instruction immediately below it is executed next.
For example, consider the following program:
nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6
These instructions are visited in this order:
nop +0 | 1 acc +1 | 2, 8(!) jmp +4 | 3 acc +3 | 6 jmp -3 | 7 acc -99 | acc +1 | 4 jmp -4 | 5 acc +6 |
nop +0 does nothing. Then, the accumulator is increased from 0 to 1 (
acc +1) and
jmp +4 sets the next instruction to the other
acc +1 near the bottom. After it increases the accumulator from 1 to 2,
jmp -4 executes, setting the next instruction to the only
acc +3. It sets the accumulator to 5, and
jmp -3 causes the program to continue back at the first
This is an infinite loop: with this sequence of jumps, the program will run forever. The moment the program tries to run any instruction a second time, you know it will never terminate.
Immediately before the program would run an instruction a second time, the value in the accumulator is
Run your copy of the boot code. Immediately before any instruction is executed a second time, what value is in the accumulator?
--- Part Two ---
After some careful analysis, you believe that exactly one instruction is corrupted.
Somewhere in the program, either a
jmp is supposed to be a
nop, or a
nop is supposed to be a
acc instructions were harmed in the corruption of this boot code.)
The program is supposed to terminate by attempting to execute an instruction immediately after the last instruction in the file. By changing exactly one
nop, you can repair the boot code and make it terminate correctly.
For example, consider the same program from above:
nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6
If you change the first instruction from
nop +0 to
jmp +0, it would create a single-instruction infinite loop, never leaving that instruction. If you change almost any of the
jmp instructions, the program will still eventually find another
jmp instruction and loop forever.
However, if you change the second-to-last instruction (from
jmp -4 to
nop -4), the program terminates! The instructions are visited in this order:
nop +0 | 1 acc +1 | 2 jmp +4 | 3 acc +3 | jmp -3 | acc -99 | acc +1 | 4 nop -4 | 5 acc +6 | 6
After the last instruction (
acc +6), the program terminates by attempting to run the instruction below the last instruction in the file. With this change, after the program terminates, the accumulator contains the value
Fix the program so that it terminates normally by changing exactly one
jmp). What is the value of the accumulator after the program terminates?
extend the class to let it identify an ending state (
ProgramEndError) and to modify itself
--- Day 9: Encoding Error ---
With your neighbor happily enjoying their video game, you turn your attention to an open data port on the little screen in the seat in front of you.
Though the port is non-standard, you manage to connect it to your computer through the clever use of several paperclips. Upon connection, the port outputs a series of numbers (your puzzle input).
The data appears to be encrypted with the eXchange-Masking Addition System (XMAS) which, conveniently for you, is an old cypher with an important weakness.
XMAS starts by transmitting a preamble of 25 numbers. After that, each number you receive should be the sum of any two of the 25 immediately previous numbers. The two numbers will have different values, and there might be more than one such pair.
For example, suppose your preamble consists of the numbers 1 through 25 in a random order. To be valid, the next number must be the sum of two of those numbers:
26would be a valid next number, as it could be
25(or many other pairs, like
49would be a valid next number, as it is the sum of
100would not be valid; no two of the previous 25 numbers sum to
50would also not be valid; although
25appears in the previous 25 numbers, the two numbers in the pair must be different.
Suppose the 26th number is
45, and the first number (no longer an option, as it is more than 25 numbers ago) was
20. Now, for the next number to be valid, there needs to be some pair of numbers among
45 that add up to it:
26would still be a valid next number, as
25are still within the previous 25 numbers.
65would not be valid, as no two of the available numbers sum to it.
66would both be valid, as they are the result of
Here is a larger example which only considers the previous 5 numbers (and has a preamble of length 5):
35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576
In this example, after the 5-number preamble, almost every number is the sum of two of the previous 5 numbers; the only number that does not follow this rule is
The first step of attacking the weakness in the XMAS data is to find the first number in the list (after the preamble) which is not the sum of two of the 25 numbers before it. What is the first number that does not have this property?
--- Part Two ---
The final step in breaking the XMAS encryption relies on the invalid number you just found: you must find a contiguous set of at least two numbers in your list which sum to the invalid number from step 1.
Again consider the above example:
35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576
In this list, adding up all of the numbers from
40 produces the invalid number from step 1,
127. (Of course, the contiguous set of numbers in your actual list might be much longer.)
To find the encryption weakness, add together the smallest and largest number in this contiguous range; in this example, these are
What is the encryption weakness in your XMAS-encrypted list of numbers?
--- Day 10: Adapter Array ---
Patched into the aircraft's data port, you discover weather forecasts of a massive tropical storm. Before you can figure out whether it will impact your vacation plans, however, your device suddenly turns off!
Its battery is dead.
You'll need to plug it in. There's only one problem: the charging outlet near your seat produces the wrong number of jolts. Always prepared, you make a list of all of the joltage adapters in your bag.
Each of your joltage adapters is rated for a specific output joltage (your puzzle input). Any given adapter can take an input
3 jolts lower than its rating and still produce its rated output joltage.
In addition, your device has a built-in joltage adapter rated for
3 jolts higher than the highest-rated adapter in your bag. (If your adapter list were
6, your device's built-in adapter would be rated for
Treat the charging outlet near your seat as having an effective joltage rating of
Since you have some time to kill, you might as well test all of your adapters. Wouldn't want to get to your resort and realize you can't even charge your device!
If you use every adapter in your bag at once, what is the distribution of joltage differences between the charging outlet, the adapters, and your device?
For example, suppose that in your bag, you have adapters with the following joltage ratings:
16 10 15 5 1 11 7 19 6 12 4
With these adapters, your device's built-in joltage adapter would be rated for
19 + 3 = 22 jolts, 3 higher than the highest-rated adapter.
Because adapters can only connect to a source 1-3 jolts lower than its rating, in order to use every adapter, you'd need to choose them like this:
- The charging outlet has an effective rating of
0jolts, so the only adapters that could connect to it directly would need to have a joltage rating of
3jolts. Of these, only one you have is an adapter rated
1jolt (difference of
- From your
1-jolt rated adapter, the only choice is your
4-jolt rated adapter (difference of
- From the
4-jolt rated adapter, the adapters rated
7are valid choices. However, in order to not skip any adapters, you have to pick the adapter rated
5jolts (difference of
- Similarly, the next choices would need to be the adapter rated
6and then the adapter rated
7(with difference of
- The only adapter that works with the
7-jolt rated adapter is the one rated
10jolts (difference of
10, the choices are
1) and then
12, only valid adapter has a rating of
- Finally, your device's built-in adapter is always
3higher than the highest adapter, so its rating is
22jolts (always a difference of
In this example, when using every adapter, there are
7 differences of 1 jolt and 5
differences of 3 jolts.
Here is a larger example:
28 33 18 42 31 14 46 20 48 47 24 23 49 45 19 38 39 11 1 32 25 35 8 17 7 9 4 2 34 10 3
In this larger example, in a chain that uses all of the adapters, there are
22 differences of 1 jolt and
10 differences of 3 jolts.
Find a chain that uses all of your adapters to connect the charging outlet to your device's built-in adapter and count the joltage differences between the charging outlet, the adapters, and your device. What is the number of 1-jolt differences multiplied by the number of 3-jolt differences?
--- Part Two ---
To completely determine whether you have enough adapters, you'll need to figure out how many different ways they can be arranged. Every arrangement needs to connect the charging outlet to your device. The previous rules about when adapters can successfully connect still apply.
The first example above (the one that starts with
15) supports the following arrangements:
(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22) (0), 1, 4, 5, 6, 7, 10, 12, 15, 16, 19, (22) (0), 1, 4, 5, 7, 10, 11, 12, 15, 16, 19, (22) (0), 1, 4, 5, 7, 10, 12, 15, 16, 19, (22) (0), 1, 4, 6, 7, 10, 11, 12, 15, 16, 19, (22) (0), 1, 4, 6, 7, 10, 12, 15, 16, 19, (22) (0), 1, 4, 7, 10, 11, 12, 15, 16, 19, (22) (0), 1, 4, 7, 10, 12, 15, 16, 19, (22)
(The charging outlet and your device's built-in adapter are shown in parentheses.) Given the adapters from the first example, the total number of arrangements that connect the charging outlet to your device is
The second example above (the one that starts with 28, 33, 18) has many arrangements. Here are a few:
(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 46, 47, 48, 49, (52) (0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 46, 47, 49, (52) (0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 46, 48, 49, (52) (0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 46, 49, (52) (0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 47, 48, 49, (52) (0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 46, 48, 49, (52) (0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 46, 49, (52) (0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 47, 48, 49, (52) (0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 47, 49, (52) (0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45, 48, 49, (52)
In total, this set of adapters can connect the charging outlet to your device in
19208 distinct arrangements.
You glance back down at your bag and try to remember why you brought so many adapters; there must be more than a trillion valid ways to arrange them! Surely, there must be an efficient way to count the arrangements.
What is the total number of distinct ways you can arrange the adapters to connect the charging outlet to your device?
There are too many combinations to exhaustively search them. But there are tight constraints that must be met: the boundaries
end+3 must be satisfied, and differences can be no bigger than
3. We can determine the solution from the differences alone - we don't need the original numbers.
Locations with a diff of
3 can't change. Blocks with diffs of
2 have a certain number of shorter arrangements...
--- Day 11: Seating System ---
Your plane lands with plenty of time to spare. The final leg of your journey is a ferry that goes directly to the tropical island where you can finally start your vacation. As you reach the waiting area to board the ferry, you realize you're so early, nobody else has even arrived yet!
By modeling the process people use to choose (or abandon) their seat in the waiting area, you're pretty sure you can predict the best place to sit. You make a quick map of the seat layout (your puzzle input).
The seat layout fits neatly on a grid. Each position is either floor (
.), an empty seat (
L), or an occupied seat (
#). For example, the initial seat layout might look like this:
L.LL.LL.LL LLLLLLL.LL L.L.L..L.. LLLL.LL.LL L.LL.LL.LL L.LLLLL.LL ..L.L..... LLLLLLLLLL L.LLLLLL.L L.LLLLL.LL
Now, you just need to model the people who will be arriving shortly. Fortunately, people are entirely predictable and always follow a simple set of rules. All decisions are based on the number of occupied seats adjacent to a given seat (one of the eight positions immediately up, down, left, right, or diagonal from the seat). The following rules are applied to every seat simultaneously:
- If a seat is empty (
L) and there are no occupied seats adjacent to it, the seat becomes occupied.
- If a seat is occupied (
#) and four or more seats adjacent to it are also occupied, the seat becomes empty.
- Otherwise, the seat's state does not change.
.) never changes; seats don't move, and nobody sits on the floor.
After one round of these rules, every seat in the example layout becomes occupied:
#.##.##.## #######.## #.#.#..#.. ####.##.## #.##.##.## #.#####.## ..#.#..... ########## #.######.# #.#####.##
After a second round, the seats with four or more occupied adjacent seats become empty again:
#.LL.L#.## #LLLLLL.L# L.L.L..L.. #LLL.LL.L# #.LL.LL.LL #.LLLL#.## ..L.L..... #LLLLLLLL# #.LLLLLL.L #.#LLLL.##
This process continues for three more rounds:
#.##.L#.## #L###LL.L# L.#.#..#.. #L##.##.L# #.##.LL.LL #.###L#.## ..#.#..... #L######L# #.LL###L.L #.#L###.##
#.#L.L#.## #LLL#LL.L# L.L.L..#.. #LLL.##.L# #.LL.LL.LL #.LL#L#.## ..L.L..... #L#LLLL#L# #.LLLLLL.L #.#L#L#.##
#.#L.L#.## #LLL#LL.L# L.#.L..#.. #L##.##.L# #.#L.LL.LL #.#L#L#.## ..L.L..... #L#L##L#L# #.LLLLLL.L #.#L#L#.##
At this point, something interesting happens: the chaos stabilizes and further applications of these rules cause no seats to change state! Once people stop moving around, you count
37 occupied seats.
Simulate your seating area by applying the seating rules repeatedly until no seats change state. How many seats end up occupied?
--- Part Two ---
As soon as people start to arrive, you realize your mistake. People don't just care about adjacent seats - they care about the first seat they can see in each of those eight directions!
Now, instead of considering just the eight immediately adjacent seats, consider the first seat in each of those eight directions. For example, the empty seat below would see eight occupied seats:
.......#. ...#..... .#....... ......... ..#L....# ....#.... ......... #........ ...#.....
The leftmost empty seat below would only see one empty seat, but cannot see any of the occupied ones:
............. .L.L.#.#.#.#. .............
The empty seat below would see no occupied seats:
.##.##. #.#.#.# ##...## ...L... ##...## #.#.#.# .##.##.
Also, people seem to be more tolerant than you expected: it now takes five or more visible occupied seats for an occupied seat to become empty (rather than four or more from the previous rules). The other rules still apply: empty seats that see no occupied seats become occupied, seats matching no rule don't change, and floor never changes.
Given the same starting layout as above, these new rules cause the seating area to shift around as follows:
L.LL.LL.LL LLLLLLL.LL L.L.L..L.. LLLL.LL.LL L.LL.LL.LL L.LLLLL.LL ..L.L..... LLLLLLLLLL L.LLLLLL.L L.LLLLL.LL #.##.##.## #######.## #.#.#..#.. ####.##.## #.##.##.## #.#####.## ..#.#..... ########## #.######.# #.#####.## #.LL.LL.L# #LLLLLL.LL L.L.L..L.. LLLL.LL.LL L.LL.LL.LL L.LLLLL.LL ..L.L..... LLLLLLLLL# #.LLLLLL.L #.LLLLL.L# #.L#.##.L# #L#####.LL L.#.#..#.. ##L#.##.## #.##.#L.## #.#####.#L ..#.#..... LLL####LL# #.L#####.L #.L####.L# #.L#.L#.L# #LLLLLL.LL L.L.L..#.. ##LL.LL.L# L.LL.LL.L# #.LLLLL.LL ..L.L..... LLLLLLLLL# #.LLLLL#.L #.L#LL#.L# #.L#.L#.L# #LLLLLL.LL L.L.L..#.. ##L#.#L.L# L.L#.#L.L# #.L####.LL ..#.#..... LLL###LLL# #.LLLLL#.L #.L#LL#.L# #.L#.L#.L# #LLLLLL.LL L.L.L..#.. ##L#.#L.L# L.L#.LL.L# #.LLLL#.LL ..#.L..... LLL###LLL# #.LLLLL#.L #.L#LL#.L#
Again, at this point, people stop shifting around and the seating area reaches equilibrium. Once this occurs, you count
26 occupied seats.
Given the new visibility method and the rule change for occupied seats becoming empty, once equilibrium is reached, how many seats end up occupied?
--- Day 12: Rain Risk ---
Your ferry made decent progress toward the island, but the storm came in faster than anyone expected. The ferry needs to take evasive actions!
Unfortunately, the ship's navigation computer seems to be malfunctioning; rather than giving a route directly to safety, it produced extremely circuitous instructions. When the captain uses the PA system to ask if anyone can help, you quickly volunteer.
The navigation instructions (your puzzle input) consists of a sequence of single-character actions paired with integer input values. After staring at them for a few minutes, you work out what they probably mean:
Nmeans to move
northby the given value.
Smeans to move
southby the given value.
Emeans to move
eastby the given value.
Wmeans to move
westby the given value.
Lmeans to turn
leftthe given number of degrees.
Rmeans to turn
rightthe given number of degrees.
Fmeans to move
forwardby the given value in the direction the ship is currently facing.
The ship starts by facing
east. Only the
R actions change the direction the ship is facing. (That is, if the ship is facing east and the next instruction is
N10, the ship would move north 10 units, but would still move east if the following action were
F10 N3 F7 R90 F11
These instructions would be handled as follows:
F10would move the ship 10 units east (because the ship starts by facing east) to east 10, north 0.
N3would move the ship 3 units north to east 10, north 3.
F7would move the ship another 7 units east (because the ship is still facing east) to east 17, north 3.
R90would cause the ship to turn right by 90 degrees and face south; it remains at east 17, north 3.
F11would move the ship 11 units south to east 17, south 8.
At the end of these instructions, the ship's Manhattan distance (sum of the absolute values of its east/west position and its north/south position) from its starting position is
17 + 8 =
Figure out where the navigation instructions lead. What is the Manhattan distance between that location and the ship's starting position?
--- Part Two ---
Before you can give the destination to the captain, you realize that the actual action meanings were printed on the back of the instructions the whole time.
Almost all of the actions indicate how to move a waypoint which is relative to the ship's position:
Nmeans to move the waypoint north by the given value.
Smeans to move the waypoint south by the given value.
Emeans to move the waypoint east by the given value.
Wmeans to move the waypoint west by the given value.
Lmeans to rotate the waypoint around the ship left (counter-clockwise) the given number of degrees.
Rmeans to rotate the waypoint around the ship right (clockwise) the given number of degrees.
Fmeans to move forward to the waypoint a number of times equal to the given value.
The waypoint starts 10 units east and 1 unit north relative to the ship. The waypoint is relative to the ship; that is, if the ship moves, the waypoint moves with it.
For example, using the same instructions as above:
F10moves the ship to the waypoint 10 times (a total of 100 units east and 10 units north), leaving the ship at east 100, north 10. The waypoint stays 10 units east and 1 unit north of the ship.
N3moves the waypoint 3 units north to 10 units east and 4 units north of the ship. The ship remains at east 100, north 10.
F7moves the ship to the waypoint 7 times (a total of 70 units east and 28 units north), leaving the ship at east 170, north 38. The waypoint stays 10 units east and 4 units north of the ship.
R90rotates the waypoint around the ship clockwise 90 degrees, moving it to 4 units east and 10 units south of the ship. The ship remains at east 170, north 38.
F11moves the ship to the waypoint 11 times (a total of 44 units east and 110 units south), leaving the ship at east 214, south 72. The waypoint stays 4 units east and 10 units south of the ship.
After these operations, the ship's Manhattan distance from its starting position is
214 + 72 =
Figure out where the navigation instructions actually lead. What is the Manhattan distance between that location and the ship's starting position?
--- Day 13: Shuttle Search ---
Your ferry can make it safely to a nearby port, but it won't get much further. When you call to book another ship, you discover that no ships embark from that port to your vacation island. You'll need to get from the port to the nearest airport.
Fortunately, a shuttle bus service is available to bring you from the sea port to the airport! Each bus has an ID number that also indicates how often the bus leaves for the airport.
Bus schedules are defined based on a timestamp that measures the number of minutes since some fixed reference point in the past. At timestamp
0, every bus simultaneously departed from the sea port. After that, each bus travels to the airport, then various other locations, and finally returns to the sea port to repeat its journey forever.
The time this loop takes a particular bus is also its ID number: the bus with ID
5 departs from the sea port at timestamps
15, and so on. The bus with ID
11 departs at
33, and so on. If you are there when the bus departs, you can ride that bus to the airport!
Your notes (your puzzle input) consist of two lines. The first line is your estimate of the earliest timestamp you could depart on a bus. The second line lists the bus IDs that are in service according to the shuttle company; entries that show
x must be out of service, so you decide to ignore them.
To save time once you arrive, your goal is to figure out the earliest bus you can take to the airport. (There will be exactly one such bus.)
For example, suppose you have the following notes:
Here, the earliest timestamp you could depart is
939, and the bus IDs in service are
19. Near timestamp
939, these bus IDs depart at the times marked D:
time bus 7 bus 13 bus 59 bus 31 bus 19 929 . . . . . 930 . . . D . 931 D . . . D 932 . . . . . 933 . . . . . 934 . . . . . 935 . . . . . 936 . D . . . 937 . . . . . 938 D . . . . 939 . . . . . 940 . . . . . 941 . . . . . 942 . . . . . 943 . . . . . 944 . . D . . 945 D . . . . 946 . . . . . 947 . . . . . 948 . . . . . 949 . D . . .
The earliest bus you could take is bus ID
59. It doesn't depart until timestamp
944, so you would need to wait
944 - 939 = 5 minutes before it departs. Multiplying the bus ID by the number of minutes you'd need to wait gives
What is the ID of the earliest bus you can take to the airport multiplied by the number of minutes you'll need to wait for that bus?
--- Part Two ---
The shuttle company is running a contest: one gold coin for anyone that can find the earliest timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs at that subsequent minute. (The first line in your input is no longer relevant.)
For example, suppose you have the same list of bus IDs as above:
An x in the schedule means there are no constraints on what bus IDs must depart at that time.
This means you are looking for the earliest timestamp (called t) such that:
- Bus ID
7departs at timestamp
- Bus ID
13departs one minute after timestamp
- There are no requirements or restrictions on departures at two or three minutes after timestamp
- Bus ID
59departs four minutes after timestamp
- There are no requirements or restrictions on departures at five minutes after timestamp
- Bus ID
31departs six minutes after timestamp
- Bus ID
19departs seven minutes after timestamp
The only bus departures that matter are the listed bus IDs at their specific offsets from
t. Those bus IDs can depart at other times, and other bus IDs can depart at those times. For example, in the list above, because bus ID 19 must depart seven minutes after the timestamp at which bus ID 7 departs, bus ID 7 will always also be departing with bus ID 19 at seven minutes after timestamp t.
In this example, the earliest timestamp at which this occurs is
time bus 7 bus 13 bus 59 bus 31 bus 19 1068773 . . . . . 1068774 D . . . . 1068775 . . . . . 1068776 . . . . . 1068777 . . . . . 1068778 . . . . . 1068779 . . . . . 1068780 . . . . . 1068781 D . . . . 1068782 . D . . . 1068783 . . . . . 1068784 . . . . . 1068785 . . D . . 1068786 . . . . . 1068787 . . . D . 1068788 D . . . D 1068789 . . . . . 1068790 . . . . . 1068791 . . . . . 1068792 . . . . . 1068793 . . . . . 1068794 . . . . . 1068795 D D . . . 1068796 . . . . . 1068797 . . . . .
In the above example, bus ID 7 departs at timestamp 1068788 (seven minutes after t). This is fine; the only requirement on that minute is that bus ID 19 departs then, and it does.
Here are some other examples:
- The earliest timestamp that matches the list
67,7,59,61first occurs at timestamp
67,x,7,59,61first occurs at timestamp
67,7,x,59,61first occurs at timestamp
1789,37,47,1889first occurs at timestamp
However, with so many bus IDs in your list, surely the actual earliest timestamp will be larger than
What is the earliest timestamp such that all of the listed bus IDs depart at offsets matching their positions in the list?