Advent of Code 2021 - Day 18

This topic is about Day 18 of the Advent of Code 2021.

We have a private leaderboard (shared with users of Erlang Forums):

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

Here is my solution:

UPDATE: I’ve also implemented a solution in Erlang with a different internal representation that simplifies the explode operation.

1 Like

soo much tedious debugging of recursion, but I love the fact that the parsing is pretty much just a Code.eval_string

also I’m pretty sure I shot myself in the foot for having each node be a {depth, [left, right]} as I think this was making some of the recursion annoying and it was easy to accidentally create the node wrong and whatnot.

Anyhow, both parts run in about 100ms - aoc/day-18.ex at 1542d38365d74533b324c4f790699767ce81b8e9 · ramuuns/aoc · GitHub

Update:
since I hate myself and apparently “enjoy spending a few more hours debugging recursion”, I implemented another version, that runs slightly faster where each node is a {depth, needs_split?, [left, right]}. Besides the ~10% perf improvement, it does slightly simplify the splitting operation at the cost of having to keep track if a node (or any of its children) need to be split. Code for the “improved” version: aoc/day-18.ex at 3419958dee43037aded833dc46c4fde183443add · ramuuns/aoc · GitHub

2 Likes

No sir, I did not at all like today’s puzzle sir. Every year there is at least one like those: too much text describing a tedious arbitrary process that’s a PITA to debug because you missed one of the many rules.

Anyway, I fought with a solution for too long where the numbers were stored as nested lists, but the recursion caused a pain behind my eyes. I fell back to just storing the numbers in a list, and exploding them by keeping track of a left and right carry that gets added to the next number to arrive. It suits nice with pattern matching, the end result is not too bad IMHO (even though some of the code looks more like Perl then Elixir), and fits in under a 100 lines,

2 Likes

Here’s my solution.
I stored the numbers as nested lists, and relied quite a lot on the Access protocol to work with nested elements.
Probably not the most efficient approach, but it takes <1s for each part on my machine anyway.

I finally managed to solve this one. I spend a lot of time changing my structure back and forth and verifying the functions (hence the ugly case blocks) that pick the target for exploding and splitting. Nice to see your solutions, a lot more comprehensive.

Experimented with different data structures and struggled quite a bit. Ended up going with a flat list of depth & num pairs. It made explode, split, relatively easier to implement.

y2021/day_18.ex

Quite late, but I really struggled with getting the explode logic to work. I also overcomplicated things implementing a tree structure rather than just using nested lists. I am excited that I was finally able to make it work though because I’ve always struggled with tree logic and I think this exercise helped solidify it a bit. I still don’t quite understand why I had to rebuild the tree after each update of the left side in the explode function. Really adds to the time complexity (would be O(n) at least anyway, but with that it’s at least O(3n) with n = length(steps). I also only really figured it out after I broke down and wrote tests for each step along the way. First time I’ve really written somewhat non-trivial tests from scratch in elixir.

1 Like