I completed Advent of Code (AoC) 2018 today. It’s a puzzle jam: yearly from Dec 1 to 25 a couple of puzzles are published everyday. It’s popular in geek circles; folks solve them in winter when business is dull. Leaderboards are filled with people who solve them well within the release day. There aren’t any restrictions on when or how you solve these puzzles.

This piece shares my experience for the general computer programmer.

Code

I used Rust but that isn’t the subject of this article. Here’s my repo:

https://github.com/legends2k/advent-of-code/tree/master/2018

I’ve peppered the code with enough comments. My commit logs usually capture context which can’t be added as comments.

I don’t like shortcuts like hard-coding puzzle inputs, keeping everything as strings, etc. I tried to make the code fast, within reason, by being disciplined. I’ve tried my best to make everything structured without yak shaving.

Raise a bug if you want to discuss something.

History

I motivated a couple of friends to join me in trying AoC around 2020 Feb. Little did we know about the then-imminent pandemic. A month from our start we’re deep in lock-downs, procuring grocery like paramilitary, setting up home offices and mini-schools, …

We agreed on completing one puzzle/week since we’re married with kids. We thought it’s a reasonable target given these puzzles are solved in a day by so many. How wrong were we! 🤣

Nevertheless we ploughed whenever we got free time.

Complete ’em!

How fast you complete the puzzles doesn’t matter much than the completion itself.

I’ve no shame in admitting it took 2½ years for me to complete what people do in 25 days. I’m glad I completed them. I didn’t have a regular schedule since life intervened, multiple times (some quite serious like death, relocation, etc. apart from the pandemic). Whenever I found time, I solved small parts of a puzzle. For instance, parsing the input itself was quite a challenge for a puzzle, I took a couple of days (an hour each) and solved it.

Maintaining perspective is important as always. If I’m doing it for fun (and knowledge), what’s the point in trying to rush with a false deadline and pressurize myself? The other extreme is to be so lax I lose interest and not complete. While there’s nothing inherently wrong about this, repeating this for all my endeavours will leave me a bunch of unfinished projects; with mediocre to no proficiency in any language/tool/concept. Let aside mastery, I’d not have stories to tell or experiences to gain with that style of working.

The balance is to complete the project at your own pace while preventing burn outs.

Cheating to learn

I completed almost all puzzles on my own. IIRC, I cheated for 2-3 puzzles; looked up someone’s solution. It’s important to know when:

I cheated when all other options are exhausted and I realized I’m stuck long enough on one puzzle to lose interest in AoC.

Since many had solved AoC 2018 by now, I looked around the forums (r/adventofcode), scoured Wikipedia articles on a data structures / algorithms and discussed with friends. When I realized all my usual options led me nowhere, I turned to someone’s solution. I didn’t read them directly. I usually ran them with my puzzle inputs and checked the correct answer against mine. This helped me solve a puzzle without cheating.

Cheating instead of dropping the project altogether seems okay. It’s okay if you’re doing it for learning; not when you’re proving your worth (e.g. exam).

Takeaways

  1. Developer time is more valuable than machine time
    • Some solutions I encountered took 10x more time to solve the same puzzle, but with a simpler approach and perhaps considerably lesser dev time. Moreover, their actual runtime were in minutes while I spent days to arrive at my optimized structured solution.
  2. Brute force solutions aren’t as bad as you might think
    • Sometimes they’re the optimal solution given other parameters
    • Optimized solutions have poor ROI at times [relates to (1)]
  3. Excessive polishing is a waste of time
    • Know when to stop; understand the Law of Diminishing Returns
  4. Code regularly periodically to avoid becoming a rusty developer; important as you become a senior
    • Corporates don’t care about your coding skills, only results
  5. There are many awesome programmers out there; learn and admire
    • I’m humbled by some solutions I encountered

References

After solving every puzzle, I’d fun going over solutions particularly of of Kanegae Gabriel and Andrew Gallant. Respect and admiration for their work.

Rust

I solved the puzzles in Rust. It’s common for participants of AoC to pick a new language they wanted to get better at as the tool to solving the puzzles. I’d been dabbling in Rust for more than 3 years now; done some Rust exercises; presented Rust sessions at my office. Wanting to improve my kata is only part reason. I knew BurntSushi, author of ripgrep, has done AoC 2018; I wanted to compare my solutions to his after every puzzle completion ;)

I wrote functional-style Rust using iterators wherever possible; it’s terse and sound coding. Thanks to Exercism.io for teaching this early on.

box_ids
  .iter()
  .enumerate()
  .find_map(|(idx, s1)| {
    box_ids
      .iter()
      .skip(idx + 1)
      .find_map(|s2| fuzzy_intersection(s1, s2))
  })

So have I mastered Rust now? Nope; it isn’t the point. More importantly, I’m now confident enough to reach for Rust when it’s the right tool. I’ve learned a bunch of concepts, techniques and standard library facilities I can employ in other projects. I still have to learn about async, generics, etc. (unneeded for AoC). It’s nice to have such backlogs to pursue.

Puzzles

This is the last section for a couple of reasons: (a) maybe uninteresting to non-participants (b) contains spoilers.

Some puzzles were very dry; questions weren’t very good at explaining the problem1. This was frustrating since the rules weren’t properly laid out.

Here’re some notable puzzles and my learnings:

Day 6

Voronoi diagram calculation problem. Involved coding up flood fill-like algorithm.

Day 7

Task scheduler puzzle involving a dependency graph and topological sort. I solved this using a dynamic array (Vec) instead of a graph. I did this by storing the dependants of a task, instead of its dependencies, and followed a push, instead of pull, model on task completions.

Learned about authoring custom iterators in Rust.

Day 9

Computing hi-scores in a game between elves. Wrote a CircularList using Vec. Many solved this using HashMap but simple Vec is fairly versatile and under-used. :)

Day 10

Points move around on an infinitely large canvas frame-by-frame; at a point in time they form a bunch of characters just for a frame. I wrote a 2D visualization to solve this but it doesn’t stop at the right frame; I’d to watch and manually pause the simulation at the right frame. I didn’t realize the bounding box of the entire data keeps shrinking and reaches its minimum when the characters are formed!

My interests in graphics and game programming biased me to take this (non-optimal) my approach. A good learning exercise.

This was my longest hiatus: resumed AoC after a 10 month break.

Day 11

Summed area table problem which I realized only after solving it using a semi-brute force approach.

Day 12

Genetic algorithm puzzle on plant growth. Using bit flags was fun! Bit fiddling is becoming a lost art these days; it isn’t esoteric once you understand the basics and it’s fast.

This is the start of puzzles where solutions can get stuck in infinite loops without a deterministic answer. I’d to bail out of a loop if solutions didn’t change across iterations.

Day 13

Fun problem with ASCII art input of carts spread across a map. It’s a simulation of carts moving around to check an eventual collision. A very satisfying problem!

Day 15

Mini turn-based battle. I gathered from the forums that many folks stopped AoC 2018 at this one. It needs implementing shortest distance path finding and meticulously follow a set of rules to find the victor.

I implemented BFS-based pathing. The puzzle itself wasn’t hard (skill-wise) but involved a lot of busy work. Though I struggled quite a bit, I’m proud I solved it without help.

Day 14 was the start of poor puzzle descriptions. Day 15 was longer, more complicated and unclear.

Day 16

Virtual machine implementation running ElfCode, a made-up instruction set. This was fun! VM created here is used in later puzzles with more complications. It roused the assembly programmer in me; it all came back!

Day 17

A simulation of liquid flow filling reservoirs. This was quite hard. My continuous approach was futile; resorted to a discrete approach and solved it.

Unlike most mine was an iterative solution but super slow (810 ms). Numerous small memory allocations was the culprit; pre-allocating memory lead to a 9x speed up (89 ms). Start pre-allocating and stop worrying!

Day 18

Conway’s Game of Life puzzle. Fun!

Part 2 of the puzzle required running the simulation for 1 billion times. This had to be short-circuited to get a result (in reasonable time). Printing the values revealed a repeating series; I vaguely remember cheating for this.

Day 19

Another ElfCode assembly puzzle. It involved understanding why assembly code was stuck in a loop. Basically it’s trying to factorize a large integer inefficiently. I’d to replace this ElfCode segment with my own (Rust) function.

Learned about Rust modules and wrote a generic Cartesian product function.

Day 20

Shortest distance path finding problem whose input is a very long regular expression. I didn’t use a regex library as it’s fairly easy to parse by hand. I implemented BFS for the shortest path reusing code from day 15. Realized many solutions were a lot simpler than mine; no path finding at all! 😲

Day 22

Another Path finding problem with constraints and edge costs that’s harder; lots of rules and corner cases. I cheated for this; got inspirations from other solutions.

Day 23

Nearest neighbour search similar to the Closest Pair and Largest Empty Circle (Computational Geometry) problems. Given a bunch of scattered spheres find the point such that it’s closest to as many spheres as possible! 😱

Tried brute force approach in vain. Solved by implementing Octree. Very unsatisfying problem; despite coding it using integers and then with floats, an off-by-one error plagued my solution.

Day 24

Another turn-based war puzzle. Input was fairly complicated; most resorted to hard coding or using regular expression libraries. I used this opportunity to learn Parsing Expression Grammar (PEG); it worked quite well! Thanks to Leafo for introducing me to PEGs and pest for such a nice Rust implementation.

Day 25

Very satisfying Union-Find problem I implemented using HashMap.

Conclusion

I thoroughly enjoyed Advent of Code and learned a bunch of things along the way. Time permitting I might try another with a different tool.

  1. I might be wrong as a non-native speaker ↩︎