(require '[clojure.string :as str]
'[clojure.core.match :refer [match]]
'[clojure.math.combinatorics :as combo])The Chief Historian is always present for the big Christmas sleigh launch, but nobody has seen him in months! Last anyone heard, he was visiting locations that are historically significant to the North Pole; a group of Senior Historians has asked you to accompany them as they check the places they think he was most likely to visit.
As each location is checked, they will mark it on their list with a star. They figure the Chief Historian must be in one of the first fifty places they’ll look, so in order to save Christmas, you need to help them get fifty stars on their list before Santa takes off on 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!
You haven’t even left yet and the group of Elvish Senior Historians has already hit a problem: their list of locations to check is currently empty. Eventually, someone decides that the best place to check first would be the Chief Historian’s office.
Upon pouring into the office, everyone confirms that the Chief Historian is indeed nowhere to be found. Instead, the Elves discover an assortment of notes and lists of historically significant locations! This seems to be the planning the Chief Historian was doing before he left. Perhaps these notes can be used to determine which locations to search?
Throughout the Chief’s office, the historically significant locations are listed not by name but by a unique number called the location ID. To make sure they don’t miss anything, The Historians split into two groups, each searching the office and trying to create their own complete list of location IDs.
There’s just one problem: by holding the two lists up side by side (your puzzle input), it quickly becomes clear that the lists aren’t very similar. Maybe you can help The Historians reconcile their lists?
For example:
3 4 4 3 2 5 1 3 3 9 3 3
Maybe the lists are only off by a small amount! To find out, pair up the numbers and measure how far apart they are. Pair up the smallest number in the left list with the smallest number in the right list, then the second-smallest left number with the second-smallest right number, and so on.
Within each pair, figure out how far apart the two numbers are; you’ll need to add up all of those distances. For example, if you pair up a 3 from the left list with a 7 from the right list, the distance apart is 4; if you pair up a 9 with a 3, the distance apart is 6.
In the example list above, the pairs and distances would be as follows:
The smallest number in the left list is 1, and the smallest number in the right list is 3. The distance between them is 2. The second-smallest number in the left list is 2, and the second-smallest number in the right list is another 3. The distance between them is 1. The third-smallest number in both lists is 3, so the distance between them is 0. The next numbers to pair up are 3 and 4, a distance of 1. The fifth-smallest numbers in each list are 3 and 5, a distance of 2. Finally, the largest number in the left list is 4, while the largest number in the right list is 9; these are a distance 5 apart.
To find the total distance between the left list and the right list, add up the distances between all of the pairs you found. In the example above, this is 2 + 1 + 0 + 1 + 2 + 5, a total distance of 11!
Your actual left and right lists contain many location IDs. What is the total distance between your lists?
(def input-1
(for [line (str/split-lines (slurp "input01.txt"))]
(map #(Integer/parseInt %) (re-seq #"\d+" line))))And for the actual problem…
(loop [[num1 & rest1] (sort (map first input-1))
[num2 & rest2] (sort (map second input-1))
dist 0]
(if-not (or num1 num2)
dist
(recur rest1 rest2 (+ dist (abs (- num1 num2))))))Your analysis only confirmed what everyone feared: the two lists of location IDs are indeed very different.
Or are they?
The Historians can’t agree on which group made the mistakes or how to read most of the Chief’s handwriting, but in the commotion you notice an interesting detail: a lot of location IDs appear in both lists! Maybe the other numbers aren’t location IDs at all but rather misinterpreted handwriting.
This time, you’ll need to figure out exactly how often each number from the left list appears in the right list. Calculate a total similarity score by adding up each number in the left list after multiplying it by the number of times that number appears in the right list.
Here are the same example lists again:
3 4 4 3 2 5 1 3 3 9 3 3
For these example lists, here is the process of finding the similarity score:
The first number in the left list is 3. It appears in the right list three times, so the similarity score increases by 3 * 3 = 9. The second number in the left list is 4. It appears in the right list once, so the similarity score increases by 4 * 1 = 4. The third number in the left list is 2. It does not appear in the right list, so the similarity score does not increase (2 * 0 = 0). The fourth number, 1, also does not appear in the right list. The fifth number, 3, appears in the right list three times; the similarity score increases by 9. The last number, 3, appears in the right list three times; the similarity score again increases by 9.
So, for these example lists, the similarity score at the end of this process is 31 (9 + 4 + 0 + 0 + 9 + 9).
Once again consider your left and right lists. What is their similarity score?
(let [freqs (frequencies (map second input-1))]
(loop [[num & rest] (map first input-1)
dist 0]
(if-not num
dist
(recur rest (+ dist (* num (or (freqs num) 0)))))))Fortunately, the first location The Historians want to search isn’t a long walk from the Chief Historian’s office.
While the Red-Nosed Reindeer nuclear fusion/fission plant appears to contain no sign of the Chief Historian, the engineers there run up to you as soon as they see you. Apparently, they still talk about the time Rudolph was saved through molecular synthesis from a single electron.
They’re quick to add that - since you’re already here - they’d really appreciate your help analyzing some unusual data from the Red-Nosed reactor. You turn to check if The Historians are waiting for you, but they seem to have already divided into groups that are currently searching every corner of the facility. You offer to help with the unusual data.
The unusual data (your puzzle input) consists of many reports, one report per line. Each report is a list of numbers called levels that are separated by spaces. For example:
7 6 4 2 1 1 2 7 8 9 9 7 6 2 1 1 3 2 4 5 8 6 4 4 1 1 3 6 7 9
This example data contains six reports each containing five levels.
The engineers are trying to figure out which reports are safe. The Red-Nosed reactor safety systems can only tolerate levels that are either gradually increasing or gradually decreasing. So, a report only counts as safe if both of the following are true:
The levels are either all increasing or all decreasing. Any two adjacent levels differ by at least one and at most three.
In the example above, the reports can be found safe or unsafe by checking those rules:
7 6 4 2 1: Safe because the levels are all decreasing by 1 or 2. 1 2 7 8 9: Unsafe because 2 7 is an increase of 5. 9 7 6 2 1: Unsafe because 6 2 is a decrease of 4. 1 3 2 4 5: Unsafe because 1 3 is increasing but 3 2 is decreasing. 8 6 4 4 1: Unsafe because 4 4 is neither an increase or a decrease. 1 3 6 7 9: Safe because the levels are all increasing by 1, 2, or 3.
So, in this example, 2 reports are safe.
Analyze the unusual data from the engineers. How many reports are safe?
(def input-2
(for [line (str/split-lines (slurp "input02.txt"))]
(map #(Integer/parseInt %) (re-seq #"\d+" line))))(defn no-big-gap? [numbers]
(loop [[first & rest1] numbers
[second & rest2] (rest numbers)]
(if-not second
true
(if (<= 1 (abs (- first second)) 3)
(recur rest1 rest2)
false))))
(defn ordered? [numbers]
(let [sorted (sort numbers)]
(or (= numbers sorted) (= numbers (reverse sorted)))))(count (filter #(and (ordered? %) (no-big-gap? %)) input-2))The engineers are surprised by the low number of safe reports until they realize they forgot to tell you about the Problem Dampener.
The Problem Dampener is a reactor-mounted module that lets the reactor safety systems tolerate a single bad level in what would otherwise be a safe report. It’s like the bad level never happened!
Now, the same rules apply as before, except if removing a single level from an unsafe report would make it safe, the report instead counts as safe.
More of the above example’s reports are now safe:
7 6 4 2 1: Safe without removing any level. 1 2 7 8 9: Unsafe regardless of which level is removed. 9 7 6 2 1: Unsafe regardless of which level is removed. 1 3 2 4 5: Safe by removing the second level, 3. 8 6 4 4 1: Safe by removing the third level, 4. 1 3 6 7 9: Safe without removing any level.
Thanks to the Problem Dampener, 4 reports are actually safe!
Update your analysis by handling situations where the Problem Dampener can remove a single level from unsafe reports. How many reports are now safe?
Huh! I guess the easiest way is to construct a list of all the lists that can happen if you also remove one item from it somewhere, which isn’t too tricky!
(defn sans-ones [numbers]
(for [i (range (+ 1 (count numbers)))]
(keep-indexed #(when (not= %1 i) %2) numbers)))(defn safe? [numbers]
(let [with-sans (sans-ones numbers)]
(some #(and (ordered? %) (no-big-gap? %)) with-sans)))
(count (filter safe? input-2))“Our computers are having issues, so I have no idea if we have any Chief Historians in stock! You’re welcome to check the warehouse, though,” says the mildly flustered shopkeeper at the North Pole Toboggan Rental Shop. The Historians head out to take a look.
The shopkeeper turns to you. “Any chance you can see why our computers are having issues again?”
The computer appears to be trying to run a program, but its memory (your puzzle input) is corrupted. All of the instructions have been jumbled up!
It seems like the goal of the program is just to multiply some numbers. It does that with instructions like mul(X,Y), where X and Y are each 1-3 digit numbers. For instance, mul(44,46) multiplies 44 by 46 to get a result of 2024. Similarly, mul(123,4) would multiply 123 by 4.
However, because the program’s memory has been corrupted, there are also many invalid characters that should be ignored, even if they look like part of a mul instruction. Sequences like mul(4*, mul(6,9!, ?(12,34), or mul ( 2 , 4 ) do nothing.
For example, consider the following section of corrupted memory:
xmul(2,4)%&mul[3,7]!@^do_not_mul(5,5)+mul(32,64]then(mul(11,8)mul(8,5))
Only the four highlighted sections are real mul instructions. Adding up the result of each instruction produces 161 (2*4 + 5*5 + 11*8 + 8*5).
Scan the corrupted memory for uncorrupted mul instructions. What do you get if you add up all of the results of the multiplications?
(defn str-* [x y]
(* (Integer/parseInt x) (Integer/parseInt y)))(reduce +
(for [[_ num1 num2] (re-seq #"mul\((\d+),(\d+)\)" (slurp "input03.txt"))]
(str-* num1 num2)))As you scan through the corrupted memory, you notice that some of the conditional statements are also still intact. If you handle some of the uncorrupted conditional statements in the program, you might be able to get an even more accurate result.
There are two new instructions you’ll need to handle:
The do() instruction enables future mul instructions. The don’t() instruction disables future mul instructions.
Only the most recent do() or don’t() instruction applies. At the beginning of the program, mul instructions are enabled.
For example:
xmul(2,4)&mul[3,7]!^don’t()_mul(5,5)+mul(32,64](mul(11,8)undo()?mul(8,5))
This corrupted memory is similar to the example from before, but this time the mul(5,5) and mul(11,8) instructions are disabled because there is a don’t() instruction before them. The other mul instructions function normally, including the one at the end that gets re-enabled by a do() instruction.
This time, the sum of the results is 48 (2*4 + 8*5).
Handle the new instructions; what do you get if you add up all of the results of just the enabled multiplications?
(def input-3
(let [command-regex #"(do)\(\)|(don't)\(\)|(mul)\((\d+),(\d+)\)"]
(re-seq command-regex (slurp "input03.txt"))))(loop [[[_ & code] & rem] input-3
on? true
acc 0]
(if-not code
acc
(match (vec code)
["do" _ _ _ _] (recur rem true acc)
[_ "don't" _ _ _] (recur rem false acc)
[_ _ "mul" x y] (recur rem on? (if on? (+ acc (str-* x y)) acc)))))“Looks like the Chief’s not here. Next!” One of The Historians pulls out a device and pushes the only button on it. After a brief flash, you recognize the interior of the Ceres monitoring station!
As the search for the Chief continues, a small Elf who lives on the station tugs on your shirt; she’d like to know if you could help her with her word search (your puzzle input). She only has to find one word: XMAS.
This word search allows words to be horizontal, vertical, diagonal, written backwards, or even overlapping other words. It’s a little unusual, though, as you don’t merely need to find one instance of XMAS - you need to find all of them. Here are a few ways XMAS might appear, where irrelevant characters have been replaced with .:
..X… .SAMX. .A..A. XMAS.S .X....
The actual word search will be full of letters instead. For example:
MMMSXXMASM MSAMXMSMSA AMXSXMAAMM MSAMASMSMX XMASAMXAMM XXAMMXXAMA SMSMSASXSS SAXAMASAAA MAMMMXMMMM MXMXAXMASX
In this word search, XMAS occurs a total of 18 times; here’s the same word search again, but where letters not involved in any XMAS have been replaced with .:
....XXMAS. .SAMXMS… …S..A… ..A.A.MS.X XMASAMX.MM X.....XA.A S.S.S.S.SS .A.A.A.A.A ..M.M.M.MM .X.X.XMASX
Take a look at the little Elf’s word search. How many times does XMAS appear?
(def input-4 (slurp "input04.txt"))Oh dear! The vertical and horizontal are easy, I can just do those with regex, after rotating a string:
(defn rotate-str [input]
(->> (str/split-lines input)
(apply mapv vector)
(map #(reduce str %))
(str/join "\n")))
(rotate-str "1111\n2222\n3333\n4444")That looks good!
Now, how the heck do we check for diagonals without indexing? What does that transform look like? I’m thinking that I want a function that takes a string like
1111 2222 3333 4444
And returns a
1 12 123 1234 234 34 4
I think if I index the dimension with the bigger number (so, like, more rows or more columns) I can return things like:
For the length of the side
1 -> 1,1 2 -> 1,2 and 2,1 3 -> 1,3, 2,2, and 3,1 4 -> 1,4, 2,3, 3,2 and 4,1
And then counting down the side with the same idea:
5 -> 2,4, 3,3, 4,2 6 -> 3,4 and 4,3 7 -> 4,4
So first, we need a cross-count like the above:
(defn cross-count [a b]
(let [finish [b a]]
(loop [a a
b b
acc []]
(if (= [a b] finish)
(conj acc finish)
(recur (+ a 1) (- b 1) (conj acc [a b]))))))
(cross-count 2 4)That looks good! Alright! Time to do a fancy indexing transform!
(defn get-corners [max-x max-y]
(loop [row 1
x 1
y 1
rows []]
(if (and (= x max-x) (= y max-y))
(conj rows [max-x max-y])
(if (>= row max-y)
(recur (+ 1 row) (+ 1 x) y (conj rows [x y]))
(recur (+ 1 row) x (+ 1 y) (conj rows [x y]))))))
(get-corners 4 4)Now, lets get some coordinate lists for each row based on these!
(defn diagonalize-list [input]
(let [[firstline & _ :as whole] (str/split-lines input)
[min max] (sort [(count firstline) (count whole)])]
(for [line (map #(apply cross-count %) (get-corners max min))]
(for [[x y] line :let [current-line (get whole (- y 1))]]
(get current-line (- x 1))))))
(defn diagonalize-string [input]
(->> (diagonalize-list input)
(map #(apply str (reverse %)))
(str/join "\n")))
(diagonalize-string "1111\n2222\n3333\n4444")Alright! Time to count everything together! (Using a lookahead to allow overlapping matches)
(defn count-xmas [input]
(let [diagonal (diagonalize-string input)
rotated (rotate-str input)
rdiagonal (diagonalize-string rotated)]
(->> [input diagonal rotated rdiagonal]
(map #(count (re-seq #"(?=XMAS|SAMX)." %)))
(reduce +))))
(count-xmas (slurp "input04t.txt"))There we go!
So how many do I have in the real deal?
(count-xmas input-4)Huh, apparently this is too low? What cases am I missing?
Horizontal:
(count (re-seq #"(?=XMAS|SAMX)." "XMASAMX"))Vertical:
(rotate-str (str/join "\n" "XMASAMX"))Diagonals:
(let [dl "X......\n.M.....\n..A....\n...S...\n....A..\n.....M.\n......X"]
(rotate-str dl))Ooh! This looks wrong How do I rotate this better?
(let [dl "X......\n.M.....\n..A....\n...S...\n....A..\n.....M.\n......X"
reversed (map (comp #(apply str %) reverse) (str/split-lines dl))]
(diagonalize-string (str/join "\n" reversed)))
There it is!
(defn reverse-str [input]
(->> (str/split-lines input)
(map (comp #(apply str %) reverse))
(str/join "\n")))
(defn count-xmas [input]
(let [diagonal (diagonalize-string input)
rotated (rotate-str input)
rdiagonal (diagonalize-string (reverse-str input))]
(->> [input diagonal rotated rdiagonal]
(map #(count (re-seq #"(?=XMAS|SAMX)." %)))
(reduce +))))
(count-xmas (slurp "input04t.txt"))Aaand moment of truth!
(count-xmas input-4)The Elf looks quizzically at you. Did you misunderstand the assignment?
Looking for the instructions, you flip over the word search to find that this isn’t actually an XMAS puzzle; it’s an X-MAS puzzle in which you’re supposed to find two MAS in the shape of an X. One way to achieve that is like this:
M.S .A. M.S
Irrelevant characters have again been replaced with . in the above diagram. Within the X, each MAS can be written forwards or backwards.
Here’s the same example from before, but this time all of the X-MASes have been kept instead:
.M.S...... ..A..MSMS. .M.S.MAA.. ..A.ASMSM. .M.S.M.... .......... S.S.S.S.S. .A.A.A.A.. M.M.M.M.M. ..........
In this example, an X-MAS appears 9 times.
Flip the word search from the instructions back over to the word search side and try again. How many times does an X-MAS appear?
Welp! I guess my approach from part 1 was a little spicy, maybe I need to do traversal instead…which means, reparsing my input! Woo
(def input-4 (str/split-lines (slurp "input04.txt")))
(defn get-4 [x y]
(get-in input-4 [y x]))So! I thought that I needed to get both diagonal crosses and vertical ones, so I had another thing called t-dirs for a bit! Oops
My reasoning for separating them out is that, as long as 2 match in either one, I was able to guarantee that a cross has been made, since "MAS" reversed will never also be "MAS"
But then again, that logic still works with only one set of directions
(def cross-dirs
(let [dirs [[[-1 -1] [0 0] [1 1]]
[[1 -1] [0 0] [-1 1]]]]
(concat dirs (map reverse dirs))))
(defn apply-dir [x y dir]
(->> (map (fn [[dx dy]] [(+ x dx) (+ y dy)]) dir)
(filter (fn [[x y]] (and (>= x 0) (>= y 0))))))
(defn get-cross-coords [x y]
(->> (map #(apply-dir x y %) cross-dirs)
(filter #(= 3 (count %)))))
(defn get-cross-strs [x y]
(frequencies
(for [cross (get-cross-coords x y)]
(apply str (map (fn [[x y]] (get-4 x y)) cross)))))
(defn cross-mas? [x y]
(= 2 ((get-cross-strs x y) "MAS")))
(cross-mas? 1 1)And with that! I just gotta move through the list and add the cross count together!
(let [width (count (first input-4))
height (count input-4)]
(loop [x 0
y 0
count 0]
(if (and (= x width) (= y height))
count
(let [mas-count (+ count (if (cross-mas? x y) 1 0))]
(if (= x width)
(recur 0 (+ 1 y) mas-count)
(recur (+ 1 x) y mas-count))))))Satisfied with their search on Ceres, the squadron of scholars suggests subsequently scanning the stationery stacks of sub-basement 17.
The North Pole printing department is busier than ever this close to Christmas, and while The Historians continue their search of this historically significant facility, an Elf operating a very familiar printer beckons you over.
The Elf must recognize you, because they waste no time explaining that the new sleigh launch safety manual updates won’t print correctly. Failure to update the safety manuals would be dire indeed, so you offer your services.
Safety protocols clearly indicate that new pages for the safety manuals must be printed in a very specific order. The notation X|Y means that if both page number X and page number Y are to be produced as part of an update, page number X must be printed at some point before page number Y.
The Elf has for you both the page ordering rules and the pages to produce in each update (your puzzle input), but can’t figure out whether each update has the pages in the right order.
For example:
47|53 97|13 97|61 97|47 75|29 61|13 75|53 29|13 97|29 53|29 61|53 97|53 61|29 47|13 75|47 97|75 47|61 75|61 47|29 75|13 53|13
75,47,61,53,29 97,61,53,29,13 75,29,13 75,97,47,61,53 61,13,29 97,13,75,29,47
The first section specifies the page ordering rules, one per line. The first rule, 47|53, means that if an update includes both page number 47 and page number 53, then page number 47 must be printed at some point before page number 53. (47 doesn’t necessarily need to be immediately before 53; other pages are allowed to be between them.)
The second section specifies the page numbers of each update. Because most safety manuals are different, the pages needed in the updates are different too. The first update, 75,47,61,53,29, means that the update consists of page numbers 75, 47, 61, 53, and 29.
To get the printers going as soon as possible, start by identifying which updates are already in the right order.
In the above example, the first update (75,47,61,53,29) is in the right order:
75 is correctly first because there are rules that put each other page after it: 75|47, 75|61, 75|53, and 75|29. 47 is correctly second because 75 must be before it (75|47) and every other page must be after it according to 47|61, 47|53, and 47|29. 61 is correctly in the middle because 75 and 47 are before it (75|61 and 47|61) and 53 and 29 are after it (61|53 and 61|29). 53 is correctly fourth because it is before page number 29 (53|29). 29 is the only page left and so is correctly last.
Because the first update does not include some page numbers, the ordering rules involving those missing page numbers are ignored.
The second and third updates are also in the correct order according to the rules. Like the first update, they also do not include every page number, and so only some of the ordering rules apply - within each update, the ordering rules that involve missing page numbers are not used.
The fourth update, 75,97,47,61,53, is not in the correct order: it would print 75 before 97, which violates the rule 97|75.
The fifth update, 61,13,29, is also not in the correct order, since it breaks the rule 29|13.
The last update, 97,13,75,29,47, is not in the correct order due to breaking several rules.
For some reason, the Elves also need to know the middle page number of each update being printed. Because you are currently only printing the correctly-ordered updates, you will need to find the middle page number of each correctly-ordered update. In the above example, the correctly-ordered updates are:
75,47,61,53,29 97,61,53,29,13 75,29,13
These have middle page numbers of 61, 53, and 29 respectively. Adding these page numbers together gives 143.
Of course, you’ll need to be careful: the actual list of page ordering rules is bigger and more complicated than the above example.
Determine which updates are already in the correct order. What do you get if you add up the middle page number from those correctly-ordered updates?
First parsing the data into two vars
(let [[rules updates] (str/split (slurp "input05.txt") #"\n\n")]
(def input-5-rules
(for [rule (str/split-lines rules) :let [[a b] (str/split rule #"\|")]]
[(Integer/parseInt a) (Integer/parseInt b)]))
(def input-5-updates
(for [ud (str/split-lines updates) :let [pages (str/split ud #",")]]
(map #(Integer/parseInt %) pages))))Then for the rules!
(defn get-valid-following [num]
(->> (filter (fn [[before]] (= before num)) input-5-rules)
(map second)
(into #{})))
(defn follows-rules? [update]
(loop [[page & following] update]
(if-not page
true
(when (every? (get-valid-following page) following)
(recur following)))))
(defn get-middle [update]
(let [idx (-> (count update) (+ 1) (/ 2) (- 1))]
(nth update idx)))And finally for the answer math!
(->> (filter follows-rules? input-5-updates)
(map get-middle)
(reduce +))While the Elves get to work printing the correctly-ordered updates, you have a little time to fix the rest of them.
For each of the incorrectly-ordered updates, use the page ordering rules to put the page numbers in the right order. For the above example, here are the three incorrectly-ordered updates and their correct orderings:
75,97,47,61,53 becomes 97,75,47,61,53. 61,13,29 becomes 61,29,13. 97,13,75,29,47 becomes 97,75,47,29,13.
After taking only the incorrectly-ordered updates and ordering them correctly, their middle page numbers are 47, 29, and 47. Adding these together produces 123.
Find the updates which are not in the correct order. What do you get if you add up the middle page numbers after correctly ordering just those updates?
So, lets get the incorrectly ordered stuff! (and order it!)
(def ordered-better
(for [bad (remove follows-rules? input-5-updates)]
(sort (fn [a b] (if ((get-valid-following a) b) -1 1)) bad)))How does this sum?
(->> ordered-better (map get-middle) (reduce +))The Historians use their fancy device again, this time to whisk you all away to the North Pole prototype suit manufacturing lab… in the year 1518! It turns out that having direct access to history is very convenient for a group of historians.
You still have to be careful of time paradoxes, and so it will be important to avoid anyone from 1518 while The Historians search for the Chief. Unfortunately, a single guard is patrolling this part of the lab.
Maybe you can work out where the guard will go ahead of time so that The Historians can search safely?
You start by making a map (your puzzle input) of the situation. For example:
....#..... .........# .......... ..#....... .......#.. .......... .#..^..... ........#. #......... ......#…
The map shows the current position of the guard with ^ (to indicate the guard is currently facing up from the perspective of the map). Any obstructions - crates, desks, alchemical reactors, etc. - are shown as #.
Lab guards in 1518 follow a very strict patrol protocol which involves repeatedly following these steps:
If there is something directly in front of you, turn right 90 degrees. Otherwise, take a step forward.
Following the above protocol, the guard moves up several times until she reaches an obstacle (in this case, a pile of failed suit prototypes):
....#..... ....^....# .......... ..#....... .......#.. .......... .#........ ........#. #......... ......#…
Because there is now an obstacle in front of the guard, she turns right before continuing straight in her new facing direction:
....#..... ........># .......... ..#....... .......#.. .......... .#........ ........#. #......... ......#…
Reaching another obstacle (a spool of several very long polymers), she turns right again and continues downward:
....#..... .........# .......... ..#....... .......#.. .......... .#......v. ........#. #......... ......#…
This process continues for a while, but the guard eventually leaves the mapped area (after walking past a tank of universal solvent):
....#..... .........# .......... ..#....... .......#.. .......... .#........ ........#. #......... ......#v..
By predicting the guard’s route, you can determine which specific positions in the lab will be in the patrol path. Including the guard’s starting position, the positions visited by the guard before leaving the area are marked with an X:
....#..... ....XXXXX# ....X…X. ..#.X…X. ..XXXXX#X. ..X.X.X.X. .#XXXXXXX. .XXXXXXX#. #XXXXXXX.. ......#X..
In this example, the guard will visit 41 distinct positions on your map.
Predict the path of the guard. How many distinct positions will the guard visit before leaving the mapped area?
(def input-6 (str/split-lines (slurp "input06.txt")))
(def guard (first
(keep-indexed
#(if-let [[[dir]] (re-seq #"\^|>|v|<" %2)]
{:dir dir :coord [(str/index-of %2 dir) %1]}) input-6)))(defn move-guard [[x y] dir]
(case dir
\^ [x (- y 1)]
\v [x (+ y 1)]
\< [(- x 1) y]
\> [(+ x 1) y]))
(defn bonk-guard [dir]
({\^ \>, \v \<, \< \^, \> \v} dir))
(defn update-guard [map {:keys [coord dir]}]
(let [[nx ny :as next] (move-guard coord dir)]
(if (= (get-in map [ny nx]) \#)
{:coord coord :dir (bonk-guard dir)}
{:coord next :dir dir})))
(defn full-walk [guard map]
(take-while
(fn [{[x y] :coord}] (get-in map [y x]))
(iterate (partial update-guard map) guard)))(->> (map :coord (full-walk guard input-6))
(into #{})
count)While The Historians begin working around the guard’s patrol route, you borrow their fancy device and step outside the lab. From the safety of a supply closet, you time travel through the last few months and record the nightly status of the lab’s guard post on the walls of the closet.
Returning after what seems like only a few seconds to The Historians, they explain that the guard’s patrol area is simply too large for them to safely search the lab without getting caught.
Fortunately, they are pretty sure that adding a single new obstruction won’t cause a time paradox. They’d like to place the new obstruction in such a way that the guard will get stuck in a loop, making the rest of the lab safe to search.
To have the lowest chance of creating a time paradox, The Historians would like to know all of the possible positions for such an obstruction. The new obstruction can’t be placed at the guard’s starting position - the guard is there right now and would notice.
In the above example, there are only 6 different positions where a new obstruction would cause the guard to get stuck in a loop. The diagrams of these six situations use O to mark the new obstruction, | to show a position where the guard moves up/down, - to show a position where the guard moves left/right, and + to show a position where the guard moves both up/down and left/right.
Option one, put a printing press next to the guard’s starting position:
....#..... ....+—+# ....|…|. ..#.|…|. ....|..#|. ....|…|. .#.O^—+. ........#. #......... ......#…
Option two, put a stack of failed suit prototypes in the bottom right quadrant of the mapped area:
....#..... ....+—+# ....|…|. ..#.|…|. ..+-+-+#|. ..|.|.|.|. .#+-^-+-+. ......O.#. #......... ......#…
Option three, put a crate of chimney-squeeze prototype fabric next to the standing desk in the bottom right quadrant:
....#..... ....+—+# ....|…|. ..#.|…|. ..+-+-+#|. ..|.|.|.|. .#+-^-+-+. .+----+O#. #+----+… ......#…
Option four, put an alchemical retroencabulator near the bottom left corner:
....#..... ....+—+# ....|…|. ..#.|…|. ..+-+-+#|. ..|.|.|.|. .#+-^-+-+. ..|…|.#. #O+—+… ......#…
Option five, put the alchemical retroencabulator a bit to the right instead:
....#..... ....+—+# ....|…|. ..#.|…|. ..+-+-+#|. ..|.|.|.|. .#+-^-+-+. ....|.|.#. #..O+-+… ......#…
Option six, put a tank of sovereign glue right next to the tank of universal solvent:
....#..... ....+—+# ....|…|. ..#.|…|. ..+-+-+#|. ..|.|.|.|. .#+-^-+-+. .+----++#. #+----++.. ......#O..
It doesn’t really matter what you choose to use as an obstacle so long as you and The Historians can put it into position without the guard noticing. The important thing is having enough options that you can find one that minimizes time paradoxes, and in this example, there are 6 different positions you could choose.
You need to get the guard stuck in a loop by adding a single new obstruction. How many different positions could you choose for this obstruction?
(defn guard-loop? [guard map]
(loop [[position & rest] (full-walk guard map)
visited #{}]
(if-not position
false
(if (visited position)
true
(recur rest (conj visited position))))))
(let [map-a (vec (map vec input-6))]
(defn with-wall [x y]
(assoc-in map-a [y x] \#)))
(defn get-blocks-that-loop [[first-row :as all-rows]]
(for [[x y] (into #{} (map :coord (full-walk guard input-6)))
:when (and (not= (guard :coord) [x y])
(guard-loop? guard (with-wall x y)))]
[x y]))(count (get-blocks-that-loop input-6))The Historians take you to a familiar rope bridge over a river in the middle of a jungle. The Chief isn’t on this side of the bridge, though; maybe he’s on the other side?
When you go to cross the bridge, you notice a group of engineers trying to repair it. (Apparently, it breaks pretty frequently.) You won’t be able to cross until it’s fixed.
You ask how long it’ll take; the engineers tell you that it only needs final calibrations, but some young elephants were playing nearby and stole all the operators from their calibration equations! They could finish the calibrations if only someone could determine which test values could possibly be produced by placing any combination of operators into their calibration equations (your puzzle input).
For example:
190: 10 19 3267: 81 40 27 83: 17 5 156: 15 6 7290: 6 8 6 15 161011: 16 10 13 192: 17 8 14 21037: 9 7 18 13 292: 11 6 16 20
Each line represents a single equation. The test value appears before the colon on each line; it is your job to determine whether the remaining numbers can be combined with operators to produce the test value.
Operators are always evaluated left-to-right, not according to precedence rules. Furthermore, numbers in the equations cannot be rearranged. Glancing into the jungle, you can see elephants holding two different types of operators: add (+) and multiply (*).
Only three of the above equations can be made true by inserting operators:
190: 10 19 has only one position that accepts an operator: between 10 and 19. Choosing + would give 29, but choosing * would give the test value (10 * 19 = 190). 3267: 81 40 27 has two positions for operators. Of the four possible configurations of the operators, two cause the right side to match the test value: 81 + 40 * 27 and 81 * 40 + 27 both equal 3267 (when evaluated left-to-right)! 292: 11 6 16 20 can be solved in exactly one way: 11 + 6 * 16 + 20.
The engineers just need the total calibration result, which is the sum of the test values from just the equations that could possibly be true. In the above example, the sum of the test values for the three equations listed above is 3749.
Determine which equations could possibly be true. What is their total calibration result?
(def input-7
(for [equation (str/split-lines (slurp "input07.txt"))]
(let [[[_ answer nums]] (re-seq #"(\d+): (.*)" equation)]
{:answer (Long/parseLong answer)
:numbers (->> (str/split nums #" ") (map #(Long/parseLong %)))})))(defn equation->forms [equation]
(loop [[form & rest] equation
forms [[]]]
(if-not form
forms
(if (vector? form)
(recur rest (mapcat (fn [op] (map #(conj % op) forms)) form))
(recur rest (map #(conj % form) forms))))))
(defn run-form [form]
(loop [[num1 op num2 & rest] form]
(if-not op
num1
(recur (cons (op num1 num2) rest)))))
(defn solveable? [ops {:keys [answer numbers]}]
(->> (equation->forms (butlast (interleave numbers (repeat ops))))
(some #(= answer (run-form %)))))
(reduce + (map :answer (filter (partial solveable? [* +]) input-7)))The engineers seem concerned; the total calibration result you gave them is nowhere close to being within safety tolerances. Just then, you spot your mistake: some well-hidden elephants are holding a third type of operator.
The concatenation operator (||) combines the digits from its left and right inputs into a single number. For example, 12 || 345 would become 12345. All operators are still evaluated left-to-right.
Now, apart from the three equations that could be made true using only addition and multiplication, the above example has three more equations that can be made true by inserting operators:
156: 15 6 can be made true through a single concatenation: 15 || 6 = 156. 7290: 6 8 6 15 can be made true using 6 * 8 || 6 * 15. 192: 17 8 14 can be made true using 17 || 8 + 14.
Adding up all six test values (the three that could be made before using only + and * plus the new three that can now be made by also using ||) produces the new total calibration result of 11387.
Using your new knowledge of elephant hiding spots, determine which equations could possibly be true. What is their total calibration result?
(let [catnum (comp Long/parseLong str)]
(->> (filter (partial solveable? [* + catnum]) input-7)
(map :answer)
(reduce +)))You find yourselves on the roof of a top-secret Easter Bunny installation.
While The Historians do their thing, you take a look at the familiar huge antenna. Much to your surprise, it seems to have been reconfigured to emit a signal that makes people 0.1% more likely to buy Easter Bunny brand Imitation Mediocre Chocolate as a Christmas gift! Unthinkable!
Scanning across the city, you find that there are actually many such antennas. Each antenna is tuned to a specific frequency indicated by a single lowercase letter, uppercase letter, or digit. You create a map (your puzzle input) of these antennas. For example:
............ ........0… .....0...... .......0.... ....0....... ......A..... ............ ............ ........A… .........A.. ............ ............
The signal only applies its nefarious effect at specific antinodes based on the resonant frequencies of the antennas. In particular, an antinode occurs at any point that is perfectly in line with two antennas of the same frequency - but only when one of the antennas is twice as far away as the other. This means that for any pair of antennas with the same frequency, there are two antinodes, one on either side of them.
So, for these two antennas with frequency a, they create the two antinodes marked with #:
.......... …#...... .......... ....a..... .......... .....a.... .......... ......#… .......... ..........
Adding a third antenna with the same frequency creates several more antinodes. It would ideally add four antinodes, but two are off the right side of the map, so instead it adds only two:
.......... …#...... #......... ....a..... ........a. .....a.... ..#....... ......#… .......... ..........
Antennas with different frequencies don’t create antinodes; A and a count as different frequencies. However, antinodes can occur at locations that contain antennas. In this diagram, the lone antenna with frequency capital A creates no antinodes but has a lowercase-a-frequency antinode at its location:
.......... …#...... #......... ....a..... ........a. .....a.... ..#....... ......A… .......... ..........
The first example has antennas with two different frequencies, so the antinodes they create look like this, plus an antinode overlapping the topmost A-frequency antenna:
......#....# …#....0… ....#0....#. ..#....0.... ....0....#.. .#....A..... …#........ #......#.... ........A… .........A.. ..........#. ..........#.
Because the topmost A-frequency antenna overlaps with a 0-frequency antinode, there are 14 total unique locations that contain an antinode within the bounds of the map.
Calculate the impact of the signal. How many unique locations within the bounds of the map contain an antinode?
(def input-8 (str/split-lines (slurp "input08.txt")))
(def antennas
(let [lines input-8
->indexed (partial map-indexed vector)]
(loop [[[y line] & rest :as full] (->indexed lines)
[[x char] & chars] (->indexed line)
acc {}]
(cond
(not y) acc
(not x) (recur rest (-> rest first second ->indexed) acc)
:else
(if-let [[antenna] (re-find #"[a-zA-Z0-9]" (str char))]
(let [cords (get acc antenna [])]
(recur full chars (assoc acc antenna (conj cords [x y]))))
(recur full chars acc))))))(defn vec-apply [f [x1 y1] [x2 y2]]
[(f x1 x2) (f y1 y2)])
(defn get-antinodes [antenna1 antenna2]
(let [dist (vec-apply - antenna1 antenna2)]
[(vec-apply + antenna1 dist) (vec-apply - antenna2 dist)]))
(defn freq-antinodes [antenna-freq]
(let [height (- (count input-8) 1)
width (- (count (first input-8)) 1)]
(->> (combo/combinations (antennas antenna-freq) 2)
(mapcat #(apply get-antinodes %))
(filter (fn [[x y]] (and (<= 0 x width) (<= 0 y height)))))))(->> (keys antennas)
(mapcat freq-antinodes)
(into #{})
count)So, 389 is too high. But why? Time to visualize it with the test data!!
(let [antenna? (->> (keys antennas) (mapcat freq-antinodes) set)]
(for [[y line] (map-indexed vector input-8)]
(str/join
(for [[x char] (map-indexed vector line)]
(if (antenna? [x y]) \# char)))))
This…is right?? But then what edge cases am I missing? Am I maybe not trimming edge nodes enough? Time to visualize the whole thing I guess!
There are 376 antinodes in this render, uhhh…what’s up with my code?
…ah, off by one in my filter in antinodes, oops.
Watching over your shoulder as you work, one of The Historians asks if you took the effects of resonant harmonics into your calculations.
Whoops!
After updating your model, it turns out that an antinode occurs at any grid position exactly in line with at least two antennas of the same frequency, regardless of distance. This means that some of the new antinodes will occur at the position of each antenna (unless that antenna is the only one of its frequency).
So, these three T-frequency antennas now create many antinodes:
T....#.... …T...... .T....#… .........# ..#....... .......... …#...... .......... ....#..... ..........
In fact, the three T-frequency antennas are all exactly in line with two antennas, so they are all also antinodes! This brings the total number of antinodes in the above example to 9.
The original example now has 34 antinodes, including the antinodes that appear on every antenna:
##....#....# .#.#....0… ..#.#0....#. ..##…0.... ....0....#.. .#…#A....# …#..#..... #....#.#.... ..#.....A… ....#....A.. .#........#. …#......##
Calculate the impact of the signal using this updated model. How many unique locations within the bounds of the map contain an antinode?
(let [height (- (count input-8) 1)
width (- (count (first input-8)) 1)]
(defn in-bounds? [[x y]]
(and (<= 0 x width) (<= 0 y height))))
(defn get-antinodes [antenna1 antenna2]
(let [dist (vec-apply - antenna1 antenna2)]
(concat
(take-while in-bounds? (iterate #(vec-apply + % dist) antenna1))
(take-while in-bounds? (iterate #(vec-apply - % dist) antenna2)))))
(->> (keys antennas)
(mapcat freq-antinodes)
(into #{})
count)Another push of the button leaves you in the familiar hallways of some friendly amphipods! Good thing you each somehow got your own personal mini submarine. The Historians jet away in search of the Chief, mostly by driving directly into walls.
While The Historians quickly figure out how to pilot these things, you notice an amphipod in the corner struggling with his computer. He’s trying to make more contiguous free space by compacting all of the files, but his program isn’t working; you offer to help.
He shows you the disk map (your puzzle input) he’s already generated. For example:
2333133121414131402
The disk map uses a dense format to represent the layout of files and free space on the disk. The digits alternate between indicating the length of a file and the length of free space.
So, a disk map like 12345 would represent a one-block file, two blocks of free space, a three-block file, four blocks of free space, and then a five-block file. A disk map like 90909 would represent three nine-block files in a row (with no free space between them).
Each file on disk also has an ID number based on the order of the files as they appear before they are rearranged, starting with ID 0. So, the disk map 12345 has three files: a one-block file with ID 0, a three-block file with ID 1, and a five-block file with ID 2. Using one character for each block where digits are the file ID and . is free space, the disk map 12345 represents these individual blocks:
0..111....22222
The first example above, 2333133121414131402, represents these individual blocks:
00…111…2…333.44.5555.6666.777.888899
The amphipod would like to move file blocks one at a time from the end of the disk to the leftmost free space block (until there are no gaps remaining between file blocks). For the disk map 12345, the process looks like this:
0..111....22222 02.111....2222. 022111....222.. 0221112…22… 02211122..2.... 022111222......
The first example requires a few more steps:
00…111…2…333.44.5555.6666.777.888899 009..111…2…333.44.5555.6666.777.88889. 0099.111…2…333.44.5555.6666.777.8888.. 00998111…2…333.44.5555.6666.777.888… 009981118..2…333.44.5555.6666.777.88.... 0099811188.2…333.44.5555.6666.777.8..... 009981118882…333.44.5555.6666.777....... 0099811188827..333.44.5555.6666.77........ 00998111888277.333.44.5555.6666.7......... 009981118882777333.44.5555.6666........... 009981118882777333644.5555.666............ 00998111888277733364465555.66............. 0099811188827773336446555566..............
The final step of this file-compacting process is to update the filesystem checksum. To calculate the checksum, add up the result of multiplying each of these blocks’ position with the file ID number it contains. The leftmost block is in position 0. If a block contains free space, skip it instead.
Continuing the first example, the first few blocks’ position multiplied by its file ID number are 0 * 0 = 0, 1 * 0 = 0, 2 * 9 = 18, 3 * 9 = 27, 4 * 8 = 32, and so on. In this example, the checksum is the sum of these, 1928.
Compact the amphipod’s hard drive using the process he requested. What is the resulting filesystem checksum? (Be careful copy/pasting the input for this puzzle; it is a single, very long line.)
(def input-9
(->> (re-seq #"\d" (slurp "input09t.txt"))
(map Integer/parseInt)
(partition 2 2 [0])
(map-indexed vector)))
(def disk-layout
(loop [[[i [num gap]] & rem] input-9
disk []]
(if-not i
disk
(recur rem (concat disk (repeat num i) (repeat gap nil))))))
(def disk-size (reduce + (map (comp first second) input-9)))(defn defrag [layout disk-size]
(loop [[sector & rem] layout
[last & rem-r :as revd] (remove nil? (reverse layout))
disk []
size 0]
(if (= size disk-size)
disk
(if sector
(recur rem revd (conj disk sector) (+ 1 size))
(recur rem rem-r (conj disk last) (+ 1 size))))))
(defn checksum [disk]
(->> (map-indexed vector disk)
(map (fn [[pos id]] (* pos id)))
(reduce +)))(checksum (defrag disk-layout disk-size))You all arrive at a Lava Production Facility on a floating island in the sky. As the others begin to search the massive industrial complex, you feel a small nose boop your leg and look down to discover a reindeer wearing a hard hat.
The reindeer is holding a book titled “Lava Island Hiking Guide”. However, when you open the book, you discover that most of it seems to have been scorched by lava! As you’re about to ask how you can help, the reindeer brings you a blank topographic map of the surrounding area (your puzzle input) and looks up at you excitedly.
Perhaps you can help fill in the missing hiking trails?
The topographic map indicates the height at each position using a scale from 0 (lowest) to 9 (highest). For example:
0123 1234 8765 9876
Based on un-scorched scraps of the book, you determine that a good hiking trail is as long as possible and has an even, gradual, uphill slope. For all practical purposes, this means that a hiking trail is any path that starts at height 0, ends at height 9, and always increases by a height of exactly 1 at each step. Hiking trails never include diagonal steps - only up, down, left, or right (from the perspective of the map).
You look up from the map and notice that the reindeer has helpfully begun to construct a small pile of pencils, markers, rulers, compasses, stickers, and other equipment you might need to update the map with hiking trails.
A trailhead is any position that starts one or more hiking trails - here, these positions will always have height 0. Assembling more fragments of pages, you establish that a trailhead’s score is the number of 9-height positions reachable from that trailhead via a hiking trail. In the above example, the single trailhead in the top left corner has a score of 1 because it can reach a single 9 (the one in the bottom left).
This trailhead has a score of 2:
…0… …1… …2… 6543456 7.....7 8.....8 9.....9
(The positions marked . are impassable tiles to simplify these examples; they do not appear on your actual topographic map.)
This trailhead has a score of 4 because every 9 is reachable via a hiking trail except the one immediately to the left of the trailhead:
..90..9 …1.98 …2..7 6543456 765.987 876.... 987....
This topographic map contains two trailheads; the trailhead at the top has a score of 1, while the trailhead at the bottom has a score of 2:
10..9.. 2…8.. 3…7.. 4567654 …8..3 …9..2 .....01
Here’s a larger example:
89010123 78121874 87430965 96549874 45678903 32019012 01329801 10456732
This larger example has 9 trailheads. Considering the trailheads in reading order, they have scores of 5, 6, 5, 3, 1, 3, 5, 3, and 5. Adding these scores together, the sum of the scores of all trailheads is 36.
The reindeer gleefully carries over a protractor and adds it to the pile. What is the sum of the scores of all trailheads on your topographic map?
(def input-10 (vec
(for [line (str/split-lines (slurp "input10t2.txt"))]
(vec (map (comp Integer/parseInt str) line)))))
(def ->idx
(partial map-indexed vector))
(loop [[[y line] & [[_ nline] :as rem-y] :as full] (->idx input-10)
[[x height] & rem-x] (->idx line)
heads #{}
peaks #{}]
(cond
(not y) [(def heads heads) (def peaks peaks)]
(not x) (recur rem-y (->idx nline) heads peaks)
(= 0 height) (recur full rem-x (conj heads [x y]) peaks)
(= 9 height) (recur full rem-x heads (conj peaks [x y]))
:else (recur full rem-x heads peaks)))
(defn get-10 [[x y]]
(get-in input-10 [y x]))(defn get-next-steps [[x y :as coord]]
(let [next (+ 1 (get-10 coord))
dirs [[0 -1] [-1 0] [1 0] [0 1]]]
(->> (map (fn [[dx dy]] [(+ x dx) (+ y dy)]) dirs)
(keep #(when (= next (get-10 %)) %)))))
(defn get-trailhead-score [start]
(loop [paths (get-next-steps start)
level 1]
(cond
(empty? paths) 0
(= 9 level) (count paths)
:else (recur (set (mapcat get-next-steps paths)) (+ 1 level)))))(reduce + (map get-trailhead-score heads))The ancient civilization on Pluto was known for its ability to manipulate spacetime, and while The Historians explore their infinite corridors, you’ve noticed a strange set of physics-defying stones.
At first glance, they seem like normal stones: they’re arranged in a perfectly straight line, and each stone has a number engraved on it.
The strange part is that every time you blink, the stones change.
Sometimes, the number engraved on a stone changes. Other times, a stone might split in two, causing all the other stones to shift over a bit to make room in their perfectly straight line.
As you observe them for a while, you find that the stones have a consistent behavior. Every time you blink, the stones each simultaneously change according to the first applicable rule in this list:
If the stone is engraved with the number 0, it is replaced by a stone engraved with the number 1. If the stone is engraved with a number that has an even number of digits, it is replaced by two stones. The left half of the digits are engraved on the new left stone, and the right half of the digits are engraved on the new right stone. (The new numbers don’t keep extra leading zeroes: 1000 would become stones 10 and 0.) If none of the other rules apply, the stone is replaced by a new stone; the old stone’s number multiplied by 2024 is engraved on the new stone.
No matter how the stones change, their order is preserved, and they stay on their perfectly straight line.
How will the stones evolve if you keep blinking at them? You take a note of the number engraved on each stone in the line (your puzzle input).
If you have an arrangement of five stones engraved with the numbers 0 1 10 99 999 and you blink once, the stones transform as follows:
The first stone, 0, becomes a stone marked 1. The second stone, 1, is multiplied by 2024 to become 2024. The third stone, 10, is split into a stone marked 1 followed by a stone marked 0. The fourth stone, 99, is split into two stones marked 9. The fifth stone, 999, is replaced by a stone marked 2021976.
So, after blinking once, your five stones would become an arrangement of seven stones engraved with the numbers 1 2024 1 0 9 9 2021976.
Here is a longer example:
Initial arrangement: 125 17
After 1 blink: 253000 1 7
After 2 blinks: 253 0 2024 14168
After 3 blinks: 512072 1 20 24 28676032
After 4 blinks: 512 72 2024 2 0 2 4 2867 6032
After 5 blinks: 1036288 7 2 20 24 4048 1 4048 8096 28 67 60 32
After 6 blinks: 2097446912 14168 4048 2 0 2 4 40 48 2024 40 48 80 96 2 8 6 7 6 0 3 2
In this example, after blinking six times, you would have 22 stones. After blinking 25 times, you would have 55312 stones!
Consider the arrangement of stones in front of you. How many stones will you have after blinking 25 times?
(def input-11
(map Integer/parseInt (re-seq #"\d+" (slurp "input11t.txt"))))(defn split-num [num]
(->> (split-at (/ (count num) 2) num)
(map (comp Integer/parseInt (partial apply str)))))
(defn num->cells [num]
(cond
(= 0 num) [1]
(-> num str count even?) (split-num (str num))
:else [(* 2024 num)]))(-> (iterate (partial mapcat num->cells) input-11)
(nth 25)
count)Why not search for the Chief Historian near the gardener and his massive farm? There’s plenty of food, so The Historians grab something to eat while they search.
You’re about to settle near a complex arrangement of garden plots when some Elves ask if you can lend a hand. They’d like to set up fences around each region of garden plots, but they can’t figure out how much fence they need to order or how much it will cost. They hand you a map (your puzzle input) of the garden plots.
Each garden plot grows only a single type of plant and is indicated by a single letter on your map. When multiple garden plots are growing the same type of plant and are touching (horizontally or vertically), they form a region. For example:
AAAA BBCD BBCC EEEC
This 4x4 arrangement includes garden plots growing five different types of plants (labeled A, B, C, D, and E), each grouped into their own region.
In order to accurately calculate the cost of the fence around a single region, you need to know that region’s area and perimeter.
The area of a region is simply the number of garden plots the region contains. The above map’s type A, B, and C plants are each in a region of area 4. The type E plants are in a region of area 3; the type D plants are in a region of area 1.
Each garden plot is a square and so has four sides. The perimeter of a region is the number of sides of garden plots in the region that do not touch another garden plot in the same region. The type A and C plants are each in a region with perimeter 10. The type B and E plants are each in a region with perimeter 8. The lone D plot forms its own region with perimeter 4.
Visually indicating the sides of plots in each region that contribute to the perimeter using - and |, the above map’s regions’ perimeters are measured as follows:
--+-+-+
A A A A
--+-+-+-
D
--+--
B B C
- + +
-
B B C C
--+-+
C
--+-+-
E E E
--+-+Plants of the same type can appear in multiple separate regions, and regions can even appear within other regions. For example:
OOOOO OXOXO OOOOO OXOXO OOOOO
The above map contains five regions, one containing all of the O garden plots, and the other four each containing a single X plot.
The four X regions each have area 1 and perimeter 4. The region containing 21 type O plants is more complicated; in addition to its outer edge contributing a perimeter of 20, its boundary with each X region contributes an additional 4 to its perimeter, for a total perimeter of 36.
Due to “modern” business practices, the price of fence required for a region is found by multiplying that region’s area by its perimeter. The total price of fencing all regions on a map is found by adding together the price of fence for every region on the map.
In the first example, region A has price 4 * 10 = 40, region B has price 4 * 8 = 32, region C has price 4 * 10 = 40, region D has price 1 * 4 = 4, and region E has price 3 * 8 = 24. So, the total price for the first example is 140.
In the second example, the region with all of the O plants has price 21 * 36 = 756, and each of the four smaller X regions has price 1 * 4 = 4, for a total price of 772 (756 + 4 + 4 + 4 + 4).
Here’s a larger example:
RRRRIICCFF RRRRIICCCF VVRRRCCFFF VVRCCCJFFF VVVVCJJCFE VVIVCCJJEE VVIIICJJEE MIIIIIJJEE MIIISIJEEE MMMISSJEEE
It contains:
A region of R plants with price 12 * 18 = 216. A region of I plants with price 4 * 8 = 32. A region of C plants with price 14 * 28 = 392. A region of F plants with price 10 * 18 = 180. A region of V plants with price 13 * 20 = 260. A region of J plants with price 11 * 20 = 220. A region of C plants with price 1 * 4 = 4. A region of E plants with price 13 * 18 = 234. A region of I plants with price 14 * 22 = 308. A region of M plants with price 5 * 12 = 60. A region of S plants with price 3 * 8 = 24.
So, it has a total price of 1930.
What is the total price of fencing all regions on your map?
(def input-12
(str/split-lines (slurp "input12t2.txt")))
(defn get-12 [[x y]]
(get-in input-12 [y x]))
(def height (count input-12))
(def width (count (first input-12)))(defn count-walls [[x y :as coord]]
(let [plant (get-12 coord)]
(->> [[0 -1] [-1 0] [1 0] [0 1]]
(remove (fn [[dx dy]] (= plant (get-12 [(+ x dx) (+ y dy)]))))
count
(vector plant))))
(defn count-all-walls []
(loop [y 0
x 0
acc {}]
(cond
(= height y) acc
(= width x) (recur (+ 1 y) 0 acc)
:else
(let [[plant walls] (count-walls [x y])
[area current] (get acc plant [0 0])
updated [(+ area 1) (+ current walls)]]
(recur y (+ 1 x) (assoc acc plant updated))))))(->> (count-all-walls)
vals
(map (partial reduce *))
(apply +))Next up: the lobby of a resort on a tropical island. The Historians take a moment to admire the hexagonal floor tiles before spreading out.
Fortunately, it looks like the resort has a new arcade! Maybe you can win some prizes from the claw machines?
The claw machines here are a little unusual. Instead of a joystick or directional buttons to control the claw, these machines have two buttons labeled A and B. Worse, you can’t just put in a token and play; it costs 3 tokens to push the A button and 1 token to push the B button.
With a little experimentation, you figure out that each machine’s buttons are configured to move the claw a specific amount to the right (along the X axis) and a specific amount forward (along the Y axis) each time that button is pressed.
Each machine contains one prize; to win the prize, the claw must be positioned exactly above the prize on both the X and Y axes.
You wonder: what is the smallest number of tokens you would have to spend to win as many prizes as possible? You assemble a list of every machine’s button behavior and prize location (your puzzle input). For example:
Button A: X+94, Y+34 Button B: X+22, Y+67 Prize: X=8400, Y=5400
Button A: X+26, Y+66 Button B: X+67, Y+21 Prize: X=12748, Y=12176
Button A: X+17, Y+86 Button B: X+84, Y+37 Prize: X=7870, Y=6450
Button A: X+69, Y+23 Button B: X+27, Y+71 Prize: X=18641, Y=10279
This list describes the button configuration and prize location of four different claw machines.
For now, consider just the first claw machine in the list:
Pushing the machine’s A button would move the claw 94 units along the X axis and 34 units along the Y axis. Pushing the B button would move the claw 22 units along the X axis and 67 units along the Y axis. The prize is located at X=8400, Y=5400; this means that from the claw’s initial position, it would need to move exactly 8400 units along the X axis and exactly 5400 units along the Y axis to be perfectly aligned with the prize in this machine.
The cheapest way to win the prize is by pushing the A button 80 times and the B button 40 times. This would line up the claw along the X axis (because 80*94 + 40*22 = 8400) and along the Y axis (because 80*34 + 40*67 = 5400). Doing this would cost 80*3 tokens for the A presses and 40*1 for the B presses, a total of 280 tokens.
For the second and fourth claw machines, there is no combination of A and B presses that will ever win a prize.
For the third claw machine, the cheapest way to win the prize is by pushing the A button 38 times and the B button 86 times. Doing this would cost a total of 200 tokens.
So, the most prizes you could possibly win is two; the minimum tokens you would have to spend to win all (two) prizes is 480.
You estimate that each button would need to be pressed no more than 100 times to win a prize. How else would someone be expected to play?
Figure out how to win as many prizes as possible. What is the fewest tokens you would have to spend to win all possible prizes?
One of The Historians needs to use the bathroom; fortunately, you know there’s a bathroom near an unvisited location on their list, and so you’re all quickly teleported directly to the lobby of Easter Bunny Headquarters.
Unfortunately, EBHQ seems to have “improved” bathroom security again after your last visit. The area outside the bathroom is swarming with robots!
To get The Historian safely to the bathroom, you’ll need a way to predict where the robots will be in the future. Fortunately, they all seem to be moving on the tile floor in predictable straight lines.
You make a list (your puzzle input) of all of the robots’ current positions (p) and velocities (v), one robot per line. For example:
p=0,4 v=3,-3 p=6,3 v=-1,-3 p=10,3 v=-1,2 p=2,0 v=2,-1 p=0,0 v=1,3 p=3,0 v=-2,-2 p=7,6 v=-1,-3 p=3,0 v=-1,-2 p=9,3 v=2,3 p=7,3 v=-1,2 p=2,4 v=2,-3 p=9,5 v=-3,-3
Each robot’s position is given as p=x,y where x represents the number of tiles the robot is from the left wall and y represents the number of tiles from the top wall (when viewed from above). So, a position of p=0,0 means the robot is all the way in the top-left corner.
Each robot’s velocity is given as v=x,y where x and y are given in tiles per second. Positive x means the robot is moving to the right, and positive y means the robot is moving down. So, a velocity of v=1,-2 means that each second, the robot moves 1 tile to the right and 2 tiles up.
The robots outside the actual bathroom are in a space which is 101 tiles wide and 103 tiles tall (when viewed from above). However, in this example, the robots are in a space which is only 11 tiles wide and 7 tiles tall.
The robots are good at navigating over/under each other (due to a combination of springs, extendable legs, and quadcopters), so they can share the same tile and don’t interact with each other. Visually, the number of robots on each tile in this example looks like this:
1.12....... ........... ........... ......11.11 1.1........ .........1. .......1…
These robots have a unique feature for maximum bathroom security: they can teleport. When a robot would run into an edge of the space they’re in, they instead teleport to the other side, effectively wrapping around the edges. Here is what robot p=2,4 v=2,-3 does for the first few seconds:
Initial state: ........... ........... ........... ........... ..1........ ........... ...........
After 1 second: ........... ....1...... ........... ........... ........... ........... ...........
After 2 seconds: ........... ........... ........... ........... ........... ......1.... ...........
After 3 seconds: ........... ........... ........1.. ........... ........... ........... ...........
After 4 seconds: ........... ........... ........... ........... ........... ........... ..........1
After 5 seconds: ........... ........... ........... .1......... ........... ........... ...........
The Historian can’t wait much longer, so you don’t have to simulate the robots for very long. Where will the robots be after 100 seconds?
In the above example, the number of robots on each tile after 100 seconds has elapsed looks like this:
......2..1. ........... 1.......... .11........ .....1..... …12...... .1....1....
To determine the safest area, count the number of robots in each quadrant after 100 seconds. Robots that are exactly in the middle (horizontally or vertically) don’t count as being in any quadrant, so the only relevant robots are:
..... 2..1. ..... ..... 1.... .....
..... ..... …12 ..... .1… 1....
In this example, the quadrants contain 1, 3, 4, and 1 robot. Multiplying these together gives a total safety factor of 12.
Predict the motion of the robots in your list within a space which is 101 tiles wide and 103 tiles tall. What will the safety factor be after exactly 100 seconds have elapsed?
You appear back inside your own mini submarine! Each Historian drives their mini submarine in a different direction; maybe the Chief has his own submarine down here somewhere as well?
You look up to see a vast school of lanternfish swimming past you. On closer inspection, they seem quite anxious, so you drive your mini submarine over to see if you can help.
Because lanternfish populations grow rapidly, they need a lot of food, and that food needs to be stored somewhere. That’s why these lanternfish have built elaborate warehouse complexes operated by robots!
These lanternfish seem so anxious because they have lost control of the robot that operates one of their most important warehouses! It is currently running amok, pushing around boxes in the warehouse with no regard for lanternfish logistics or lanternfish inventory management strategies.
Right now, none of the lanternfish are brave enough to swim up to an unpredictable robot so they could shut it off. However, if you could anticipate the robot’s movements, maybe they could find a safe option.
The lanternfish already have a map of the warehouse and a list of movements the robot will attempt to make (your puzzle input). The problem is that the movements will sometimes fail as boxes are shifted around, making the actual movements of the robot difficult to predict.
For example:
########## #..O..O.O# #......O.# #.OO..O.O# #[email protected].# #O#..O…# #O..O..O.# #.OO.O.OO# #....O…# ##########
<vv>^<v^>v>^vv^v>v<>v^v<v<^vv<<<^><<><>>v<vvv<>^v^>^<<<><<v<<<v^vv^v>^ vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<<v<^v>^<^^>>>^<v<v ><>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^<v>v^^<^^vv< <<v<^>>^^^^>>>v^<>vvv^><v<<<>^^^vv^<vvv>^>v<^^^^v<>^>vvvv><>>v^<<^^^^^ ^><^><>>><>^^<<^^v>>><^<v>^<vv>>v>>>^v><>^v><<<<v>>v<v<v>vvv>^<><<>^>< ^>><>^v<><^vvv<^^<><v<<<<<><^v<<<><<<^^<v<^^^><^>>^<v^><<<^>>^v<v^v<v^ >^>>^v>vv>^<<^v<>><<><<v<<v><>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^ <><^^>^^^<><vvvvv^v<v<<>^v<v>v<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<> ^^>vv<^v^v<vv>^<><v<^v>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<><<v> v^^>>><<^^<>>^v^<v^vv<>v^<<>^<^v^v><^<<<><<^<v><v<>vv>>v><v^<vv<>v^<<^
As the robot (@) attempts to move, if there are any boxes (O) in the way, the robot will also attempt to push those boxes. However, if this action would cause the robot or a box to move into a wall (#), nothing moves instead, including the robot. The initial positions of these are shown on the map at the top of the document the lanternfish gave you.
The rest of the document describes the moves (^ for up, v for down, < for left, > for right) that the robot will attempt to make, in order. (The moves form a single giant sequence; they are broken into multiple lines just to make copy-pasting easier. Newlines within the move sequence should be ignored.)
Here is a smaller example to get started:
######## #..O.O.# ##@.O..# #…O..# #.#.O..# #…O..# #......# ########
<^^>>>vv<v>>v<<
Were the robot to attempt the given sequence of moves, it would push around the boxes as follows:
Initial state: ######## #..O.O.# ##@.O..# #…O..# #.#.O..# #…O..# #......# ########
Move <: ######## #..O.O.# ##@.O..# #…O..# #.#.O..# #…O..# #......# ########
Move ^: ######## #[email protected].# ##..O..# #…O..# #.#.O..# #…O..# #......# ########
Move ^: ######## #[email protected].# ##..O..# #…O..# #.#.O..# #…O..# #......# ########
Move >: ######## #..@OO.# ##..O..# #…O..# #.#.O..# #…O..# #......# ########
Move >: ######## #…@OO# ##..O..# #…O..# #.#.O..# #…O..# #......# ########
Move >: ######## #…@OO# ##..O..# #…O..# #.#.O..# #…O..# #......# ########
Move v: ######## #....OO# ##..@..# #…O..# #.#.O..# #…O..# #…O..# ########
Move v: ######## #....OO# ##..@..# #…O..# #.#.O..# #…O..# #…O..# ########
Move <: ######## #....OO# ##.@…# #…O..# #.#.O..# #…O..# #…O..# ########
Move v: ######## #....OO# ##.....# #..@O..# #.#.O..# #…O..# #…O..# ########
Move >: ######## #....OO# ##.....# #…@O.# #.#.O..# #…O..# #…O..# ########
Move >: ######## #....OO# ##.....# #....@O# #.#.O..# #…O..# #…O..# ########
Move v: ######## #....OO# ##.....# #.....O# #.#.O@.# #…O..# #…O..# ########
Move <: ######## #....OO# ##.....# #.....O# #.#O@..# #…O..# #…O..# ########
Move <: ######## #....OO# ##.....# #.....O# #.#O@..# #…O..# #…O..# ########
The larger example has many more moves; after the robot has finished those moves, the warehouse would look like this:
########## #.O.O.OOO# #........# #OO......# #OO@.....# #O#.....O# #O.....OO# #O.....OO# #OO....OO# ##########
The lanternfish use their own custom Goods Positioning System (GPS for short) to track the locations of the boxes. The GPS coordinate of a box is equal to 100 times its distance from the top edge of the map plus its distance from the left edge of the map. (This process does not stop at wall tiles; measure all the way to the edges of the map.)
So, the box shown below has a distance of 1 from the top edge of the map and 4 from the left edge of the map, resulting in a GPS coordinate of 100 * 1 + 4 = 104.
####### #…O.. #......
The lanternfish would like to know the sum of all boxes’ GPS coordinates after the robot finishes moving. In the larger example, the sum of all boxes’ GPS coordinates is 10092. In the smaller example, the sum is 2028.
Predict the motion of the robot and boxes in the warehouse. After the robot is finished moving, what is the sum of all boxes’ GPS coordinates?
It’s time again for the Reindeer Olympics! This year, the big event is the Reindeer Maze, where the Reindeer compete for the lowest score.
You and The Historians arrive to search for the Chief right as the event is about to start. It wouldn’t hurt to watch a little, right?
The Reindeer start on the Start Tile (marked S) facing East and need to reach the End Tile (marked E). They can move forward one tile at a time (increasing their score by 1 point), but never into a wall (#). They can also rotate clockwise or counterclockwise 90 degrees at a time (increasing their score by 1000 points).
To figure out the best place to sit, you start by grabbing a map (your puzzle input) from a nearby kiosk. For example:
############### #.......#....E# #.#.###.#.###.# #.....#.#…#.# #.###.#####.#.# #.#.#.......#.# #.#.#####.###.# #...........#.# ###.#.#####.#.# #…#.....#.#.# #.#.#.###.#.#.# #.....#…#.#.# #.###.#.#.#.#.# #S..#.....#…# ###############
There are many paths through this maze, but taking any of the best paths would incur a score of only 7036. This can be achieved by taking a total of 36 steps forward and turning 90 degrees a total of 7 times:
############### #.......#....E# #.#.###.#.###^# #.....#.#…#^# #.###.#####.#^# #.#.#.......#^# #.#.#####.###^# #..>>>>>>>>v#^# ###^#.#####v#^# #>>^#.....#v#^# #^#.#.###.#v#^# #^....#…#v#^# #^###.#.#.#v#^# #S..#.....#>>^# ###############
Here’s a second example:
################# #…#…#…#..E# #.#.#.#.#.#.#.#.# #.#.#.#…#…#.# #.#.#.#.###.#.#.# #…#.#.#.....#.# #.#.#.#.#.#####.# #.#…#.#.#.....# #.#.#####.#.###.# #.#.#.......#…# #.#.###.#####.### #.#.#…#.....#.# #.#.#.#####.###.# #.#.#.........#.# #.#.#.#########.# #S#.............# #################
In this maze, the best paths cost 11048 points; following one such path would look like this:
################# #…#…#…#..E# #.#.#.#.#.#.#.#^# #.#.#.#…#…#^# #.#.#.#.###.#.#^# #>>v#.#.#.....#^# #^#v#.#.#.#####^# #^#v..#.#.#>>>>^# #^#v#####.#^###.# #^#v#..>>>>^#…# #^#v###^#####.### #^#v#>>^#.....#.# #^#v#^#####.###.# #^#v#^........#.# #^#v#^#########.# #S#>>^..........# #################
Note that the path shown above includes one 90 degree turn as the very first move, rotating the Reindeer from facing East to facing North.
Analyze your map carefully. What is the lowest score a Reindeer could possibly get?
The Historians push the button on their strange device, but this time, you all just feel like you’re falling.
“Situation critical”, the device announces in a familiar voice. “Bootstrapping process failed. Initializing debugger....”
The small handheld device suddenly unfolds into an entire computer! The Historians look around nervously before one of them tosses it to you.
This seems to be a 3-bit computer: its program is a list of 3-bit numbers (0 through 7), like 0,1,2,3. The computer also has three registers named A, B, and C, but these registers aren’t limited to 3 bits and can instead hold any integer.
The computer knows eight instructions, each identified by a 3-bit number (called the instruction’s opcode). Each instruction also reads the 3-bit number after it as an input; this is called its operand.
A number called the instruction pointer identifies the position in the program from which the next opcode will be read; it starts at 0, pointing at the first 3-bit number in the program. Except for jump instructions, the instruction pointer increases by 2 after each instruction is processed (to move past the instruction’s opcode and its operand). If the computer tries to read an opcode past the end of the program, it instead halts.
So, the program 0,1,2,3 would run the instruction whose opcode is 0 and pass it the operand 1, then run the instruction having opcode 2 and pass it the operand 3, then halt.
There are two types of operands; each instruction specifies the type of its operand. The value of a literal operand is the operand itself. For example, the value of the literal operand 7 is the number 7. The value of a combo operand can be found as follows:
Combo operands 0 through 3 represent literal values 0 through 3. Combo operand 4 represents the value of register A. Combo operand 5 represents the value of register B. Combo operand 6 represents the value of register C. Combo operand 7 is reserved and will not appear in valid programs.
The eight instructions are as follows:
The adv instruction (opcode 0) performs division. The numerator is the value in the A register. The denominator is found by raising 2 to the power of the instruction’s combo operand. (So, an operand of 2 would divide A by 4 (2^2); an operand of 5 would divide A by 2^B.) The result of the division operation is truncated to an integer and then written to the A register.
The bxl instruction (opcode 1) calculates the bitwise XOR of register B and the instruction’s literal operand, then stores the result in register B.
The bst instruction (opcode 2) calculates the value of its combo operand modulo 8 (thereby keeping only its lowest 3 bits), then writes that value to the B register.
The jnz instruction (opcode 3) does nothing if the A register is 0. However, if the A register is not zero, it jumps by setting the instruction pointer to the value of its literal operand; if this instruction jumps, the instruction pointer is not increased by 2 after this instruction.
The bxc instruction (opcode 4) calculates the bitwise XOR of register B and register C, then stores the result in register B. (For legacy reasons, this instruction reads an operand but ignores it.)
The out instruction (opcode 5) calculates the value of its combo operand modulo 8, then outputs that value. (If a program outputs multiple values, they are separated by commas.)
The bdv instruction (opcode 6) works exactly like the adv instruction except that the result is stored in the B register. (The numerator is still read from the A register.)
The cdv instruction (opcode 7) works exactly like the adv instruction except that the result is stored in the C register. (The numerator is still read from the A register.)
Here are some examples of instruction operation:
If register C contains 9, the program 2,6 would set register B to 1. If register A contains 10, the program 5,0,5,1,5,4 would output 0,1,2. If register A contains 2024, the program 0,1,5,4,3,0 would output 4,2,5,6,7,7,7,7,3,1,0 and leave 0 in register A. If register B contains 29, the program 1,7 would set register B to 26. If register B contains 2024 and register C contains 43690, the program 4,0 would set register B to 44354.
The Historians’ strange device has finished initializing its debugger and is displaying some information about the program it is trying to run (your puzzle input). For example:
Register A: 729 Register B: 0 Register C: 0
Program: 0,1,5,4,3,0
Your first task is to determine what the program is trying to output. To do this, initialize the registers to the given values, then run the given program, collecting any output produced by out instructions. (Always join the values produced by out instructions with commas.) After the above program halts, its final output will be 4,6,3,5,6,3,5,2,1,0.
Using the information provided by the debugger, initialize the registers to the given values, then run the program. Once it halts, what do you get if you use commas to join the values it output into a single string?