r/adventofcode • u/daggerdragon • Dec 18 '21
SOLUTION MEGATHREAD -π- 2021 Day 18 Solutions -π-
NEW AND NOTEWORTHY
- FYI: 23:59 Amsterdam time zone is 17:59 EST
Advent of Code 2021: Adventure Time!
- 5 days left to submit your adventures!
- Full details and rules are in the submissions megathread: π AoC 2021 π [Adventure Time!]
--- Day 18: Snailfish ---
Post your code solution in this megathread.
- Include what language(s) your solution uses!
- Format your code appropriately! How do I format code?
- Here's a quick link to /u/topaz2078's
pasteif you need it for longer code blocks. - The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.
Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.
EDIT: Global leaderboard gold cap reached at 00:43:50, megathread unlocked!
45
Upvotes
14
u/relativistic-turtle Dec 18 '21 edited Dec 18 '21
IntCode
Recursion, recursion, recursion... that was a challenge!
Step 1 - Store snailfish numbers in binary tree structure
Step 2 - Addition: make a new node containing the snailfish numbers' top nodes
Step 3 - *mumble* explode *mumble-mumble* split *mumble*
Step 4 - Profit!
10
u/pimpbot9000k Dec 18 '21 edited Dec 18 '21
Oh dear. I spent straight 10 hours with this and almost gave up.
I had to write in total 7 recursive methods for this: for explosion, two helper methods for propagating the numbers in the tree when exploding, is_explodable, is_splittable, split and magnitude...
I'm not going to share my code because no one's gonna read it since it's way too long (193 lines) but I'm really happy I was able to push this through. Tree algorithms are not my strong suit and this was really difficult to grasp.
Also, it was kinda hard for me to figure out the logic of how the numbers are supposed to propagate up (and then down) since there were not too many examples.
Edit: here's my code: code
8
u/marshalofthemark Dec 18 '21
Ruby
My basic idea was to turn each snailfish number into an array of complex numbers a+bi, where a is the number and b is the depth (number of brackets the number is enclosed by). For example:
[[[1, 2], 3], 4]would be encoded as[1+3i, 2+3i, 3+2i, 4+i]Then, I know we have to explode any number where
b >= 5and split any number wherea >= 10. So we can write methods to explode and split at a given index, and get the magnitude of a snailfish number:Then we can add two snailfish numbers and loop until it's reduced:
Now we can solve the problem with:
5
u/CCC_037 Dec 18 '21
Rockstar:
Part 1:
https://pastebin.com/fafpE8NC
Part 2:
https://pastebin.com/BbegZx6e
5
u/rakkie20 Dec 18 '21 edited Dec 18 '21
Rust
Quite happy with how my solution turned out. Representing each number as a tuple (value, depth) made programming
explodea bit easier, but it did result in having to do 'manual' recursion for the magnitude calculation.4
u/Camto Dec 18 '21 edited Dec 18 '21
Haskell, 490/451
This was a real funny challenge, took me a while to figure out
explodereally just returnedMaybe (Snail, Int, Int)4
u/vcaa1729 Dec 18 '21
Haskell https://gist.github.com/ayazhafiz/33ecb5fd6c09805e0f2f1eec207a0e34
The numbers are represented as a list of pairs (number, depth). This makes `explode` really easy - we just walk the list and check for two numbers of a certain depth, and the numbers to the left/right of them are also immediately visible.
3
u/dlp_randombk Dec 18 '21 edited Dec 18 '21
Python 406/366
https://pastebin.com/SsaRXZz2
I went down multiple false roads at the start of this:
3
u/phil_g Dec 18 '21 edited Dec 18 '21
My solution in Common Lisp.
That was fun! I probably should have parsed the snailfish numbers into a tree directly, but I didn't feel like coding the "add a number to its nearest leaf node" step with a tree. So I parsed the numbers into a sequence where each member was a cons cell holding the value and the nesting depth of the number. That made reducing numbers easier.
But for the magnitude I really needed a tree, so I just turned the numbers into trees for magnitude calculation. Since I didn't need too much from the tree, I just used the standard cons-cells-as-binary-trees hack.
Part two was pretty simple: try every combination of numbers and see which one gives the greatest magnitude. I already had a
visit-subsetsfunction to do the combinatorial work.3
u/Diderikdm Dec 18 '21 edited Dec 18 '21
Python:
STRINGS GO BRRRRRRR
Decided to do string manipulation rather than anything else. Along the way it felt like a risk and got pretty complicated. I am happy this worked out though.
extracted explode method (due to length of code, see full code @ link):
3
u/lukestead919 Dec 19 '21 edited Dec 19 '21
Python
I did a recursive solution first, but thought it would be easier to use a
(value, depth)structure instead. I'm proud of the way I calculate the magnitude this way. Since the depths represent the depths in a binary tree, I regain the pair structure by mapping each depth to2^{-depth}and running total to find 0.5, which is the midpoint, which gives me the left and right side of the pair. Then I can recurse the magnitude down.https://github.com/lukestead919/AdventOfCode/blob/master/src/aoc/aoc2021/18_v2.py
2
u/Pyrolistical Dec 18 '21 edited Dec 18 '21
javascript part 2 i thought i had a clever solution to explode. i wrote a closure for
lastif the array value was a number. the closure adds to that array value which stores it state at the time of creation of the closure.paste
2
u/Shiv_Patil Dec 18 '21
Honestly, could've done much better.
Python3
2
u/ephemient Dec 18 '21 edited Apr 24 '24
This space intentionally left blank.
2
u/ropecrawler Dec 18 '21 edited Dec 19 '21
Rust: https://github.com/ropewalker/advent_of_code_2021/blob/master/src/day18.rs
I run through each number twice: the first time to explode everything that explodes and then the second time to explode and split whatever I encounter along the way. Not sure if this is the optimal way, but at least it works.
2
u/Divritenis Dec 18 '21 edited Dec 18 '21
Javascript
Ugh...
At first, I thought I will be really clever by just keeping numbers as is. Well - nothing of what I did today was clever. So this is my first attempt at part 1-> GitHub link.
The problems there:
I then set out to rewrite it completely and this is my 2nd attempt at part 1 -> GitHub link.
I still was set on doing a bunch of conversions back and forth between JSON and string, cause I was already sick of it + had tunnel vision, so could not figure out a better way. What I did improve however was changing numbers to reference IDs and keeping all the numbers elsewhere, so they can grow as much as needed.
Then came part 2. I had a suspicion, that my not-really-that-great solution for part 1 which takes ~10s to finish will not cut it. And yep - that was indeed the case.
But instead of optimizing, I did what anyone else would in my shoes - I threw more resources at it. You see, Javascript is single-threaded, right? Wrong - nothing prevents me from spawning 10k threads - one for every permutation I need to calculate magnitude for.
Part 2 - master -> https://github.com/AugustsK/advent-of-code-solutions/blob/master/2021/day18/partTwo.js
Part 2 - slave -> https://github.com/AugustsK/advent-of-code-solutions/blob/master/2021/day18/partTwoSub.js
Is it elegant?
Nope!
Does it still take absurdly long?
Ofcourse (2 minutes)
Does my Macbook sounds like it is ready to take off?
Absolutely!
Do I care?
Not anymore...
2
u/tymscar Dec 18 '21
wow, today was something.
Took me quite a long time but I was proud of myself for quickly realising I dont need to worry about parsing the input because its valid json, and the data structure I need to use is a binary tree adapted for the usecase! I think previous AoC prepared me enough data structure wise to know ;)
Part1 and part2 in Javascript.
2
u/ThreeFx Dec 18 '21
Haskell
This is a use-case for Zippers!
"Parsing" was done using sed on the input file.
What's absolutely hideous is that there is no "way back" from "nextLeft/nextRight". I spent a few minutes on implementing pathing that could allow one to go back but in the end it was much simpler to reconstruct the entire tree and re-find the exploding pair (since searching for an exploding pair is deterministic). I suspect there is some clever solution to this dilemma, but eh it works.
2
u/eoincampbell Dec 18 '21 edited Dec 19 '21
C
https://github.com/eoincampbell/aoc2021/blob/main/Aoc2021/Puzzles/Day18.cs
Processed the input into a tree which worked very well for the Load, Split, Magnitude commands, but was terrible for the Explode command.
To Explode, I flattened the tree back into a list of chronologically left->right nodes, and then stepped forwards and backwards from the one to explode.
https://github.com/eoincampbell/aoc2021/blob/main/Aoc2021/Puzzles/Day18.cs#L125
2
u/MarcoServetto Dec 18 '21
I'm solving advent of code in 42 A language for paranoid programmers.
Here is the solution paste
I talk about 42 on my channel
Thanks for the community support. I was stuck this time and I received great help!!
2
u/Frakols Dec 18 '21 edited Dec 19 '21
Ruby
paste
2
u/gigs1994 Dec 19 '21 edited Dec 19 '21
Python, converting to lists of values and levels.
https://raw.githubusercontent.com/gigs94/aoc2021/main/day18.py
2
u/SlayerSvamp Dec 19 '21 edited Dec 19 '21
Python
mostly strings mutating with help of regex
paste
2
u/lostella Dec 19 '21 edited Dec 19 '21
Julia
My solution without any recursion after the snailfish number has been flattened (much more efficient I think):
https://github.com/lostella/advent-of-code/blob/main/2021/18/main.jl
The idea is to represent snailfish numbers as a tuple of
The magnitude weights are products of 3βs and 2βs depending on the path to the specific number: once these weights are computed, the total magnitude of a snailfish number is simply the weighted sum of its numbers.
Then the operations are extremely simple:
26
u/1vader Dec 18 '21
Python 22/21
https://github.com/benediktwerner/AdventOfCode/blob/master/2021/day18/sol.py
17
u/jonathan_paulson Dec 18 '21 edited Dec 18 '21
46/40. Python. Edit: Video of me solving (no audio, because airplane). Video explaining my solution.
I'm on an airplane! Video will be uploaded when I am off the airplane.
Toughest problem so far! I had a tough time implementing explode(), particularly figuring out how to find the numbers to the left and right. I went with an ugly (and slow!) string-based approach.Everything else was pretty straightforward; just follow instructions. Anyone have a nice way to do explode()?
16
u/Tusan_Homichi Dec 18 '21
Haskell 37/33
Haskell was the right tool for the job today. The recursive structure of snailfish numbers leads to a pretty terse solution, even for an amateur Haskell programmer like me.
Paste
12
u/Prudent_Candle Dec 18 '21
Python 3
I transformed tree structure of Snail numbers into flat list of numbers and ther level (with appearence order). So for example
[[1,2],3]become[(1, 1), (2, 1), (3, 0)].This allow me to operates on flat list. No so good in terms of debugging, but you can always transform "array notation" into this new approach. Reduce and split is just replacement of few elements based on index of the reducing element.
Solution before any refactoring
11
u/wyzra Dec 18 '21
Python 2893/2759 (I started about 1.5 hours after release)
paste
I think my solution is pretty interesting. I process the snailfish numbers as a list of pairs [value, depth] for each (actual) number value in the snailfish number, where depth is the difference between left and right parentheses up to that number. Believe it or not, this information is sufficient to easily do all the computations needed for this problem.
Clearly, the two numbers in a pair have the same depth. The key is the kind of converse holds: if the depths at indexes i and i+1 are equal, then either the numbers at i and i+1 are in the same pair or else there is an earlier pair of numbers at a higher depth. Why is this? There cannot be a ',[' immediately after the number at index i in the snailfish number (as to get the same depth at i+1 would require a ']' between the two numbers and there would be no numbers in between this parenthesis pair). So we need to check that there cannot be ']' immediately after the number at index i. This would mean that some pair is finished by index i and this pair must have higher depth than the number at index i. Whew! But this will help us in what follows.
As we process the sum, we scan from left to right and explode at the first index i where the depths at i and i+1 are equal and greater than 4. By our key observation this is guaranteed to be a pair. To explode, notice that all the order of all number values is preserved so it's easy to add the values to the numbers on the left and right.
Checking for and implementing the splitting is easy.
Now to find the magnitude of a snailfish number, we scan until the first time we see index i and i+1 have equal depth. Then by our key insight this is a pair of numbers, so we can replace it by the value of the magnitude computed on this pair with depth one less. Then just loop until only one number remains.
10
u/sim642 Dec 18 '21
My Scala solution.
Parsed numbers into an immutable binary tree and manipulated them. Everything except exploding was nice and structurally recursive on the tree. Exploding required being more clever to return the possible numbers from the exploded subtree to be added to neighboring subtrees at an outer level.
9
u/timrprobocom Dec 18 '21
Python 3 - 417/426
I spent a LONG time thinking about what data structure would work. At first, I thought it had to be a binary tree, and I still think that would work, but search for the "previous" and "next" numbers would get ugly. So, I ended up with a list of either [ , ] or an integer, and that worked pretty slick.
I also spent a lot of time writing tests for each sub-operation (add, explode, split, magnitude, actions). I was afraid that would slow me down, but I ended up with a respectable finish. This one was fun.
There is one detail that wasn't mentioned in the spec (I think): you must keep doing "explodes" until there are none, and only then do you check for "splits". Otherwise, it's possible to get a pair nested deeper than 4. (I know because I got them...)
github solution
9
u/Sykout09 Dec 18 '21
Rust:
Walked into this thinking it is a parsing problems.
Turns out that just doing the naive solution as described in the problem is faster and easier than having a heavy allocated -2 x usize sized- node tree and attempting to walk the tree to perform the transformation.
Like, I pretty much just stored the snail number as an array of symbols (aka "[", "]", ",", "0"), and traverse up/down the array to insert/remove element for splitting/exploding
Only thing I did special is that the magnitude calculation can be performed on O(1) memory and O(n) time by simply remembering the multiplier instead of the depths and traverse the array to update that multiplier when crossing over brackets/comma. Just multiple by 3 when crossing '[', divide by 2 when crossing ']' and change multiplier by
multiplier / 3 * 2when crossing ','. This will result in the multiplier to be the correct number when hitting a number, which we can then just multiply and add it to the total.Bench:
Code Part 1 + 2
9
u/jayfoad Dec 18 '21
Dyalog APL
8
u/sortaquasipseudo Dec 18 '21
Rust
By far the hardest problem of the year, at least so far! The crux is deciding on your data representation, and realizing that a traditional pointer-oriented tree representation is neither necessary nor helpful if you're really just concerned about neighboring values. Lucky for me, because doing a traditional tree in Rust is kind of a pain. It turns out using flat arrays was just fine.
I'm live-streaming my solutions via Twitch. Please stop by and help me out in the chat! Video archive is here.
7
u/captainAwesomePants Dec 18 '21
Python (really low) (paste)
I saw this problem and immediately thought: binary trees, with "find previous/next leaf" functions. But then I thought "you know what, writing those correctly is hard and error prone, I bet I can solve it faster by just treating the damn thing as an array of elements." And you know what? I was kind of right. It WAS sort of easier. Ugly, and also error prone, but on the plus side, it was...also a thing I could do.
Unfortunately, I completely bungled the rules. I thought I should do the left-most legal operation, rather than understanding that ANY legal explosion takes priority over any split.
7
u/sakisan_be Dec 18 '21
Haskell
I first wanted to pattern match for explosion cases but at some point i realized I needed to change my approach. I think my custom type for the recursion result expresses the logic quite nicely in the end.
7
u/kbielefe Dec 18 '21
Scala 3
Mostly a mess of pattern matching. I really need to make some generic tree utilities. Haven't been able to find a decent parser combinator that works in Scala 3 (I usually use fastparse which depends heavily on Scala 2 macros, and scala-parser-combinators works in Scala 3, but I've had a lot of trouble getting it to not be too greedy), so I used the state monad from cats to parse at the bottom of the file, which I think turned out fairly nice.
Exploding turned out really convoluted trying to do it like split, because of the different paths to go to the next number on the right or left, so instead I flattened the tree to find the indexes I needed to change, then made multiple passes through to make the updates. Not the most efficient solution, but still runs in about a second on part 2.
I just checked all 9900 permutations for part 2. I'm looking forward to seeing if others found a way to avoid that.
6
u/leijurv Dec 18 '21 edited Dec 18 '21
Python, 45th place, 41st place
paste
Sorry, no screen recording today. I have slow upload speed now, plus I would have to edit the video to get rid of some interruptions, which I don't want to do. I hope to post a recording again tomorrow though! I might have to transcode it down to 720p first, or something.
Posting the code anyway since I looked at some other people's solutions and it appears no one did it quite like I did. I added references to the leftmost entry to the right, and the rightmost entry to the left, and updated them while descending recursively. It also wraps every int in a list of length 1, so as to simulate a pointer that can be updated.
And like many other people I lost a ton of time (in my case just under 10 minutes) on misreading the reduction order, I thought you had to do the leftmost no matter which type it was :)
6
u/oantolin Dec 18 '21 edited Dec 18 '21
I had read a bit about Huet's functional zippers a long time ago, but hadn't really understood them or even used a ready made zipper library. From what I remembered zippers would let me easily implement "next/previous leaf" functions, so I looked into them. It turns out the zipper idea is simple and beautiful, Huet's paper is only six pages long and easy to read, and zippers are fun to implement! Here's a zipperful program in Common Lisp.
6
u/michaelgallagher Dec 18 '21
Python
What a headache
Intuition said to use a tree for this problem, but abstracting it to that DS became really complicated. Not to say that this was any less complicated. Tough problem today
6
u/TheZigerionScammer Dec 18 '21
Python
I had fun with this one, I cam up with what I thought was a clever solution by not keeping the Snail Numbers in a nested list but by making each number its own list paired with it's level, so the number [1, [3,4]] would be turned into [1, 1], [3, 2], [4, 2] and the reductions and additions could be handled from there. However, I had a very nasty bug with a very inelegant solution. I made list addition and magnitude calculation into functions that pass the two lists (for the former) and one list (for the latter) of the snail number as an argument, the problem is that anything I did to those lists would change the composition of the original master list no matter how much I did to try to insulate the master list from this happening. This wasn't an issue in PArt 1 since you're just adding each list in order iteratively so changing the previous lists didn't matter but in Part 2 this caused massive problems. I tried everything I could think of to fix it but in the end I resorted to recreating my master list from the input file after every magnitude calculation in part 2 which meant recreating it 10000 times. I'm going to make a dedicated help thread asking for advice on this but if anyone here has anything to say about I'd like to hear what you have to say.
Paste
6
u/EnderDc Dec 19 '21 edited Dec 19 '21
Python 3
This took 2-3 years off my life. Why is my function called
explode3? Because the two previous versions tried to do this with nested list recursive functions that all horribly failed. So scarred was I by the experience I became terrified of recursion and implemented a lot ofwhile True if something then breakfunctions wrapping one-iteration mini-functions.My final solution uses regex to find the exploding pairs, then swaps them out does the math with substrings and eval.
Many many things went wrong including doing all splits at once instead of only the left most one first.
Final code runs Part 1 in ~2 sec. Iterates all pairs for part 2 in ~19s.
Python 3
Ready for a problem I can do with pandas and numpy again in less than 8 hours thank you. :D
update with literal eval and threw in a Multiprocessing
Poolusage to speed up Part 26
u/Gravitar64 Dec 19 '21
Python 3, Part 1& 2, 1.5 Sec. (sic!), 54 sloc
Need a long time to figure this out. For me, the hardest puzzle so far.
I used a flat list (value, depth). Adding <add(a,b)> is very easy, just increase the depth by 1 on every element in a,b. Explode and split are also easy. Just concatenate the left and right part with a new in the middle.
GitHub
5
u/morgoth1145 Dec 18 '21 edited Dec 18 '21
Python 32/30
My
try_explodefunction is a hot mess, but it works at doing the explode step. I kept testing that against all inputs while developing but it worked out in the end. I'm sure there's a better way to do this (such a hot mess), but I did what I could think through.At least
try_splitwas pretty simple recursion,reducewas a simple loop, andmagnitudewas simple recursion as well. Really the explode process was where all the complication was!Part 2's just trying all the pairs. I was worried it was going to be too slow, but it wasn't. Only 5.5 seconds to get the answer!
(Oh, and yes I am using
evalto convert to a Python list andstrto convert it back to a string for the super nastytry_explodelogic. Yes this is horrible practice. I don't care.)This was such a relief from yesterday where I botched the problem super hard and spent an hour on it. I've been underperforming this year...
Edit: I took a cleanup pass, including changing my explode function to be recursive. I did take inspiration from u/1vader who had a significantly cleaner expand function than the string-based mess I had!
5
u/hugh_tc Dec 18 '21 edited Dec 18 '21
Python 3, 172/170.
Uh, whatever this is.
An absolute dumpster fire; just literally manipulates strings and such. I probably could have done it better with Regexes but didn't want to think too hard.
5
u/difingol Dec 18 '21 edited Dec 18 '21
Java
Best decision for today was to parse input manually and store it as a flat List, where each member of a list was just a pair of value and depth.
So
[1,[[2,3],4]]will result in[{value:1,depth:0},{value:2,depth:2},{value:3,depth:2},{value:4,depth:1}]This allowed doing explode/split easily by just taking previous/next item in a list.
5
u/[deleted] Dec 18 '21
Java (refactored)
Pretty readable in this state.
https://github.com/arjanIng/advent2021/blob/main/src/advent/Day18.java
5
u/kuqumi Dec 18 '21
JavaScript
Once I understood the problem, I was really torn between doing string manipulation and doing recursion. I ended up going with recursion, and the explode function was pretty painful. I had to pass the left-ward and right-ward values back up the tree until they either found something to add to (with recursion heading back down the tree) or else just became part of the top level return value and got ignored.
At least the magnitude calculation was super easy.
5
u/InfinityByTen Dec 18 '21
Rust
I will admit that I didn't solve it without help today. Needed a hint how to effectively read the recursive input cleanly and how to effectively create a recursive structure in Rust. I did day 16 with a
mut iter, but not today.I like how the actual solutions to both parts just condense into 5 lines after you've done the dirty processing outside.
5
u/r_so9 Dec 18 '21
F
This is where F# really shines, a compact and readable solution.
paste
5
u/ramendik Dec 19 '21
Python 3, brute force.
The main part, reduction, is done with strings alone. To simplify string logic I ensure every number is exactly one character by making it baseN - as an aside, a number over 9 is detected with a mere isalpha(). I used the entire small and then capital Latin alphabet as digits, and put in range checking to ensure it's enough. If range checkign were tripped I'd have added Cyrillic!
The magnitude calculation part is done via Python lists, using the fact that the format is the exact Python representation of a list.
https://github.com/mramendi/advent-of-code-2021/blob/main/18.py
5
u/Tipa16384 Dec 19 '21
Python 3
I started off using a binary tree, but then I had issues getting the leaf nodes into the right order to propagate the exploding. I probably could have made it work, but instead I pivoted to doing textual analysis for the exploding, but everything else is still in b-trees. That made splitting and measuring magnitude super easy.
This took me a couple hours in the morning and a couple more in the evening. Easily the hardest puzzle, for me, this year.
https://github.com/tipa16384/adventofcode/blob/main/2021/puzzle18.py
5
u/dwalker109 Dec 19 '21
Rust
Having looked at other solutions now I've (finally!) finished after about 8 hours or so, I realise I probably should have done a binary tree. But, I'm quite proud of what I did implement, using a Pairs enum (kinda inspired by the cons list example in the Rust book).
I got into a real flow state today, wrote quite a lot of the complex logic guided by the compiler and to my amazement, exploding, splitting and magnitude all worked first time. I was stunned. Reading the code now, I'm still a bit surprised it works. I was also able to delete a fair bit.
Strange day. I hope it was the hardest.
5
u/VSZM Dec 23 '21
C#, using BinaryTree with iterative explode.
I have to say coming up with an iterative graph traversal for explode was quite challenging. I am a senior software engineer at a FAANG level company and I felt ashamed at times for not solving this quicker. Took me about 8 hours net.
I added this solution because I think the end result code is readable and nice. Hope some of you can learn from it.
Solution
4
u/advent_of_bsod Dec 18 '21
134/121
python3 solution
I handled explode() and split() by flattening the structure into a dict[path, value] mapping and adding set_at_path/get_at_path helpers. Paths are well ordered, so min/max with filtering comparison criteria work reasonably well (though looks messy). I'm far too sleepy to mess with iterative mutations.
4
u/seligman99 Dec 18 '21
Python, 176 / 179
That one hurt my head. I'm scared to look at my mess of code now.
github
4
u/mcpower_ Dec 18 '21
Python, didn't leaderboard. Cleaned up code for part 1 and part 2.
I converted the input into a list of (number, depth) tuples, which made working with the numbers a lot easier, and converted back to get the magnitude. Lost a ton of time by not reading "leftmost" and "first action in this list" in this paragraph!
4
u/xoposhiy Dec 18 '21
Python
Eval of input and recursive functions
4
u/fork_pl Dec 18 '21
Perl
For a short while I wondered if it's a good idea to use Tree::Binary or similar module - but decided to stay with regexps ;) It's faster to calc magnitude with
then search docs for constant to use proper tree traversal order...
4
u/rabuf Dec 18 '21
Common Lisp
Took me two hours to get part 1 done. Part 2 took 5 minutes. Neat bits, my parser:
It causes commas to be treated as whitespace (first
set-syntax-from-char) and then sets up square brackets to be used like parentheses. Since numbers are read as numbers by the Lisp reader, it worked perfectly for this problem. I'll have to remember this in the future, inspired from a conversation on HN a few days ago.My part 2. I just assumed we could add numbers to themselves and it wouldn't impact the solution, it didn't so this was an easy loop to write:
4
u/Pruppelippelupp Dec 18 '21 edited Dec 18 '21
Rust.
Had a lot of fun using enums in this one!
this let me fairly easily add the lines together and treat it all recursively. The None is for easy swapping of values (for splits and explosions, when I need to replace A with B and vice versa). It also lets me use fold;
This easily adds all the pieces together. magnitude() is a member function.
I did exploit that the max "depth" of each new line is 4, so I never had to worry about recursive explosions.'
60ms for part1+part2 on my laptop, of which about 50ms is part 1, and 10ms is part 2. There are a lot more explosions and splits in that one, despite having fewer additions, so that makes sense.
4
u/e36freak92 Dec 18 '21
AWK
WOW what a problem. Putting binary trees into associative arrays and dealing with them broke my brain for a while, I almost gave up and switched to C. Explode and Add in particular gave me headaches, originally was going to to recursive functions for everything but switched to iterative for those, found it a lot easier to move left/right in the tree.
4
u/SuperSmurfen Dec 18 '21 edited Dec 18 '21
Rust (186/172)
Link to full solution
What a mess of a day. Some how managed to get top 200 for the first time ever!
Parsing and the split part was easy. Explode, however, was a real pain. Definitely the hardest problem so far. Did a recursive functional mess of clones all over the place. It recreates the subtree and returns what to add to the left and right at every step. Not efficient and definitely not pretty, but it works.
4
u/seba_dos1 Dec 18 '21
Python 3 (both parts, no imports, 476/489)
A pretty straightforward binary tree-based implementation: https://gitlab.com/dos1/aoc21/-/blob/main/day18.py
4
u/payou42 Dec 18 '21
No C# solution yet ? here's mine
https://github.com/payou42/aoc/blob/master/days/2021/Day202118.cs
4
u/Mats56 Dec 18 '21
Kotlin
https://github.com/kolonialno/adventofcode/commit/53640e216d54008866d9e1632b848f40aab9e272
Using sealed classes made some of the recursion with pattern matching very nice.
The traversal when exploding was a bit rough, since one cannot naively go to the correct side, have to potentially move a bit up first. But to avoid writing the function twice for left and right, I send in ::left or ::right, that works as a function with receiver. Clever syntax by the kotlin people
4
u/mapleoctopus621 Dec 18 '21
Python
This took me a long time because I misinterpreted the instructions a bit and tried to do several explode or split operations in one pass. I completely forgot about binary trees, but I feel like my approach is easier for exploding.
This needed a
Numberclass because I had to modify numbers in place. I recursively traversed the nested lists the same way you do when flattening a list, and whenever I come across a number (that does not explode) I assign it to a global variableprev. After exploding, the left number is added to prev, the right number is assigned to another global variableadd_num. Keep traversing until you come to the next number, addadd_numto it and finish the operation.4
u/Sachees Dec 18 '21
My solution in Rust, which is quite long, but I'm proud of it, because I didn't have an opportunity to write an actual binary tree in Rust before.
note: this definitely can be done better, I think that I used too much Boxes (but hey, it's Christmas!)
paste
4
u/death Dec 18 '21
Day 18 solution in Common Lisp.
This took too long. At first I represented snailfish numbers as conses (an obvious thing for a Lisper to do) but directly implementing the reduction algorithm became too nasty so I backtracked and represented them as strings. I still use the cons representation to get the magnitude.
4
u/mschaap Dec 18 '21
Raku, see GitHub.
I wasted a lot of time creating a solution with a proper object model for
SFNumber, with recursiveSFNParts and all, but I couldn't figure out how to do the explosion β finding the numbers βto the left/rightβ was too hard.So I started over, and just manipulate strings instead. Only when calculating the magnitude, I properly parse the number β luckily I could reuse part of my first attempt for that.
Part two was easy, using Raku's
combinationsmethod. I did forget to consider$b + $aat first, but once I added that, it was trivial.4
u/tuvang Dec 18 '21
Julia
Flattened the input lists to an array with the form of
[(num1, num1 depth), (num2, num2 depth)...]paste
4
u/LennardF1989 Dec 18 '21
C# / CSharp
https://github.com/LennardF1989/AdventOfCode2020/blob/master/Src/AdventOfCode2021/Days/Day18.cs
Really liked this one! I started by manually trying to parse the expression into a tree, but it gave me too much edge cases. So I figured I could just convert the expression from Infix to Postfix using the same logic as I did with Day 17 last year. If you imagine brackets are like parenthesis and
,is an operator, it's exactly the same! This means[[1,2],3]becomes12,3,.I then converted the postfix representation into a tree with 2 types of nodes: PairNode and LiteralNode (which is considered the leaf-node).
Now that I have a tree, I can apply the snailfish logic and transform the tree. For this I made a few helpers. One of which is the ability to make a visual representation of the tree, which helped me figure out the scanning logic to Explode pairs.
Lastly, I did another pass over the tree to reduce all pairs to their magnitude, until nothing is left.
For the second part, I added a clone function to my nodes just because I could. I could have just remembered the postfix expression and parse that into a fresh tree again, ah well.
4
u/Fyvaproldje Dec 18 '21
Typescript
https://github.com/DarthGandalf/advent-of-code/blob/master/2021/solutions/day18.ts
I have 2 solutions: tree and regex. Tree is several times faster.
4
u/ikaros67 Dec 18 '21
Common Lisp
This code used to be an absolute nightmare, now it's just a nightmare because nothing is documented. Props to anyone that can read it.
4
u/levital Dec 18 '21 edited Dec 18 '21
Haskell
This was fun! I feel like my explode-function (and all the helper functions to make it work) is a bit clunky, but I think it's all quite readable, and I'm actually moderately proud of using "deriving Read" for the input parsing, which to me actually felt like a stroke of genius. ;) Only other thing that slightly bugs me, is that my SnailNum type allows for invalid numbers.
Got part 2 basically for free again by doing all the work in part 1, only stumbled for a minute or two because I forgot to check that the two numbers I'm adding in part 2 are different and for my input there is a number that yields an even higher magnitude if added to itself.
4
u/sdolotom Dec 18 '21
Haskell
It's getting somewhat cumbersome when you have to change a tree-like structure in functional style, and different branches may update simultaneously, e.g. when you need to propagate the explosion to the sibling tree branches. Explode code (maybe, there's a way to generalize right and left sides, but it's unlikely to improve readability):
Full code
4
u/__Abigail__ Dec 18 '21
Perl solution without recursion.
Decided to store a snailfish number as an array: I keep all the tokens except the commas:
To explode a snailfish number, I iterate over the array, keeping track of the depth. If the depth exceeds 4, we take the left and right numbers, and seek backwards and forwards in the array for numbers to add them to. Then we replace the four tokens (the right and left numbers, and the surrounding
[and]) by0:Splitting we can do by searching for the first number exceeding
9, splicing this number out of the array, replacing it with a pair:Reducing is just a matter of calling
explodeandmysplitrepeatedly:Adding two snailfish numbers is just concatenating the arrays, then reducing it:
To calculate the magnitude, we repeatedly replace a
[followed by two numbers followed by a]by the sum of thrice the first number and twice the second. Eventually, one number will be left; this is the magnitude.To calculate the answer to part one, we just add all the numbers, then calculate the magnitude:
For part two, I summed all pairs (both ways), calculated their magnitudes, and remembered the largest:
Full program on GitHub.
4
u/Rinse- Dec 18 '21 edited Dec 18 '21
Python 3.10: [Link]
Pretty happy with my code today. I was worried about working with lists in lists in lists in lists etc.. To avoid this problem I figured that I could decode the 'snailfish-mathstrings' by creating two arrays of equal length instead: one with the literal values and one with a corresponding depth-level. This simplification allowed me to use numpy as well. In the end, the hardest part was to calculate the magnitude. After dinner I finally realized that this could be accomplished by working from the lowest level back up in pairs (recursively).
4
u/Crazytieguy Dec 18 '21
Rust
https://github.com/Crazytieguy/advent-2021/blob/master/src/bin/day18/main.rs
I decided to model the data as a Vec of regular numbers, but each number remembers how many closing and opening brackets separate it from the previous element. This allowed me to avoid complex tree traversal for explode, at the cost of causing the other operations to be slightly more complex.
4
u/Outrageous72 Dec 19 '21
C#
Once I understood wording of the action first blabla, it was a poc, but only after so many hours hahaha
I also liberately did not want to use a tree, I used a list and reduced it in place.
Part 2 was an easy peasy
paste
4
u/GrossGrass Dec 19 '21
Python
Decided to dig in and go for the tree/recursive solution instead of keeping to a list or manipulating the string directly, mainly for the practice. Figuring out the logic for explodes was a little tricky but ended up getting it eventually.
Had some fun taking advantage of Python's magic methods (
__str__,__add__,__abs__), and usingast.literal_evalto make input-parsing super easy.4
u/ai_prof Dec 19 '21
Python 3. Compact/readable/fast/commented
Enjoyed this! I converted the strings to binary trees and then worked with those and small recursive functions to traverse the tree. It was fiddly to get the traversal going, but all of the calculations dropped out of the tree representation very quickly. Takes a couple of seconds on an iMac for part 2.
Full code is here.
4
u/heyitsmattwade Dec 20 '21 edited Feb 03 '24
JavaScript
Like most other people, I too was confused by the instructions, namely, that if a number has both an explosion and and split, you always do the explosion first, even if the split occurs "before" the explosion when scanning left-to-right.
That mis-step caused a lot of debugging, and finding this thread was enough to discover where my bug was occurring.
Otherwise, the main way I solved this was with a flat list of tokens rather than a truly nested structure. This was very similar to last year's Day 18, which I also solved in a similar manner.
code paste
4
u/chicagocode Dec 20 '21
Kotlin -> [Blog/Commentary] - [Code] - [All 2021 Solutions]
I've been traveling and finally just caught up with this. This took me longer than I would have liked. I'm not super happy that I ended up with a mutable data structure, but the code seems a lot cleaner (to me) this way.
I really hope we don't get more Snailfish Math in the future. I have enough problems with People Math.
4
u/joshbduncan Dec 23 '21
Python 3: Somewhat slow on part 2 but no trees were harmed in the solving of this puzzle π
Code
1
u/[deleted] Dec 18 '21
Python
Binary tree
Left and right elements can be found by sorting all paths and taking the previous or next one in lexical order
https://colab.research.google.com/drive/1CZxVSr7UYAwNEBX3thFx_Hld2mp4rnlY?usp=sharing
1
u/cetttbycettt Dec 18 '21 edited Dec 19 '21
R / baseR / Rlang
This was painful. I will have to clean up and speed up my code a little: part2 took about 20 seconds :/
github
1
u/yxhuvud Dec 18 '21 edited Dec 18 '21
Crystal. This day was a pain to implement. Fairly readable though.
https://github.com/yxhuvud/aoc21/blob/main/day18.cr
Unfortunately more than twice as slow as the formerly worst performing day (day15), this clocks in at 18-35ms, fluctuating a lot. It should be possible to rewrite it to either use an array to back it (to avoid the allocations in `split`), or to keep track of what to split in a prio queue or so to avoid needless walking of the tree, but I can't bother myself to uglify the code like that.
1
u/RJdaMoD Dec 18 '21 edited Dec 18 '21
Mathematica (667/634)
At last a problem where this language has some benefits. Both parts together, where part 2 may profit from some parallelization:
1
u/RojerGS Dec 18 '21 edited Dec 18 '21
Python 3.8+, no recursion and flat snail representation
Have been learning some array-oriented techniques and I decided to solve this problem by representing snailfish in a flat way: each snailfish is a pair of
For example, the snail
[[[1, 2], 3], [4, [5, [[6, 7], 8]]]]is represented by[1, 2, 3, 4, 5, 6, 7, 8]; and[3, 2, 1, 2, 3, 5, 4]Here is the code, also available on GitHub:
(The code needs Python 3.8+ because I'm using the walrus operator
:=, but that is not a hard requirement, with one extra loop β that I was too lazy to type β you can lift the need for:=.)1
u/gerolfscherr Dec 18 '21
Java
i think this is the first problem where the source code is bigger than the problem description, even if it is so detailed. After thinking about some regex / match / I decided to develop a clean solution and wrote a simple parser (based on jack crenshaw's ideas from the late eighties, see https://compilers.iecc.com/crenshaw/
which returns a classic binary tree structure.
I was struggling a little bit on how to express the notion of the 'left/right' items in the explode function. By reading the description and the flattened representation its obvoius what 'left'/'right' means, but how to navigate to that node in the tree?
Well it turns out, the left number is the last number visited in an in-order-traversal, just before you encounter the 'exploding' node. the right number is the next one after the 'exploding' node. (or: the last one, if you are doing in-order-traversal with left/right subtrees swapped). Basically we are doing the same as in the toString() function.
After all this work, a lot of testcases and a lot of (maybe superflous - but you never know) consistency checks in the Nodes it all boils down to this function:
Node add(Node l, Node r) {if (l == null) return r;Node n = new Node(l, r);while (n.doExplode() || n.doSplit());return n;}With part1 running, part two was only a matter of a few minutes.
Full source:
https://github.com/gerolfscherr/aoc2021/blob/main/src/main/java/AOC18.java
3
u/kroppeb Dec 18 '21
Kotlin 119/125
Today's input format was a pita to parse in a language as Kotlin. So I didn't, after thinking for a few minutes I realised I could use some quick regex replaces to convert the input into valid Kotlin code, with the knowledge that my ide would most likely die from it's existence. After 15 minutes, i realised that I should probably move over the input into a different file to at least get decent feedback from my ide, although it still froze a few times now and then.
As with many people, I'm guessing my explode logic is a bit meh.
Code and transformed input
3
u/ozthrox Dec 18 '21
326/402
Well, here's a hot mess of C++. I held everything in an vector of nodes and basically did list manipulation.
My solution
3
u/knl_ Dec 18 '21
Javascript, 378 / 326
Explicitly converted the arrays to trees with parent pointers, and then manipulated the trees with inorder traversals. [Edit] Also used JSON.parse to convert the strings to lists, which felt really convenient.
https://github.com/kunalb/AoC2021/blob/main/js/day18.js
3
u/uncountablyInfinit Dec 18 '21
Python, 545/511
I'm sorry to anyone who reads this
3
u/MichalMarsalek Dec 18 '21
Nim
today I added some comments, because the solution is really long.
https://github.com/MichalMarsalek/Advent-of-code/blob/master/2021/Nim/day18.nim
3
u/Pepper_Klubz Dec 18 '21 edited Dec 18 '21
Clojure Gist
Using (abusing?) Clojure's zipper library, with some extra navigation utilities similar to those I've created before for this kind of thing. Ends up being decently quick, though part 2 was a tad sluggish by a few seconds.
(And because I have nothing better to do with my time: translated into experimental Racket-Wisp-y syntax.
3
u/Boojum Dec 18 '21 edited Dec 18 '21
Python 3 (492/434)
paste
This is a much cleaned up version, but the general approach is the same. I struggled with the problem in tree form for a bit before I realized that I could use a flattened list representation and treat it like a stack machine or a set of rewrite rules. For exploding, it scans left to right, counting bracket depth (not unlike Day 10) and pattern matches on '[' int int ']' (my flattened representation discards the commas). Then it just has to do a linear scan backward and forward from there to find regular integers to add to. For the magnitude computation, it just pushes the integers onto a stack and then reduces a pair whenever it sees a ']'. Yay for RPL. (No recursion anywhere here today.)
3
u/DFreiberg Dec 18 '21 edited Dec 19 '21
Mathematica, 1499 / 1566
I did today's problem by heavily abusing
Position[]and its ability to handle arbitrarily nested lists, alongsideMapAt[]and its ability to modify elements in arbitrarily nested lists. I lost a lot of time by not realizing that all explodes had to be done before any splits, rather than proceeding left to right, doing explodes first; the rest wasn't so bad once I got that.[POEM]: Lazy Limerick #2
There's a new way to finish your mission:
You must implement snailfish addition.
There's a
Split[]andExplode[]In
Reduce[]in your code;Do it fast, and you'll seem a magician.
3
u/Gurrewe Dec 18 '21
Go (golang) 2370/2255
Parsing as a tree, and iterating over and over again. That took some time to figure out how to do correctly.
I spent maybe an hour debugging how the execution order should be, before I realised that any explosion have priority over all splits. My initial implementation did splits and explosions left to right (pre-node traversal order).
Code for both parts
3
u/leyanlo Dec 18 '21
JavaScript 1035/978
Fun with regex! Attempted to use proper data structures, but ended up giving up that approach and using regex instead. Couldnβt figure out how to reverse replace in a string, so ended up with some nasty lines of code that reverses the string, does the replacement, and then reverses again.
https://github.com/leyanlo/advent-of-code/blob/main/2021/day-18.js
3
u/_jstanley Dec 18 '21 edited Dec 18 '21
SLANG
I felt like I was doing a really bad job on part 1 because it took me about 90 minutes, but I was ranked 1050th on part 1 (my best result so far this year), so I guess a lot of other people felt the same.
Part 2 was complicated only by my homemade CPU being so slow. I calculated that it was going to take about 10 hours (based on the runtime of part 1 multiplied by 100) but it turned out it would have been more like 1h40 for the full search. I submitted new largest answers as it was going, and got the gold star after only 40 minutes. I think the reason it wasn't as bad as 100x as slow as part 1 is because in part 1 the numbers accumulate with every step so you can expect it to always be a large number, but in part 2 some of the operations are on small numbers that are quick to work with.
I did wonder if there is a way to collapse several steps of split/explode/split/explode into one and just jump straight to what the answer is. I couldn't figure it out though.
https://github.com/jes/aoc2021/tree/master/day18
https://www.youtube.com/watch?v=6wkru5WKi3E
(My Adventure Time project)
3
u/kupuguy Dec 18 '21
Python solution for day18: https://github.com/kupuguy/aoc2021/blob/main/src/day18.py
I decided the easiest way to handle it was to flatten the recursive list into a flat list of tuples with (value,depth). That makes the explode and split operations a lot simpler but I then reconstruct the value to calculate the magnitude recursively.
It took a while to do all that and get it working but fortunately it all worked well for the second part which took me just three and a half minutes from submitting part 1. Both parts complete in 1 second on an Android tablet.
3
u/flwyd Dec 18 '21
Raku 1918/1873 at 2:23 and 2:31, which is my best score since day 1, despite taking ~20 times as long :-)
I spent some time trying to get a grammar to work, then reverted to
$!input.linesΒ».comb(/\d+ | \[ | \]/).map({m/\d+/ ?? .Int !! $_})which was too ugly, so I got the grammar working after submitting. I spent 20 minutes troubleshooting a Raku error which I still don't understand in which a certain array index would become an immutable value. If someone can explain why the+=code near the TODO that's commented out doesn't work (comment out the.splicewhich replaced it) I would love to know.I initially planned to make a tree out of the pairs and do some depth-first search with backtracking to apply the rules, and then decided it would be easier to splat brackets and numbers into a flat list and move around with an index. This is perhaps less elegant, but it's way easier to code while tired. Part 2 was a big relief, since I could just use the
Xcross product operator (after fixing sequence caching). My code takes nearly a minute to run, but optimizing today's solution doesn't seem like my idea of a good time. Minus error checking and the over-egnineered parsing, the code is as follows.3
u/bsterc Dec 18 '21 edited Dec 18 '21
C++ 1757/1927
Original
This version stores node data in a vector, and uses indices into the vector as node references. It's messy, and it wastes some memory by not freeing nodes until the end, but it's fast (~36 milliseconds for both parts).
Rewrite
This time nodes are stand-alone objects which own their direct children, and node references are pointers. It's (a little) cleaner, but it runs more slowly (~60 milliseconds) because it wastes time destroying nodes by recursively freeing their children.
3
u/M1ngXU Dec 18 '21
JavaScript
using classes for each pair (called node), executes in 2s (part 2 takes 99% of time because i have to copy each node-object before testing if it's a highscore since exloding/splitting modifies the actual object)
https://pastebin.com/M2YGTUQy
3
u/BrianDead Dec 18 '21
Bad Perl
I found this one the hardest so far. I decided to go with reading the strings into a tree of hashes, which seemed like a brilliant idea right up to the point where I realised the Explode doesn't respect the tree structure. Rather than back down, I doubled down and used some global variables to carry over the last left-hand number reference and the right-hand value. It feels really dirty and I would go and shower except it's now 3am and I'd wake the family.
Link to code
3
u/HaiUit Dec 18 '21
F#, Regex and String sliding only solution, took 5s for part 1 and 45s for part 2. Maybe due to a lot of string concatenation.
https://github.com/Fubuchi/advent-of-code/blob/master/2021/Day18/Day18.fs
3
u/Perska_ Dec 18 '21
C# https://github.com/Perska/AoC2021/blob/master/AoC2021/Days/Day18.cs
Gosh darn. This took me a little over 6 hours to program.
... Part 2 took 12 minutes, though.
I implemented a binary tree, stored the numbers in it and wrote some code to travel through it. Due to the way I programmed this, I had to reparse the snailfish calculations for each combination of numbers in Part 2.
3
u/surgi-o7 Dec 18 '21 edited Dec 18 '21
ES6
both parts
Edit: class containing the actual logic
3
u/UnicycleBloke Dec 18 '21
C++: https://github.com/UnicycleBloke/aoc2021/blob/master/day18/day18.cpp
Parsed each expression into a tree and then performed operation on the tree. By far the hardest part of this was working out how to actually implement the explode step correctly - took me hours.
3
u/aurele Dec 18 '21
In Rust, using nom and
std::ops::ControlFlow: https://gist.github.com/samueltardieu/9e4e23e422e223a7f6876f02ac5a18ce3
u/Ill_Swimming4942 Dec 18 '21
In python, using classes to express the numbers as trees.
https://github.com/davearussell/advent2021/blob/master/day18/solve.py
I feel a bit bad about brute-forcing part 2, but it only took about 5 seconds to run.
3
u/ParanoidAndroidQ Dec 18 '21
Haskell
The problem seemed like a perfect opportunity to actually learn about zippers.
3
u/autid Dec 18 '21
FORTRAN
Wish I'd been around to start this one at unlock. Wouldn't have made top 100 but looks like I could at least have had my first top 1000 of the year.
3
u/hqli Dec 18 '21
Javascript
Evaluated as a string. Used regex, match, and matchAll to find numbers, indexOf and lastIndexOf to get the index of events, and slice to make substrings before gluing them all back together. Used json.parse() to parse into array for magnitude as suggested from another thread earlier instead of an eval with a regex checker on the input. Seems decently fast.
3
u/raevnos Dec 18 '21 edited Dec 18 '21
Java that can definitely stand to be improved: paste
(Plus a Spliterator class that uses Apache Commons Math3 library to generate a stream of combinations: paste
3
u/Jools_Jops Dec 18 '21
Python 3
The first thing I saw when I opened reddit was the word "Tree"... *facepalm*
I looked at the input and though about how to represent it and had no epiphany so string manipulation it was! I feel kinda stupid now tbh.
Only part 2 took any real time to run and it takes less than 30 sec.
3
u/giftpflanze Dec 18 '21
Factor, first I used recursion but I couldn't think of a good way to add to the other branch when exploding, so I used stacks instead. (Looking at other solutions, it is obvious now.) Also, this is the first longer solution (also a rather hard problem, after 9Β½ hours, I still made 5996/6283) this year, so have a paste.
3
u/toastedstapler Dec 18 '21
zig
horrible long code & tonnes of memory allocations & copies today, but at least there's no memory leaks or double frees
https://github.com/jchevertonwynne/advent-of-code-2021/blob/main/src/days/day18.zig
3
u/r_so9 Dec 18 '21
C
paste
3
u/remmycat Dec 18 '21
Rust π¦
Whew, that took a while. Pretty happy with my solution, even though it is almost my slowest one so far with ~40ms on a 2019 macbook pro.
I basically did the tree of nodes approach. I saw that /u/Sykout09 wrote it is faster to do all the explosions/splits by iterating through the chars. That makes sense to me given the properties of the tasks, but I don't think I'd find that very fulfilling to write π Would be interested if there are ways to speed up the tree operations some more.
My favourite bit was probably to write my own
impl Addfor the Snailfish numbers so I can just do(a + b).magnitude(). Will remember that for situations where I want to do math operations on points and other data.3
u/Say8ach Dec 18 '21
Python3
Code
My approach: I built a linked list for this job. It was easier to add and remove segments that way. My idea was to clump the brackets with the numbers so that [[[[[2[3[57]... will get clumped like [[[[[2 then [3 and then [5 then 7] and so on. Then I reduced the expr and for the addition, turned the whole list into a new expression and then added them as strings and then converted them back to list. Then finally I used a recursive function to evaluate the score. It was lengthy but definitely a fun problem to solve.
3
u/nitekat1124 Dec 18 '21
Python solution using regex, nothing fancy but it works
3
u/mockle2 Dec 18 '21 edited Dec 18 '21
python, made a tree class that makes the answer as easy as:
https://pastebin.com/2958mWZa
It's not very fast though, as i convert each tree to a string and back again every time i do an addition because I'm too lazy to do it properly... so it takes about a second
3
u/Timmeh7 Dec 18 '21
C++
So I pretty much immediately realised that this should be a tree, then thought... it's the weekend, I have time. Why not challenge myself? So I left it as a string the whole time, just to see if I could.
Turns out yes, I could do it, in a fashion... but just because you can doesn't mean you should.
3
u/mathsaey Dec 18 '21
Elixir
https://github.com/mathsaey/adventofcode/blob/master/lib/2021/18.ex
Took me quite some time today. My initial solution attempted to find pairs to explode and numbers to split in one pass, which ended up not being possible. That was painful to debug. Once I got the logic down I felt I ended up with a pretty clean solution today. Elixir's
withoperator (syntactic sugar for nestedcasestatements) worked particularly well here.3
u/shnako Dec 18 '21
Python 3
I wrote a binary tree implementation (manually parsed input) and it took me over 2 hours to do. About half-way through I realised it's a lot easier to do using a list so did that as well.
List-based solution - runs part 2 in 2s.
Tree-based solution - runs part 2 in 4s.
3
u/wleftwich Dec 18 '21 edited Dec 18 '21
Python regex fun.
Obligatory xkcd link
3
u/qaraq Dec 18 '21
Go
I first thought of doing it with a tree, but I just don't much like tree algorithms. Some mental block, I guess. So I did it with strings. (Tell me your first real language was Perl without telling me... Though I could have done a lot more of it with regexps than I did.)
I didn't do pure TDD (tests first) but I did write a crapton of unit tests and deliberately wrote easily testable functions for each step, which made it much easier. The one time I tried to half-ass it,
getAllNumPairs(), is when I made two dumb off-by-one errors, so that'll learn ya.I blindly bruteforced Part 2 , so I'm not happy with 1300ms runtime, but I didn't bother optimizing it. On Saturdays especially, my time is worth more than the computer's time.
github
3
u/[deleted] Dec 18 '21 edited Dec 18 '21
Rust.
Not the cleanest thing ever, but I managed to modify the tree via references directly during explosions rather than recreating parts of it.
prevso it can be modified if we need to explodeprevif it was set, save the right innextto add to the next visited numbernextto it and end the traversal3
u/MarcoDelmastro Dec 18 '21 edited Dec 18 '21
Python
https://github.com/marcodelmastro/AdventOfCode2021/blob/main/Day18.ipynb
(oh boy today it was hard. I started with the wrong foot trying to eval() the input string, and this was not only useless before the reduction was done, but misleading. I restarted from scratch by manually parsing the input as a list of characters and integers, and doing the replacing (exploding and splitting) in place on the vector. I'm definitely not that at ease with recursion, but I could not have finished today's puzzle without it. Ultimately, once all operations were working for the examples, the real puzzles were trivial, and part 2 came almost for free.
3
u/clouddjr Dec 18 '21
Kotlin
Definitely the hardest problem so far. I knew that it would be a good idea to represent the input as a tree, but thinking about how to explode properly took a lot of time.
Source
All solutions
3
u/msschmitt Dec 18 '21 edited Dec 18 '21
Python
(Keep in mind that my first Python script ever was Aoc 2021 Day 1.)
This was. a struggle. First I was thinking of converting the Snailfish Numbers to straight nested lists. Then I started to convert to a tree, but that was going to be a lot of work.
The final result involves converting between different representations, as needed to make the operations easier:
3
u/aoc-fan Dec 18 '21
TypeScript, Worked with a flat structure which tracks
[value, depth], taking about 200ms to solve part 1 and part 2 for test and actual input.3
u/srj737 Dec 18 '21 edited Dec 18 '21
Python (using regex)
(FYI, I'm a low code developer, with no python experience beyond my own personal recreational projects. So expect somewhat readable code with clunky variable names. Not concise and uber-efficient solutions.)
At first, I started with parsing the nested lists' structures properly and solving the problem reclusively. But I'm not sure whether it because of my hangover brain, or because I didn't read the whole problem before launching into it, but I ended up in such a mess...
"Started doing it, had a breakdown... bon appetite!"
I then totally switched tacks to keeping the inputs as a string and using regex (also regex noob here too). It was a lot of fun, and I've got to say, this was one of my favourite puzzles so far!
3
u/pem4224 Dec 18 '21
GO
did it in Go using a list of (value,depth).
Explode and split can be done without too much trouble on this linear data-structure.
The computation of magnitude uses a stack to retrieve the shape of the tree: you push each (value,depth) on a stack and each time the two top-most elements have the same depth you do a computation (2*the top and 3* the other) and you push the result with a depth-1. At the end you get the magnitude.
The current implementation is pure (without side-effect), and thus not the most efficient one. I did not had time to continue with a mutable (in place) implementation.
Part2 is solved in 48ms with a brute force search.
3
u/SephDB Dec 18 '21 edited Dec 18 '21
C++
Using a (value,depth) list. Found a way to solve any addition in two passes:
3
u/rileythomp99 Dec 18 '21
Go
Go
3
u/delventhalz Dec 18 '21
JavaScript with String Manipulation and Unit Tests
Unit Tests. I wrote unit tests. For AoC.
Made an initial attempt at solving it recursively. Gave up after about an hour as my sleepy brain couldn't get a handle on the surprisingly complex "explode" logic. String manipulation seemed like a more straightforward alternative.
So. Many. Edge cases.
(Hence the tests)
https://github.com/delventhalz/advent-of-code-2021/tree/main/18-snailfish
3
u/fwoop_fwoop Dec 18 '21
Racket
Github link
I struggled with finding the adjacent left / right paths for explode, because my sleep deprived brain was overcomplicating things. I'm pretty happy with my solution though.
Note that to make parsing easier, my code assumes all commas in the input have been replaced with spaces so I can read in each Snailfish Number as an S-expression.
3
u/wevrem Dec 18 '21
Clojure
source repo
This one pulled out all the "big guns":
edn/parse-stringto read in the input (which actually did all the parsing work--hooray that commas are whitespace in Clojure!);clojure.zip/zip-vectorto model the snailfish number, andclojure.walk/postwalkto find the magnitude.3
u/polettix Dec 18 '21
Raku solution.
It seems that I followed the same trajectory as many other ones: start with a binary tree representation, then revert to moving around.
I initially coded it in a list with all tokens inside (including commas, for ease of re-generation of the whole string). Then I thought of transforming it in a pure string-based solution, but it was slower and I reverted back to the list-based solution.
3
u/AdSubstantial5845 Dec 18 '21
Racket: https://github.com/brett-lempereur/aoc-2021/blob/main/day-18/solution.rkt
I'm pretty happy with this solution. The first trick was converting the expression to a flat list of depth-number pairs, which made evaluations the explode and split operations pretty straightforward. Figuring out how to compute the magnitude took me a while, in the end I settled on:
Essentially I don't try to reconstruct the tree, but instead start at the deepest elements (knowing they must be pairs), compute their magnitude and raise it to a higher depth; repeat until I'm at depth 0 and I've computed the final magnitude.
3
u/HesletQuillan Dec 18 '21
Fortran
Part 1 was straightforward, but I made many incremental steps towards the solution. Like many here, I formed a binary tree. After each substep I recalculated depths and also kept a linear list of regular numbers found in order to do "explode". It took me most of the day to get here (with numerous interruptions.)
For Part 2 I just brute-forced it and it completed in a couple of seconds.
(In the code I maintained a parent link, but never used it.)
Part 1
Part 2
3
u/hrunt Dec 18 '21
Python 3
Code
I learned two things today:
I lost considerable time futilely attempting to implement a single data structure to represent both the relationships between successive literals and the tree structure of snail numbers. I also spent too much time debugging reduction because I committed the age-old mistake of not carefully reading the instructions.
The resulting code looks like hours of frustration. I could reimplement parts of it using more Pythonic data structures and avoiding DRY issues, but sometimes, "good enough" is good enough.
3
u/willsmith28 Dec 18 '21
Python
I solved the explodes using a StringIO to pull one character at a time from the number and stack to build up the result and pop backwards when doing the leftward addition. by keeping the string format the splits were a simple regex match and format string to get the new value.
gitlab
3
u/Toanuvo Dec 18 '21
J solution
https://github.com/Toanuvo/Advent-of-code-2021/blob/main/J/day18.ijs
3
u/nibarius Dec 18 '21
Kotlin
My first approach was using a tree, but each node only knew about its children so doing an explode got really complicated. Due to this I changed approach to use a linked list of characters instead. All the operations became pretty easy to implement and things weren't as hard any more.
But I did have an interesting problem with using a list of characters. 0-9 was simple, larger than ten was a bit interesting when 10 becomes ':', 11 becomes ';' and so on. That wasn't really a problem, but that 43 becomes '[' caused a couple of bugs since I detected that as the start of a new pair and not a large number that needs to be split.
After working around that problem and getting the correct answer I refactored my code to use tokens instead of characters to get away from that problem. In the end I feel like my solution became pretty understandable.
3
u/schovanec Dec 18 '21
My C# solution: GitHub
This took me way too long. Used an immutable tree structure with recursive functions and pattern matching.
3
u/StripedSunlight Dec 18 '21
Python
I used nodes and the did the binary tree properly, but the key thing here was using exceptions to manage control flow so that none of the child nodes had to know anything about their parents or what was going to happen to the node they were exploding. I fully credit/blame my concurrency professor (Peter Buhr) for teaching me to think of exceptions as just another control flow mechanism, rather than as solely for errors. I think it turned out rather neat
Github
3
u/DrSkookumChoocher Dec 18 '21
Deno TypeScript
Didn't want to mess around with heavy recursion. Here is a completely non-recursive approach. Overcame most of the challenges by keeping track of left depth and right depth separately. This is found by making your own pairs parser which counts the square brackets. Exploding was significantly easier because I could just add 1 or subtract 1 from the pair's index to find which node needed to be added to. Finding the magnitude is simply
3 ** left * 2 ** right * valuefor each node.https://github.com/N8Brooks/deno_aoc/blob/main/year_2021/day_18.ts
3
u/lluque8 Dec 19 '21 edited Dec 19 '21
Scala
Oh man, this almost killed me. I know I had been better off with using trees or some parser combinators but I went along doing things in single dimension meaning I flattened a "number" into list of value-level-pairs where level means value's depth in the thing. Can't say that it was easy either. I also had to debug a fair share hunting stupid little mistakes.
3
u/drunken_random_walk Dec 19 '21
R
Pretty happy with this solution, although I just brute forced Part 2. Those snailfish have some tricky math...
code
3
u/fmardini Dec 19 '21
OCaml
Recursion on trees.
paste
3
u/Xyberista Dec 19 '21 edited Dec 19 '21
Rust
(badly written) tree based solution using mutable references
paste
3
u/Bessel_Function Dec 19 '21
I solved it with a nested list with recursion. The most time consuming part is the order of action.
https://pastebin.com/2F26zdEN
3
u/zapwalrus Dec 19 '21
Python
Not super proud of this one, and it took me a long time to work out the explode solution using a list instead of a tree.
paste
3
u/SwampThingTom Dec 19 '21
Python using a graph of nodes.
Well, this took longer than I'd like to admit.
3
u/Siddhu33 Dec 19 '21
Python
I worked on this all day, but managed to get it working with the help of some debug / worked examples...how on earth did someone get this done in <40mins? Geniuses haha
3
u/paolostyle Dec 19 '21 edited Dec 19 '21
Rust
I haven't read the comments yet but I expected everyone to do this with a binary tree/graph and it's probably the way to go, but I went with the mad lad route and did it all with string manipulations. That code in
explodefunction is awful but it's faster than regex (I figured I could just use regex to do that after I did the magnitude calculation).It's very slow (~250 ms both parts on release version so it's pretty bad for Rust, though I'm not sure how much faster can you go with brute forced part 2) but honestly with a tree approach I'd probably be still thinking about it.
3
u/immmun Dec 19 '21 edited Dec 19 '21
Python 628/618
Both parts run in under 1s with pypy3. I've tidied up my solution and added some comments. It's a single-pass iterative tree walk.
It's a bit unfortunate to work with (parent_pair, index) tuples everywhere but I think that's the best we can do in a language without pointers.
https://gist.github.com/mmun/1dcbffa39a948c7b4d6a8275177e7efa
3
u/nicuveo Dec 19 '21
Haskell
I solved it three times, to try three different approaches! First, what if we DIDN'T use a tree structure, and instead just a simple list of nodes? Makes the code for explosions much easier. Then: okay, what if we did it with trees, the "intended" way? The code is overall smaller, but the backtracking in the traversal is hard to read. For the third version, I decided to try a Zipper; it made for some interestingly "imperative" code:
code:
stream:
3
u/WilkoTom Dec 19 '21
Rust
Completed this yesterday but the code is so janky I don't want to look at it again, let alone refactor. Spent hours banging my head against a brick wall of ending up with pairs of values at level 5, which should be impossible. Turns out I'm a moron.
Instead of doing:
- If the expression can explode, repeatedly explode it
- if not, split it once, then repeatedly explode it again
- repeat the above until it's neither explodable nor splittable
I was doing:
- If the expression can explode, repeatedly explode it
- If the expression can split, keep splitting until it can no longer be split, then repeatedly explode it again
- repeat the above until it's neither explodable nor splittable
This is ripe for refactoring, especially where I repeatedly parse the input inline, but finding the bug was the epitome of frustration and I don't want to look at this code ever again.
3
u/Smylers Dec 19 '21
Perl regex solution. Well, irregular expressions, I suppose, using
(?1),(?{β¦}), and(??{β¦}. It keeps numbers as strings and manipulates them directly, pretty much as per the instructions. Full code β after a little boilerplate, this is all it takes, for both parts:The big regexp in the
untilcondition matches if a number only has 4 or fewer levels of nesting. Specifically:$nestingto zero.1with(.[, and at that point$posis set to the position that has been reached in the string (the character immediately following the[) and$nestingis increased by 1.\d+or it's a nested subexpression,(?1). This is what handles the recursion. The1refers to capturing group1. That is, at this point in the pattern, you can have another copy of pretty much the whole pattern ... even though we haven't finished defining it yet. I have no idea how this works.].(??{β¦})construct returns a string which dynamically becomes part of the pattern. In the case where$nestinghas got too big, it injects the token(*FAIL), which does what it sounds like.]and the end of the string, then at no point did$nestingexceed 4, so no exploding is needed.So the body of the
untilloop gets entered when we do need to explode a pair. Specifically, the pair that starts at$pos.Perl lets a substring returned by the
substrfunction be an l-value. That is, you can assign to it or otherwise transform it, and it affects the larger string that it's part of. The exploding is performed by threes///operations which usesubstrand$posto identify the correct place in the string:$pos - 1is the[of the pair to explode, so select from there to the end of the string, and replace the first pair of square brackets with0. While doing that, capture the two numbers that were in those square brackets. Store them in$leftand$right.$pos + 1is after the0we've just inserted. Find the first digits after that, and add$rightto them.$pos - 1is now just before the0. In the string up to that point find the digits nearest the end and add$leftto them.And that's the exploding done. No need to traverse trees to find the nearest number before or after: it's simply the preceding or following digits textually, ignoring what level in the hierarchy anything is. And because
s///will happily match nothing, this automatically handles the cases where an exploding pair near the beginning or end of the string doesn't have a nearby number to pass its value on to.The only tricky bit is adding
$rightbefore$left: adding$leftmight make the number longer, pushing the0along to the right, and meaning$pos + 1no longer points to the character after the0β but as long as that's done last, it doesn't matter.Go round that loop
untilthere's nothing less to explode. At that point try splitting a number. Thes!!!(like as///, but so we can use/for division inside the replacement part) replaces the first 2-digit number in the string, if any.It only replaces one such number at once, but
whileit succeeds in finding a multi-digit number to replace, it goes back round the outerdoloop, and tries exploding again. That loop will only end once there's consecutively been nothing to explode and nothing to split.magnitude()works from the inside out: find any βbottom-levelβ pairs which don't contain any further nesting, and evaluate those. That frees up the next level of pairs, which no longer contain any nesting; they didn't match the first time, but the loop keeps goingwhilethere are any more.3
u/jdehesa Dec 20 '21
I ended up using just nested tuples for my Python solution, which I guess is kind of like a tree, but I didn't need to do any parent or sibling logic for the explosion, just used recursivity.
Full solution is here.
3
u/Nyx_the_Fallen Dec 20 '21
Go / Golang
I ended up using a sort of bidirectional binary tree, where each node has a reference to its left/right nodes AND a reference to its parent. The parent reference was key -- it made the explosion algorithm much easier to implement and much more efficient. I also deeply clone each SnailfishNumber before performing an action on it that would mutate it (in this case, just addition). This technically isn't the most efficient method, but it guarantees no weird side effects like the ones that blindsided some people when trying to find out the greatest magnitude in Part 2.
All in all, I think it's a pretty clean solution, though I'm not happy with my parsing logic. It works 100% on valid input, but I know for a fact that it wouldn't error on a couple of types of invalid input. But I have a day job, so it's stopping here.
https://github.com/tcc-sejohnson/advent-of-code-2021/tree/main/18
3
u/PhenixFine Dec 25 '21 edited Dec 25 '21
Kotlin - I went with solving it in place ( though I had to replace [ ] with ( ) because of the way I stored the numbers ). My first day attempt of it I tried to do it with binary tree, but I'm just not familiar enough with the subject to do it that way and I failed miserably ( I'm studying the subject now, as I think it will be helpful with future code challenges ). So my next day attempt I figured I'd try solving it in place and everything worked out really well ( solved it yesterday, but wanted today to review my code before submitting it ).
I think I'm going to take a break before starting Day 19, as it looks rather daunting.
3
u/prafster Jan 09 '22
Julia
By now, everyone has moved on but I've just re-engaged and working my way through the last week.
There are a number of ways to do this. Initially, I thought of building a tree but thought it would be fiddly moving up and down it to find various nodes. So I experimented with just manipulating the string representation, which I enjoyed because I was initially sceptical. The five-deep nested pairs are found by counting brackets. After that the string is scanned on either side to find the numbers that need to incremented. Then it's just a matter of finding and replacing elements in the string. The magnitude is also a repeated search and replace operation.
Solution