Advent of Code is an advent calendar offering a two-parts puzzle every day.
It is for people interested in programming or problem solving.
I came across the first puzzle on december 1st and decided to keep up until completion, on december 26th.
This was the first time I participated in AoC and I guess not last.
Here are some notes I took during the event, aggremented with more recent comments.
See that page as a scratchpad of peregrinations or an exotic writing experiment.
One day, one language
It's been some times since I'd wanted to diversify my coding expressivity.
As a beginner, I've found myself a bit stuck on my first programming languages' syntax, and habits made it hard to switch.
That's no discovery, the more you use it the more syntax crystallizes, either you're conscious of it or not.
So, as opening problems were doable in a reasonable amount of time, I settled with the "one day, one language" rule to torture myself for learning purposes.
To learn new languages is not something trivial, but the semantics we inject our code into (what we mean to do) usually does not vary much.
In this regard, we can leverage semantics to learn new languages.
Chosing types, storing variables, looping through lists, arrays or sets, creating functions, branching by condition, printing things on the screen, and so on.
I spent a fair amount of time looking for how to do those things with every new languages I've tried, and that worked.
An interesting thing is syntax can also make you learn new things in terms of semantics ("I did not know I could want to do that").
There would be a lot more to say on the subject but let's just say it is a bidirectional process and not digress too much.
Ok, I've said leveraging semantics to overcome the syntax obstacle worked, but from day 13, with difficulty increase, I returned to good old Python, and only "translated" my solutions in another language afterward.
Dissecting portions of code and translating them was sometimes harder than solving the puzzle!
For sure not the same task.
There's no secret, to learn a language you need to use it and start thinking into it.
The same goes for programming.
Find a problem you really want to solve (not too hard if you still have hair).
Decompose it into smaller parts and solve step by step.
Don't be afraid not knowing and search for resources when stuck.
I know: platitudes, but that's how it is.
Simplicity without too much constraint
I prefer implementing things myself and tend to not use external libraries (to the exception of a couple of days).
I guess that's all there is to say about my "preparation" to this event.
Audience for that post is unexpected. I think at best it could motivate someone to tackle some of those problems.
So, to the lost visitor: from here, things gets quite poorly organized, but don't forget it is a writing experiment (a way to keep track of previous achievements, and to gain expressivity in a natural language as well).
Everyday I wrote a highly condensed summary of the problem and took some notes about what was needed to solve it (tools and thoughts), some pros/cons about the language in use, useful resources, etc.
Titles contain a hint about the language used that specific day.
Floppy drives in titles 💾 lead to my solution scripts on GitHub.
💾 day_01.{sh,py}
Given a thousand lines input, form a two-digits number from the first and last digit of each line. For part two, digits can either be numerical or spelled in letters. Sum them up.This problem got me hooked in. I've used a slow one-liner in Bash for the first part, and Python for the second to warm me up!
result=0;while read line; do num=$(echo $line | tr "[a-zA-Z]" " " | sed "s/\ //g"); num1=$(echo $num | grep -Eo "^."); num2=$(echo $num | grep -Eo ".$"); num3=$(echo $num1$num2); result=$(( result + num3)) ; done < assets/01.txt; echo $result
Tip: if there is only one digit on a line, can we construct a 2-tuple composed of the first digit and the last digit of that line?
💾 day_02.pl
Suppose you're in complete darkness searching for a pair of socks. You know the room by heart and easily reach your drawer. You know your socks can only be of 3 different colors. What's the minimal number of socks you need to extract from the drawer to be sure obtaining a matched pair?If you know how to answer that, you'll surely solve this problem easily!
I like scripting languages, and Perl is a really good one. Some call it Bash on steroids. What I liked the most about Perl is its embedded regular expression engine. Felt like using this operator all day
=~.
There are a lot of interesting things with Perl, like implicit actions. Check this :
$filepath = 'input.txt';
open(FH,'<',$filepath);
while (<FH>) { # iterates through lines of "input.txt"
next unless s/^(.*)\s*:\s*//; # if match occurs: replace and store (.*) in $1
print $1;
}
💾 day_03.rs
Count numbers adjacent to symbols, then count symbols adjacent to exactly two numbers in 2D space.Nothing much to say here: iterating over columns and rows, looking around each character, storing pertinent information.
Even if I already tweaked around with Rust, it still feels a bit overwhelming to me. Haven't approached it from the right angle yet.
💾 day_04.php
Count scores on scratchcards, then count how many magic cards you'll have given their property is to multiply byx the remaining scratchcards in the deck (x being that card's score).
Tip: don't forget to count the initial deck of cards.
💾 day_05.dart
Keep track of a conditionally splitting range of values. Values needs to be converted successively (seven times), according to conversion dictionnaries.
First puzzle to bother me (partly because bruteforce couldn't lead anywhere!).
Never had to follow ranges in different function calls. It was a really good training for day 19.
💾 day_06.R
You're competing in a race. How long should you press a button that the more you hold the faster your car BUT also the more you lose time in the race? Find the optimal strategy to break a list of records.R for the win! With a single function to break all time records:
compute_ways <- function(duration, record) {
ways = 0
for (x in 1:(duration-1)) {
distance <- (duration - x) * x
if (distance > record) {
ways = ways + 1
}
}
return (ways)
}
Didn't even have to implement another way to solve part two. R is really good for vector computations.
💾 day_07.js
Determine winners of exotic poker hands pairs.
As I've already came across Project Euler 54th problem (where "real" rules of poker needs to be implemented to compare hands), there was not too much thinking here, even for the weird poker game of the day: a double
for loop to compare every pair of hands.
💾 day_08.go
Keep track of cycling circuits and deduce when an "alignment" condition is met.
Six ghosts are following different paths in parallel, the question is when are they all gonna be on a path finishing by the letter 'A' at the same time.
That was the second hardest problem I came across on this adventure. Looking back I realize that it is not that hard when you think about it as a least common multiple problem. What's "funny" is that I thought of this as a planetary alignment problem when... it is exactly the case.
Talking about that, did you know that a straight-line alignment between celestial bodies has its own word in astronomy? It is called a syzygy.
💾 day_09.rb
Given data about the environment and some rules, predict the future and retrodict the past.Nothing much to say about that puzzle: append a value to the bottom of a tree and sum two values at each step on your way up.
list.each { |item| statement } # iterate on a list
string.split(" ").map{|splitted_item| Integer(splitted_item)} # map operation
Ruby felt fast and intuitive, loved the experience.
💾 day_10.jl
What's the length of a looping circuit in a grid, and how many tiles does it enclose?This is again a problem in 2D-space, where the looping circuit is drawn with symbols representing edges and corners:
|, -, 4, J, 7 and L.
Tip: Line by line and then character by character, meeting
| toggles the "inside/outside" bit.
Some corners toggle a substate that can only be exited by another one (e.g. after meeting 4, you can only exit the state you are in when meeting J).
Julia seems like a good compiled Python alternative with an easy syntax.
💾 day_11.java
The universe expands, increasing space between galaxies. Given a screenshot of the universe at timet, and an expansion of of a million "cosmic rows/columns" at specific locations at time t+1, what is the sum of the lengths of the shortest paths between every two pairs of galaxies? (fiou!)
Tip: consider only the space between each pair of galaxies (restrict a frame on each pair, and don't consider the whole space around them).
On a side note: Java was not that much of a fiesta (french pun intended).
💾 day_12.exs
In how many ways can we place sequential objects of various sizes in a large box (with some position constraints)?To solve this one, I sipped some of the functionnal programming elixir with... Elixir. Loved starting to understand functionnal programming with it! Hated looking back at my code 3 days later... as I did not (and still haven't) wrapped my head around FP that much.
Note that this was the third hardest problem of the event... until I read about memoization. From what I understand, if a function
f with argument x is called for the first time, we compute f(x) (let's say the result is y) then cache it in a hashmap with a representation of f(x) as the key, and the result y as the value.
If f(x) is ever called again (note that is with the same argument x), we do not execute it but look up for the cached result.
It may sound simple, but one should try to implement it before guessing. I had a hard time, first in Python then in Elixir (as a matter of fact: I failed for the latter!).
I could not believe my eyes that (in Python) my computer could solve the astronomically impressively huge numbers of the puzzle (can you spell that number 118997000525790?) in such a small amount of time. The result must have been false!?
Nope. Memoization is hungry for memory but a relief for the CPU.
I failed to implement memoization correctly in Elixir.
The script takes almost 3 hours (...coffee? ) to give the correct answer while it takes only 3 seconds in Python.
Orders of magnitude 😬.
I might take a look back at it when feeling like it.
Elixir: like a scripting functional programming language, accessible syntax, good documentation
💾 day_13.kt
Find vertical or horizontal lines of reflection on mirrors, then find the exact point on each mirror that would create a new line of reflection if it was not here (i.e. the smudge).
Then sum (in a weird way) the number of rows(columns) above(on the left of) the horizontal(vertical) line of reflection.
Tip: two lines can mirror each other only if the gap between them is even.
Trap: some rows/columns must be counted even if they have no corresponding reflection line (e.g. if the line of reflection is almost at the bottom).
💾 day_14.cpp
Rotating a maze full of rolling round rocks. What would be the structure of that maze after a billion rotations?I searched for and identified a cycle in the maze after X rotations. From the first state of the loop, I rotated
(1000000000 - number of steps before looping) modulo (number of steps in the loop) times to find the solution.
💾 day_15.lisp
Sequentially hash strings, then place lenses in boxes in the correct order to solve.Pleasant cryptographic vibes in that one. Loved tinkering with Lisp.
💾 day_16.cs
A light beam on a map with mirrors reflecting or duplicating it. How many squares are going to be traversed by that light beam?Nothing too fancy here, a 2D-array and a Beam class in C#.
Trap: don't count enlighted squares twice!
💾 day_17.ml
Find the shortest path on a grid with move constraints (no loops obviously, and no more thanx steps in the same direction).
Another hard one. Would rank it third in the hardest puzzles of the event. This wasn't easy, especially when I knew nothing about Dijsktra's algorithm. Computerphile made a great video on how it works. Something interesting is that you need a priority queue. This is "just" a list where the highest priority element will easily be dropped at each iteration.
Rosetta Code helped transposing priority queue in OCaml.
💾 day_18.clj
Determine the superficy of a lake given only the digging instructions (number of steps and orientation).Using Clojure was some kind of a relief for a jvm compiled language. I still don't know why it is so close to Lisp in terms of syntax, but that made me like Java more. However, I still could not avoid using imperative style in both parts. For part one I drew the map and used day 10 as a reference to draw corners to count enclosed tiles.
Here is the formula:
Area = Interior + (Perimeter / 2) - 1
I have the perimeter of the polygon when iterating through instructions. As each instruction gives an edge, the area is computed with the Shoelace formula,
abs([Σ(Xa * Yb) - (Xb * Ya)]/2) (given each pair of consecutive edges, compute a subpart of the total area).
All we need now is to find how many points are on the interior by reversing a bit the Pick's theorem formula.
Interior = Area - (Perimeter / 2) + 1
Anyway, Clojure is interesting, but as I am yet not spoiled with a specific FP language, I'd rather go with Lisp or OCaml.
💾 day_19.lua
Given functions returning a boolean, what is the sum of the numbers for which they will return "true"? Then, how many will return "true" for specific ranges of numbers? (splitted ranges again -- see day_05).Simple sequential algorithm for part 1. For part 2, I used the same method as day 05 splitting on intervals. Worked like a charm: .01 second.
In Lua, variables are global by default. You need to specify "local" in functions when you don't want it to be spread around. This is specifically useful to know when writing recursive functions where the same variable could compete with itself in differents subcalls. I really enjoyed Lua, gave me the same feel as Ruby.
💾 day_20.groovy
Given switches (called flipflops), relays (called conjunctions) and untyped modules traversed by low or high pulses after a push on a button, what is the number of pushes needed to activate a specific switch? (again a "planet alignement" puzzle).In Groovy, impossible to access a top-level function from within a class method. I wanted to store every object of the class into a top-level list whenever this object was created. In Python I just had to
objects.append(self) inside the class constructor itself.
The workaround in Groovy was to append to this list from outside the class, whenever we called an object creation.
Not that big of a deal, but that shows how languages can differ.
💾 day_21.boo
Find the number of occupied squares on an infinitely expandable map after a huge amount of steps.Hardest problem of the event 😈. To understand what's going on here, one should unlock part one and read AoC instruction for part two. The second part of this puzzle gave me headaches! Mostly solved it with pen and paper (and a calculator) and a lot of testing on the input. Luckily, I noticed a pattern in the input. Can you spot it?
Thankfully,
[number_of_steps-(length_of_map/2)]/length_of_map gives an integer.
Moreover, the borders and center vertical/horizontal lines of the map are empty: there are thus no obstacles for the "advancing" symbol, so every neighbour map will either be ignited by a symbol coming from the center top/bottom/right/left (for top/bottom/right/left neighbours) or from a corner (for corner neighbours).
This way, after s steps, m maps will be filled completely (notice that once a map is filled, it keeps cycling between only two states).
We also need to count h half and q quarterly-filled maps.
Computing this was easy, finding the "formula" was a bit of a pain. Here is a part of my thinking template:
💾 day_22.ts
A huge pile of bricks falling one on each other. How many can be removed safely? How many will fall if you remove a specific brick? Find the sum of all "fallable" bricks given each "unremovable" ones.A 3D-array, a class of bricks and two
for loops did the trick.
This 3D tetris was fun.
Nothing special to say about TypeScript, some kind of a statically and strongly typed JS, right?
💾 day_23.scala
Find the longest path...
I thought it would be the same as finding the shortest path... How wrong was I? This problem is "known" to be NP-hard. That means we are not sure we can solve this problem in polynomial time. What does that mean? That if you want to know what is the longest path between two points, you need to take EVERY paths between those two points. I counted what I called "roundabouts" in the maze (places where your direction is not forced). Then counted the distance between every neighbours roundabouts. And finally computed the longest of about a million possible paths. I think the implementation of my algorithm is called BFS but I am not sure as I write those lines. More exploration to be done.
When I first wrote the solution in Python, I placed a class of object in the queue list. Problem was: how do you compare priorities of non-number objects of a class? Well, you can do that adding this in the class:
def __lt__(self,other): # strictly inferior definition
return self.x > other.x
def __le__(self,other): #less or equal definition
return self.x >= other.x
Anyway, I rewrote this in Scala (2.2). Unusual to me: there are no
continue nor break in loops.
In functions, return does not act like in most other languages.
BEST advice, DO NOT listen to this music!
💾 day_24.hs
There's a hailstorm. Count how many hails paths will cross in a space-delimited window, then... determine the initial position and velocity of a rock that could hit EVERY hails in only one throw!Tip: consider everything relative to an arbitrary hail (make it stationary and the origin of the new frame of reference), let's call it
h0. The path of another arbitrary hail (h1) relative to h0 forms a line. The rock's path MUST be located on the plane crossing h1's path AND h0. Then determine the moment and position where two other arbitrary hails will cross that plane, go backward in time, renormalize data (h0 not the frame of reference anymore) and you have it.
Really glad I could translate my Python script to Haskell, even if I am spoiled with imperative style...
Arbitrary precision arithmetic is not by default in Haskell? I had to load a "Scientific" library to get the correct number, else I had some rounded value.
💾 day_25.{py,sh}
Looping the loop, and cut those wires!You have a bunch of wires connecting 1515 modules. What are the three wires that, if cut, would make two distinct groups of connected modules?
After squiggling this I thought "if I could take a look at something like that, that would be easy to know where to cut".
Well... lazy last day: I've used the
networkx library to draw the wires and modules (with labels, so I knew which ones to cut).
Visualization helped tremendously. Here, take a look:
See? 😄✂
#!/bin/sh
echo "See you next year!"
Conclusion
I have learned a lot this month. It gave me confidence to build and learn new things. I am not afraid to approach new languages and find myself better in pinpointing necessary tools to solve never-encountered problems. That was time well spent for someone not coming from the field of CS. As seeing computer science from new angles is certainly the sign of a progressing learning process, it will be interesting to compare this 2023 state to 2024's.