#+TITLE: Advent of Code

Advent of Code is an excellent annual collection of programming
puzzles. It's quickly become my favorite part of the holiday season as
a celebration of programming: carefully crafted puzzles, amazing
solutions spanning astonishing technical stacks, beautiful
visualizations -- with a sense of humor and joy around it all.

The reason I recommend AoC strongly is because it's simply so much
fun: there's a surreal and light-hearted Santa-themed story wound
around each year's story, an amazing -- and inspiring -- community on
Reddit; and the puzzles are generally aimed towards teaching something
new. I'd strongly recommend it even if you don't generally enjoy
programming competitions like Code Jam or Hacker Cup.

* The format
Very briefly: a new puzzle unlocks every night at midnight, Eastern
time from 1st to 25th December. Each puzzle has 2 parts, with
the 2nd part generally being a more complex variation on the theme.

Inputs vary and can be large; occasionally involve ASCII art or other
sentences that need to be parsed. Solutions, on the other hand, tend to
be single numbers or strings that can pasted in: there's no submission
of code required, so you can solve problems however you want. And
people do. In mind-bending, esoteric, eccentric and delightfully
twisty ways.

"Good" solutions should be able to compute the answer in 15 seconds on
old hardware; interpreted languages like Python are perfectly suited
to Advent of Code.

Submissions are rate limited to at most 1 per minute: otherwise one
lateral solution to problems would be to simply brute force the
server with multiple possible solutions.

Scores are tracked for people who manage to be the first hundred to
submit their solutions; the first 1000 explicitly get a rank back on
submission. The rest of us gaze in awe at their short and sweet
solutions.

* Advice for participants
This is as much for me in 2021 as for anyone who's somewhat unfamiliar
with it; there are a couple of things I would recommend to have the
most fun with the contest:

** Play to learn
As satisfying as leaderboard positions can be, it's much more
satisfying to truly learn from Advent of Code: depending on the year
and the puzzle, I've improved my knowledge of -- and fluency with --
graph search algorithms, number theory, learning to choose the right
data structure, and -- yes -- trying to program quickly and failing.

The 2-part format also encourages trading off good design and quickly
hammering out something; a well thought through first answer often
means a faster second answer -- but it effectively trades off your
rank in the first problem with your rank in the second.

** Learn twice as much
Pairing Advent with a new technology that you want to adopt can also
be excellent: the programs are perfectly sized to explore a language
-- or editor -- or other tool that you would like to adopt and are an
excellent mechanism to explore a wide breadth of that particular tool.

For 2018, I tried to improve my Rust but ended up significantly
improving my command of C instead. For 2019, I used every single
Jupyter Notebook interface I could get my hands on to understand all
the amazing software out there (EIN: Emacs IPython Notebooks) ended up
being the solution I enjoyed the most.

Finally, this year was a deep dive back into Rust that went fairly
well -- I also used this as an opportunity to try out different Rust
editors: including VSCode, IntelliJ, and unsurprisingly finding my way
back to Emacs -- albeit with a much more pleasant configuration than
the one I started with.

** Compare your solutions after 
Every day has a corresponding megathread in the Reddit community where
people post their solutions and discuss their approaches. I inevitably
find that I learn something every time I browse through the solutions
-- whether it's in the algorithmic approach, how to structure my
solution, or some features or libraries that I simply wasn't aware
of.

This is generally my favorite part of the contest -- I can see how
other programmers approach exactly the same problem, and learn from
them.  Given that I've also spent a significant amount of time
thinking through the problem first I can also appreciate their solutions
that much better.  This is particularly valuable when exploring
solutions from excellent programmers like Peter Norvig.

** Write about it!
There are so many new tricks and techniques you might come across
during the competition that it's hard to remember them all, let alone
apply them when you next see a similar problem.

Writing about them -- perhaps as notes in your code repo, tweets, blog
posts, perhaps even a Substack if you're with the zeitgeist and an
extrovert, or a Zettelkasten if you're an introvert -- goes a very
long way. I (somewhat annoyingly for any followers) tweeted my way
through 2020, and regret not keeping a better record for earlier years.

** Spend a lot of time on Reddit
The r/adventofcode community is pretty amazing: there's a solid
collection of posts ranging from discussions on different approaches
to problem solving to the best memes and everything in between.

Participating there to learn and have fun is a pretty good use of your
time.

** AoC++
Eric Wastl clearly crafts the problems with a lot of thought and care:
which is evident in how clearly the problems are defined, with useful
edge cases, and each round is beta tested be we get our grubby hands
on it. There's also a significant amount of effort in making sure we
don't DDOS the website.

There's a little more detail around what goes into the sausage in
this video and the FAQ, and I can't even imagine the amount of work
that goes into making good puzzles.

AoC++ is basically a way to get a shiny gold badge next to your name
on the Advent of Code website, and also a way to support AoC with a
little bit of money. I'd strongly recommend donating if you can
afford to -- just to have a higher chance that AoC sticks around
forever (until the heat death of the universe -- or thereabouts).

** Important!?!! Name your files with 01, 02, 03, ...
It's all fun and games till December 10th rolls around and now I *
twitch * every time I see the contents of the folder.

#+CAPTION: Sigh
../static/images/ordering.png


* Resources

** Blitzen
One part of Advent of Code that I dislike is having to manually save
the input files, and then pass them into my solution program
somehow. I ended up writing a CLI to speed me up and stop filling up
my Downloads folder with input1.txt, input2.txt and so on an so forth.

Eric provides an excellent and easy to use API to fetch inputs, and
submit solutions: so I wrote a small program that would fetch the
input and write to stdout -- which I could then pipe into my solution.

Somewhat less useful -- but more cool -- is the ability to submit
solutions through the CLI; it can read from stdin and write to stdout.
Any responses from the server are parsed into markdown and displayed
in the terminal -- this is particularly useful when the answer's
incorrect, and the message from the server includes a hint ("Your
solution is too low", or "Someone else has this exact solution").

I'd intended to make this a trivially small binary given the little
work it does, but adding support for Markdown parsing blew it up to
several Megabytes -- which is something I'll revisit in time for the
next AoC to roll around.

** Excellent solutions
As I said earlier, there are some excellent programmers working
through Advent of Code -- occasionally focusing on readable code
instead of aiming at the leader board, and it's a pleasure to look at
their solutions.

The opportunity to see what others do on the same problem with similar
constraints is extremely rare for me: so I really enjoy comparing my
solutions with others' and learning from them.

- Peter Norvig's Pytudes: A single, elegantly structured notebook that
  solves all the problems in one go. There're some very interesting
  generic functions that apply through all solutions for parsing and
  folding the outputs into solutions.

- Sophiebits's solutions: Sophie is constantly on the leaderboard, and
  I'm generally floored by the terseness of her solutions. It takes me
  some time to figure out how those few lines of code worked.

- Awesome Advent of Code: a massive collection of tools, templates and
  solutions.

- Axel Lind's rust solutions: I found these really useful to be able
  to see significantly more idiomatic Rust than what I'd been writing.

- There are also a tremendous number of people live-streaming or
  recording videos as they go: including Uncle Bob, Joel Grus, and
  several Twitch streamers -- I've skimmed a few videos, but I normally
  don't have the patience to watch so I don't have strong
  recommendations.


* Vignettes from AoC 2020 (Spoilers!)
The unfiltered version of this section is a Twitter thread on my
account where I'd annoy my followers and record my victories and
failures along the way.

Using AoC as means to polish up my command of Rust seemed like an
excellent opportunity. Sadly, that also meant giving up any hope of
making it to the top 100 this time around (I achieved it once in
2019!), but that's a trade I was willing to make.

** What I learned from the problems
This is a collection of things I learned about from this round of AoC:
your personal list will probably be very different.

*** A refresher in modular arithmetic, Chinese Remainder Theorem, etc.
Day 13 had a problem that could be solved cleverly -- by manually
looking for a solution with a constantly increasing loop size, or by
finding a value $x$ that satisfied a series of equations of the form:
$x \equiv b \mod m$

I spent quite a bit of time revising all I'd learned  with Khan
Academy. (Prof. A. T. -- my number theory professor from college --
would be very disappointed at how little I remember; but that class
was 11 years ago.) 

I rolled my own function to get a modular inverse and then
successively reduced the equations by combining 2 constraints into 1
repeatedly till I got a single modular congruence, which I solved to
get the least positive integer that worked..

I enjoyed this problem a lot, and was feeling particularly proud. Then
I saw Sophiebits's ~20 line solution and couldn't believe that it 
worked. Figuring out how this solution worked was fairly gratifying in
itself:
- Calculating the solution for the Chinese remainder theorem by
  applying the direct construction of the existence proof, and getting
  the value much more simply.
- Calculating the modular inverse in Python using Fermat's little
  theorem, where $a^{p - 1} \equiv 1 \mod p$ if $a$ is not divisible
  by $p$; or $a^{p-2}$ is the modular inverse of $a$ mod $p$.

  Of course, since version 3.8 python also directly supports taking
  the inverse by passing in a negative value pow(a, -1, m) as the
  exponent instead.

*** The Van Eck Sequence
After brute forcing my solution for day 15 and assuming I'd messed up
somewhere, Reddit pointed me to an excellent video by Numberphile on
the Van Eck Sequence which was fascinating.

../static/images/vaneck.jpeg


*** An exercise in parsing
I'd become fairly arrogant with my abilities writing parsers after
writing a few trivial procfile and s expression parsers. I completely
missed out on the fact that operator precedence is a thing parsers
have to account for and Day 18 drove that home.

Obviously, with my superior (/s) parsing skills I wasn't going to look
up anything. I wrote some code to break the input into tokens
manually, and then simply evaluate left to right eagerly for part 1.

For part 2, I ended up creating trees and then re-rooting them while
parsing according to manually determined operator precedence rules. I
also added support for eagerly evaluating parts that were known to be
complete, which was surprisingly trivial.

Given this was a tree based implementation in Rust you can imagine
that I had a lot of fun dealing with borrows as well. I suspect this
was my favorite day from AoC 2020.

Reading other solutions after the fact was amazing:  u/fizbin
collected a lot of approaches in their Reddit post. My favorites
include:
- How fortran did operator precedence, described in Wikipedia
- eval-ing the string in Python after some shenanigans to override
  operator behavior.

*** Linked lists inside an array
The ideal solution for day 23 involved a linked list: that made the
required operations significantly cheaper. Given I've been using Rust,
one of the last things I want to do is write a pointer based linked
list -- for this particular problem I could do it by using a long
Vector where the position in the vector identified the value, and the
actually value stored at that point pointed to the next element in the
list.

Faking pointers using indexes into an array works out surprisingly
smoothly in Rust.

This was fairly satisfying to figure out, particularly because my
initial solution took 3 hours and the one with the correct data
structure took <1s.

*** Hexagonal grids and indexing
Figuring out how to translate hexagonal movement into absolute
coordinates was a lot of fun: the key insight to making this all work 
was realizing that I could represent a single point with several
hexagonal paths -- and a single set of (x, y) coordinates. Avoiding
complex irrational numbers meant I could translate things fairly
simply into an offset of 2 along the East-west direction, and 1 up and
1 east for the others.

Red Blob Games has an excellent article on hexagonal grids that I'd
read several years ago, but I must admit I never really internalized
it till I worked things out myself this time around.
 
** What I learned about Rust
For the first couple of weeks I was basically trying to write Python
in Rust: not really relying on the typing system, keeping all the
"business" logic in my head and simply manipulating plain data
structures.

After spending far too much time debugging my solution to Day 20
I decided to start leveraging the compiler instead and actually
defining types and structs and enums.

*** =dbg!=
This one was embarrassing to find out: I couldn't believe I'd been
doing println!("{}", val) for so many years when dbg! was an option. I
do wish there was a way to ask for more compact output.

*** rem_euclid, saturating_sub and friends
I came across this while looking through Axel Lind's solutions:
primitive integers have an astonishing collection of useful functions
baked in. My original solution to emulate this for an arbitrary
integer was to hackily do ((val % mod) + mod) % mod instead to get a
positive remainder.

There's a lot more in the primitive documentation, including several
bit manipulation functions like reverse_bits, which is something else
I'd implemented manually this year.

*** Building familiarity with the Regex crate
BurntSushi's regex crate is fairly famous and really fast: though I
must admit to being a little disappointed that a regex implementation
doesn't ship in the std library for Rust.

I ended up including a snippet using lazy_static! and Regex so that I
wouldn't have to constantly look up documentation.
#+begin_src rust
use lazy_static::lazy_static;
use regex::Regex;

fn parse(line: &str) -> Result<&str, Box<dyn Error>> {
    lazy_static! {
        static ref RE: Regex = Regex::new(r#"(?P<cap>.*)"#).unwrap();
    }
    let captures = RE.captures(line)?;
    let result = captures.name("cap")?.as_str();
    Ok(result)
}
#+end_src

Looking at Sophiebits's Python solutions, I also realized I almost
never try to use a match that matches multiple times and that's
something I should try more of in the future.

*** The magic of Itertools
Itertools almost feels like cheating with all the helpful functions it
provides; I imagine I'm back in Python when applying it liberally.

My favorite functions include
- cartesian product which is very useful for generating all possible
  neighbors for a given grid point. Instead of looping from -1..=1
  twice, I can do a cartesian_product and walk over all the cells in a
  3 by 3 grid. There's also the =iproduct!= macro for this particular
  use case: iproduct!(-1..=1, -1..=1).

- collect tuple is a nice convenience method to collect values into a
  tuple instead of a Vector.

*** Wielding iterators with more skill
It's been extraordinarily tempting to convert all my for loops to
iterators and code-golf my solutions away to nothingness; but if I'm
perfectly honest abusing iterators often makes the code more
unreadable and harder to work with.

That said, some functions I found really useful include:
- =.cloned()= and copied(): Converts an Iter over &T to one over T.
- =std::iter::once= with =chain()=: this is particularly useful to
  append an extra delimiter to make sure the last row in the input is
  handled appropriately.
- =filter_map=: Good for simplifying code and making it easier to
  clean up a collection of Result-s and Option-s.

*** Destructuring vectors (slice & sub-slice patterns, to be precise)
Finding out that this was possible helped simplify some of my
solutions significantly. 

This is partially well documented under Slice Patterns (which sadly don't
show up when searching for "Rust Vector Patterns"). I believe the
latest stable state of the world is captured in a blog post on Sub
slice patterns instead (and the corresponding stabilization pull
request).

A contrived example of the syntax:
#+begin_src rust
fn test(nums: &[i64]) -> i64 {
    let (start, end) = match nums {
        [x0, _xs @ .., xn] => (x0, xn),
        [x] => (x, x),
        [] => unreachable!(),
    };

    start * end
}
#+end_src

*** Profiling Rust
I tried to profile my solution to Day 15: I was a little surprised to
learn that benchmarks needed nightly support, and ultimately ended up
settling on using Inferno to generate Flamegraphs instead.

The changes I needed to make included adding debug symbols for releases,
#+Caption: Cargo.toml
#+begin_src 
[profile.release]
debug = true
#+end_src

and then simply following instructions:
#+begin_src sh
perf record --call-graph dwarf ./target/release/day15 profile
perf script | inferno-collapse-perf > stacks.folded
cat stacks.folded | inferno-flamegraph > profile3.svg
#+end_src

In this case I kind of knew what I was going to find: I was abusing a
HashMap and not using the Entry API, so it was doing multiple lookups.

This showed up clearly in the first profile where most of my time is
spent in looking up keys:

../static/images/profile.svg

Replacing it with an entry API halved the time from 7s to 3s:

../static/images/profile2.svg

And finally I decided to trade off memory for speed and brought it
down to 1s by simply using a Vec in the final solution:

../static/images/profile3.svg


*** Organizing my solutions 
Looking through other people's Rust solutions I've seen several
different mechanisms for organizing repos: some people have a Cargo
project per day, per part, and some of us (including me) decided to
use Cargo's bin support: Cargo Targets#binaries.

This allows me to simply drop in a new file at src/bin/ every day with
a corresponding [[bin]] entry in Cargo.toml.

#+Caption: Cargo.toml
#+begin_src
[[bin]]
name = "day1"

[[bin]]
name = "day2"

[[bin]]
name = "day3"

...
#+end_src

*** IDEs for Rust
I tried out Emacs, VSCode, and IntelliJ IDEA while solving the
problems. IntelliJ was the smoothest option out of the box,
particularly with default-on support for inline types and argument
labels.

A little bit of tweaking allowed me to get the same functionality in
Emacs with support for everything else I'm already comfortable with
thanks to lsp-mode, lsp-rust-analyzer-server-display-inlay-hints and
lsp-rust-analyzer-display-parameter-hints: I'll share my Rust based
configuration separately.

** Some other tools I picked up along the way

*** Cheap screen recordings
My personal laptop is a 2012 Macbook Air running Arch Linux, so it's
not particularly powerful: running OBS to record my screen at a
readable resolution started causing my keystrokes to lag.

As an alternative to be able to actually look at how I perform under
time constraints, I set up a few simple scripts to take a screenshot
every few seconds and then stitched them together into a sped up video
instead. This was surprisingly satisfying and still let me get an idea
of what I was doing and how long I took to do it.

Recording my screen was as simple as running an infinite loop:
#+begin_src sh
sleep 300; while true; do; maim -o "$(date)"; sleep 10; done;
#+end_src

ffmpeg made it nice and trivial to stitch everything together into a
fast video:
#+begin_src sh
ffmpeg -framerate 2 -pattern_type glob -i "*.png" -c:v libx264 -pix_fmt yuv420p video.mp4
#+end_src

** Partial screen recordings: Peek
Peek was really useful in capturing a rough sea full of sea monsters:
I suspect I'll be using it a lot more frequently at and away from work
to capture snippets from my screen.

The UI was a little surprising, but extremely intuitive once I
understood what was happening; using it with a tiled window manager
takes a little bit more effort because it isn't initially obvious that
you're supposed to move the window onto the part of the screen that
you're recording.

#+CAPTION: My blinking Day 20 solution
../static/images/monsters.gif


* Thank you! 
AoC wouldn't exist without Eric Wastl and his team: Tim Giannetti, Ben
Lucek, JP Burke, Aneurysm9, Andrew Skalski and Danielle Lucek -- thank
you all so much!

At the same time, it wouldn't be half as much fun without the
crazy solutions and visualizations by everyone participating in
r/adventofcode -- thank you all so much as well!

All the ridiculous solutions in Excel, on Gameboys, and extremely
obscure languages; the extremely elegant and the extremely minimal but
fast solutions; the professional animations visualizing the problems,
the cartoons; and last but not least -- the memes! -- make it so much
better than any other competition I've seen.

../static/images/memes.png

Until next year!

* Comments?
Discuss this post on Reddit, message me on Twitter or email.