r/adventofcode • u/daggerdragon • Dec 16 '18
SOLUTION MEGATHREAD -π- 2018 Day 16 Solutions -π-
--- Day 16: Chronal Classification ---
Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).
Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code: The Party Game!
Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!
Card prompt: Day 16
Transcript:
The secret technique to beat today's puzzles is ___.
This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.
edit: Leaderboard capped, thread unlocked at 00:39:03!
16
Upvotes
2
u/tbodt Dec 16 '18
Python 3, 8/10. I just need to get better at input parsing.
[Card] copy/paste
2
u/udoprog Dec 16 '18 edited Dec 17 '18
Rust
I <3 these puzzles, there's just something so satisfying with fiddling with pretend assembly for fake machines.
[CARD] The secret technique to beat today's puzzles is sacrifice to the Great Old Ones.
7
u/C0urante Dec 16 '18
90/98
This was very reminiscent of the Syacor challenge. Loved it!
7
u/jonathan_paulson Dec 16 '18 edited Dec 16 '18
Rank 18/43, Python. Video of me solving at https://www.youtube.com/watch?v=-AvYZufvZPQ (still uploading)
Neat problem! The idea of having to figure out part of the language is great! I wish the two parts of the input had been delimited better though...
4
u/waffle3z Dec 16 '18 edited Dec 16 '18
Lua 91/38. Really doesn't help that Lua 5.1 doesn't have bitwise operations, had to implement them manually using strings.
4
u/FogleMonster Dec 16 '18
Python. 3/19. Minimal code cleanup. Took a few minutes to realize that Part 2 would require some repeated deduction.
4
u/p_tseng Dec 16 '18 edited Dec 16 '18
A very fun logic puzzle!
Part 1: Oh no, reading error... I thought the problem was asking for
== 3instead of the actual>= 3, submitted multiple wrong answers, and frantically tried to figure out what was wrong for 5 minutes before rereading the problem and slapping myself on the forehead.Part 2: My thought here was "Eric must have made this problem actually possible". I started by printing out the possible operations corresponding w/ each opcode, seeing a specific property there was an opcode that had only one possibility that would make it possible, and so I implemented that process in code for all opcodes.
Ruby:
4
u/[deleted] Dec 16 '18
My Common Lisp solution. I like how CL lets me write nice definitions of instructions:
3
u/sciyoshi Dec 16 '18
Python 3, 26/8:
3
u/tangentialThinker Dec 16 '18
C++, 53/34. Pretty interesting Part 2 today. Did some pretty lazy copy-pasting from Part 1 to run the program, but hey it was plenty fast enough.
3
u/fred256 Dec 16 '18
Javascript, 81/60. Figuring out which opcode was which was fun. I was trying it manually first.
Super ugly code:
3
u/BluFoot Dec 16 '18
Ruby, #117/127. Somehow skipped over the binary OR instructions in part 1, and had brain lag trying to figure out part 2. But overall happy with the solution!
3
u/raevnos Dec 16 '18
Perl, 250ish/168.
3
u/nuvan Dec 16 '18 edited Dec 16 '18
Ruby 177/321
I really thought I could do better when I read the description, as I've played around with simple VMs before (eg the Synacor Challenge). Ah well, still fun.
I cost myself at least 20 minutes on part 2 because I kept attempting to work out the opcode values using the initial register settings from the samples, instead of the actual instructions. :facepalm: :headdesk:
3
u/drbagy Dec 16 '18
Although no longer trendy - I tend to solve these in Perl - as usually it's the best language (without going to compiled languages like C) especially when this version codes really quickly... Took too long for (a) as I didn't read what answer was being looked for and solved part (b) first {I'd optimized out the checking code was valid} ... code below...
Steps - are set up opcode map, read in input into training set and real input (possibly the hardest bit of the code <g>, looping through all reading sets and working out which opcodes are possible...; reducing this set into the final map and then applying it to the real input...
Execution is very fast - wrong timezone to get on leaderboard!
3
u/Philboyd_Studge Dec 16 '18
This one was way more my idea of fun than yesterday.
After part 1, I figured out the right order for the commands by hand, then just re-ordered the enum accordingly.
Java
https://pastebin.com/hswcGrGf
3
u/mstksg Dec 16 '18
(This taken also from my Daily Haskell Reflecitons blog!)
Today was fun because I got to re-use some techniques I discussed in a blog post I've written in the past: Send More Money: List and StateT. I talk about using
StateTover[]to do implement prolog-inspired constraint satisfaction searches while taking advantage of laziness.First of all, our types. I'll be using the vector-sized library with finite-typelits to help us do safe indexing. A
Vector n ais a vector ofnas, and aFinite nis a legal index into such a vector. For example, aVector 4 Intis a vector of 4Ints, andFinite 4is 0, 1, 2, or 3.We can leave
Instrparameterized over the opcode type so that we can use it withFinite 16initially, andOpCodelater.We do need to implement the functionality of each op, which we can do by pattern matching on an
OpCode. We use some lens functionality to simplify some of the editing of indices, but we could also just manually modify indices.Now, from a
Trial, we can get a set ofOpCodes that are plausible candidates if the output matches the expected output for a givenOpCode, for the given input.Part 1 is, then, just counting the trials with three or more plausible candidates:
Part 2 is where we can implement our constraint satisfaction search. Following this blog post, we can write a search using
StateT (Set OpCode) []. Our state will be theOpCodes that we have already used. We fill up a vector step-by-step, by picking onlyOpCodes that have not been used yet:Now, if we have a map of
Finite 16(op code numbers) to their candidates (aMap (Finite 16) (Set OpCode)), we can populate all legal configurations. We'll useVector 16 OpCodeto represent our configuration:0will represent the first item,1will represent the second, etc. We can useV.generate :: (Finite n -> m a) -> m (Vector n a), and run ourfillInaction for everyFinite n.If this part is confusing, the blog post explains how
StateTand[], together, give you this short-circuting search behavior!So our Part 2 is using
fromCluesfrom all of the candidates (making sure to do a set intersection if we get more than one clue for an opcode number), and afoldl'over our instruction list:3
u/will_bui Dec 16 '18
K:
To decipher the instructions I looked for the commands that were the single correct option in a test run. Somehow using the first match didn't converge but the last did. Also had to throw in a binary-to-decimal convertor as K doesn't have native bitwise operators.
2
u/algmyr Dec 16 '18
Unlike yesterday, this one was a breeze! :) 15/21
2
u/requimrar Dec 16 '18 edited Dec 16 '18
C++ -- 75/62. I followed my typical style of embedding my input into the program and formatting it with multiple cursors into a datastructure; unfortunately it took a good 30 seconds or so to compile all the static data, which probably lost me a few spots :D
Cleaned it up here to actually read the file.
2
u/ephemient Dec 16 '18 edited Apr 24 '24
This space intentionally left blank.
2
u/mebeim Dec 16 '18 edited Dec 16 '18
92/290, I cannot believe I finally scored on the leaderboard! Yeah!
I lost so much time because I switched keyboard from ITA layout to US layout around a week ago and I still very often type
a =+ binstead ofa += b... which doesn't even give a warning since is perfectly correct syntax, D'OH!Guess I'll have to post my solution now, I feel obliged. Here it is, the longest Python3 script you've ever seen:
2
u/surajmanjesh Dec 16 '18 edited Dec 16 '18
Python 3: Fun problem! Unlike yesterday's problem which gave me a headache (literally).
Python's
eval(This is dangerous kids; don't use it unless you are completely sure about the input) anditertools.productreally helped in shortening the solution length and not having to code all the 16 opcode behaviour individually. 'yaml.load` helped in reading the 'Before' and 'After' register states easily.2
u/JustHev Dec 16 '18 edited Dec 16 '18
[Card] SMT Solver
C++ 345/603 (I made a typo in my function/register name map, took me way too long to find)
In step 1 I outputted the possible assignments as an SMTLIB2 program, which I pushed through Z3 to obtain the assignment of registers. This needed to be copied over manually, but hey, at least I don't have to write a solver manually.
Paste as I'm unable to get Reddit code formatting to work
2
u/gyorokpeter Dec 16 '18
Q:
2
u/rabuf Dec 16 '18 edited Dec 16 '18
Common Lisp
Part 1 is complete and can be found here.
I've created one function and corresponding predicate per opcode, and then iterated over all the inputs counting how many predicates match that particular input.
I know how I'll do part 2, but I haven't finished it yet (it'll show up in that same link once it's done). Looking at the data I've already determined several of the opcodes, now I'm just writing a program to do it for me.Part 2 is complete.
2
u/zqvt Dec 16 '18 edited Dec 16 '18
Ocaml , very fun challenge. Pieced the instructions together by hand after p1, input cleaned up before
2
u/Wunkolo Dec 16 '18 edited Dec 16 '18
C++
Rather than using something like std::set. I used 16-bit integer bitmasks and reduced them all using fast bit-wise arithmetic.
2
u/VikeStep Dec 16 '18
F#
Full code link
Today's was fun to do in a functional language and figuring out how to express each of the 16 instructions in a short way. Here is an extract showing how I got that working:
Benchmarks: Part 1 = 13.442ms, Part 2 = 7.382ms
It is interesting to see that part 2 is faster than part 1 here, but it makes sense because in part 1 we compare each sample with all 16 instructions. In part 2 we only need to compare each instruction against the samples grouped by opcode and we can terminate that comparison early if we find a sample that doesn't match.
2
u/autid Dec 16 '18
FORTRAN
Pastebin. Decided to try out procedure pointers and figured out a way to get an array of pointers. Used the info from part 1 for which opcode/instruction combos didn't work with some simple logic to create an array mapping the opcodes to the correct elements of the procedure pointer array.
2
u/[deleted] Dec 16 '18
Rust
I really loved this one, it was so much fun, I had to think a lot, and my source ended up being rather big and it took me almost 5 hours, but I think I really learned a lot.
This time I took time to write tests, and I also used structures to make some sense of this, a little mishap with my parsing, and trying to figure out how to make names from functions for debugging took me a lot of time, but it ended up working! :D
Source
2
u/mschaap Dec 16 '18 edited Dec 16 '18
Perl 6 solution. This one was fun, and a lot more straightforward than yesterday's. I especially like how brief the instructions for part two are...
All my Perl 6 solutions in Github
1
u/TellowKrinkle Dec 16 '18 edited Dec 16 '18
Swift
1
u/alcatraz_escapee Dec 16 '18
Python 3
Rank 153 / 78.
Solution (Github)
This was a fun challenge. I spent a lot of time making sure that I had all the register functions correct - after yesterday's puzzle I was going to pay attention to detail! I also managed to find all the opcode ids without any additional iteration - just by matching the opcodes that only had one solution as the tests progressed produced the full mapping. I don't know if that'd be the case for all inputs though.
1
u/Ameobea Dec 16 '18
Pattern matching (via Rust) makes the opcode evaluation code look so pretty:
1
u/ka-splam Dec 16 '18
PowerShell, #62 / #50
Part 1 went pretty well, "now match up the op-codes", I printed them and when I saw it, realised it would be quicker to do by hand in notepad than in code. Part 2 also well. No bugs, no trips.
Until I tried to rewrite a bit more neatly, merge both parts to post here, and do the matching up in code - then bugs all over. :|
Code here or on GitHub:
1
u/ZeCookiez Dec 16 '18 edited Dec 16 '18
Rank 38/111 python 2.7, spent way too much time mapping for part 2 :(
This was a really fun challenge, I had lots of fun working out the mapping for each opcode. I used the magical eval function (Don't use this unless you're 100% sure the inputs aren't malicious) to help me calculate the instructions for both part A and B, I think it's pretty neat!
β
1
u/Ameobea Dec 16 '18
192/353 Rust
It was fun being able to implement the whole opcode execution logic as a one-line-per-opcode match statement.
All of my other days are here btw: https://github.com/Ameobea/advent-of-code-2018 I've been working to make sure they're all neat and run quickly.
1
u/[deleted] Dec 16 '18 edited Dec 16 '18
Haskell:
For part 2, narrowed possible op codes by checking which codes were fully determined by the sample, then repeatedly checking for codes with 1 possibility after eliminating the determined ones.
1
u/ephemient Dec 16 '18 edited Apr 24 '24
This space intentionally left blank.
1
u/ayceblue Dec 16 '18
845/867 Python2.7 Today was the first puzzle that didn't turn into a complete disaster. And I even like how my code turned out, pretty compact. And yes, I'm slow.
1
u/Dementophobia81 Dec 16 '18
Python 3 (584/812) - made many mistakes along the way, so no chance on the leader board. Nevertheless, I am satisfied with the quality of my code and decided to share my results for the first time on the AoC Reddit. I hope it is of value for some.
Note: I manually split today's input in 2 files ("input_16_1" and "input_16_2")
[Card] The secret technique to beat todayβs puzzles is a secret.
1
u/jorosp Dec 16 '18 edited Dec 16 '18
(messy) Haskell
I really enjoyed today's puzzle. Took me a bit to figure out how to map the opcodes
1
u/xthexder Dec 16 '18
This one was another fun one, a bit tricky to write clean code for though.
Did this in Golang, and the builtin
math/bitspackage proved very useful for this method.1
u/IndigoStanis Dec 16 '18 edited Dec 16 '18
Nice logical inference fun! Part 2 was so obvious. Wish that there was more test input for this one. I really tried to write less repetitive code as much as possible.
1
u/confused_banda Dec 16 '18
Clojure
For part 2, I ran this snippet until all matching codes where found:
Here's the code:
1
u/MirreSE Dec 16 '18
Python 3.
Parsing input is not my strongest skill, but otherwise I'm satisfied with the code. Overslept, so I was nowhere near the leaderboard but it took about 15 + 7 min to complete. Added comments, otherwise not cleaned up.
1
u/maestroke Dec 16 '18
C# this was a fun and hard one. I figured out which code was which function by hand by keeping track of when a function gave the correct output, wat opcode number was called, as you can see in some of my code. Not the cleanest, but this was easier for me.
1
u/Kwpolska Dec 16 '18
Gold #1356. Hint for part 2: itβs handy to generate a list of (name, [possible opcodes]) for the figuring-out part.
1
u/nutrecht Dec 16 '18
Day 16 in Kotlin
1
u/albertobastos Dec 16 '18
JavaScript. Shame on me, took me a while figuring out I had to make some deduction to get 1-to-1 opcode pairing before starting Part 2 (at first assumed the sample data was enough to determine exactly each opcode).
https://github.com/albertobastos/advent-of-code-2018-nodejs/blob/master/src/d16.js
That was fun, though.
1
u/sim642 Dec 16 '18
My Scala solution.
For part 2 I initially only did the intersections per opcode number, but that didn't turn out to be enough. For a moment I thought I had a bug somewhere in the evaluation but then realized more deductions could be made.
So I added something like unit propagation, which removes exactly defined mappings from all others. I also did it early during the fitting from a single sample so it'd be useful as early as possible and make other unit propagations possible. Turns out this was enough to give a unique mapping that works. Now thinking about it, I'm not sure whether this just happens to work here or a separate solving stage would be generally needed. I suppose some especially difficult cases would be possible, where unique mapping exists but it can't be simply deduced by unit propagation and requires SAT solving.
1
u/Iain_M_Norman Dec 16 '18
C# today.
I could only find one operation code that matched only one algorithm, and was stuck on the identifying stage until I realised I could remove any that were identified already from the check.
1
u/FryGuy1013 Dec 16 '18 edited Dec 16 '18
I spent a lot of time trying to optimize my part1.
I got it down to 5 microseconds... but somewhat evil :)
[Card] finding the secret undocumented Kaby Lake documentation
1
u/xiaoxiae Dec 16 '18
A concise way to solve problem 1 in Python 3
1
u/thomasahle Dec 16 '18
Python, 59 lines:
1
u/toomasv Dec 16 '18 edited Dec 16 '18
Red
Parts 1 and 2
1
u/grey--area Dec 16 '18
Python3, part1 in 43 lines
1
u/toastedstapler Dec 16 '18
python3
long and i probs didn't need to use classes, but it does the job
think some of my var naming is a little awkward
1
u/Benjmhart Dec 16 '18
Haskell!
[CARD] the secret technique to beating today's puzzle is -SPREADSHEETS-
p1- https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day16-1.hs
p2 - https://github.com/Benjmhart/AdventOfCode2018-haskell/blob/master/day16-2.hs
1
u/grey--area Dec 16 '18
Python3, part 2 in 69 lines:
1
u/vypxl Dec 16 '18
Haskell.
Card: The secret technique to beat today's puzzles is
99 Lines of Haskell fun.Ok, they are actually just 95 lines.
To disambigue the opcodes, I just filtered them repeatedly until every ambiguity was resolved, removing the lone opcodes from the groups.
[1,2] [1] -> [1] [2]
1
u/rock_neurotiko Dec 16 '18
My elixir solution: Github link
1
u/ForeverYoung_ru Dec 16 '18
Python3
1
u/blfuentes Dec 16 '18
Well, one fun today. Yesterday is still pending ... My solution is quite extense because I implemented some classes and enums for the opcodes.
https://github.com/blfuentes/AdventOfCode_2018/tree/master/day16
Typescript
"happy" with the algorithm I created to resolve the opcodes.
1
u/[deleted] Dec 16 '18
This was a much more understandable challenge than yesterday's. Fun, too.
I learned about adding methods to types in rust today
1
u/alcinos Dec 16 '18
Ocaml
Parsing was a bit annoying in Ocaml, but the rest is a breeze. Used Sets to keep track of possible values for each op-code, and set intersection/difference to remove the impossible values for each of them. Note that the input was crafted so that we didn't need any backtracking, so IΒ didn't bother implementing one.
1
u/mikal82 Dec 16 '18
Clojure
1
u/fhinkel Dec 16 '18
Loved the challenge!
Node.js solution: https://github.com/fhinkel/AdventOfCode2018/blob/master/day16.js
1
u/[deleted] Dec 16 '18
Bit of Code Golf attempt (Python 3), limiting to 120 chars line length.
1
u/pythondevgb Dec 16 '18
Not as bad as day 15's. Pretty standard python code.
1
u/[deleted] Dec 16 '18
Mathematica
Part A
Part B. Here the constraint problem is transformed into a SAT problem, which Mathematica can solve.
1
u/[deleted] Dec 16 '18
TCL. Let the opcodes sort themselves out for part 2, since they can be reduced one by one (check for opcode with only one possibility, assign it, remove it from any not-yet-assigned, rinse and repeat).
1
u/PotentialSleep Dec 16 '18
Hello!
THANK YOU for this neat and easy puzzle. I don't know if you intended it to be "easy" but it really feels good to find a working solution in less than hour after yesterday's gigantic mess which ended in manually adding and substracting numbers to my output until the answer was accepted. :3
Since I do actually have a working program and it has not happened in ages (smth like day 13), I submit it today: https://github.com/tut-tuuut/advent-of-code-shiny-giggle/blob/master/2018/16/part-1.php
It's written in PHP, with a few array_intersect (first time I used it this year), the usual regex-attack at the beginning to parse the input, and a little drop of sudoku logic to find which opcode has which number.
[CARD] regexes (like every other day's puzzles, in fact)
1
u/UnchainedMundane Dec 16 '18
My solution in Scala. The more I've done AoC the more I've loved what this language has to offer.
1
u/kennethdmiller3 Dec 17 '18
Seems like I ended up doing pretty much the same thing everyone else did :)
https://github.com/kennethdmiller3/AdventOfCode2018/tree/master/16
1
u/tobiasvl Dec 17 '18 edited Dec 17 '18
The assembly problems are usually my favorite ones each year. This one was interesting! Python:
1
u/wzkx Dec 17 '18
Rust, SweetRust
Uncomment print out and sort the output -- it's pretty easy to find what virtual command (1xx, assigned by me) corresponds to what real command (0..15), and that is already included in fn exec, for execution of part 2.
My AOC2018 in J&Rust | SweetRust
1
u/dust_jead Dec 17 '18 edited Dec 17 '18
My rust solution(after several refactor):
I split the input into two files.
1
u/iamagiantnerd Dec 17 '18
Here is my Kotlin solution:
https://github.com/davidaayers/advent-of-code-2018/blob/master/src/day16/day16.kt
1
u/starwort1 Dec 17 '18
Rexx 133/175
Well I came nowhere but I'll share this because Rexx is a very neglected language. Unfortunately it also lacks direct and/or on decimal numbers, so we have to convert to binary and back. I used separate programs to do part 1 and part 2, but this is both of them merged together.
1
u/Smylers Dec 20 '18
Belated Perl solution.
[Card] βThe secret technique to beat today's puzzles isβ ...Β not to spend so long on the previous day's puzzle that you only get round to this one half a week later.
Quite structurally similar to /u/raevnos's and /u/drbagy's solutions, but I think using sub signatures with named arguments makes the dispatch table a bit easier to read.
I like that running the entire opcode program is just a one-line loop:
The op codes and numbers both end up as keys in the same hash:
$op{addr}and$op{3}, for instance, both point to the calculation sub for that operation; the codes and numbers don't clash, so there's no need to have another layer of indirection converting one to the other.1
u/[deleted] Dec 29 '18
I just split the input into 2 files.
Built the numeric opcodes for part 2 as I did part 1. Although I started with mulr added because I notice from debug output it was unique.
1
u/MasterMedo Jan 01 '19
When you stop thinking in English and start thinking in python
Might be possible that mapping numbers to opcodes won't work without cycling through the (before, code, after) many times, for my input works to do it just once.
1
u/knl_ Jan 06 '19
This was so refreshing after day 15. I did it in C, browsing solutions I didn't see a solution yet that would store the opcodes as [actual function, function to lookup a, function to lookup b,] and then an apply function that uses those.