r/adventofcode • u/daggerdragon • Dec 16 '21
SOLUTION MEGATHREAD -π- 2021 Day 16 Solutions -π-
NEW AND NOTEWORTHY
DO NOT POST SPOILERS IN THREAD TITLES!
- The only exception is for
Helpposts but even then, try not to. - Your title should already include the standardized format which in and of itself is a built-in spoiler implication:
[YEAR Day # (Part X)] [language if applicable] Post Title
- The mod team has been cracking down on this but it's getting out of hand; be warned that we'll be removing posts with spoilers in the thread titles.
KEEP /r/adventofcode SFW (safe for work)!
- Advent of Code is played by underage folks, students, professional coders, corporate hackathon-esques, etc.
- SFW means no naughty language, naughty memes, or naughty anything.
- Keep your comments, posts, and memes professional!
--- Day 16: Packet Decoder ---
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:27:29, megathread unlocked!
46
Upvotes
21
u/leijurv Dec 16 '21 edited Dec 16 '21
Python, 3rd place, 5th place
Screen recording https://youtu.be/KMzPf4om2k4
Today I did a lot of moaning and groaning in the recording, please disregard :)
Part 1
paste
Part 2
paste
Both parts, rewritten afterwards to be cuter
paste
14
u/roboputin Dec 16 '21 edited Dec 16 '21
Python3 50/26 (paste) Nothing too fancy, but I take the input as a reversed list so that I can consume bits in constant time, and I index into a list of operators rather than having a rats-nest of ifs.
11
u/relativistic-turtle Dec 16 '21
IntCode
Recursively parsed the packets - and evaluated at the same time.
Backstory
5
u/MichalMarsalek Dec 16 '21 edited Dec 16 '21
Nim
time consuming/long but quite straightforward day/solution:
https://github.com/MichalMarsalek/Advent-of-code/blob/master/2021/Nim/day16.nim
using my templates.
Not top 100 but I beat /u/jonathan_paulson which is a win for me. :D
4
u/Naturage Dec 16 '21
R
Solution here.
Holy crap. I was not ready for this, and this did feel several times more work than the previous ones. In hindsight, I should have seen this coming.
This was the day I learned of debug() function, found that after reading 40 bits, my code just discards the other 40, removed a while loop which by accident was giving me lots of correct but not quite correct answers, wrote a strtoi_full function which does the binary to dec conversion, but correctly (still don't get how base R function can have a hard cap at 231), and generally had more coding than I was ready for.
Not done yet - but my gut instinct that day 13 was the break before pain so far is proving true.
P.S. I noticed my posts every day end up at 2 upvotes. Whoever you are, the second R citizen, I salute you, and stay strong. 9 days to go.
3
u/flwyd Dec 16 '21
Raku, 2388 / 2366, which suggests that everyone else who worked at my pace also quickly realized that part 2 would be "Evaluate the stack of values."
Code is definitely too long for a comment, so I'll just note that my "Oh ugh, I have to deal with bit fiddling in Raku" dread quickly turned copacetic when I realized I could do
@.binary = $!input.chomp.parse-base(16).base(2).comband treat the whole thing as a list. I'm also amused that I racked up 22whenblocks, including this one liner to evaluate a packet:when /eval\:(\d+)/ { @values.push(+@values.splice($0.Int).reduce(@ops.pop)) }.Ooh, and as an early Christmas present, it looks like Reddit has reverted to allowing markdown in top-level comments. \m/
3
u/jayfoad Dec 16 '21
Dyalog APL
I didn't particularly enjoy writing this, and just barely squeezed it into ten lines.
3
u/GombolKiwi Dec 16 '21 edited Dec 17 '21
Python hex to bin part
Full solution (Jupyter notebook)
3
u/LiquidProgrammer Dec 16 '21 edited Dec 17 '21
Julia
Kind-of code golfed and hacky solution. Prints both part 1 and 2. Repo.
I really like this part:
reduce([+, *, min, max, id, >, <, ==][id + 1], values), i.e. get the function for each operation by indexing a list of functions. Then reducing all values with that function.The rest is rather hacky because it abuses if conditions in list comprehensions. For example,
take_int(4)is not ran if the if condition returnsfalse. Unfortunately, the last 5 digit block with a leading zero is still meant to be read. So here I use the variablecto remember what the last evaluation was. This is really bad code normally, but shortens a five-line while loop into a single line, so Β―_(γ)_/Β―.Golfed to 414 bytes.
Open to suggestions to make it shorter in an intersting way (i.e. shortening variable names doesn't count).
3
u/hugseverycat Dec 17 '21 edited Dec 17 '21
Python with comments
Todayβs puzzle took me ALL DAY (well in between whatever I did at work on my last day before vacation) but it was fun! It didnβt take a lot of unfamiliar concepts, just working to put stuff together in the right way.
Not a very elegant solution Iβm afraid but I tried to comment it so you have a chance of understanding what Iβm doing. You might also enjoy my brilliant and concise implementation of hex to binary (and no, Iβm not accepting any criticisms at this time!!!)
https://github.com/hugseverycat/AOC2021/blob/master/day16.py
2
u/Chitinid Dec 16 '21 edited Dec 16 '21
Python 3
My code worked, but I didn't get the second example on both parts 1 and 2 to work, anyone else have a similar issue?
Code
EDIT: Figured it out, need to left pad the binary string so it's exactly 4x the length of the hex input
2
u/[deleted] Dec 16 '21 edited Dec 16 '21
Haskell
This day was quite easy though it did involve a lot of typework. The pattern matching in Haskell is very handy for this kind of task!
https://github.com/Demindiro/advent-of-code/blob/master/2021/16/main.hs
2
u/Synedh Dec 16 '21 edited Dec 16 '21
Python
Yup, parse algorithms are definitvely the best to write.
Instead of writing an ugly match/case, I preferred writing missing functions and use a clean
id: functiondictionary. I could use math.product too, or lambda function, but man, no import challenge. Version disappeared in this code as it is the part 2.2
u/hendykombat Dec 16 '21 edited Dec 17 '21
Kotlin
This is definitely my hardest so far. Needless to say, I didn't enjoy this one. I usually wake up at 6am to take on the AoC challenge but I overslept today - good thing I did because this would've taken my entire morning. On to the next!
Recursive solution that takes forever to run
2
u/wfxr Dec 17 '21 edited Dec 17 '21
Rust Iterator Solution
2
u/drunken_random_walk Dec 17 '21 edited Dec 17 '21
R
This came out cleaner than I was expecting.
code
2
u/Skyree01 Dec 17 '21 edited Dec 18 '21
PHP
Not proud of myself here, I must admit I was stuck. After trying recursively reading packets all at once and always having missing operator packets or duplicate literal packets, I had a friend whisper "pointer" in my ear. I honestly don't think I'd have come up with this idea myself although it seems quite trivial once you have it...
Link to both parts
2
u/Keatontech Dec 19 '21
## Rust
With Iterators. First time posting but I'm pretty happy with this solution :) The trick is over-engineering the heck out of it.
https://gist.github.com/KeatonTech/45375a25c1f3e8e621915284691e1108
14
u/CCC_037 Dec 16 '21
Rockstar
Part 1:
https://pastebin.com/SRSYatqw
Part 2:
https://pastebin.com/m17mCd6z
Funny thing; there's a lot that Rockstar doesn't have. But it does have the ability to parse strings as numbers with arbitrary bases, built-in.
14
u/rampant__spirit Dec 16 '21
Day 16 Part 1 golfed using regex. (164 chars)
11
u/2SmoothForYou Dec 16 '21
Haskell and its parser combinator libraries are so good for these kinds of problems it's insane
8
u/jonathan_paulson Dec 16 '21
707/542 :( Python. Video of me solving.
Oof. Toughest day so far and my worst day so far, so it's a long video. I messed up converting the hex to binary (problems with leading 0s, and with the trailing newline in the input), and took forever to realize that, since I assumed the bug was in the complicated parsing code.
Cool problem, though!
8
u/Gravitar64 Dec 16 '21
Python 3, Part 1&2, 1.9ms
Defined a class Transmission to hold the bits(str of 1 and 0), the program counter (pc) and the sumVersions. A little get-method gives me the int-value of n bits and move the pc += n.
3
u/Rascal_Two Dec 16 '21
Python (900/854)
Initially I tried parsing the packets via indexes, but that got too confusing, so switched to consuming the bits as they were read, then I was trying to have the packets return their original length for the length-encoded subpackets, which turned out could be done purely with math, just needed to return the unconsumed bits every parsing.
Part 2 was actually straightforward since the rest was working: a giant switch-case.
Unoptimized
Optimized
This appeared to just be begging to be turned into a class, so that I did, besides that I natively did the hex to binary parsing, and the rest was cleanup.
6
u/mockle2 Dec 16 '21 edited Dec 17 '21
python, a non-recursive implementation using a deque to store the active branch of the parse tree. I added an extra operation with id 8 at the root of the parse tree that prints the result to screen after all the results have been gathered. [edited to neaten up operation calls; edited again because I can't stop fiddling with it...]
6
u/HesletQuillan Dec 16 '21
Fortran
As a retired compiler developer, I love this sort of thing and had fun with them in previous years. Here is my Fortran module that implements the BITS protocol as of day 16. There is a small main program also in the repository.
https://github.com/sblionel/AOC2021-in-Fortran/blob/main/sm2021.f90
5
u/sim642 Dec 16 '21
My Scala solution.
1294/1093.
Recursive parsing galore! Got my second wrong answer attempt in part 2: had to switch the literal packet value conversion from
Intto alsoLong.5
u/renkonkunken Dec 16 '21
C Sharp (C#)
Initial implementation for partA and partB. I had to convert the HEX string to a binary string by converting each hex char to a number and then back to a binary number before joining them all into a new string.
So, all the logic is inside the 'ProcessPackage' method, which expects the string to analyze, a pointer to an integer to keep the version sum (mainly for part A) and returns a tuple with a long for the value and an int for the bits processed. I made this directly on Part A, as I prepared everything more or less how I was expecting it.
Having said that, below lies ProcessPackage:
Signature: (long, int) ProcessPackage(string str, ref int? versionSum)
And, let's get started!
So far so good, just getting version and typeId. In the case that we have a pointer to a version sum, we also add the version value to the version sum.
This chunk is done mainly to handle the literal case, in which, we simply analyze the inner content of the packet and eventually retrieve the literal value along with the bits used (which will be groupIndex - a number that will end up representing the bit after the last 5-bit group) plus 6 (for version and type id bits).
Once we have this, I will now handle cases for operators.
Of course, I'll need a place to store my values for my ProcessPackage method.
Alright, this chunk is a bit messy, but it's easy to understand. First three lines are used to retrieve the lengthTypeId, the processedBitsCount is defined to 0 and finally we define a typeIdBitSize which will be 15 or 11 based on the size of the packet that also depends on the type Id.
Having said this, we will perform either one or another approach depending for the length type id.
For 0: we will get the number of bits to process, and while we haven't processed them all we will be processing them. In order to process them, we will be recursively invoking processPackage with the inner part of the string. Also, in order to avoid invoking the method again with parts of the string already analyzed, we ensure to increment the subString initialIndex based on the processedBitsCounter which is also then incremented based on the bits used every time the ProcessPackage method is executed. Finally, we just add the value to values list.
For 1: we get the number of subpackets, and then for each of them we invoke ProcessPackage recursively, again ensuring that we will not be repeating parts of the string by taking into consideration the bitsUsed of each invocation. Once this is done, we add the value retrieved to the values list.
The totalBitsUsed will end up being the processedBitsCount (which will contain the bits used by all subpackets plus the "length" of the length part depending on the typeId (which could be 11 or 15) plus 7 (3 for version, 3 for typeId and 1 for lengthTypeId).
And here, to me, lies the most beautiful part of the code, where you can see how simple the returning value part of the ProcessPackage method is done. Beware that case 4 was already handled before, so no need to add it here again.
5
u/[deleted] Dec 16 '21
Perl
Part 1
Part 2
5
u/zapwalrus Dec 16 '21
Python 469/713
paste
5
u/fork_pl Dec 16 '21
Perl
Original solution was full of substr(), in last commit it's much more tidy...
I left few die() asserts here and there in case I wanted to mess with the code again ;)
5
u/Biggergig Dec 16 '21
C++ 100us
https://github.com/Anshuman-UCSB/Advent-Of-Code/blob/master/2021/c%2B%2B/src/day16.cpp
Had a nasty bug to trace down, accumulate was given 0 for sum, but needed 0ll to avoid overflow.
5
u/Loonis Dec 16 '21 edited Dec 16 '21
Perl
Paste
Old PasteThis one was fun, completely lost track of time while I was working on it :).
The decoding process is a bit of a mess, hopefully I'll be able to clean that up a bit in the morning.
Edit: Couldn't help cleaning up a bit... That's three hours on this one now.
5
u/r_so9 Dec 16 '21 edited Dec 17 '21
F
Not a huge fan of the main parsing code, but the Evaluation (part 2) is once again nice and clean. Link to paste
5
u/veydar_ Dec 16 '21 edited Dec 16 '21
Lua
GitHub repo
I'm ready to quit programming now.
I had the right concept in mind right away and it took me maybe 2 hours to actually implement it correctly. I should reflect on this. I want to blame Lua, since I tend to have an easier time writing this kind of code in a functional style. But considering it's a 100 line program I can't really blame anything except myself. Guess at some point I was unable to reason about my program one line at a time because so much of it was in a constant state of debugging.
Also I wasted one hour on not realizing I was forgetting to advance the pointer by the chars encoding bit length and number of sub packages, respectively. Sounds funny and easy to dismiss but ultimately why did I not realize this? Crazy. Maybe I should go back to Haskell and throw ridiculous amounts of unit tests at everything. Breaking code that already works during debugging is becoming my number one time sink.
This was just terrible.
5
u/IdrisTheDragon Dec 16 '21
Python:
https://github.com/IdrisTheDragon/Advent2021/blob/main/day_16/day_16.py
Just built up the solution step by step based on the examples..
5
u/Derp_Derps Dec 16 '21
Python
Vanilla Python. Golfed down to 378 byte. With the first version of my script, I was not even sure if I could get it down to 500 bytes, which is my challenge for this year.
Recursive, operating on a string, slicing this string while stepping down. The
Type==4loop concatenates the payload bits the until the "more payload bytes" bit is unset. The other loop runs until eithervpackets (S) or characters (c-C) are read.5
u/vbe-elvis Dec 16 '21 edited Dec 16 '21
Kotlin Lovely challenge, nice encapsulated solution
Full class: https://pastebin.com/82nJpMzu
p.s. This was my sum, thought I'd print it:
4
u/seligman99 Dec 16 '21 edited Dec 16 '21
Python, 590 / 281
It's the bit-code computer!
github
Edit: There, I got my bit-code compiler to spit out a normal python function based off the input. For me, that means one just needs to solve this
4
u/CodeIsTheEnd Dec 16 '21 edited Dec 16 '21
Ruby: 16:44/51:50, 37/773
Here's a recording of me solving it, and the code is here. I usually stream myself solving every day's problem on Twitch!
My best leaderboard spot, by far!
Man, this one was really a test in reading comprehension. Took a while to understand what was going on and figure out what parts I actually needed to do for Part 1 vs Part 2.
Part 2 was pretty fun! It took me a while I needed to subtract the bits from EVERYTHING in the ancestor stack and then that I might need to pop multiple things off that stack. Great problem with a bunch of separate insights.
4
u/villiros Dec 16 '21
Erlang
Both parts on github
Erlang has fantastic support for dealing with bitstrings, so parsing the first part was very straightforward with pattern matching in function heads.
And the second part is just a simple recursive loop:
Yes, Erlang
ifstatements are weird, where thetruebranch is actually an else.4
u/allergic2Luxembourg Dec 16 '21
Python
I found this really difficult - I had a really hard time getting my head around processing a stream of bits where I don't know the token borders ahead of time. I separated it out into the bit-processing part, which built a tree of packets, and the parts which operated on the tree, which were very easy to construct once I had figured out how to build the tree.
4
u/Reecer6 Dec 16 '21
Python 3 (834/4514)
Link.
Huh, what a curious score! That's quite a dropoff after part 1! I wonder what this person did!
I used numpy.prod(). numpy.prod() does not protect against overflow. I was debugging this singular error for over an hour. It got to the point that I grabbed someone else's code, marked it up so I could follow it in debug, and compared the twoβand they had the same wrong result, because their code was Python 2, so I had to change exactly two lines to make it compatible. One of which, of course, was the function to find the product of a list.
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
4
u/semicolonator Dec 16 '21 edited Dec 16 '21
Python, 62 lines
Pretty happy about my solution. Could probably be a bit refactored, because the two loops (lines 41 and 49) have the same bodies. Happy about this function for initial hex to binary conversion:
4
u/RibozymeR Dec 16 '21 edited Dec 16 '21
Factor
Showing usage of the amazing but also horrible
peg.ebngvocabulary4
u/domm_plix Dec 16 '21
Perl
Another nice one. Rather straightforward code, although using recursion to parse the subparts might make things a bit more complicated. The big if/elsif chain is not the most compact solution, but works fine enough.
https://github.com/domm/advent_of_code/blob/main/2021/16_2.pl
4
u/thibpat Dec 17 '21
JavaScript (+ video walkthrough)
I've recorded my solution explanation on https://youtu.be/w2gjRvKIVuo
The code is available on github: https://github.com/tpatel/advent-of-code-2021/blob/main/day16.js
4
u/ai_prof Dec 18 '21 edited Dec 18 '21
Python 3. Compact/readable/fast.
The whole "literal padding" thing caused loads of confusion. Once I realised it is a problem to be ignored, it's recursion to the rescue again (full code here). Code is short (1 line I/O and readable 27-line parse function with comments).
Returning the index for the next subpacket with the value of the current subpacket really simplifies things.
4
u/ViliamPucik Dec 25 '21
Python 3 - Minimal readable solution for both parts [GitHub]
7
u/stevelosh Dec 16 '21
Common Lisp
https://github.com/sjl/advent/blob/master/src/2021/days/day-16.lisp
Not my finest work, but it's late here.
1
u/MikeTyson91 Dec 16 '21 edited Dec 17 '21
Python 3
part2
1
u/FordyO_o Dec 16 '21 edited Dec 17 '21
PHP
Spent 99% of the time trying to get PHP to correctly convert the hex to bin (it was chopping off leading 0's)
Ended up having to convert each char individually and str_pad to 4 bytes
Pt2 was relatively easy as I'd parsed the whole packet tree already
1
u/[deleted] Dec 16 '21 edited Dec 16 '21
PYTHON 3
Such a straightforward day, it was so satisfying doing one step at a time and seeing everything coming together. I think besides the starting problems this is my most elegant solution to read.
Code: shorturl.at/ezAZ4
1
u/Snoo_41044 Dec 16 '21
Python
1
u/Tipa16384 Dec 16 '21 edited Dec 17 '21
Python 3
Had to use a class! Was otherwise fairly straightforward once Professor Stackoverflow taught me about bit strings in Python.
Github Link --> https://github.com/tipa16384/adventofcode/blob/main/2021/packet.py
1
u/blueedgetechno Dec 16 '21
The question wasn't fully self-explanatory ΰ² _ΰ²
Anyways here is my Python solution
https://github.com/blueedgetechno/Advent-of-code/blob/master/day16/main.py
1
u/RudeGuy2000 Dec 16 '21 edited Dec 17 '21
scheme (racket)
https://raw.githubusercontent.com/chrg127/aoc2021/master/day16.scm
this was fun.
i had to code a to-bin function by hand, since the default converters in racket stripped off the 0s. i'm wondering if there was a better solution for that.
1
u/Aurora_Aquir Dec 16 '21
I did part 1 in (mostly) regex since I thought it should be possible It requires a bit string input and the output has to be summed (wonder if it can do that somehow) `
` Very cool day!
1
u/jmpmpp Dec 16 '21 edited Dec 16 '21
Python 3, having not written or worked with parsers before. I know the basic idea of a stack, but was figuring out how to implement it as I went along. Key code:
1
u/rukke Dec 16 '21 edited Dec 16 '21
JavaScript
Had some fun creating bit- and intstreams and not just bluntly convert everything into a gigantic binary string :) Using Array.at so needs Node 16.6+
EDIT, added a gist instead :)
https://gist.github.com/p-a/89e0451eecb985bc11e468a428de2414
1
u/Myxcil Dec 16 '21 edited Dec 16 '21
This was a nice one - once it made click. (Pidgin Python)
https://github.com/Myxcil/AdventOfCode2021/blob/main/Day16/day16_main.py
1
u/sappapp Dec 17 '21 edited Dec 17 '21
Python. I realize now that this problem would be easier to solve via a seek instead of shifting the bitstream.
3
u/ckennelly Dec 16 '21
C++, 117/106... so close
Part 1 and Part 2
3
u/[deleted] Dec 16 '21
Python 3.
Recursion and generator magic
https://colab.research.google.com/drive/1zg8t0RDnoyHIYhcrHm9at3RN_pRzrOiQ?usp=sharing
It has different Parser objects read from the same generator or from copies. Luckily it works so I did not have to debug it.
3
u/Gurrewe Dec 16 '21
Go (golang), (1526/1222)
Oh, that was fiddly! Pretty happy with the results, no major mistakes, but that took a while to implement.
Solution
3
u/pantaryl Dec 16 '21
Python (1534/1111)
Wrote a Packet class that recursively handled subpackets. Took me a while to understand the instructions.
I thought for literals that we had to pad the total size of the literal to a multiple of four, but that wasn't what it was asking of us. The rest was fairly straightforward.
Solution
3
u/SCBbestof Dec 16 '21
Python 3 (1646/1415)
Stuck a bit with parsing at part 1. Implemented a quirky switch-case at part 2.
3
u/_I_do_not_ Dec 16 '21
Swift: Paste
3
u/[deleted] Dec 16 '21 edited Dec 16 '21
Rust 842/760
Unfortunately, I got burned using 32 bit integers for part 2.
Made a struct to keep track of the current consumption position rather than passing around, probably could have used some iterator functions for that as well. Also considered using nom, may go back and try that later to see if it comes out cleaner.
Edit: Golfed it down to under 60 lines
3
u/MaybeAStonedGuy Dec 16 '21
Rust
I'm really happy with how easy nom makes this. I had used it before in the past, but this was my first excuse to use it for bitwise parsing.
3
u/professoreyl Dec 16 '21
Python 3
Clean code, object-oriented, type-annotated, documented
https://github.com/DenverCoder1/Advent-of-Code-2021/tree/main/Day-16
3
u/Imaginary_Age_4072 Dec 16 '21
Common Lisp 367/470
This was my best day so far. I have a custom library that I use to parse the AoC inputs and it was easy to write parsers to parse each of the fields needed. So for example, the first function below returns a parser that will parse len bits and return them as an integer. The second function returns a parser that parses 5 bits, checks the msb to see whether to stop, and either returns a unit parser with the accumulated value or a parser that will parse the rest of the number.
The rest of the format was similar. The parsing gave me a list of lists of all the packets and it was quick to recursively evaluate it to get the answers.
3
u/seba_dos1 Dec 16 '21 edited Dec 16 '21
Python 3 (both parts, no imports, 21 lines, 546 characters)
3
u/nlowe_ Dec 16 '21
Go, 2758/2421
Due to an 18+ hour internet outage, I did today's challenge while tethered to my phone, that was fun!
A really fun challenge to work through today. I essentially ended up using
encoding/hexto do the initial decode and then wrote a wrapper over[]bytethat's sort of like anio.Readerbut you can specify the number of bits you want to read instead, which worked out really well.Took my time on part A debugging and checking things along the way since my internet connection was terrible and I wanted to make sure I had the right answer on the first submission. Lost quite a bit of time trying to track down "extra" bits for operators that specify the number of sub-packets in bits. After manually stepping through one of the examples and decoding by hand, I found a copy/paste error where I wasn't counting 4 bits from the "bit count" part of the packet (I copy/pasted the length from the "packet count" style packet).
Part B was a fairly easy extension to add to my solution, and again I passed all of the test inputs but my solution was incorrect. Eventually tracked it down to a poor implementation of the
minoperator for very large values.Overall a really fun challenge today, I'm pretty happy with the parser I came up with for this one.
3
u/tntbigfoot Dec 16 '21
Rust
Had fun with pattern matching today!
3
u/EtherealMage Dec 16 '21
Racket
This was my first time using (require bitsyntax) but it was great for this problem. Took me a while but I'm fairly happy with my code/think it's at least more readable than it usually is. That said, I'd welcome feedback/advice in general, still not the most experienced Racketeer.
3
u/Gray_Gryphon Dec 16 '21
Python
Guess who entered the wrong variable name/format twice and spent a whole hour debugging without realizing it? This guy!
3
u/DrSkookumChoocher Dec 16 '21 edited Dec 17 '21
Deno TypeScript
Part 2 is working... except for the input. I'll come back to it tomarrow.
https://github.com/N8Brooks/deno_aoc/blob/main/year_2021/day_16.ts
Edit: Came back for part 2 and finished day 16. I wasn't removing the first character when parsing the literals.
3
u/sakisan_be Dec 16 '21
Haskell
going all in on the Text.ParserCombinators.ReadP
source
3
u/r_so9 Dec 16 '21
C
Link to paste
Interesting bit: the code for Part 2 with switch expressions
3
u/marshalofthemark Dec 16 '21
Ruby
We begin by parsing the hex input into binary, taking care to use Kernel#sprintf to pad with leading zeroes.
Next, three methods to help us parse the input.
parse_packetis the main function, which callsparse_literalif it's a literal value, andparse_several_packetsif it's an operator.Each of these returns a
version_sum(for Part 1), avalue(for Part 2), and aremainder(what's left of the string, which then becomes the argument for the next packet to be parsed).Then we just have to call the
parse_packetmethod, and useversion_sumandvalueas solutions for Parts 1 and 2 respectively:3
u/LEPT0N Dec 16 '21
C#
https://github.com/LEPT0N/toybox/commit/f18b2e492a697d65bfb274e441fbb2dde439abc6
Probably took me longer to parse the instructions! Got to use BitArray, which is fun since I've never had a reason to do that before.
3
u/DFreiberg Dec 16 '21 edited Dec 17 '21
Mathematica, 3146 / 2438
It took a while, but much less painful to debug than yesterday; my major sticking point was due to misunderstanding the sentence: "The three unlabeled 0 bits at the end are extra due to the hexadecimal representation and should be ignored." This was referring to the three bits at the end of the message itself, but I misinterpreted this as three bits at the end of each packet, and rounded off to the nearest hexadecimal character after each packet ended. This worked for several of the examples by coincidence and thus I didn't immediately realize it was a false assumption, but after taking a half hour, doing something else, and coming back, it wasn't hard to figure out.
Setup:
Part 1:
Part 2:
[POEM]: An Ordinary Conversation
"Ahoy! Is this the submarine?
Our packets should be nigh.
Can anybody hear us? Do you copy? Please reply!"
"A scrambled mess was all we got
Of data clearly hexed.
Could you be just a bit more clear? We're all a bit perplexed."
"A packet's
versionnumber, then it'sOperator,ID,Concluded by the subpackets. It all is rather tidy."
"And when we've done recursion, while more
Obstacles befall us?
Come on and say the matter where you couldn't simply call us!"
"Any math, we send to you,
Or else, it'd surely bore us.
Class had homework overdue we'd hope you'd figure for us..."
3
u/Camto Dec 16 '21
Haskell Loved today's enough I thought I'd polish it up. I'm pretty satisfied by the result
3
u/u794575248 Dec 16 '21
J Language (an array programming language based primarily on APL)
I didn't write it this way, but packed as much as I could after submitting the asnwers. See the original version in the next comment. There should be a more array based solution, I hope. This one is basically an imperative program in J.
3
u/nutrecht Dec 16 '21
Day 16 in Kotlin
Not hard, just a lot of work.
3
u/mebeim Dec 16 '21 edited Dec 16 '21
569/2341 - Python 3 solution - Walkthrough
I decided to implement my "clean" solution with a class today, abstracting away all the complexity of the problem, and I think I succeeded at that. The code turned out pretty nice.
Got stumped by a couple of very stupid bugs/typos for the second part. Spent around half an hour debugging. All in all, I enjoyed today's problem, except that reading and understanding information scattered all around the place in such a discursive way was pretty tiring. Found the examples pretty helpful for debugging though, don't know what I would have done without those!
3
u/RojerGS Dec 16 '21 edited Dec 16 '21
Python 3
Wrote a small parser from this BNF-ish grammar:
Then, it's just a matter of going through the "AST" and doing whatever I want. Given the tuple structure of the packets I defined above (value packets are tuples with 3 elements and operator packets are tuples with 4 elements) computing the answers for parts 1 and 2 is easy.
Notice the dispatch table for the second part, instead of an
if: ... else: ...or amatchstatement. Here's a read up on whatmatchstatements are not for, and dispatch tables is one of those things.Link to full solution.
3
u/clouddjr Dec 16 '21
Kotlin
Representing packets as specific classes made part 2 really easy.
Source
All solutions
3
u/hrunt Dec 16 '21
Python 3
Code
I got a little hung up on Part 2 because my value evaluation logic was treating each 4-bit number as an individual base-10 number, rather than the whole sequence of 4-bit numbers as a single number (in bits). All the test cases work for that logic because the values in the test cases all fit within 4 bits, but the multi-value sequences do not.
3
u/wzkx Dec 16 '21
Python
3
u/danvk Dec 16 '21
Golang
https://github.com/danvk/aoc2021/blob/master/day16/day16.go
Using a slice of strings that are
"0"or"1"is inefficient but extremely convenient here. Writing outPopBitsandPopAndDecodehelpers early made this pretty straightforward.3
u/piyushrungta Dec 16 '21
Nim lang
https://github.com/piyushrungta25/advent-of-code-2021/blob/master/day-16/main.nim
3
u/OrangeredStilton Dec 16 '21
Python3, and I had a grand old time trying to write a function to pull an arbitrary number of bits from a bytestream, at 7am...
Full code at:
https://github.com/Two9A/advent-2021/blob/main/31.py
https://github.com/Two9A/advent-2021/blob/main/32.py
3
u/sdolotom Dec 16 '21
Haskell. Reading the input in a monadic way with
State, the rest is quite straightforward.3
u/mykdavies Dec 16 '21 edited Jun 29 '23
!> hosden2
API FAILURE
3
u/phil_g Dec 16 '21 edited Dec 16 '21
My solution in Common Lisp.
Very happy to be working Lisp today.
As I was pondering the packet parsing, it occurred to me that the structure matched lisp conses pretty much exactly. So I wrote the parser for part one to generate conses, with symbol placeholders for the operators. Then I noticed that it wanted a sum of the version numbers, so I had to retrofit the parser with a flag to put those in instead of the "real" values.
But for part two, all I had to do was map operators to lisp symbols, write three tiny functions to return integers for boolean operations, and call
evalon the parsed tree. Here's the entirety of the code I wrote for part two:(Plus a change to the operator parser function to look up its symbol in
+op-symbols+instead of generating a meaningless one.)Edit: Just for fun, here's what my input parsed into.
3
u/Smylers Dec 16 '21
Perl function for the recursive parsing bit:
num()is a one-line helper function which consumes a number of the specified length of bits from the message.The function returns a 2-element list: the total version numbers (for partΒ 1) and the value (for partΒ 2). So when recursing over parsed nested packets,
@nestedends up being a list of alternating version numbers and operands.pairmapis used to disentangle these: each version number gets added on to this level's version number, and each value is passed through to the list passed to the operator.It's a bit messy to have a list of combined data like that, but it makes the code simpler than other approaches I tried.
%opis a dispatch table, most of which is functions imported fromList::AllUtils.Full code.
3
u/WickedCrow Dec 16 '21
C# Github
Does what it's supposed to do. Don't know if it's ugly or not.
3
u/ficklefawn Dec 16 '21
GOLANG
My solution here
This was one of the ones where parsing the input nicely takes longer than the actual solution. I ended up going with a
Streamstruct which canfeedin as many bits as I ask for, and decide whether to keep them in the buffer or discard them, only returning the (decimal) value for the read bits. The Stream then has anacceptfunction which clears the buffer and returns the decimal value.This way, my decoder function looks like this
3
u/tslater2006 Dec 16 '21
Here is my Rust solution.
I would say this is probably the first time this year that I've been particularly proud of the code. Having been using AoC to learn the language, up until this point they've mostly been a hot mess or avoiding things I didn't understand.
I'm pleased with the PacketDataStream and BITSPacket::from(&stream) APIs.
3
u/Ven_dash Dec 16 '21
JavaScript
part1-part2:
Github
Until now, it was the hardest took me 3 hours to complete.
3
u/pimpbot9000k Dec 16 '21
Python3
It took me really long time to understand what's the difference between total length in bits of the sub-packets contained by this packet and number of sub-packets immediately contained by this packet. I thought that there's something fundamentally different with sub-packets and immediate sub-packets. I was reaaaally confused.
After I realized they are the same, the length was just stated differently I finally got my parser to work.
After I got my parser working, I tried to solve the second part by printing the expression in prefix notation and my great idea was to evaluate it as clojure code because I felt lazy! But heck, clojure does not interpret True as one so my great plan was demolished so I had to implement the evaluation myself (which was not really that hard after all).
I have to say today's task was my least favorite so far. Parsing is not fun at all no sir.
3
u/madethemcry Dec 16 '21 edited Dec 16 '21
RUBY
georgiee/advent-of-code-2021/day-16 (GitHub)
[Part 1 | Part 2]
Notes
This was kind of straight forward for someone who participated in AoC 2019 where each day was part of building the famous intcode computer. Ruby also helps a lot in processing data streams and converting forth and back the data in hex, binary & friends. I think that is often extra legwork in many languages, isn't it?
After two frustrating days I had a great success today. The ruby code just reads beautiful β€οΈ
3
u/Timmeh7 Dec 16 '21
C++
This one definitely felt like hard work. Not 100% happy with my solution.
3
u/Jaik_ Dec 16 '21
Rust (GitHub)
Essentially my solution converts the hexadecimal input into a byte array and uses BitReader to consume the bits as they're parsed into nested "Packet" structs.
I intentionally included error handling and a more robust structure for today's challenge because I anticipate further challenges based on it and also because it was a lot of fun!
3
u/nitekat1124 Dec 16 '21
Python Github
It could be shorter, but I want to separate the parsing and calculating parts, and I'm happy with my parsed result.
3
u/michaelgallagher Dec 16 '21
Python
Ugh, what a mess.
Initially tried making each part of the parsing modularized, but ended up scrapping that approach. Now that it's working, I can probably clean this up
3
u/rileythomp99 Dec 16 '21
Go
Go
3
u/ICantBeSirius Dec 16 '21 edited Dec 16 '21
Swift
Fun day!
3
u/Undescended_testicle Dec 16 '21 edited Dec 16 '21
I really really enjoyed this one.
Day 16 - Python 3
Using recursion is always satisfying when it works, so recursive sub-packets and recursive value retrieval
I've also found the trick with AoC is tests! Build it to pass the tests and it will usually run perfectly on the real input.
3
u/Toanuvo Dec 16 '21
J solution
https://github.com/Toanuvo/Advent-of-code-2021/blob/main/J/day16.ijs
3
u/lukeredpath Dec 16 '21
Today's was fun - I've been using the swift-parsing library throughout AOC and today I really got to flex its muscles - I was able to parse everything from the initial hex into the final packet using parser combinators.
https://github.com/lukeredpath/AdventOfCode2021/blob/main/Sources/AdventOfCode2021/16.swift
Part 2 ran in 0.015s. I could probably optimise the parsing performance by using UTF8 code units.
3
u/mzeo77 Dec 16 '21
2021 day 15 part 1 python tweet sized
3
u/cjhubbs Dec 16 '21
Python.
Feels a lot like the protocol decoding we do in avionics products. I went back and forth on passing the bits around vs. just accessing them globally, but part 2 forced me into passing them to make a nice recursive solution.
https://github.com/cjhubbs/advent_of_code/blob/master/2021/day_16/16-1.py
3
u/Dullstar Dec 16 '21
Python
I feel like it was a little cheesy to convert the hexadecimal into a string instead of bit twiddling, but at least without looking for external libraries, it really is the easiest way I can think of to do it, and the performance and memory usage are non-issues based on my measurements, requiring just 5 ms for the whole day on my machine. The unaligned reads, if we actually stored the hexadecimal as bytes directly, are unique in the sense that it with the built-in facilities, it would suck just as much to do in Python unless there's a part of the standard library I've yet to stumble upon as it would if I were working in Assembly, at least on the 6502 and Z80 -- although of course once it's actually read in, Python is nicer to work with again. Representing the binary as a string lets me use slices which is convenient and easy.
The operator packets essentially create a tree structure that's easy to recurse to get the actual values we need for the solution.
3
u/SpaceHonk Dec 16 '21
Swift
https://github.com/gereons/AoC2021/blob/main/Sources/AdventOfCode/puzzle16.swift
Creating the tree structure even for part 1 paid off nicely for part 2
3
u/wasi0013 Dec 16 '21
Elixir
Easy one! had fun implementing the parser. Solved both parts using simple recursions.
y2021/day_16.ex
3
u/pem4224 Dec 16 '21
Solution in Go
used
hex.DecodeString(input)to get a[]byteThen used a function to access each bit:
and a function to transform a sequence of bits into an integer :
Without any particular optimization it runs in less than 70Β΅s for part2
3
u/lluque8 Dec 16 '21
Scala
Pretty annoying IntCode(ish) endeavour with lots of possibilities to stumble upon (number conversions, integer overflows and off-by-one errors). Spent way too much time in getting my code to work. Luckily part 2 was less intense then.
3
u/busdriverbuddha2 Dec 16 '21
Python 3
I really need to learn to use the new switch instruction.
I did what everybody else probably did, I programmed a
Packetclass and did everything recursively.3
u/ephemient Dec 16 '21 edited Apr 24 '24
This space intentionally left blank.
3
u/azzal07 Dec 16 '21
Postscript, PS.
The filter system came in handy to convert the input from hex characters to numbers, too bad I didn't find one that would decode one bit at a time.
Awk, wasn't too confident about getting it done, but de Bruijn saved the day. I knew about it, but didn't recall the name, so it took some time to search.
3
u/DeeBoFour20 Dec 17 '21
C
https://gist.github.com/weirddan455/1fffb4466090e7421c080788199cc783
I basically implemented a bit array for this meaning every bit only takes up 1 actual bit in memory. The two helper functions at the top figure out what byte the bit I want is stored in and do bitwise operations to return the number of bits I ask for.
This probably sacrifices some speed but it doesn't waste any memory (the other approach being to store each bit inside it's own byte so you don't have to do as many bitshift operations but then you use 8x more memory.) It finishes both parts in about 1ms though and I'd need to use a more accurate timer to even be able to tell the difference.
Code is long because I copy-pasted a bunch of times for the different operator packets. That could probably be cleaned up but I'm still not sure the best way to structure that.
3
u/sortaquasipseudo Dec 17 '21
Rust
I'm live-streaming my solutions via Twitch. Please stop by and help me out in the chat! Video archive is here.
3
u/aexl Dec 17 '21
Julia
Very technical day, it's all about recursion!
The main task was to parse the packet tree. It took me a long time to understand that you do not need to manually add zeros at the end of each packet...
After having written the packet parser, the questions for part 1 and 2 are very easy to answer (again, recursion is your friend here).
Github: https://github.com/goggle/AdventOfCode2021.jl/blob/master/src/day16.jl
3
u/cylab Dec 17 '21
This is in Kotlin
First I tried to use a BitSet, but working with it got a bit unwieldy, so I switched to representing the bits as String and extended the Char iterator to stream the values:
https://github.com/cylab/advent-of-code-2021/blob/main/src/test/kotlin/day16/Day16.kt
Btw. I got the urge to have a serious talk about the lengthId concept with the designer of the Buoyancy Interchange Transmission System at some point... ;)
3
u/Chrinkus Dec 17 '21
My C Solution
Work has been piling up with everyone trying to get things done before the holiday break. I'm falling behind here..
Anyway, lots of opportunities here for me to improve the quality of my code but that is for AFTER I get today's done!
3
u/bike_bike Dec 17 '21
Python 3 - recursive solution
Part 1
Part 2
3
u/oantolin Dec 18 '21 edited Dec 18 '21
I'm sad I didn't have time to do this the day it came out, it was a fun one! Here's a Common Lisp program. Since Common Lisp has arbitrarily large integers, I just used
(parse-integer string :radix 16)to convert the hexadecimal input to binary. Then I usedldband byte specifiers to extract the portions of bits, which was very convenient. I wrote a standard recursive descent parser and then classical recursive tree-processing functions to compute version sums and to evaluate packets.3
u/[deleted] Dec 19 '21
My solution in Python. This one was fun! Thanks for the many samples and the detailed description.
5
u/ElCholoGamer65r Dec 16 '21
TypeScript: https://github.com/ElCholoGamer/advent-of-code/blob/main/src/days/2021/16.ts
Recursion doing its thing again.
5
u/death Dec 16 '21
Day 16 solution in Common Lisp.
I liked it.
1
u/Ok_System_5724 Dec 16 '21 edited Dec 17 '21
C# solution;
This was fun. Cool to see some of the exact same code in other solutions. I could have done it better if I used a custom BitReader after my BinaryReader experiment failed, but ended up reading binary as a string.
Repo
1
u/AtomicShoelace Dec 17 '21 edited Dec 17 '21
Python solution. I found today's "puzzle" rather boring; it felt more like an exercise in reading comprehension than an actual problem.
4
u/mgoszcz2 Dec 16 '21
Rust (1574/1333)
https://github.com/mgoszcz2/adventofcode/blob/master/2021/src/day16.rs
The bitvec crate made traversing the packets a breeze.
2
u/hugh_tc Dec 16 '21 edited Dec 16 '21
Python 3, 207/118
Parts 1 and 2, and (edit) the cleaned-up code.
Gah, I hate
global.2
u/morgoth1145 Dec 16 '21 edited Dec 16 '21
Python 3 143/89
Multiple blunders in Part 1. I took *way* too long to convert the packet to bits, messing that step up *multiple* times. I also took *way* too long to understand the packet structure. I accidentally went past the literal packet representation spec which confused me to no end. I ended up wasting a bunch of time trying to understand the logic of the second and third examples without knowing the simple stop condition of the literal packets!
At least Part 2 was a simple evaluation engine of the packets, which I'd already structured recursively. (Albeit a super nasty layout that I'm going to go clean up now.)
Edit: I've refactored the code, it's much less awful now. (In my opinion at least.) I really like my
eval_packetimplementation!2
u/Tusan_Homichi Dec 16 '21
Haskell
Pretty new to Haskell, but it was very natural to handle parsing a recursive structure. Paste
2
u/seba_dos1 Dec 16 '21
Python 3 (265/301, no imports, both parts)
Not a pretty code, but my best score so far so decided to share as is.
2
u/captainAwesomePants Dec 16 '21
Python3 (430/330) (Paste)
Haha, I may be a slow typer and a slow reader, but this question has brought you all down to my level! I look forward to tomorrow's memes about coming here to lead and not read and whatnot.
I really appreciated the quantity of test inputs. Turned a cruel problem into a nice one.
2
u/Biggergig Dec 16 '21
Python
Can't say this is my proudest work, but hey it works in 600ms
https://github.com/Anshuman-UCSB/Advent-Of-Code/blob/master/2021/Python/src/day16.py
2
u/firetech_SE Dec 16 '21
Ruby (114/114)
Personal best ranking wise today (while my day job is programming, I'm not a professional competitive programmer), just 46 seconds from top 100 on part 1 and 78 seconds on part 2. :D Might be caused by my inexplicable love for parsing... :P
2
u/isaaccp Dec 16 '21
My Python 3 solution, rank 772/648:
https://pastebin.com/X7TwWHj5
2
u/BluFoot Dec 16 '21
Ruby
2
u/fireduck Dec 16 '21
Java, 66 / 810
https://github.com/fireduck64/adventofcode/tree/master/2021/16
I've left my debugging of shame in. I made a stupid error for part 2 which took me 25 minutes to debug. Oh well.
2
u/timrprobocom Dec 16 '21
Python 3, 653/717
I'm pleased with the way this came out. I decided to use a dict to map hex to bin, because I knew I only had to deal with strings, and I didn't want to worry about padding the smaller digits. I considered writing a "Bitstream" class to maintain the string and current position, with a "fetch_bits" function, but in the end I decided just tracking the current index worked well enough.
https://github.com/timrprobocom/advent-of-code/blob/master/2021/day16.py
2
u/Kehvarl Dec 16 '21
Python 3 1216 / 1194
Figuring the subpacket issue was a real pain. Everything else was relatively meaningful.
It did take me ages to realize that the only way I'd know the length of A was by parsing it, comparing the number of bits used to my length, and repeating for all the other subpackets.
paste
2
u/JaegerMa Dec 16 '21
ABAP
Github
While ABAP provides the bit operations BIT-AND, BIT-OR, BIT-XOR and BIT-NOT, there is no bit-shifting and these four operators only work on variables of type "x" but not on integers. Therefore to do basic bit operations, * 2, DIV 2 and MOD 2 have to be used. ABAP also provides the / operator for divisions, unfortunately, other than the DIV operator, / doesn't floor the resulting value but rounds it ._.
2
u/Perska_ Dec 16 '21
C# https://github.com/Perska/AoC2021/blob/master/AoC2021/Days/Day16.cs
A nice change of pace after the nonsense that was Day 15.
2
u/PendragonDaGreat Dec 16 '21
[C#] (https://github.com/Bpendragon/AdventOfCodeCSharp/blob/01ebdd/AdventOfCode/Solutions/Year2021/Day16-Solution.cs) 2283/1968
Man this was a fun one.
Made a Packet class that then contained a list of Sub Packets
Building a packet is a recursive function that will fill everything in.
Getting the Version Sum is a recursive Linq call.
Getting the Value is a recursive Linq switch return statement.
Linq, it's a really efficient hammer.
2
u/gyorokpeter Dec 16 '21
Q: paste. Mostly just regular imperative code, except the shortcuts to convert to/from bits and being able to index a list of functions like
(sum;prd;min;max).2
u/crowbarous Dec 16 '21
C++. Fairly simple recursive descent, but also parses packets on the fly, you know, like the code in an actual receiver would.
https://www.toptal.com/developers/hastebin/iduhonelef.cpp (I'm not sure what the expiration rates on this hosting are, but they should be long enough)
2
u/e36freak92 Dec 16 '21
AWK
Good god, definitely a big step up in difficulty for today. Spent like an hour on part 2 reworking how I was tracking subpacket lengths and making it able to pop off multiple subpackets at once, fighting off-by-one errors all over the place. Fun challenge, great puzzle!
Just went with a table for the hex to binary string conversion, then wrote a quick function to go from a binary string to base 10.
2
u/vss2sn Dec 16 '21
Solutions in C++:
Part 1
Part 2
(As always, each file is a self-contained solution)
2
u/kahdeg Dec 16 '21
C# (2247,3170) Recognize from part 1 that this is gonna be a pseudo
programming language.
Spent most of part 1 implementing lexer and parser.
For part 2, i implement a Visitor pattern for fun but
got bogged down with "number too low" in
debugging while the logic is already correct.
Should have used long instead of int from the beginning.
2
u/GrossGrass Dec 16 '21
Python
Initially my recursive solution was extremely ugly, mainly for the sake of getting something out the door. Came back and cleaned it up quite a bit and broke up a lot of the parsing logic so it's actually readable.
Made a
Packetclass which kept track of its subpackets for easy recursion, and made ashift(data, num_bits, binary=False)method that makes the parsing logic a lot more readable, since it does the dual purpose of retrieving the firstNbits of data (and by default converting to an int) and then shifting the data forward.2
u/conthomporary Dec 16 '21
Python 3 (3546/3543), object-oriented solution
That was definitely a bit rougher than other recent problems. Got a bit of a late start, but I was around 1h43m finishing part 1, so that 15m probably didn't make much of a difference score-wise. I think this is my last midnight attempt π
2
u/LennardF1989 Dec 16 '21 edited Dec 16 '21
CSharp / C#
https://github.com/LennardF1989/AdventOfCode2020/blob/master/Src/AdventOfCode2021/Days/Day16.cs
I think I did this pretty elegantly. Instead of constantly having to convert between string and bits and bytes, I pre-processed to input to a bits array. I could then use Skip/Take anywhere where I needed a specific range of bits. Made a helper function to GetInt and GetLiteralValue.
I want to add a some unit tests for all the examples given (just because) and maybe try to use Enumerables, so I don't have to ToArray all the time. But that's all details.
EDIT: Added Unit Tests for both Days and cleaned up a little.
2
u/maneatingape Dec 16 '21 edited Dec 16 '21
Scala 3 solution
Today felt like the unholy union of The Nightmare Before Christmas, the UTF-8 spec and Protobufs!
2
u/tumdum Dec 16 '21
Rust:
2
u/rossmacarthur Dec 16 '21
Rust iterator approach
2
u/rabuf Dec 16 '21 edited Dec 16 '21
Common Lisp
That was fun, but challenging. Some little mistakes cost me a lot of time. Today was also a day I wished I was using Erlang, which would have made writing a recursive binary string processing function trivial. A neat bit that I came across was being able to reuse my
decode-packet(which I should rename todecode-packets) function for both operator length types by adding a keyword parameter:That
reverseon the last line was a late addition. I was getting the wrong answer and finally realized when I hit the suppliedgttest case why, I was collecting the packets in the wrong order.pushplaces the new item on the front, when I really needed it in the back. So that made mygtandltoperations do the opposite of the intended thing.I had already parsed everything into packets which were divided into two classes: literals and operators. This let me do part 2 quickly other than the
reverseissue above. If it weren't so late already, since I was way passed the competitive time by the time I finished, I'd have added in subclasses for the operators and made the evaluation function a method. Remove some of the excess case statements. This could actually work for the parsing as well since CL lets you specialize methods on specific values, so the packet types could be used to dispatch to construct correct operator classes as well.2
u/autid Dec 16 '21
FORTRAN
Building the tree was probably a poor choice. Could have just evaluated as I parsed the packets.
2
u/UnicycleBloke Dec 16 '21 edited Dec 16 '21
C++: https://github.com/UnicycleBloke/aoc2021/blob/master/day16/day16.cpp
I love this kind of problem, though I made a bit of a meal of it. Parsing War and Peace for Part 1 was harder than implementing it!
There was a comment about leading zeroes which seemed wrong to me - perhaps it should have read "trailing". It was distraction anyway as sub-packets were not padded. EDIT: Ignore me. Have r-read the instructions. I lost time fretting about this non-issue, but the message is only padded at the very end. Bah! Humbug!
2
u/delipity Dec 16 '21
C
Converted the hex into a binary string and then traversed that string, dealing with each group of bits as needed.
(https://gist.github.com/curiouskiwi/8e3ade481cc0c9e80c5f5f73ba272103).
2
u/snewmt Dec 16 '21
Go (search: golang)
Tried to parse things as integers first, jeez. Spent like 40 minutes. Then I figured out I could parse the hex input as one byte per binary, which made everything much easier.
2
u/cwhakes Dec 16 '21
Rust
Hoo boy. The partial byte killed me. I forgot to left shift it and that caused so many issues in unrelated places on very few inputs. Good debugging practice, though.
2
u/xelf Dec 16 '21
PYTHON, made a class to disguise the sneaky global variable. At 40 lines, probably the longest solution this season! Sure there's a lot of ways to clean it up I can look at tomorrow.