Keep on reading, but I just want to say that I have used the following sites as a therapy after finishing my daily puzzles:
- Saaste's AoC blog (in Finnish)
- Reddit AoC solution megathreads
Assignment: Historian Hysteria
Started in the evening. Started using Haskell because I had been using Haskell in a company project in last few weeks and had the libraries in fresh memory.
I noticed it would've been possible to do it with LibreOffice spreadsheet, but decided to write a decent parser since I started late and being quick wasn't important and it was Sunday so had free time.
Joined to the private leaderboard of my former student club.
Very easy, did both stars it in less than 30 min from scratch while wandering in Hackage library docs.
View my code: Day01.hs
Assignment: Red-Nosed Reports
A little bit dull CS1 grade assignment. First part could've be done in a spreadsheet but the second probably not since it required branching.
Well, maybe it could've been done without loops with clever conditions and state passing but I didn't want it to become too complex and unreadable mess. In Haskell I have a garbage collector and I'm not afraid to use it.
I was so bored after this that I made proper command line parser and small framework to help solving the assignments in upcoming days.
I'm so tired about the culture war around master/main terminology so I decided to rename my AoC repository default branch as pukki after joulupukki, the Finnish word for Santa Claus.
View my code: Day02.hs
Assignment: Mull It Over
I really didn't do the full parser initially. I hacked a very quick and dirty parser first and I wrote a proper parser in Part 2. I reused the more complete parser from Part 2 and processed the output with input that has been pre-filtered to remove Don't statements.
I liked the assignment because it was no longer a spreadsheet task. Finally got the possibility to benefit from a proper backtracking parser library.
Maybe 30 min solution again. I was quicker than expected because I already had the bells and whistles at hand.
View my code: Day03.hs
Assignment: Ceres Search
Not my day, not the right tools.
Started over 4 times after getting super desperate about how to process this in a functional language.
Noticed that Text index function is O(n) rather than O(1) so decided to fix the "framework" to use ByteStrings instead of Text. This should've been the first thought and not an afterthought since AoC never uses weird UTF-8 input. Let's see if tomorrow there will be 🎅 in the input and I'll start spinning again.
There was nothing to parse so the solution was to just extract bounds from the input and write the index to coordinate conversion functions so that they manage with the newlines.
The correct language in this case would have been plain old C. Very straightforward character comparison and stuff. I just didn't want to give up. I was that close to make it in C with FFI interface.
After getting my shit together after hours of running around aimlessly I had one incorrect answer because I forgot top right to bottom left and bottom left to top right diagonals. After adding them, I got a correct answer.
The second part required new approach but I was able to reuse the coordinate conversions. This time I got everything correct on first try but getting there lead me to matrix algebra and stuff like that which I decided not to use.
I would've sacked the guy who was hopelessly pressing buttons in front of a computer. Definitely not a professional. That guy was me.
PS. Obfuscated variable and type names for your extra amusement.
View my code: Day04.hs
Assignment: Print Queue
Okay, this time it was a Haskell day. Even though I could've been fast, it was morning and didn't manage to speedcode. It took something like 1h 13min to complete the Part 1 and about two minutes to complete the second, both without retrys.
Initially, I read the instructions incorrectly and thought what would
come in Part 2 would've been the first part. No bad feelings though,
since I managed to do Part 2 extraordinarily quick, just changing ==
to /=.
I was happy that I had my CS degree, immediately noticed that this is a case for a user-supplied comparator. So I did it and we can enjoy a nice and smooth O(n log n) complexity in computation. Well, in AoC, the assignments are simple enough to brute-force anyway. But it gives a warm fuzzy feeling, like a glass of warm mulled wine. 🍵
Afterwards, while cleaning up code, I noticed I had a bug in the
comparator, where I did compare a < b correctly but not a > b because
of quick copy-pasting around. Well, it didn't hit, but a fixed version is
now in the repo.
PS. In case you've wondered why there are JSON instances in my code
even though I'm not processing JSON. It's for the command line switch
-j which dumps the parsed output to JSON which is quick to process
with jq if I needed to. In most cases I write them afterwards, not
while the timer runs.
View my code: Day05.hs
Assignment: Guard Gallivant
Alright, it's a day off. It's the Finnish independence day. Last evening I had couple of beers with bunch of nerds, one of them was also doing AoC and does it way more competitively. Has a wake up every morning at 07:00 (05:00 UTC) so he starts immediately when the assignment goes live. I often start at some point in the morning, the earliest so far was at 09:30.
This morning I wanted to make it easy and not competitive at all. I wanted to make a proper parser since the last table based assignment was yesterday (Day 4) and I started over multiple times. This time I wanted to parse the input properly so instead of a table I had a set of obstacles and bounds of the arena. It took too long and my day schedule went out of the window.
After hours of hacking I finally managed to book train and plane tickets to 38C3 and even go to a sauna. It was very relaxing, better than ragecoding AoC assignments.
The code is rather beautiful in my opinion, but naming of parsers could be better. The efficiency could be better, since I just iterate over all possible obstacle positions in part 2. I just didn't have a good idea about any drastically more efficient algorithm.
Part 2 run time on my laptop was 19 seconds (non-threaded) and under 6 seconds when parallelized.
View my code: Day06.hs
Assignment: Bridge Repair
Very haskellish task. Super straightforward, in theory.
At first I was accidentally first doing right-to-left evaluation and
then fixing the algorithm to left-to-right but so that every other
element it was doing right-to-left. The mistake was I was using two
functions, evalLTR and evalRTL and I was calling the other
recursively. 🤣 I tilted.
Due to tilting the easy assignment went to a try-and-fail loop, and I
got 5 minute ban from AoC. The ban lead to me reading my code with a
thought and found evalLTR in evalRTL function and the part 1
solved immediately.
Part 2 was just adding a new number concatenation operator which I did using just Show and Read, not fancy and optimized base 10 shifting.
Run time 3.5 seconds on my laptop without threading.
View my code: Day07.hs
Assignment: Resonant Collinearity
Waking up late, doing it easy and slow. I was finished about 18:45 local time.
I noticed AoC author wastl likes grids. It was just the day before yesterday when another grid task was on AoC. So I generalized the grid parser from Day 6 which took me maybe even an hour.
Once again, I didn't read the part 2 assignment text properly and got
a bit desperate and had an hour break after part 1. Then I just
noticed that I can merge antenna locations with the "antinodes" list
to get the correct output because antinodesRepeat does not add
antenna positions to the set.
Once again I was refactoring the code after finishing part 2 and before committing. So the actual code you see in this repo with all type definitions and comments is not done before submitting the answer. Today I was a bit disorganized so I added most of the comments while I was coding.
Yesterday evening I made new_day script which downloads the puzzle text and converts it to PDF and gets puzzle input. Today after finishing part 2 I added a feature which populates the links in this logbook as well. Now I just need a faster me coding so fast that I'll receive both stars in a minute.
View my code: Day08.hs
Assignment: Disk Fragmenter
It wasn't a grid puzzle day, maybe once again tomorrow. I made a more complex parser than needed which parsed files instead of just parsing the digits. It would've been faster in both computationally and in coding time to parse the digits first and then fold the list. But I picked my poison and the taste was bitter.
Anyway, having a File type was useful in part 2 when the files were
ordered in contiguous fashion.
Once again, for the 3rd time or so, I didn't read the assignment well. Wastl has a C coder mindset and probably had decided not to allow overlapping moves in the assignment to make the puzzle simpler. That was a bit ambiguous, it was in examples but not in the text. Anyway, in my solution overlapped moves were easier to do and I assumed it and lost over an hour in debugging this very trivial case.
I'm using too much time on these puzzles. I have two options: To be more efficient or stop doing this. I'll decide after tomorrow if I have to stop to not to ruin my life.
Anyway, there's a cool projection sort trick in function
idAndPositionSort. You should check it out!
View my code: Day09.hs
Assignment: Hoof It
Grid puzzle! How predictive.
Was straightforward to do. Parsing the grid and the trailheads to
separate items, Map and a list. Could be done with plain iterating the
data list until 0 is found like C programmers would do. But I have
my values and they're not null.
Once again the procedural bias of AoC author was visible. Part 2 was shorter simpler in Haskell than Part 1 because I needed to filter duplicate results (which was super simple, too). But in case anyone thinks coding AoC functionally is harder, it may have something to do with the puzzles. Real world problems are often more functional programming friendly than human-invented coding challenges.
My code is not super interesting this time but maybe it's readable. I didn't even put Finnish in the variable for the lulz names this time.
PS. Yesterday evening after finishing the previous puzzle I added parallel evaluation for the command-line tool which runs the puzzles. Just to practice with deepseq. Parallel computing is rather horrible with Haskell. It just has so many must-know things before it works as expected.
View my code: Day10.hs
Assignment: Plutonian Pebbles
Part 1 was super simple with brute force. Just a list comprehension and one ugly integer to string and back to integer trick.
Quickly noticed that part 2 is intentionally taking forever with brute force, so needed to get back to drawing desk. Some similarities with Day 6 part 2 where a loop had to be detected and one has to move away and not to stick to initial data structures.
At first I planned to make a "generation cache" where a number of iterations produce a cache for each input value. That way you could've brute-forced the sum of, let's say 10 generations for the most common values such as 0 and 1, and pre-fill those values. I dropped the plan after 15 min pen and paper testing lead me to the outcome that another take, grouping, is possibly faster and most importantly, simpler.
The key to the solution was to discover that the order of the "stones" in the run is not relevant, so grouping same numbers and counting them only once is way more effective. In my solution it's a map with number as a key and count as a value, and the value is initially 1 for each input element. Iterate it 75 times and there's your part 2.
Run time < 50 ms, non-threaded. I have polished my code after puzzle completion and it's very nice and readable. No more string conversions! Go and check it!
Tomorrow it's an even day so maybe there will be grids again. I know you well, Mr. Wastl.
View my code: Day11.hs
Assignment: Garden Groups
Yeah it indeed was a grid day. And a pretty demanding one. Used basically all of my non-working hours with this task and also coded during monthly work meeting.
My algorithms were way too complex. Tried to walk the outer line and developed a fancy algorithm for it, just to be thrown to a garbage pile after reading the assignment examples more carefully to notice there are enclaves in the data (letters B inside A area in the end of part 2 example section.
Finally just a horizontal and vertical walk "between the lines" worked, checking if the pair on left & right and up & down were the same.
I feel stupid and unhappy. Don't have time to write this log since I used all of my time and even more.
The only part made me slightly happy was the somewhat epic set algebra
function isles and its helper function getTouching.
View my code: Day12.hs
Assignment: Claw Contraption
Very pleasant task, some parser writing and euclidean math.
First part I did with brute-forcing since I didn't know if what would come next. Then some pen and paper excercises to get the line intersection math correctly. It took me hours, anyway. I get out of competition mode immediately after seeing the 10000000000000 addition and didn't even try to improve the brute-forcer I had.
The code explains the details better than text, but the idea is to find a line-line intersection of two lines. "Home points" are defined so that the line for A intersects the origin (0,0) and line for B intersects the prize point. Line slopes are defined simply so that y delta is divided by x delta. If the horizontal (x-axis) distance between the "home point" and the intersection point is divisible by the x delta of the corresponding button and it applies to both A and B, then the count of button presses is that integer value. Otherwise there is no winning combination.
Haskell was a good tool choice with built-in Rational type which allows doing non-lossy divisions and there was no need to do integer-only math. It might've improved computational efficiency, but this time there wasn't any need to optimize further. Calculating the solution takes 3 milliseconds on my laptop, non-threaded.
I also replaced the original bruteforcer from part 2 with the analytical solution but if you're interested, the old one is found in the commit history.
View my code: Day13.hs
Assignment: Restroom Redoubt
Puzzle soundtrack: paniq - Heavy Working Robot
Part 1 was rather straightforward. I didn't like there wasn't dimensions in the input file so those needed to be hard-coded in the code to run the code against the example and when switching to real input.
Part 2. What the !%&%? I found the repeating period which gave me the upper bound of the value. Then I entered half of it to the answer validator to binary search the answer. It said "too small". Then I redid with the upper part and got the frames limited to one quarter than original. It was 4 minutes of rendered video at 10 fps. Faster than coding the logic.
In the top row of the video is the generation ("second") number LSB binary encoded.
My code produced raw grayscale pixels which can be rendered to a video using ffmpeg:
ffmpeg -f rawvideo -pixel_format gray8 -video_size 101x104 -framerate 10 -i /tmp/day14part2 -vf scale=iw*8:ih*8:flags=neighbor hullu.mp4
Life is.
Update from December 15th: My friend told his strategy was to look for a frame where no robots were overlapping. There's only such frame in the cycle. This is probably because Wastl has designed the puzzle so that he first places the christmas tree and then randomizes some dots outside of the tree thingy. And then randomizes velocity vector for each robot and runs the simulation some random amount of frames. Or probably pseudorandom, so it's possible to recreate the puzzle.
So, my code solution is looking for such frame and there's no need to watch videos anymore. Part 2 run time was a little less than 1 second.
View my code: Day14.hs
Assignment: Warehouse Woes
Not too difficult but I was just not productive. The resulting code is rather clean and I'm happy with it, just not happy about my development time.
If I had completed the puzzle quicker I would've had time to play Sokoban or actually a nice clone called KAtomic. But now I'm quite fed up with warehouses and skip the fun.
View my code: Day15.hs
Assignment: Reindeer Maze
First for some stupid reason I implemented my own shortest path algorithm but quickly found it's algorithmically way too complex. Was able to solve simple cases but not the real input. Too much time spent here.
Then I spend much time reformatting my code to produce a graph instead which was fed to Martin Erwig's Functional Graph Library which was able to find the route in 0.25 seconds. And my graph generation algorithm is far from efficient since it generates graph IDs by sorting the graph material to a Set and then numbering them.
I learned how to use the graph library and my first shortest path algorithm task after my Master's degree and it was 14 years ago. Also, I can now say I master practical, real world use of list monad.
Update from December 20th: Part 2 finished by using a clever bidirectional Dijkstra trick. First, shortest paths are calculated to all nodes normally, then edge directions are reversed and shortest routes are calculated from end to start instead. Then, intersection of those two tables are made with sum function, basically getting the shortest path length which goes via that node.
Then, get the ones with smallest numbers, extract their coordinates, deduplicate, and count. The only gotcha is that End is extra node added earlier in my code which needs to be filtered out before counting.
This took me some time but managed to not to spoil myself on Reddit.
View my code: Day16.hs
Assignment: Chronospatial Computer
First, I implemented the Elf computer as a function step which
basically runs one instruction at a time. This was necessary to
complete part 1.
In part 2 I was, once again trying to bruteforce first. Then, while my
CPU fan was singing Christmas carols I found out there's 3 bit shift
in the code before jump. To find the
quine, the initial
register A value has to be
I manually transpiled the code in my puzzle input from the Elf machine to Haskell, changed variable names a little bit and got:
transpiled :: Int -> [Int]
transpiled a = let b = a .&. 7 `xor` 2
out = (b `xor` (a .>>. b) `xor` 3) .&. 7
c = a .>>. 3
in out : if c == 0
then []
else transpiled cThe clue here was that the recursion runs until c == 0 and c is
right shifted from function input a. That means that if we want to
go back in time, we know that x <- [0..7], a <- 8*c+x, in other
words there are 8 possible inputs, but not all of them are valid. At
least one should be, or the puzzle is insolvable.
So, I defined function back which takes a test function (the "CPU"),
possible c values and outputs valid a values. This is iterated until
quine is constructed.
Run time 4 milliseconds. Development time... don't ask? Maybe 10 hours. AoC burnout intensifies...
View my code: Day17.hs
Assignment: RAM Run
Very straightforward shortest path task, much simpler than day 16. However, managed still to spend 35 minutes to part 1 and 19 minutes to part 2.
While solving the puzzle, I had to wait for a solution for couple of minutes due to bruteforce nature of my list iteration from the item 1024 onwards. So, afterwards, I added a binary search. For some reason I didn't find uncomplex binary search such as bsearch(3) in libc. I made one. Now it runs part 2 in 0.22 seconds on my PC and part 1 takes only 53 milliseconds.
I didn't even add all checks to edge generation so some of my edges are heading to dead ends, so there are some hidden efficiency around the corner, too.
View my code: Day18.hs
Assignment: Linen Layout
First, I got easy first star by just editing the input to a
regex by replacing
, in the first line with | and adding the match rule around
it. With the example in the puzzle and puzzle input in inputfile,
that would lead to:
grep '^(r|wr|b|g|bwu|rb|gb|br)+$' inputfile | wc
And there's your answer.
The second part required to go back to basics about what the computing is, what algorithmic complexity is, and most importantly, what the significance of a single human being is on the time line of our galaxy and the entire universe.
So many hours before I got the clue but the answer was 78 lines of code including comments and the runtime is less than a second.
I ended up to write generator for a graph and then count possible routes from the end point of the graph back to the start element and summing all the routes together, avoiding the branching which would've otherwise occurred and made it impossible to obtain the answer in a lifetime of an average human life.
View my code: Day19.hs
Assignment: Race Condition
First obvious note from the assignment is that the reindeer maze from day 16 would be a good boilerplate code. Another note is that all references to time can be thought as a distance like in RAM Run assignment from day 18 "RAM Run" assignment.
Part 1 started with the regular art of bruteforcing. Take one wall block away, then find shortest route, try another one. This is fortunately dividable to multiple independent workers. Bruteforce wallhack with threading on 12 cores took 6 min 44 sec. There's the first star, took about an hour since I was only partially awake in the morning.
I looked to part 2 assignment and it was clearly no longer brute force. I didn't have a clue where part 2 would go, so bruteforcing answer to get the second part visible was clearly a winning move. Making the code more generic in the way I didn't have a clue would've taken way longer.
Had a lunch and other life related obstacles and then on the lunch break I had a clue to the impossible-sounding assignment. The wallhack could be done so that we do the same than in day 16 and calculate shortest distances to every node from both the start and the end. In this case even reversing edges weren't needed since the graph was bidirectional (if you walk somewhere you can walk back without any turn penalty unlike in day 16. The actual algorithm is probably self-explaining in the code, but here's a non-edgecasing version:
For every reachable node (x,y position there's a walkway) we know the
shortest path both from the start and the end. We iterate through
every node (a) and there we look every node in the given distance of
20 cells (b). The total "cheated distance" is
Then I replaced the hacky bruteforcer I did in part 1 with the efficient algorithm from part 2. The final run times were 0.13 seconds for part 1 and 1.1 seconds for part 2. The difference comes not from running Dijkstra algorithm (it is run twice in both parts), but the number of neighbour lookups (836 in part 2 and only 8 in part 1). So doubling the cheat duration quadruples the number of lookups.
After finishing the part 2 with an efficient algorithm I noted that the bruteforcer could've been used for part 2 as well. Instead of taking a single wall away I could've exploded everything for a given distance from each cell and run Dijkstra algorithm from start to end for every cell there is. That would've taken around 10 minutes on my PC, so it would've been a winning choice over efficient code, if only measuring the development time plus time to run the code once, which is the AoC goal after all.
View my code: Day20.hs
Assignment: Keypad Conundrum
I had a busy day and I needed to skip the puzzle.
View my code: Day21.hs
Assignment: Monkey Market
Day started with a 7-hour train trip, so I had plenty of time to hack around starting from 07:00 local time. After finishing part 1 the train started to become rather crowded, with children and grown-ups running around aimlessly. Soon after, the window next to me was smashed partially. So, there was plenty of action while I was at the Monkey Market. Monkeys were both inside and outside of my computer.
Happily I was compensated by 8 euro voucher because I had to change my seat due to the broken window. But also, I was distracted one more time because I decided to eat something on the train restaurant.
Part 1 was indeed very fast to finish. It was basically getting the pseudorandom algorithm right and part 2 was actually doing something with it. With the second part I was almost there after half an hour but then got totally on incorrect track, thinking the pseudorandom would fail for some reason and I spent almost an hour reading the assignment over and over again from so many different angles to find out if I had missed something important.
Finally, between Oulu and Kemi I found it. I had the following function:
candidates :: (Eq a, Num a) => [a] -> [([a], a)]
candidates (a:rest@(b:c:d:e:_)) =
if b == e
then ([a-b, b-c, c-d, d-e], e) : candidates rest
else candidates rest
candidates _ = []I usually try to avoid these kind of variable messes. The problem was
that I had a instead of e in the second of the tuple, more
specifically this: ([a-b, b-c, c-d, d-e], a) which
lead tho the outcome that it didn't return the correct price value but
the one before. Why I had a in the function at the first place was
to count the difference between successive elements and it shouldn't
have been used for anything else.
So simple and took me so many hours. I almost lost faith.
In general this puzzle favoured high level languages such as Haskell,
allowing to do the counting of sequences of four by using simple set
algebra. First, valid pairs of (sequence, price) are produced, the map
is generated with flip const, meaning the monkey's earlier sequence
has precedence over later (since the the puzzle says the monkey stops
at the first match) and then all maps are folded together using union
with (+) as the combining function (just sum the
occurences). Because the winning sequence wasn't required but the
amount of bananas, we just look for the highest value from the map,
and there's your answer.
Set algebra was indeed a very efficient approach. Run times: First part took 0.081 seconds and second part took 0.274 seconds.
So long and thanks for all the bananas!
View my code: Day22.hs