Advent of Code 2022
Intro
This notebook contains the solutions to the Advent of Code 2022 problems. The repository with source code for this notebook (and solutions for AoC 2020) can be found here.
From Wikipedia: Advent of Code is an annual set of Christmas-themed computer programming challenges that follow an Advent calendar. It has been running since 2015.
Summary
I got busy and had to skip a week of answers - hence why not all problems are solved yet.
| Week 1 | Week 2 | Week 3 | Week 4 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|
Day 1: Calorie Counting
Part one ⭐
The jungle must be too overgrown and difficult to navigate in vehicles or access from the air; the Elves’ expedition traditionally goes on foot. As your boats approach land, the Elves begin taking inventory of their supplies. One important consideration is food - in particular, the number of Calories each Elf is carrying (your puzzle input).
The Elves take turns writing down the number of Calories contained by the various meals, snacks, rations, etc. that they’ve brought with them, one item per line. Each Elf separates their own inventory from the previous Elf’s inventory (if any) by a blank line.
For example, suppose the Elves finish writing their items’ Calories and end up with the following list:
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000This list represents the Calories of the food carried by five Elves:
- The first Elf is carrying food with
1000,2000, and3000Calories, a total of6000Calories.
- The second Elf is carrying one food item with
4000Calories.
- The third Elf is carrying food with
5000and6000Calories, a total of11000Calories.
- The fourth Elf is carrying food with
7000,8000, and9000Calories, a total of24000Calories. The fifth Elf is carrying one food item with10000Calories. In case the Elves get hungry and need extra snacks, they need to know which Elf to ask: they’d like to know how many Calories are being carried by the Elf carrying the most Calories. In the example above, this is24000(carried by the fourth Elf).
Find the Elf carrying the most Calories. How many total Calories is that Elf carrying?
def max_calories_snacks(input_file):
snacks = []
i = 0
start = True
with open(input_file, "r+") as f:
lines = [line.rstrip() for line in f]
for line in lines:
if line == "":
i += 1
else:
if len(snacks) > i:
snacks[i].append(int(line))
else:
snacks.append([int(line)])
sum_snacks = [sum(snacks_) for snacks_ in snacks]
max_calories = max(sum_snacks)
return max_calories
# passing test?
max_calories_snacks("inputs/01_test_case.txt") == 24000Truemax_calories_snacks("inputs/01_input.txt")69528Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
By the time you calculate the answer to the Elves’ question, they’ve already realized that the Elf carrying the most Calories of food might eventually run out of snacks.
To avoid this unacceptable situation, the Elves would instead like to know the total Calories carried by the top three Elves carrying the most Calories. That way, even if one of those Elves runs out of snacks, they still have two backups.
In the example above, the top three Elves are the fourth Elf (with 24000 Calories), then the third Elf (with 11000 Calories), then the fifth Elf (with 10000 Calories). The sum of the Calories carried by these three elves is 45000.
Find the top three Elves carrying the most Calories. How many Calories are those Elves carrying in total?
def nmax_calories_snacks(input_file, n):
snacks = []
i = 0
start = True
with open(input_file, "r+") as f:
lines = [line.rstrip() for line in f]
for line in lines:
if line == "":
i += 1
else:
if len(snacks) > i:
snacks[i].append(int(line))
else:
snacks.append([int(line)])
sum_snacks = [sum(snacks_) for snacks_ in snacks]
sum_snacks.sort(reverse=True)
return sum(sum_snacks[:n])
# passing test?
nmax_calories_snacks("inputs/01_test_case.txt", 2) == 35000Truenmax_calories_snacks("inputs/01_input.txt", 3)206152Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Day 2: Rock Paper Scissors
Part one ⭐
The Elves begin to set up camp on the beach. To decide whose tent gets to be closest to the snack storage, a giant Rock Paper Scissors tournament is already in progress.
Rock Paper Scissors is a game between two players. Each game contains many rounds; in each round, the players each simultaneously choose one of Rock, Paper, or Scissors using a hand shape. Then, a winner for that round is selected: Rock defeats Scissors, Scissors defeats Paper, and Paper defeats Rock. If both players choose the same shape, the round instead ends in a draw.
Appreciative of your help yesterday, one Elf gives you an encrypted strategy guide (your puzzle input) that they say will be sure to help you win. “The first column is what your opponent is going to play: A for Rock, B for Paper, and C for Scissors. The second column–” Suddenly, the Elf is called away to help with someone’s tent.
The second column, you reason, must be what you should play in response: X for Rock, Y for Paper, and Z for Scissors. Winning every time would be suspicious, so the responses must have been carefully chosen.
The winner of the whole tournament is the player with the highest score. Your total score is the sum of your scores for each round. The score for a single round is the score for the shape you selected (1 for Rock, 2 for Paper, and 3 for Scissors) plus the score for the outcome of the round (0 if you lost, 3 if the round was a draw, and 6 if you won).
Since you can’t be sure if the Elf is trying to help you or trick you, you should calculate the score you would get if you were to follow the strategy guide.
For example, suppose you were given the following strategy guide:
A Y
B X
C ZThis strategy guide predicts and recommends the following:
- In the first round, your opponent will choose Rock (
A), and you should choose Paper (Y). This ends in a win for you with a score of 8 (2 because you chose Paper + 6 because you won).
- In the second round, your opponent will choose Paper (
B), and you should choose Rock (X). This ends in a loss for you with a score of 1 (1 + 0).
- The third round is a draw with both players choosing Scissors, giving you a score of 3 + 3 = 6.
In this example, if you were to follow the strategy guide, you would get a total score of 15 (8 + 1 + 6).
What would your total score be if everything goes exactly according to your strategy guide?
def rps(input_file):
outcomes = {"A": {"X": 3+1, "Y": 6+2, "Z": 0+3},
"B": {"X": 0+1, "Y": 3+2, "Z": 6+3},
"C": {"X": 6+1, "Y": 0+2, "Z": 3+3}}
scores = []
with open(input_file, "r+") as f:
for line in f.readlines():
game = line.rstrip().split(" ")
scores.append(outcomes[game[0]][game[1]])
return sum(scores)
rps("inputs/02_test_case.txt") == 15Truerps("inputs/02_input.txt")14264Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
The Elf finishes helping with the tent and sneaks back over to you. “Anyway, the second column says how the round needs to end: X means you need to lose, Y means you need to end the round in a draw, and Z means you need to win. Good luck!”
The total score is still calculated in the same way, but now you need to figure out what shape to choose so the round ends as indicated. The example above now goes like this:
- In the first round, your opponent will choose Rock (
A), and you need the round to end in a draw (Y), so you also choose Rock. This gives you a score of 1 + 3 = 4.
- In the second round, your opponent will choose Paper (
B), and you choose Rock so you lose (X) with a score of 1 + 0 = 1.
- In the third round, you will defeat your opponent’s Scissors with Rock for a score of 1 + 6 = 7.
Now that you’re correctly decrypting the ultra top secret strategy guide, you would get a total score of 12.
Following the Elf’s instructions for the second column, what would your total score be if everything goes exactly according to your strategy guide?
def rps_modified(input_file):
outcomes = {"A": {"X": 0+3, # lose (0) => scissors (3)
"Y": 3+1, # draw (3) => rock (1)
"Z": 6+2}, # win (6) => paper (2)
"B": {"X": 0+1, # lose => rock (1)
"Y": 3+2, # draw => paper (2)
"Z": 6+3}, # win => scissors (3)
"C": {"X": 0+2, # lose => paper (2)
"Y": 3+3, # draw => scissors (3)
"Z": 6+1}} # win => rock (1)
scores = []
with open(input_file, "r+") as f:
for line in f.readlines():
game = line.rstrip().split(" ")
scores.append(outcomes[game[0]][game[1]])
return sum(scores)
# does it pass test case?
rps_modified("inputs/02_test_case.txt") == 12Truerps_modified("inputs/02_input.txt")12382Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Day 3: Rucksack Reorganization
Part one ⭐
One Elf has the important job of loading all of the rucksacks with supplies for the jungle journey. Unfortunately, that Elf didn’t quite follow the packing instructions, and so a few items now need to be rearranged.
Each rucksack has two large compartments. All items of a given type are meant to go into exactly one of the two compartments. The Elf that did the packing failed to follow this rule for exactly one item type per rucksack.
The Elves have made a list of all of the items currently in each rucksack (your puzzle input), but they need your help finding the errors. Every item type is identified by a single lowercase or uppercase letter (that is, a and A refer to different types of items).
The list of items for each rucksack is given as characters all on a single line. A given rucksack always has the same number of items in each of its two compartments, so the first half of the characters represent items in the first compartment, while the second half of the characters represent items in the second compartment.
For example, suppose you have the following list of contents from six rucksacks:
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw- The first rucksack contains the items
vJrwpWtwJgWrhcsFMMfFFhFp, which means its first compartment contains the itemsvJrwpWtwJgWr, while the second compartment contains the itemshcsFMMfFFhFp. The only item type that appears in both compartments is lowercasep.
- The second rucksack’s compartments contain
jqHRNqRjqzjGDLGLandrsFMfFZSrLrFZsSL. The only item type that appears in both compartments is uppercaseL.
- The third rucksack’s compartments contain
PmmdzqPrVandvPwwTWBwg; the only common item type is uppercaseP.
- The fourth rucksack’s compartments only share item type
v.
- The fifth rucksack’s compartments only share item type
t.
- The sixth rucksack’s compartments only share item type
s.
To help prioritize item rearrangement, every item type can be converted to a priority:
- Lowercase item types
athroughzhave priorities 1 through 26.
- Uppercase item types
AthroughZhave priorities 27 through 52.
In the above example, the priority of the item type that appears in both compartments of each rucksack is 16 (p), 38 (L), 42 (P), 22 (v), 20 (t), and 19 (s); the sum of these is 157.
Find the item type that appears in both compartments of each rucksack. What is the sum of the priorities of those item types?
def rucksuck(input_file):
prior_sum = 0
with open(input_file, "r+") as f:
for line in f.readlines():
inside = [el for el in line.rstrip()]
# get unique items of each compartment
comp1 = set(inside[:len(inside)//2])
comp2 = set(inside[len(inside)//2:])
# get the element that is common
el = list(comp1.intersection(comp2))[0]
if el == el.upper():
p = ord(el) - 65 + 27
else:
p = ord(el) - 97 + 1
# add the priority to the sum
prior_sum += p
return prior_sum
rucksuck("inputs/03_test_case.txt") == 157Truerucksuck("inputs/03_input.txt")8018Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
As you finish identifying the misplaced items, the Elves come to you with another issue.
For safety, the Elves are divided into groups of three. Every Elf carries a badge that identifies their group. For efficiency, within each group of three Elves, the badge is the only item type carried by all three Elves. That is, if a group’s badge is item type B, then all three Elves will have item type B somewhere in their rucksack, and at most two of the Elves will be carrying any other item type.
The problem is that someone forgot to put this year’s updated authenticity sticker on the badges. All of the badges need to be pulled out of the rucksacks so the new authenticity stickers can be attached.
Additionally, nobody wrote down which item type corresponds to each group’s badges. The only way to tell which item type is the right one is by finding the one item type that is common between all three Elves in each group.
Every set of three lines in your list corresponds to a single group, but each group can have a different badge item type. So, in the above example, the first group’s rucksacks are the first three lines:
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwgAnd the second group’s rucksacks are the next three lines:
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDwIn the first group, the only item type that appears in all three rucksacks is lowercase r; this must be their badges. In the second group, their badge item type must be Z.
Priorities for these items must still be found to organize the sticker attachment efforts: here, they are 18 (r) for the first group and 52 (Z) for the second group. The sum of these is 70.
Find the item type that corresponds to the badges of each three-Elf group. What is the sum of the priorities of those item types?
def rucksuck_badges(input_file):
cc = set()
elves = 0
prior_sum = 0
with open(input_file, "r+") as f:
for line in f.readlines():
carryon = set([el for el in line.rstrip()])
elves += 1
cc = carryon if elves % 3 == 1 else cc.intersection(carryon)
if (elves % 3 == 0):
badge = list(cc)[0]
cc = set()
if badge == badge.upper():
p = ord(badge) - 65 + 27
else:
p = ord(badge) - 97 + 1
# add the priority to the sum
prior_sum += p
return prior_sum
# does it pass test?
rucksuck_badges("inputs/03_test_case.txt") == 70Truerucksuck_badges("inputs/03_input.txt") 2518Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Day 4: Camp Cleanup
Part one ⭐
Space needs to be cleared before the last supplies can be unloaded from the ships, and so several Elves have been assigned the job of cleaning up sections of the camp. Every section has a unique ID number, and each Elf is assigned a range of section IDs.
However, as some of the Elves compare their section assignments with each other, they’ve noticed that many of the assignments overlap. To try to quickly find overlaps and reduce duplicated effort, the Elves pair up and make a big list of the section assignments for each pair (your puzzle input).
For example, consider the following list of section assignment pairs:
2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8For the first few pairs, this list means:
- Within the first pair of Elves, the first Elf was assigned sections
2-4(sections2,3, and4), while the second Elf was assigned sections6-8(sections6,7,8).
- The Elves in the second pair were each assigned two sections.
- The Elves in the third pair were each assigned three sections: one got sections
5,6, and7, while the other also got7, plus8and9.
This example list uses single-digit section IDs to make it easier to draw; your actual list might contain larger numbers. Visually, these pairs of section assignments look like this:
.234..... 2-4
.....678. 6-8
.23...... 2-3
...45.... 4-5
....567.. 5-7
......789 7-9
.2345678. 2-8
..34567.. 3-7
.....6... 6-6
...456... 4-6
.23456... 2-6
...45678. 4-8Some of the pairs have noticed that one of their assignments fully contains the other. For example, 2-8 fully contains 3-7, and 6-6 is fully contained by 4-6. In pairs where one assignment fully contains the other, one Elf in the pair would be exclusively cleaning sections their partner will already be cleaning, so these seem like the most in need of reconsideration. In this example, there are 2 such pairs.
In how many assignment pairs does one range fully contain the other?
# Define wrapper for checking test case
def test_case(cmd, result):
assert cmd == result, f"Should be {result}, is {cmd}"
def compare_ranges(range1, range2):
r1 = [int(el) for el in range1.split("-")]
r2 = [int(el) for el in range2.split("-")]
if ((r1[0] >= r2[0]) & (r1[1] <= r2[1])):
return True
elif ((r2[0] >= r1[0]) & (r2[1] <= r1[1])):
return True
else:
return False
test_case(compare_ranges("1-3", "2-5"), False)
test_case(compare_ranges("1-6", "2-5"), True)
def camp_cleanup(input_file):
with open(input_file, "r+") as f:
ranges = [line.split(",") for line in f.readlines()]
fully_contain = [compare_ranges(r[0], r[1]) for r in ranges]
return sum(fully_contain)
test_case(camp_cleanup("inputs/04_test_case.txt"), 2)camp_cleanup("inputs/04_input.txt")483Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
It seems like there is still quite a bit of duplicate work planned. Instead, the Elves would like to know the number of pairs that overlap at all.
In the above example, the first two pairs (2-4,6-8 and 2-3,4-5) don’t overlap, while the remaining four pairs (5-7,7-9, 2-8,3-7, 6-6,4-6, and 2-6,4-8) do overlap:
5-7,7-9overlaps in a single section,7.2-8,3-7overlaps all of the sections3through7.6-6,4-6overlaps in a single section,6.2-6,4-8overlaps in sections4,5, and6.
So, in this example, the number of overlapping assignment pairs is 4.
In how many assignment pairs do the ranges overlap?
# this solution also works for part 1
def compare_ranges_p2(range1, range2, fully=True):
r1 = [int(el) for el in range1.split("-")]
r1 = set(range(r1[0], r1[1] + 1))
r2 = [int(el) for el in range2.split("-")]
r2 = set(range(r2[0], r2[1] + 1))
# get the intersection
inter = r1.intersection(r2)
# if interested in fully only, check if intersection
# is the size of smaller set
if ((fully) & (len(inter) == min(len(r1), len(r2)))):
return True
# if any overlap, check if intersection non empty
if ((not fully) & (len(inter) > 0)):
return True
# all other case mean no overlap
return False
# check if part 1 would be good
test_case(compare_ranges_p2("1-3", "2-5"), False)
# check the test cases for not fully overlapping
test_case(compare_ranges_p2("1-3", "2-5", fully=False), True)
test_case(compare_ranges_p2("1-3", "4-5", fully=False), False)
def camp_cleanup_p2(input_file, fully=True):
with open(input_file, "r+") as f:
ranges = [line.split(",") for line in f.readlines()]
overlaps = [compare_ranges_p2(r[0], r[1], fully) for r in ranges]
return sum(overlaps)
# check if part 1 would be good
test_case(camp_cleanup_p2("inputs/04_test_case.txt"), 2)
# check test case
test_case(camp_cleanup_p2("inputs/04_test_case.txt", fully=False), 4)camp_cleanup_p2("inputs/04_input.txt", fully=False)874Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Visualisation
First, I will read in the data and process it.
Code
camp_cleanup_input_df <-
# read in input
readr::read_csv("inputs/04_input.txt",
col_names = c("elf1", "elf2"),
col_types = "c") %>%
# number pairs
dplyr::mutate(pair = as.character(1:n())) %>%
# make longer to look like this:
# pair elf range
# 1 "elf1" "1-3"
# 1 "elf2" "3-5"
tidyr::pivot_longer(names_to = "elf", values_to = "range",
dplyr::starts_with("elf")) %>%
# extract start & end range to look like this:
# pair elf range range_start range_end
# 1 "elf1" "1-3" 1 3
# 1 "elf2" "3-5" 3 5
tidyr::separate(range, into = c("range_start", "range_end"),
sep = "-", convert = TRUE, remove = FALSE) %>%
# list all assignments within range:
# pair elf range range_start range_end range_pos
# 1 "elf1" "1-3" 1 3 "1;2;3"
# 1 "elf2" "3-5" 3 5 "3;4;5"
dplyr::rowwise() %>%
dplyr::mutate(range_pos = paste(seq(range_start, range_end),
collapse = ";")) %>%
# replace elf range with both ranges:
# pair elf range range_start range_end range_pos
# 1 "elf1" "1-3,3-5" 1 3 "1;2;3"
# 1 "elf2" "1-3,3-5" 3 5 "3;4;5"
dplyr::group_by(pair) %>%
dplyr::mutate(range = paste(unique(range), collapse = ",")) %>%
# separate rows:
# pair elf range range_start range_end range_pos
# 1 "elf1" "1-3,3-5" 1 3 1
# 1 "elf1" "1-3,3-5" 1 3 2
# 1 "elf1" "1-3,3-5" 1 3 3
# 1 "elf2" "1-3,3-5" 3 5 3
# 1 "elf2" "1-3,3-5" 3 5 4
# 1 "elf2" "1-3,3-5" 3 5 5
tidyr::separate_rows(range_pos, sep = ";", convert = TRUE) %>%
# make a note if both elves assigned same room:
# pair range range_pos elf
# 1 "1-3,3-5" 1 "elf1"
# 1 "1-3,3-5" 2 "elf1"
# 1 "1-3,3-5" 3 "both"
# 1 "1-3,3-5" 4 "elf2"
# 1 "1-3,3-5" 5 "elf2"
dplyr::group_by(pair, range, range_pos) %>%
dplyr::mutate(elf = case_when(
dplyr::n() == 1 ~ elf,
TRUE ~ "both"
), .groups = "drop") %>%
unique() %>%
# label the pair as one of 3 cases
# pair range range_pos elf overlap
# 1 "1-3,3-5" 1 "elf1" "Case 2: there is some overlap"
# 2 "1-2,4-7" 4 "elf2" "Case 3: no overlap"
# 3 "4-5,2-6" 5 "both" "Case 1: one fully contains the other"
dplyr::group_by(pair) %>%
dplyr::mutate(
overlap = case_when(
# when one contains the other, there is only "both" and one
# of the elves
length(unique(elf)) < 3 &
"both" %in% unique(elf) ~ "Case 1: one fully contains the other",
# when there is just some overlap - that's the second case
any(elf == "both") ~ "Case 2: there is some overlap",
# all other cases - no overlap
TRUE ~ "Case 3: no overlap"),
# make into factor for nice plotting
overlap = factor(overlap,
levels = c("Case 1: one fully contains the other",
"Case 2: there is some overlap",
"Case 3: no overlap"))) %>%
dplyr::ungroup()Code
camp_cleanup_counted_df <-
camp_cleanup_input_df %>%
dplyr::select(pair, overlap) %>%
unique() %>%
dplyr::count(overlap)
n_pairs_with_full_overlap <-
camp_cleanup_counted_df %>%
dplyr::filter(overlap == "Case 1: one fully contains the other") %>%
dplyr::pull(n)
n_pairs_with_overlap <-
camp_cleanup_counted_df %>%
dplyr::filter(overlap != "Case 3: no overlap") %>%
dplyr::pull(n) %>%
sum()
n_pairs_without_overlap <-
camp_cleanup_counted_df %>%
dplyr::filter(overlap == "Case 3: no overlap") %>%
dplyr::pull(n) %>%
sum()After processing the data, I can check the answers:
camp_cleanup_counted_df# A tibble: 3 × 2
overlap n
<fct> <int>
1 Case 1: one fully contains the other 483
2 Case 2: there is some overlap 391
3 Case 3: no overlap 126For part 1, the answer is 483 and for part 2: 874 (sum of Case 1 and Case 2).
Code
library(ggplot2)
sysfonts::font_add_google("Permanent Marker")
showtext::showtext_auto()
theme_set(theme_minimal() +
theme(panel.grid.minor = element_blank(),
panel.grid.major.y = element_line(linetype = "dotted", color = "black"),
panel.grid.major.x = element_blank(),
axis.ticks.x = element_line(), legend.position = "bottom",
text = element_text(family = "Permanent Marker", size = 16)))Now, let’s see how do those cases look like if visualised. We have 3 cases - where assignment of one fully contains the other, where there is some overlap and when the assignments do not overlap.
Code
camp_cleanup_input_df %>%
dplyr::group_by(overlap) %>%
dplyr::filter(pair %in% sample(unique(pair), 10)) %>%
ggplot(aes(range_pos, pair, fill = elf)) +
geom_tile(alpha = 0.6, color = "black") +
facet_wrap(overlap~., scales = "free_y", ncol = 1) +
scale_fill_manual(values = c("elf1" = "#EC9A29",
"elf2" = "#94D1BE",
"both" = "#3A4E48")) +
theme(axis.ticks = element_blank(),
axis.text = element_blank(),
legend.position = "bottom",
panel.grid.major.y = element_blank(),
axis.ticks.x = element_blank()) +
labs(x = "Section #",
y = "Random selection of pairs of elves",
title = "Visualisation of section assignments",
fill = "Assigned elf",
caption = "Day 4 AoC 2022")
What fraction of the assignments overlaps between the elves (as fraction of the bigger assignment)?
Code
fract_per_section_df <-
camp_cleanup_input_df %>%
dplyr::group_by(pair, range) %>%
dplyr::mutate(max_range = max(range_pos) - min(range_pos) + 1) %>%
dplyr::group_by(pair, max_range, overlap) %>%
dplyr::summarise(count = sum(elf == "both"), .groups = "drop") %>%
dplyr::mutate(fract_overlap = count / max_range)
fract_per_section_df %>%
ggplot(aes(fract_overlap)) +
geom_histogram(data = . %>% dplyr::filter(fract_overlap > 0),
binwidth = 0.01, fill = "darkgreen", color = "black") +
geom_histogram(data = . %>% dplyr::filter(fract_overlap == 0),
binwidth = 0.01, fill = "darkorange", color = "black") +
annotate("curve",
x = 0.4, xend = 0.02,
y = 110, yend = 120,
curvature = .3,
arrow = arrow(length = unit(2, "mm"))) +
annotate(geom = "label",
x = 0.2, y = 110,
label = glue::glue("There are {n_pairs_without_overlap} pairs without any overlap "),
hjust = "left", family = "Permanent Marker", size = 6) +
annotate(geom = "label",
x = 0.4, y = 60,
label = glue::glue("and {n_pairs_with_overlap} pair with varying fraction of overlap "),
hjust = "left", family = "Permanent Marker", size = 6) +
labs(title = "How much of assignments are overlapping?",
caption = "Day 4 AoC 2022",
x = "Fraction of overlap",
y = "Frequency") +
scale_x_continuous(breaks = seq(0, 1, 0.2)) 
How many elves were assigned per each section?
Code
per_pos_counts_df <-
camp_cleanup_input_df %>%
dplyr::mutate(elf = stringr::str_remove(elf, "[1-2]")) %>%
dplyr::count(range_pos, elf) %>%
dplyr::ungroup() %>%
dplyr::mutate(n = case_when(
elf == "both" ~ as.integer(2*n),
TRUE ~ n)) %>%
dplyr::group_by(range_pos) %>%
dplyr::mutate(sum_cleaned = sum(n)) %>%
dplyr::ungroup() %>%
dplyr::mutate(most_cleaned = sum_cleaned == max(sum_cleaned),
least_cleaned = sum_cleaned == min(sum_cleaned))
min_pos <-
per_pos_counts_df %>% filter(least_cleaned) %>% pull(range_pos)
max_pos <-
per_pos_counts_df %>% filter(most_cleaned) %>% pull(range_pos)
min_n <-
per_pos_counts_df %>% filter(least_cleaned) %>% pull(sum_cleaned)
max_n <-
per_pos_counts_df %>% filter(most_cleaned) %>% pull(sum_cleaned)
per_pos_counts_df %>%
ggplot(aes(range_pos, n)) +
geom_bar(aes(fill = elf), stat = "identity", width = 1, color = NA) +
geom_bar(data = . %>% dplyr::filter(most_cleaned | least_cleaned),
aes(group = elf), stat = "identity", width = 1, color = NA,
fill = "white", alpha = .5) +
annotate("curve",
x = max_pos + 5, xend = max_pos + 1,
y = max_n - 370, yend = max_n - 30,
arrow = arrow(length = unit(2, "mm"))) +
annotate(geom = "label",
x = max_pos - 25, y = max_n - 430,
label = glue::glue("Section #{max_pos} was asigned to {max_n} elves "),
hjust = "left", family = "Permanent Marker", size = 6) +
annotate("curve",
x = min_pos + 10, xend = min_pos + 0.9,
y = min_n + 20, yend = min_n*0.9,
curvature = .3, arrow = arrow(length = unit(2, "mm"))) +
annotate(geom = "label", x = min_pos + 10 + 0.1, y = min_n + 20,
label = glue::glue("Section #{min_pos} was asigned to {min_n} elves "),
hjust = "left", family = "Permanent Marker", size = 6) +
ggthemes::scale_fill_wsj(labels = c("doubled", "unique")) +
labs(title = "How many elves assigned per each section?",
caption = "Day 4 AoC 2022",
x = "Section #", y = "Number of elves",
fill = "Assignment") +
theme(legend.position = "top")
How many sections were assigned per elf? Size of assignments tends to be bigger in case of one assignment containing other one.
Code
sections_per_elf_df <-
camp_cleanup_input_df %>%
dplyr::mutate(elf = case_when(
elf == "both" ~ "elf1;elf2",
TRUE ~ elf
)) %>%
tidyr::separate_rows(elf, sep = ";") %>%
dplyr::count(pair, overlap, elf)
sections_per_elf_df %>%
dplyr::group_by(overlap) %>%
dplyr::mutate(median = round(median(n), 1),
mean = round(mean(n), 1),
temp_fill = stringr::str_extract(overlap, "Case [0-9]+")) %>%
ggplot(aes(n)) +
geom_histogram(color = "black", aes(fill = temp_fill), bins = 50) +
geom_label(data = . %>% dplyr::select(overlap, median, mean) %>% unique(),
size = 6,
aes(x = max(sections_per_elf_df$n)/2, y = 90,
label = glue::glue("median: {median}\nmean: {mean}")),
family = "Permanent Marker") +
facet_wrap(~overlap) +
scale_fill_manual(values = c("Case 1" = "#4D6A6D",
"Case 2" = "#798478",
"Case 3" = "#C9ADA1")) +
theme(legend.position = "none") +
labs(title = "# of sections assigned per elfves",
y = "Frequency",
x = "Size of the assignmnent",
caption = "Day 4 AoC 2022")
There are a lot of pairs with same length of assignments in the overlap cases.
Code
sections_per_elf_df %>%
dplyr::group_by(overlap) %>%
dplyr::mutate(median = round(median(n), 1),
mean = round(mean(n), 1),
temp_fill = stringr::str_extract(overlap, "Case [0-9]+")) %>%
tidyr::pivot_wider(names_from = "elf", values_from = "n") %>%
ggplot(aes(elf1, elf2)) +
geom_jitter(aes(color = temp_fill)) +
facet_wrap(~overlap) +
scale_color_manual(values = c("Case 1" = "#4D6A6D",
"Case 2" = "#798478",
"Case 3" = "#C9ADA1")) +
theme(legend.position = "none") +
labs(caption = "Day 4 AoC 2022",
title = "Relationship between size of assignements")
Day 5: Supply Stacks
Part one ⭐
The expedition can depart as soon as the final supplies have been unloaded from the ships. Supplies are stored in stacks of marked crates, but because the needed supplies are buried under many other crates, the crates need to be rearranged.
The ship has a giant cargo crane capable of moving crates between stacks. To ensure none of the crates get crushed or fall over, the crane operator will rearrange them in a series of carefully-planned steps. After the crates are rearranged, the desired crates will be at the top of each stack.
The Elves don’t want to interrupt the crane operator during this delicate procedure, but they forgot to ask her which crate will end up where, and they want to be ready to unload them as soon as possible so they can embark.
They do, however, have a drawing of the starting stacks of crates and the rearrangement procedure (your puzzle input). For example:
[D]
[N] [C]
[Z] [M] [P]
1 2 3
move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2In this example, there are three stacks of crates. Stack 1 contains two crates: crate Z is on the bottom, and crate N is on top. Stack 2 contains three crates; from bottom to top, they are crates M, C, and D. Finally, stack 3 contains a single crate, P.
Then, the rearrangement procedure is given. In each step of the procedure, a quantity of crates is moved from one stack to a different stack. In the first step of the above rearrangement procedure, one crate is moved from stack 2 to stack 1, resulting in this configuration:
[D]
[N] [C]
[Z] [M] [P]
1 2 3In the second step, three crates are moved from stack 1 to stack 3. Crates are moved one at a time, so the first crate to be moved (D) ends up below the second and third crates:
[Z]
[N]
[C] [D]
[M] [P]
1 2 3Then, both crates are moved from stack 2 to stack 1. Again, because crates are moved one at a time, crate C ends up below crate M:
[Z]
[N]
[M] [D]
[C] [P]
1 2 3Finally, one crate is moved from stack 1 to stack 2:
[Z]
[N]
[D]
[C] [M] [P]
1 2 3The Elves just need to know which crate will end up on top of each stack; in this example, the top crates are C in stack 1, M in stack 2, and Z in stack 3, so you should combine these together and give the Elves the message CMZ.
After the rearrangement procedure completes, what crate ends up on top of each stack?
First, I need to deal with input. I will sepatate the stacks and instructions into two files. I will also clean up stacks to ease reading it in, from this:
[D]
[N] [C]
[Z] [M] [P]
1 2 3 to this:
0D0
NC0
ZMP
123Here 0 is an empty space, all spaces are removed such us that each space is represented by crate A-Z or 0. Crates are numbered in the last line.
input_file=$1
# create the stacks input
grep -v ^move ${input_file} |
# remove empty lines
awk 'NF' |
# treat all 4 spaces as empty position in stacks
sed 's/ {4}/0/g' |
# remove all spaces & [], each character should be stack
sed 's/ //g;s/\[//g; s/\]//g' > ${input_file/.txt/_stacks.txt}
# create instructions input
grep ^move ${input_file} > ${input_file/.txt/_inst.txt}I put the code in the script and run if from Python.
def process_input(input_file):
from subprocess import call, DEVNULL, STDOUT
call("./helper_scripts/05_process_inputs.sh " + input_file,
shell=True, stdout=DEVNULL, stderr=STDOUT)
process_input("inputs/05_test_case.txt")Then, I process stacks input and create the stacks list - first element is the top of each stack.
def read_input(input_file):
levels = []
with open(input_file, "r+") as f:
lines = f.readlines()
for line in lines:
if line[0] != '1':
levels.append([el for el in line.strip()])
stacks = [[m[i] for m in levels if m[i] != '0'] for i in range(len(levels[0]))]
return stacks
stacks = read_input("inputs/05_test_case_stacks.txt")
stacks[['N', 'Z'], ['D', 'C', 'M'], ['P']]Now, define logic to move crane, as per description the crane moves one crate at a time.
def move_crane(input_instuctions, input_stacks):
stacks = input_stacks.copy()
with open(input_instuctions, "r+") as f:
instructions = f.readlines()
for inst in instructions:
inst_l = inst.strip().split(" ")
inst_l = [int(el) for el in inst_l[1::2]]
how_many = inst_l[0]
stack_from = stacks[inst_l[1]-1]
stack_to = stacks[inst_l[2]-1]
# print(f"Move {how_many} from {stack_from} to {stack_to}")
for i in range(how_many):
crate = stack_from[::-1].pop()
stack_to.insert(0, crate)
stack_from = stack_from[1:]
stacks[inst_l[1]-1] = stack_from
stacks[inst_l[2]-1] = stack_to
return "".join([s[0] for s in stacks])
move_crane("inputs/05_test_case_inst.txt", stacks)'CMZ'And finally, create a function to run them all
def day5_part1(input_file):
# make sure the inputs are processed
process_input(input_file)
# read in the stacks
stacks = read_input(input_file.replace(".txt", "_stacks.txt"))
# move the crane
out_str = move_crane(input_file.replace(".txt", "_inst.txt"), stacks)
return out_str
# Define wrapper for checking test case
def test_case(cmd, result):
assert cmd == result, f"Should be {result}, is {cmd}"
test_case(day5_part1("inputs/05_test_case.txt"), "CMZ")
# added after discovering bug in bash script
test_case(day5_part1("inputs/05_test_case_alt.txt"), "ZMN")Check the answer
day5_part1("inputs/05_input.txt")'ZRLJGSCTR'Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
As you watch the crane operator expertly rearrange the crates, you notice the process isn’t following your prediction.
Some mud was covering the writing on the side of the crane, and you quickly wipe it away. The crane isn’t a CrateMover 9000 - it’s a CrateMover 9001.
The CrateMover 9001 is notable for many new and exciting features: air conditioning, leather seats, an extra cup holder, and the ability to pick up and move multiple crates at once.
Again considering the example above, the crates begin in the same configuration:
[D]
[N] [C]
[Z] [M] [P]
1 2 3 Moving a single crate from stack 2 to stack 1 behaves the same as before:
[D]
[N] [C]
[Z] [M] [P]
1 2 3 However, the action of moving three crates from stack 1 to stack 3 means that those three moved crates stay in the same order, resulting in this new configuration:
[D]
[N]
[C] [Z]
[M] [P]
1 2 3Next, as both crates are moved from stack 2 to stack 1, they retain their order as well:
[D]
[N]
[C] [Z]
[M] [P]
1 2 3Finally, a single crate is still moved from stack 1 to stack 2, but now it’s crate C that gets moved:
[D]
[N]
[Z]
[M] [C] [P]
1 2 3In this example, the CrateMover 9001 has put the crates in a totally different order: MCD.
Before the rearrangement process finishes, update your simulation so that the Elves know where they should stand to be ready to unload the final supplies. After the rearrangement procedure completes, what crate ends up on top of each stack?
I need to update the crane function - where I will multiple crates at one time.
def move_crane_9001(input_instuctions, input_stacks):
stacks = input_stacks.copy()
with open(input_instuctions, "r+") as f:
instructions = f.readlines()
for inst in instructions:
inst_l = inst.strip().split(" ")
inst_l = [int(el) for el in inst_l[1::2]]
how_many = inst_l[0]
stack_from = stacks[inst_l[1]-1]
stack_to = stacks[inst_l[2]-1]
# print(f"Move {how_many} from {stack_from} to {stack_to}")
crates = stack_from[:how_many]
stack_to = crates + stack_to
stack_from = stack_from[how_many:]
stacks[inst_l[1]-1] = stack_from
stacks[inst_l[2]-1] = stack_to
return "".join([s[0] for s in stacks])
stacks = read_input("inputs/05_test_case_stacks.txt")
test_case(move_crane_9001("inputs/05_test_case_inst.txt", stacks), "MCD")
test_case(move_crane_9001("inputs/05_test_case_alt_inst.txt", stacks), "DCN")And function to run all components
def day5_part2(input_file):
# make sure the inputs are processed
process_input(input_file)
# read in the stacks
stacks = read_input(input_file.replace(".txt", "_stacks.txt"))
# move the crane
out_str = move_crane_9001(input_file.replace(".txt", "_inst.txt"), stacks)
return out_str
test_case(day5_part2("inputs/05_test_case.txt"), "MCD")
test_case(day5_part2("inputs/05_test_case_alt.txt"), "DCN")What’s the answer?
day5_part2("inputs/05_input.txt")'PRTTGRFPB'Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Day 6: Tuning Trouble
Part one ⭐
The preparations are finally complete; you and the Elves leave camp on foot and begin to make your way toward the star fruit grove.
As you move through the dense undergrowth, one of the Elves gives you a handheld device. He says that it has many fancy features, but the most important one to set up right now is the communication system.
However, because he’s heard you have significant experience dealing with signal-based systems, he convinced the other Elves that it would be okay to give you their one malfunctioning device - surely you’ll have no problem fixing it.
As if inspired by comedic timing, the device emits a few colorful sparks.
To be able to communicate with the Elves, the device needs to lock on to their signal. The signal is a series of seemingly-random characters that the device receives one at a time.
To fix the communication system, you need to add a subroutine to the device that detects a start-of-packet marker in the datastream. In the protocol being used by the Elves, the start of a packet is indicated by a sequence of four characters that are all different.
The device will send your subroutine a datastream buffer (your puzzle input); your subroutine needs to identify the first position where the four most recently received characters were all different. Specifically, it needs to report the number of characters from the beginning of the buffer to the end of the first such four-character marker.
For example, suppose you receive the following datastream buffer:
mjqjpqmgbljsphdztnvjfqwrcgsmlbAfter the first three characters (mjq) have been received, there haven’t been enough characters received yet to find the marker. The first time a marker could occur is after the fourth character is received, making the most recent four characters mjqj. Because j is repeated, this isn’t a marker.
The first time a marker appears is after the seventh character arrives. Once it does, the last four characters received are jpqm, which are all different. In this case, your subroutine should report the value 7, because the first start-of-packet marker is complete after 7 characters have been processed.
Here are a few more examples:
bvwbjplbgvbhsrlpgdmjqwftvncz: first marker after character5
nppdvjthqldpwncqszvftbrmjlhg: first marker after character6
nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg: first marker after character10
zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw: first marker after character11
How many characters need to be processed before the first start-of-packet marker is detected?
# Define wrapper for checking test case
def test_case(cmd, result):
assert cmd == result, f"Should be {result}, is {cmd}"
# define finding marker function
def find_marker(in_str):
for i in range(4, len(in_str)):
temp = in_str[i-4:i]
if (len(temp) == len(set([t for t in temp]))):
break
return i
# tests for mentioned test cases
test_case(find_marker("mjqjpqmgbljsphdztnvjfqwrcgsmlb"), 7)
test_case(find_marker("bvwbjplbgvbhsrlpgdmjqwftvncz"), 5)
test_case(find_marker("nppdvjthqldpwncqszvftbrmjlhg"), 6)
test_case(find_marker("nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg"), 10)
test_case(find_marker("zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw"), 11)Now, check the value for the input.
with open("inputs/06_input.txt", "r+") as f:
input_string = f.readline().strip()
find_marker(input_string)1876Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
Your device’s communication system is correctly detecting packets, but still isn’t working. It looks like it also needs to look for messages.
A start-of-message marker is just like a start-of-packet marker, except it consists of 14 distinct characters rather than 4.
Here are the first positions of start-of-message markers for all of the above examples:
mjqjpqmgbljsphdztnvjfqwrcgsmlb: first marker after character19
bvwbjplbgvbhsrlpgdmjqwftvncz: first marker after character23
nppdvjthqldpwncqszvftbrmjlhg: first marker after character23
nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg: first marker after character29
zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw: first marker after character26
How many characters need to be processed before the first start-of-message marker is detected?
I need to generalise the function from the part one and voila.
# define finding any function, works for part one too
def find_any(in_str, n=4):
for i in range(n, len(in_str)):
temp = in_str[i-n:i]
if (len(temp) == len(set([t for t in temp]))):
break
return i
# tests for part one
test_case(find_any("mjqjpqmgbljsphdztnvjfqwrcgsmlb", 4), 7)
test_case(find_any("bvwbjplbgvbhsrlpgdmjqwftvncz", 4), 5)
test_case(find_any("nppdvjthqldpwncqszvftbrmjlhg", 4), 6)
test_case(find_any("nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg", 4), 10)
test_case(find_any("zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw", 4), 11)
# tests for part two
test_case(find_any("mjqjpqmgbljsphdztnvjfqwrcgsmlb", 14), 19)
test_case(find_any("bvwbjplbgvbhsrlpgdmjqwftvncz", 14), 23)
test_case(find_any("nppdvjthqldpwncqszvftbrmjlhg", 14), 23)
test_case(find_any("nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg", 14), 29)
test_case(find_any("zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw", 14), 26)And when do we find message in the input?
find_any(input_string, n=14)2202Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Day 7: No Space Left On Device
Part one ⭐
You can hear birds chirping and raindrops hitting leaves as the expedition proceeds. Occasionally, you can even hear much louder sounds in the distance; how big do the animals get out here, anyway?
The device the Elves gave you has problems with more than just its communication system. You try to run a system update:
$ system-update --please --pretty-please-with-sugar-on-top
Error: No space left on devicePerhaps you can delete some files to make space for the update?
You browse around the filesystem to assess the situation and save the resulting terminal output (your puzzle input). For example:
$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 kThe filesystem consists of a tree of files (plain data) and directories (which can contain other directories or files). The outermost directory is called /. You can navigate around the filesystem, moving into or out of directories and listing the contents of the directory you’re currently in.
Within the terminal output, lines that begin with $ are commands you executed, very much like some modern computers:
cdmeans change directory. This changes which directory is the current directory, but the specific result depends on the argument:cd xmoves in one level: it looks in the current directory for the directory namedxand makes it the current directory.
cd ..moves out one level: it finds the directory that contains the current directory, then makes that directory the current directory.
cd /switches the current directory to the outermost directory,/.
lsmeans list. It prints out all of the files and directories immediately contained by the current directory:123 abcmeans that the current directory contains a file namedabcwith size123.
- dir
xyzmeans that the current directory contains a directory namedxyz.
- / (dir)
- a (dir)
- e (dir)
- i (file, size=584)
- f (file, size=29116)
- g (file, size=2557)
- h.lst (file, size=62596)
- b.txt (file, size=14848514)
- c.dat (file, size=8504156)
- d (dir)
- j (file, size=4060174)
- d.log (file, size=8033020)
- d.ext (file, size=5626152)
- k (file, size=7214296)Here, there are four directories: / (the outermost directory), a and d (which are in /), and e (which is in a). These directories also contain files of various sizes.
Since the disk is full, your first step should probably be to find directories that are good candidates for deletion. To do this, you need to determine the total size of each directory. The total size of a directory is the sum of the sizes of the files it contains, directly or indirectly. (Directories themselves do not count as having any intrinsic size.)
The total sizes of the directories above can be found as follows: * The total size of directory e is 584 because it contains a single file i of size 584 and no other directories.
* The directory a has total size 94853 because it contains files f (size 29116), g (size 2557), and h.lst (size 62596), plus file i indirectly (a contains e which contains i).
* Directory d has total size 24933642.
* As the outermost directory, / contains every file. Its total size is 48381165, the sum of the size of every file.
To begin, find all of the directories with a total size of at most 100000, then calculate the sum of their total sizes. In the example above, these directories are a and e; the sum of their total sizes is 95437 (94853 + 584). (As in this example, this process can count files more than once!)
Find all of the directories with a total size of at most 100000. What is the sum of the total sizes of those directories?
import re
def parse_input(input_file):
with open(input_file, "r+") as f:
lines=f.readlines()
parent_dir=""
current_dir=""
dirs = {"/": {'size': 0, 'parent_dir': ""}}
for line in lines:
lin_ = [el for el in line.strip().split(" ")]
# handle changing directories
if (lin_[0] == "$") & (lin_[1] == "cd"):
# change directory to higher up
if lin_[2] == "..":
# you can't go higher up
if current_dir != "/":
current_dir = parent_dir
parent_dir = dirs[current_dir]['parent_dir']
# or to named directory
else:
parent_dir = "" if lin_[2] == "/" else current_dir
current_dir = parent_dir + '/' + lin_[2]
current_dir = re.sub("/{1,}", "/", current_dir)
# if it's a directory
elif lin_[0] == "dir":
dir_n = current_dir + '/' + lin_[1]
dir_n = re.sub("/{1,}", "/", dir_n)
# clean up the path
dirs[dir_n] = {'size': 0, 'parent_dir': current_dir}
# if it is a file
elif lin_[0] != "$":
size = int(lin_[0])
cur_d = current_dir
while True:
dirs[cur_d]['size'] += size
if cur_d == "/":
break
cur_d = dirs[cur_d]['parent_dir']
return dirs
parse_input("inputs/07_test_case.txt"){'/': {'size': 48381165, 'parent_dir': ''}, '/a': {'size': 94853, 'parent_dir': '/'}, '/d': {'size': 24933642, 'parent_dir': '/'}, '/a/e': {'size': 584, 'parent_dir': '/a'}}# Define wrapper for checking test case
def test_case(cmd, result):
assert cmd == result, f"Should be {result}, is {cmd}"
test_case(parse_input("inputs/07_test_case.txt")["/"]['size'], 48381165)dirs_input = parse_input("inputs/07_input.txt")
sum([v['size'] for k, v in dirs_input.items() if v['size'] <= 100000])1491614Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
Now, you’re ready to choose a directory to delete.
The total disk space available to the filesystem is 70000000. To run the update, you need unused space of at least 30000000. You need to find a directory you can delete that will free up enough space to run the update.
In the example above, the total size of the outermost directory (and thus the total amount of used space) is 48381165; this means that the size of the unused space must currently be 21618835, which isn’t quite the 30000000 required by the update. Therefore, the update still requires a directory with total size of at least 8381165 to be deleted before it can run.
To achieve this, you have the following options:
- Delete directory
e, which would increase unused space by584.
- Delete directory
a, which would increase unused space by94853.
- Delete directory
d, which would increase unused space by24933642.
- Delete directory
/, which would increase unused space by48381165.
Directories e and a are both too small; deleting them would not free up enough space. However, directories d and / are both big enough! Between these, choose the smallest: d, increasing unused space by 24933642.
Find the smallest directory that, if deleted, would free up enough space on the filesystem to run the update. What is the total size of that directory?
needed_space = dirs_input['/']['size'] - 40000000
dirs_its = dirs_input.items()
sorted([v['size'] for k, v in dirs_its if v['size'] > needed_space])[0]6400111Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Day 8: Treetop Tree House
Part one ⭐
The expedition comes across a peculiar patch of tall trees all planted carefully in a grid. The Elves explain that a previous expedition planted these trees as a reforestation effort. Now, they’re curious if this would be a good location for a tree house.
First, determine whether there is enough tree cover here to keep a tree house hidden. To do this, you need to count the number of trees that are visible from outside the grid when looking directly along a row or column.
The Elves have already launched a quadcopter to generate a map with the height of each tree (your puzzle input). For example:
30373
25512
65332
33549
35390Each tree is represented as a single digit whose value is its height, where 0 is the shortest and 9 is the tallest.
A tree is visible if all of the other trees between it and an edge of the grid are shorter than it. Only consider trees in the same row or column; that is, only look up, down, left, or right from any given tree.
All of the trees around the edge of the grid are visible - since they are already on the edge, there are no trees to block the view. In this example, that only leaves the interior nine trees to consider:
- The top-left
5is visible from the left and top. (It isn’t visible from the right or bottom since other trees of height5are in the way.)
|
v
3|0|373
-|-|---
-> 2|5|512
-|-|---
6|5|332
3|3|549
3|5|390- The top-middle
5is visible from the top and right.
|
v
30|3|73
--|-|--
25|5|12 <-
--|-|--
65|3|32
33|5|49
35|3|90- The top-right
1is not visible from any direction; for it to be visible, there would need to only be trees of height 0 between it and an edge.
- The left-middle
5is visible, but only from the right.
- The center
3is not visible from any direction; for it to be visible, there would need to be only trees of at most height2between it and an edge.
- The right-middle
3is visible from the right. - In the bottom row, the middle
5is visible, but the3and4are not.
With 16 trees visible on the edge and another 5 visible in the interior, a total of 21 trees are visible in this arrangement.
Consider your map; how many trees are visible from outside the grid?
import numpy as np
def count_visible(input_file):
# get the input matrix
with open(input_file, "r+") as f:
lines = f.readlines()
a = np.array([[int(el) for el in lin.strip()] for lin in lines])
# get the output placeholder
res = np.zeros(a.shape)
# get the shapes
I = a.shape[0]
J = a.shape[1]
# iterate over insides, skipping edges
for i in range(1, I-1):
for j in range(1, J-1):
# left, right, up, down
sides = [a[i, 0:j], a[i, (j+1):J], a[0:i, j], a[(i+1):I, j]]
if any([np.max(side) < a[i,j] for side in sides]):
continue
else:
res[i,j] = 1
return np.size(a) - np.sum(res)
# define test
def test_case(cmd, result):
assert cmd == result, f"Should be {result}, is {cmd}"
# test
test_case(count_visible("inputs/08_test_case.txt"), 21)And the answer to the question?
count_visible("inputs/08_input.txt")1679.0Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
Content with the amount of tree cover available, the Elves just need to know the best spot to build their tree house: they would like to be able to see a lot of trees.
To measure the viewing distance from a given tree, look up, down, left, and right from that tree; stop if you reach an edge or at the first tree that is the same height or taller than the tree under consideration. (If a tree is right on the edge, at least one of its viewing distances will be zero.)
The Elves don’t care about distant trees taller than those found by the rules above; the proposed tree house has large eaves to keep it dry, so they wouldn’t be able to see higher than the tree house anyway.
In the example above, consider the middle 5 in the second row:
30|3|73
--|-|--
25|5|12
--|-|--
65|3|32
33|5|49
35|3|90- Looking up, its view is not blocked; it can see
1tree (of height3).
- Looking left, its view is blocked immediately; it can see only
1tree (of height5, right next to it).
- Looking right, its view is not blocked; it can see
2trees.
- Looking down, its view is blocked eventually; it can see
2trees (one of height3, then the tree of height5that blocks its view).
A tree’s scenic score is found by multiplying together its viewing distance in each of the four directions. For this tree, this is 4 (found by multiplying 1 * 1 * 2 * 2).
However, you can do even better: consider the tree of height 5 in the middle of the fourth row:
30|3|73
25|5|12
65|3|32
--|-|--
33|5|49
--|-|--
35|3|90- Looking up, its view is blocked at
2trees (by another tree with a height of5).
- Looking left, its view is not blocked; it can see
2trees.
- Looking down, its view is also not blocked; it can see
1tree.
- Looking right, its view is blocked at
2trees (by a massive tree of height9).
This tree’s scenic score is 8 (2 * 2 * 1 * 2); this is the ideal spot for the tree house.
Consider each tree on your map. What is the highest scenic score possible for any tree?
def scenic_view(input_file):
# get the input matrix
with open(input_file, "r+") as f:
lines = f.readlines()
a = np.array([[int(el) for el in lin.strip()] for lin in lines])
# get the output placeholder
res = np.zeros(a.shape)
# get the shapes
I = a.shape[0]
J = a.shape[1]
# iterate over insides, skipping edges
for i in range(1, I-1):
for j in range(1, J-1):
el = a[i, j]
left = a[i, 0:j]
right = a[i, (j+1):J]
up = a[0:i, j]
down = a[(i+1):I, j]
sides = [np.flip(left), right, np.flip(up), down]
# get the first equal or higher tree and count trees (including it)
# if there are no equal or higher tree, view is unobstructed count
# all trees up to the edge
scenic_list = [np.where(side >= el)[0][0] + 1 if np.any(side >= el) else side.size for side in sides]
# get the product of all four sides
scenic = np.prod(np.array(scenic_list))
# write it down
res[i,j] = scenic
# report the biggest number
return np.max(res)
# test solution
test_case(scenic_view("inputs/08_test_case.txt"), 8)Check the answer:
scenic_view("inputs/08_input.txt")536625.0Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Day 9: Rope Bridge
Part one
Day 10: Cathode-Ray Tube
Part one ⭐
def read_commands(file_path):
with open(file_path, "r+") as f:
lines = f.readlines()
adds = [0]*241
adds[0] = 1
cycle = 0
for line in lines:
args = [arg for arg in line.strip().split(" ")]
if args[0] == "addx":
adds[cycle+2] = int(args[1])
cycle+=2
else:
cycle+=1
return adds
def get_signal_strengths(adds, cycles = range(20, 221, 40)):
strengths = [sum(adds[0:cycle])*cycle for cycle in cycles]
return strengths
def get_sum_signal_strength(file_path, cycles = range(20, 221, 40)):
addxs = read_commands(file_path)
signal_strengths = get_signal_strengths(addxs, cycles = cycles)
return sum(signal_strengths)
# define test
def test_case(cmd, result):
assert cmd == result, f"Should be {result}, is {cmd}"
test_case(get_sum_signal_strength("inputs/10_test_case.txt"), 13140)get_sum_signal_strength("inputs/10_input.txt")17380Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
def print_crt_output(file_path):
addxs = read_commands(file_path)
out = ""
sprite = ["_"] * 40
sprite[0:3] = ["█"]*3
for i in range(240):
j = i % 40
if addxs[i] != 0:
pos = sum(addxs[:(i+1)])
sprite = ["_"] * 40
if pos > 0:
sprite[(pos-1):(pos+2)] = ["█"]*3
elif pos >= -2:
sprite[0:(pos+2)] = ["█"] * (3+pos)
out += sprite[j]
if (j == 39):
print(out)
out = ""
i += 1
print_crt_output("inputs/10_test_case.txt")██__██__██__██__██__██__██__██__██__██__
███___███___███___███___███___███___███_
████____████____████____████____████____
█████_____█████_____█████_____█████_____
██████______██████______██████______████
███████_______███████_______███████_____print_crt_output("inputs/10_input.txt")████__██___██__█__█_████_███__████__██__
█____█__█_█__█_█__█____█_█__█_█____█__█_
███__█____█____█__█___█__█__█_███__█____
██___█_██_█____█__█__█___███__█____█____
██___█__█_█__█_█__█_█____█_█__█____█__█_
██____███__██___██__████_█__█_████__██__Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Day 11: Monkey in the Middle
Part one ⭐
Problem desciption. This time we are dealing with monkeys playing with our stuff.
import numpy as np
def process_monkey_instructions(flie_path):
monkey=-1
monkeys=[]
with open(flie_path, "r+") as f:
lines = f.readlines()
for line in lines:
line = line.strip()
if "Monkey" in line:
monkey+=1
elif "Starting" in line:
items = [int(item) for item in line.split(":")[1].split(",")]
elif "Operation" in line:
oper = line.split("Operation: ")[1]
elif "Test" in line:
divider = int(line.split("by ")[1])
elif "If true:" in line:
true_monkey = int(line.split("monkey ")[1])
elif "If false:" in line:
false_monkey = int(line.split("monkey ")[1])
else:
monkeys.append({"items": items,
"operation": oper,
"divider": divider,
"if_true": true_monkey,
"if_false": false_monkey,
"inspected": 0})
# after last line, check if last monkey was added
try:
a = monkeys[monkey]
except IndexError:
monkeys.append({"items": items,
"operation": oper,
"divider": divider,
"if_true": true_monkey,
"if_false": false_monkey,
"inspected": 0})
return monkeys
def get_level_monkey_business(file_path, cycles = 20):
monkeys = process_monkey_instructions(file_path)
new = 0
for rounds in range(cycles):
for monkey in monkeys:
while len(monkey['items']) > 0:
# execute the operation code in safe temporary dict
d = {'old': monkey['items'].pop(0)}
exec(monkey["operation"], d)
# change worry level
worry = d['new'] // 3
if worry % monkey["divider"] == 0:
monkeys[monkey["if_true"]]["items"].append(worry)
else:
monkeys[monkey["if_false"]]["items"].append(worry)
monkey["inspected"] +=1
inspected = sorted([monkey['inspected'] for monkey in monkeys], reverse=True)
return np.prod(inspected[:2])
# define test
def test_case(cmd, result):
assert cmd == result, f"Should be {result}, is {cmd}"
# test answer
test_case(get_level_monkey_business("inputs/11_test_case.txt"), 10605) get_level_monkey_business("inputs/11_input.txt")66124Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Part two ⭐
Modifications to the task can be found here.
def get_level_monkey_business2(file_path, cycles=20):
monkeys = process_monkey_instructions(file_path)
# get the lowest common multiplier
lcm = np.lcm.reduce([monkey['divider'] for monkey in monkeys])
new = 0
for rounds in range(cycles):
for monkey in monkeys:
while len(monkey['items']) > 0:
# execute the operation code in safe temporary dict
d = {'old': monkey['items'].pop(0)}
exec(monkey["operation"], d)
# change worry level using lcm
worry = d['new'] % lcm
if worry % monkey["divider"] == 0:
monkeys[monkey["if_true"]]["items"].append(worry)
else:
monkeys[monkey["if_false"]]["items"].append(worry)
monkey["inspected"] +=1
inspected = sorted([monkey['inspected'] for monkey in monkeys], reverse=True)
return np.prod(inspected[:2])
test_case(get_level_monkey_business2("inputs/11_test_case.txt", cycles=10000),
2713310158)get_level_monkey_business2("inputs/11_input.txt", cycles = 10000)19309892877Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.
Day 18: Boiling Boulders
Part one ⭐
My idea is to create a 3D tensor with zeros and populate it with each cube (-Inf) and mark the walls as accessible with +1. That way I can count how many walls of cubes are accessible from each coordinates. After adding up all cubes, I can simply sum all elements bigger than 0.
import numpy as np
def count_walls(file_path):
with open(file_path, "r+") as f:
lines = f.readlines()
# create an init matrix
dim = 5
a = np.zeros([dim] * 3)
for line in lines:
coord = [int(p) for p in line.strip().split(",")]
# check if matrix is big enough, if not, extend it
biggest_dim = max(coord) + 2
if biggest_dim > dim:
# double the dim to extend it effectively
biggest_dim *= 2
temp_a = np.zeros([biggest_dim] * 3)
temp_a[0:dim, 0:dim, 0:dim] = a
a = temp_a
dim = biggest_dim
# now, add the cubes
[i, j, k] = coord
a[i, j, k] = -np.inf
# mark which sides are not connected to other cubes
for c in [-1, +1]:
for b in [0, 1, 2]:
coord_ = coord.copy()
coord_[b] += c
[i_, j_, k_] = coord_
a[i_, j_, k_] += 1
return int(np.sum(a[a>0]))
# define test
def test_case(cmd, result):
assert cmd == result, f"Should be {result}, is {cmd}"
test_case(count_walls("inputs/18_test_case.txt"), 64)count_walls("inputs/18_input.txt")4460Outcome: That’s the right answer! You are one gold star ⭐ closer to collecting enough star fruit.