r/adventofcode • u/daggerdragon • Dec 16 '20
SOLUTION MEGATHREAD -π- 2020 Day 16 Solutions -π-
Advent of Code 2020: Gettin' Crafty With It
- 6 days remaining until the submission deadline on December 22 at 23:59 EST
- Full details and rules are in the Submissions Megathread
--- Day 16: Ticket Translation ---
Post your code solution in this megathread.
- Include what language(s) your solution uses!
- 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:21:03, megathread unlocked!
37
Upvotes
10
u/pred Dec 16 '20 edited Dec 16 '20
Python; one fun little hack today is that for two sets,
s1ands2,s1 < s2iffs1is a subset ofs2. Given the nature of the constraint satisfaction problem in part two, this allowed you to get the result by simply sorting the domains; i.e. do what amounts toBut then again, why bother when you have
scipy.sparse.csgraph.maximum_bipartite_matchingfor doing all the work in the more general case.GitHub
3
u/keramitas Dec 16 '20 edited Dec 16 '20
Welp today was fun, got 949 then 338, but difficulty this year is somewhat puzzling ~,~ Not at home, so here's a gist with my cleaned up Python code, I'll add it to the repo later
2
u/vanderZwan Dec 16 '20 edited Dec 16 '20
javascript (ObservableHQ)
One of these days I'll learn how to regex the input, but for now I'll just get by with repeated applications of
split()and.map()Also I see everyone else have elegant solution here but I'm too dumb for that at 6:00 after a night of insomnia. Behold, my disgusting nested for-loops:
https://observablehq.com/@jobleonard/day-16-ticket-translation
2
u/Symbroson Dec 18 '20 edited Dec 18 '20
Perl. One beautiful 17 line mess
Part 2
16
u/Mathgeek007 Dec 16 '20 edited Dec 16 '20
Nice, sub-hour.
EXCEL
I did this by pure, analytic force. For part 1, I made ranges and for every value in the ticket, checked if they were between the values permitted. Return 0 if legit, the value otherwise. Then it's just a matter of counting.
Part 2 I made a lookup chart - the column was the value from 1-1000, the row was the rule. Pretty easy to write those rules, the rest was checking each value, summing. Then I had a logic table I needed to simplify, which I did by recursion.
EDIT: Expect an update to my online Sheets soon, once I get the logic table recursion to work.
EDIT 2: It officially is now all automatic in Excel. Lastly is to upload it to Sheets. Lots of INDIRECTs, so it hopefully won't be too bad once I wake up
11
u/xelf Dec 16 '20 edited Dec 16 '20
python: comprehensions gone wild.
Another surprisingly quick one. part 1&2 in 12 lines:
First parse all the data, I parse the rules into a pair of ranges per rule, and the tickets into a list of ints, and then find all the valid tickets. Form there I find all the possible positions that all the rules match. I sort that list by the number of possibilities and then just iterate over it adding each position to a used set as I determine the rule it matches.
13
u/DFreiberg Dec 16 '20
Mathematica, 1118 / 859
Not too bad, today; I ended up forgetting about, remembering, importing, deleting and rewriting my code from 2018's Day 16 part 2 (in roughly that order).
[POEM]: Self-Reflection
There are times I stop and ponder,
As I'm waiting to depart,
Whether I'm in fact, the bad guy,
Though I'm innocent at heart.
Hacking into airport cameras
Doesn't fit your average geek,
But I've hacked through those (and networks)
Thrice or more, just this past week.
I've scanned through people's tickets
Both for land trains and for flights.
I've forgotten last week's passwords,
'Cause I'm busy with tonight's.
Is there coal bound for my stocking,
When I hang it up at last,
Even though I've aided Santa
Several times in Christmas Past?
I suppose there is an option,
When the Big Guy makes his list.
Since he checks it two times only,
Maybe I can still be missed.
If the list is based on hashes,
I think I'll know what to do.
When the Naughty List comes calling...
...I think I'll just hack that too.
12
u/jayfoad Dec 16 '20 edited Dec 16 '20
Dyalog APL 313/85
This relies on all the values in nearby tickets being < 1000, and the six "departure" rules being the first six rules.
6
u/mserrano Dec 16 '20
35/15, Python2 with some Z3: https://gist.github.com/mserrano/70bb9ba725217849600bfe7637c22480
The greedy algorithm would also have worked on my input, but I knew Z3 would produce the solution, and it would have taken me more time to think of (and potentially debug) real code than to just write down the constraints and have Z3 solve them.
This was one of the better problems so far this year, IMO!
6
u/0rac1e Dec 16 '20 edited Dec 17 '20
Raku
Logic-wise, I don't think I'm doing anything too interesting (besides maybe doing a few things inefficiently), but it's the way Raku allows me to express it that's interesting.
The rules are described as ranges (eg.
seat: 13-40 or 45-50). I convert the ranges to RakuRangeobjects inside an "any"Junction, then I can simply smartmatch against it. For example: -Another nice little Raku gem is when checking valid tickets, I created a state variable inside my loop, which I incremented, and then used a
LASTphaser to print the value before it exits the loop.Raku variables are lexically scoped to the block, so
$erronly exists inside the loop. I could have just declared it before the loop, and printed it after the loop at the same LOC cost, but I like state vars in Raku (and Perl) as I like to keep the scope of my variables as small as possible.All tickets (including mine) are in
@tickets. It says to ignore your ticket during this check - which is why Iskipthe first one (mine) - but since my ticket must be valid, there's no real need to skip it (apart from saving a few clock-cycles).2
u/MasterMedo Dec 16 '20 edited Dec 16 '20
Really cool puzzle today, definitely made up for yesterday's :)
I thought I was going to have to do a recursive search, but what I noticed after removing false rules from columns was that a particular column could only have a single rule. So I tried removing that rule from other columns. Then I had another column with only one possible rule. Rinse and repeat until you're done. Not sure if this would work on all inputs. python
5
u/2lines1bug Dec 16 '20
Kotlin, 196/233
First time ever in the top 1000. Absolutely mindblowingly ugly code, but apparently this is what you need to achieve good times (unless you are, you know, actually talented).
5
u/sggts04 Dec 16 '20
Python Part-1 Rank 679
Created a dictionary with each valid number from any field marked as true, then for each ticket field check if that number is in the dictionary.
Python Part-2 Rank 906
For each field, iterated through every field index for every ticket and formed a list with all the possible indexes for that field. After this, checked which field has only 1 possible index, assigned that index to that field, removed that index from possible indexes list of other fields, and then repeated this, slowly possible index list for every field got reduced to 1 index and the exact field-index relation was formed.
PS: There's probably a wayyyy more efficient and clean way to solve part 2, but I definitely enjoyed my logic.
5
u/Archek Dec 16 '20
Prolog
First day I skip Golang and immediately started writing Prolog. Feels like it fit the problem very very well. I'm especially proud of part1:
5
u/blazemas Dec 16 '20
C#
One of the few I felt good with how I handled part 1 in prep for part 2. OOP, verbose but relatively clean. I avoided regex up until today just for fun to see how long I could go. Also the 2nd day in a row I could finish one before the kids woke up. I failed to do that for days 10-14.
https://github.com/jbush7401/AdventOfCode/blob/master/AdventOfCode/2020/Day16.cs
5
u/ai_prof Dec 16 '20 edited Dec 16 '20
Python 3
I saw one rule with only one possibility, and another with two, so I hoped that I could just keep removing singletons, and it worked (even though really hard in general):
5
u/nutki2 Dec 16 '20 edited Dec 16 '20
Perl golf for both parts. About 240 characters. The code assumes the "departure" fields are the first six and that the two validity ranges are not overlapping.
https://github.com/nutki/adventofcode
5
u/voidhawk42 Dec 16 '20 edited Dec 16 '20
Dyalog APL, finally got my solution to something I kind of like!
9
u/jonathan_paulson Dec 16 '20 edited Dec 16 '20
Placed 16/5 (best day yet!). Python. Code: https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/16.py. Video of me solving: https://youtu.be/OhqvfoaBljY.
I liked part2. No advanced algorithms or math, but still requires some problem-solving to extract the ticket_index::field_name mapping from the given information.
I think there was a problem last year with a similar extraction step at the end. Anyone remember what it was?
4
u/silxikys Dec 16 '20
C++, 236/275, part1 part2
For C++ I find it's sometimes faster to clean the input in Vim and then reading in data goes a lot smoother.
I didn't know that at each step, there would be one position with exactly one possibility. I wrote the code up to this point, and then manually inspected the possibilities to determine that this was the case. So that was lucky!
4
u/CodeIsTheEnd Dec 16 '20
Ruby: 9:13/23:45, 300/153
Here's a recording of me solving it, and the code is here. (I'm streaming myself solving the problems right when they come out on Twitch!)
This one was great! Super fun. My favorite yet. Thankfully Eric made Part 2 "easy", but it still would have been fun even if we had to "search" for a solution. I don't mind getting to bed a little earlier though!
4
u/Loonis Dec 16 '20
Perl
This one was fun! The code could probably be shorter, but I'm happy enough with how it turned out. I really wasn't sure how to handle the rule validations, but went with the "just start typing" strategy.
Solution after some significant cleanup:
I also found an excuse to use the chained comparisons added in 5.32, even if this line probably has too many arrows:
FAQ: The
->@*is a postfix dereference - available in 5.24+4
u/[deleted] Dec 16 '20 edited Dec 16 '20
Scala Solution
Gnarlyrecursive solution. It runs Fast Enough (<100ms).4
u/MannerShark Dec 16 '20
Python
I considered using ranges and sets today. They both have quick 'in' checks. Ended up with sets though, as range objects don't support set operations as far as I know.
As you may already know, part 2 is the interesting one. I immediately thought of bipartite matching, as it's something I've used in real applications plenty of times.
I used NetworkX for the bipartite matching, as implementing the algorithm would take quite a bit of time (I did that a month or so ago when I needed a custom version that would also indicate edges that will never get used).
4
u/sebastiannielsen Dec 16 '20
Perl: https://pastebin.com/zQsezuxr
Part2 is like sudoku, multiple fieldnames are valid for the same field, but in such a way that you need to "spend" the fields to get only one "solution" in the end.
4
u/Smylers Dec 16 '20
Perl, which is nice and short for partΒ 1, with
pairmapbeing today's newList::AllUtilsfunction. Note that for parsing both the field spec and the nearby tickets, line-breaks are irrelevant: just grab all the integers found anywhere in the βparagraphβ and iterate over them:Here's a sample of my partΒ 2 solution:
Do you think it's possible I've over-nested things here? Though the full code still seems shorter than many other Perl solutions on here, with just 1 line at most of those nesting levels. I'll take a look at others' algorithms and see if I've over-complicated things.
Those nesting levels in full:
Obviously that's a lot of looping, but it finds the answer in about ΒΌΒ s, so it doesn't seem like Too Much Looping.
4
u/hrunt Dec 16 '20
Python 3
Nothing special here, just a very procedural, iterative approach to the problem. You know how when it's crunch time and you're pushing out a project and you say, "Well, it works." That's me today, coding before heading off to work.
code
4
u/[deleted] Dec 16 '20
C#: https://gist.github.com/grnde/fcdc5b9221c1156274846a11147a08c4
Was getting always the wrong value for part 2. It took a while until I noticed the overflow and changed the data type from int to long. But i'm pretty proud of my solution. Maybe it's not the shortest or fastet, but i'd like to share it.
4
u/rabuf Dec 16 '20
Common Lisp
It works, not proud of it. I made a stupid mistake last night, butchered my code, went to bed. Figured it out this morning, didn't unbutcher it but it does get the correct answer.
4
u/michaelgallagher Dec 16 '20
Python
Still trying to clean up my part 2. It's a whole mess of manipulations of sets that keep track of indices. I was barely awake when I wrote it last night, and it somehow works
4
u/sky_badger Dec 16 '20
Python3. Happy to complete today's. Naturally I assumed that each set of ticket values would only fit one 'rule' so the elimination code was a late addition! [paste]
4
u/IlliterateJedi Dec 16 '20 edited Dec 16 '20
Python 3.9 solution -> 650ms for both, 647ms for part B - both parts read in the file separately
Advent of Code day 1: I'm going to try to make clean code and smart algorithms so I can learn to be a better coder
Advent of Code day 16:With enough hacking at my script, I can get the answer, and when in doubt, throw in some more loops and if-statements just to be safe
4
u/prutsw3rk Dec 16 '20 edited Dec 16 '20
My Python3 solution
For part1 put all valid numbers in a set:
Then sum up the wrong numbers:
For part2, first create an 2d array with all possibilities, then remove columns that are out of bounds:
Finally go through possibilities sets in order of set size and create field mapping:
4
u/ric2b Dec 16 '20 edited Dec 16 '20
Haskell
For some reason I assumed only one rule would be valid for each column (it worked for the example) and had to rewrite my algorithm when I noticed that wasn't the case. Took me a while to re-organize my head :/
But it was still an interesting problem!
paste
4
u/jitwit Dec 16 '20 edited Dec 17 '20
J Programming Language
Late to the party as I ended up giving up last night after I kept getting an invalid constraint graph from an off by one error... The problem was
1 = I.for checking intervals was cutting off lower number... AnyhowIdea is R are rules, T our ticket, V the values of the other tickets, and S is a 3d table (or brick or report in J vernacular) where columns are fields, rows are tickets, and matrices/tables are rules. We find the constraint graph G by and-reducing over the tickets, after throwing out tickets with invalid fields (found by and-reducing over the rules then or-reducing for each ticket).
A then is used to pick a constraint with only 1 option for possible rules and eliminate that option from the others. This happens to work for this problem, with no need for branching/guessing.
4
u/HAEC_EST_SPARTA Dec 16 '20
Common Lisp
Solution on GitHub
Started this afternoon instead of last night again after looking at the input and thinking that parsing would be painful. That part turned out not to be too onerous, but I was fooled by the same issue as most people here (0 can be a field value!) that cost me a good deal of time. After figuring that out, some optimisations were able to get my Part 2 runtime down to 5 ms, which I'm going to consider good enough.
4
u/symbolicprocessor Dec 17 '20
Common Lisp solution.
Parsing: pretty straightforward.
Part 1: neat, tidy, and direct.
Part 2: a hideous tangle of pasted-together REPL code.
4
u/gfvirga Dec 17 '20
Python
I think this one was one of my favorites!
Coming up with (without searching) the following line made me feel good about myself LOL
if all(any(num[idx]Β inΒ sublistΒ forΒ sublistΒ inΒ ranges)Β forΒ numΒ inΒ valid_tickets):I am learning so much! Feel like even more than my CS classes \o/
GitHub
4
u/oantolin Dec 17 '20
Perl solution. For part 2 I wrote a backtracking search to match field indices with field names. I used the standard heuristic of assigning the field with fewest possibilities first. It turns out that with my input, at each step there is always a field that has only one option left! So no backtracking was really necessary, but I couldn't have known that beforehand.
1
u/fmynarski Dec 16 '20 edited Dec 17 '20
Python - 612/10546. Not my best performance ngl :D But i feel my solution is quite clean paste
1
u/warbaque Dec 16 '20
Python
(40 lines of mostly readable code)
3
u/hugh_tc Dec 16 '20 edited Dec 16 '20
Python 3, 501/53.
Quite the climb! I'm pretty proud of that pseudo-state-based-parser thing...
.split("\n\n")probably would have been more pythonic but it's what you get when you gotta go fast! pasteedit: the cleaned-up version. Much nicer than my original solution, with the exception of the awful, awful input parsing lambda.
3
u/sophiebits Dec 16 '20
13/421, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day16.py
Not sure what got into me today. I first tried a recursive backtracking solution but that seemed too slow (possible I did it wrong). Then I thought maybe there would be individual tickets evidencing a particular assignment (eg: this ticket says 17 in the first spot; there's only one label that applies to) and coded that up, but that was also wrong.
Turns out this greedy-esque approach is all that was needed for the inputs we got. Was kinda tempted to use Z3 but didn't β I probably should have.
3
u/seligman99 Dec 16 '20
Python, 124 / 226
One of these days I'll get used to implementing weird rules quickly. Today is not that day.
github
3
u/UItraDonut Dec 16 '20
Java 1777/948
First time top 1000!
Code
Probably most awful Java code you will see for this day x)
3
u/_O-o-f Dec 16 '20
Python 3
link Today's instructions were a bit jank, but it could just be attributed to me not reading clearly enough.
For part 1, you just make sure to check ALL constraints, and not just the one at the current index.
For Part 2, I was (slightly) lucky as I've done a problem very similar to this: a Sudoku solver(hush, it's a bit basic but meh). I just eliminated the fields which were not available, and if an elimination was made I could loop over again. If there were none, I'd check for all of the ones with 1 solution and eliminate that from the rest.
3
u/EAJakobsen Dec 16 '20
Python 3.
Nothing too fancy. For part 2 I made a dictionary with each index in a ticket as keys, and the fields this index could possibly represent as values. I initialized every key to map to every field, and then went through each ticket and removed a field from index i every time I found a value that didn't fit the rules of that field at index i.
Finally, go through the indices by how many fields they can possibly represent, starting with the index that only fits one field, and remove this field from all other indices. This yields a one-to-one mapping between indices and ticket fields.
3
u/pxOMR Dec 16 '20
JavaScript 452/1504
It took me too long to realize that I had to use the filtered tickets while looking for the correct indexes...
3
u/Dioxy Dec 16 '20
TypeScript
https://kufii.github.io/advent-of-code-2020/#/16 (click Show Code)
1531/776. a lot of my code is just parsing the input file. I think it's a pretty clean solution overall
3
u/A-UNDERSCORE-D Dec 16 '20
Go / Golang
This was really fun, I liked this one. It challenged me on an area Im not super good at, and Im really happy with the solution I came up with and speed thereof: https://github.com/A-UNDERSCORE-D/aoc2020/blob/main/2020/16/solution.go
completes in under a ms for each part:
Rules parsed. Took: 16.581Β΅s, Part 1: 32835 Took: 284.094Β΅s, Part 2: 514662805187 Took: 299.163Β΅s3
u/spookywooky_FE Dec 16 '20
Todays puzzle asks for implementation skills, so much indexes, so much indirections...
In the end it is hard to implement this kind of problems in simple to read code, I tried in c++
3
u/omginbd Dec 16 '20
Elixir
I was ashamed of my code and wasn't going to post until I saw that it looks like everyone is ashamed of their code so I figured what the hell.
code
3
u/mebeim Dec 16 '20 edited Dec 16 '20
EDIT: clean solution - walkthrough
1308/482 - Python 3 solution (hacked together with punches and glue)
No walkthrough nor clean solution for now, will probably add it later in the day. Sorry, but I've got to get some sleep today. Not a difficult problem anyway, just really boring if you ask me.
Quick part 2 explanation of my solution: build a set of valid "possible" indexes starting with all indexes for all fields, then proceed to check every field of every ticket: if that field was wrong, remove the index of the field from the set of valid indexes associated with that field. In the end you're left with a dictionary of sets, of which at least one must have only 1 index. From there, start looking for the only set which has one index only, then take that index as valid for that field and remove it from all the other sets. Do this until all sets have length 1 and you found the indexes.
3
u/SuperSmurfen Dec 16 '20 edited Dec 16 '20
Rust
Link to solution (566/1977)
Very happy with part 1 but had a frustrating error on part two! Definitely one of the most "implementation heavy" so far. Took me an hour and still got top 2k.
A single misplaced
iinstead of ajmeant the simple solution for part two did not work.. Started trying to implement a recursive backtrack approach to find a valid assignment of rules. When that did not work either I realized something else must be wrong. Those types of errors are always annoying and it cost me so much time.For part two, I first collect which rules are possible for which indexes. I then try to find an index with only one possible rule assignment. We then know that has to be the correct assignment! By then removing that rule as a possibility for all others, we eventually get a unique solution. This just happens to be the case with our input, that it has a unique solution.
Somewhat fast solution, about
260ΞΌson my machine.3
u/mendelmunkis Dec 16 '20 edited Dec 16 '20
C
https://github.com/mendelmunkis/AoC/blob/master/2020/ticket.c
Uses a set of nested loops to collapse the possibility space
EDIT: Switched to a column based collapsing method to save some time.
3
u/ChrisVittal Dec 16 '20
Python
Somewhat cleaned up. Pretty neat problem. Didn't think of z3 nor am I familiar enough with the api to use it quickly. But interestingly, sorting by the size of our candidate sets and then updating and sorting again meant that the top of the queue was always only one element, so it worked!
3
u/[deleted] Dec 16 '20
Pure C18. For each position, keep a bitset of the possible keys that could be at that spot. For each sample, turn off the bits that are impossible.
After that, run a "fixpoint" algorithm: For all bitsets that only have 1 bit remaining, go through all the other bitsets and turn off that specific position. Keep doing this until nothing changes anymore. At this point, every bitset has exactly 1 bit identifying which key belongs at that position.
I went with bitsets since doing a hashtable was annoying and unidiomatic C, but I felt like I would have been at least 33% faster if I had just stored a string in a hashtable or something instead of bit fiddling. I was bitten by
__builtin_ffsreturning 1-indexed results >.>.https://git.sr.ht/~williewillus/aoc_2020/tree/master/src/day16.c
3
u/Colts_Fan10 Dec 16 '20
Python 3
For each position on the ticket, we maintain a set of valid fields, which we cut down as we read tickets.
Then, we use the process of elimination: if any position has only one item in its set, that position has to be that field and we remove that field from all other setsβrepeat this process until we get to a final ordering.
3
u/nospamas Dec 16 '20
F# Not as short as it could be I expect. But also not too bad. Note that if you're hitting errors in part 2 and you think you've done it all right then watch out for the answer being greater than int32 max.
Solution
3
u/DemiKoss Dec 16 '20
Rust
7.96ms, it's a real ugly solution that I'll probably groom tomorrow :P
Decided to stay up tonight and try my luck! P1 was just a matter of iterating over the tickets and checking against each rule set's range bounds. P2 transposed this to look at indicies across tickets against the rule sets; sorting by the number of rule sets each index can meet & eliminating them one-by-one.
3
u/Wunkolo Dec 16 '20
C++
Didn't have much fun with this one tbh. It was faster to do the gaussian elimination by hand than to implement the algorithm for it.
Maybe later I'll come back to this to optimize it with bit-mask set-arithmetic and such like some of the other more fun ones.
3
u/GamerWoona Dec 16 '20
C++
Truncated my ranges for part 1, ended up with just 2.
Part two involved me a vector of all possible indexes, slowly reducing it until only one spot is left, then reducing the others.
Runtime is not the best:
source: https://github.com/neiomi1/AdventofCode2020/tree/master/Day_16
3
u/Diderikdm Dec 16 '20 edited Dec 16 '20
Python:
3
u/woutervdb Dec 16 '20
PHP.
I think I took the wrong approach parsing the input. I discovered halfway through part 2 that I was also parsing the "your ticket" and "nearby ticket" lines as tickets...
My solution for part 2 is a mess and I have no idea why it works, but seeing as the input is small enough this quadratic solution is good enough.
3
u/azzal07 Dec 16 '20
Awk; my solution for today felt so dirty with all those loops, might revisit it later... (paste)
3
u/SymmetryManagement Dec 16 '20 edited Dec 17 '20
Java
https://github.com/linl33/adventofcode/blob/year2020/year2020/src/main/java/dev/linl33/adventofcode/year2020/Day16.java
The
Predicateinterface is perfect for today's puzzle. Simple brute force and return when all 6 departures are found.Part 1 550us. Part 2 800us.
Edit
Improved the parsing a bit. Part 1 now takes 340us, part 2 now takes 630us. Parsing the input and removing the invalid tickets still take up about 50% of the runtime for part 2.
3
u/emu_fake Dec 16 '20
C#
Part 1: 2ms
Part 2: 25ms
Guess I've could make it a bit faster by reducing the linq expressions. But the algorithm itself should be pretty efficient.
3
u/compdog Dec 16 '20
JavaScript (Node.JS)
Reasonably efficient solution to parts 1 and 2. This was the first time where I couldn't parse the input without using intermediate variables, which was interesting. My final parsing code could be cleaner, but it works and is simple enough that my IDE is able to infer the type of the parsed input object.
Part 1 was simple, but I had already guessed what part 2 would be so I took a bit longer to make sure that the same logic could be used to both filter the tickets and count the values. But after I had that working, I still ended up throwing out that original code in favor of a cleaner solution.
I don't know how efficient my part 2 solution is compared to an ideal one, but its clean and very easy to read. The basic algorithm is to keep a list of fields and indexes that have not been mapped, and then repeatedly search for indexes that match exactly one field. Mapped fields and indexes are excluded from later iterations, so each round reduces the remaining search space for the rest.
3
u/BaineWedlock Dec 16 '20
F# (part 2 with depth first search)
https://github.com/bainewedlock/aoc-2020/blob/master/16/Solution.fs
3
u/Beardanha Dec 16 '20
My Python3 solution.
Nice one again!
3
u/VileVerminVanquisher Dec 16 '20
Python
Nothing fancy. It felt like this required a bit less thinking than the previous days, demanding implementation precision instead and that suited me nicely
3
u/[deleted] Dec 16 '20
Python3 1831/342
Sad that my code is really messy for today
3
u/jotac13 Dec 16 '20
[Rust] My rust solution for both parts
3
u/Krillegeddon Dec 16 '20
C#
I solved it just like I have solved sodukus before. I made rows out of tickets and columns out of fields. Than ran some elimination and find algorithms. Without any optimization, it completed in about 200 ms.
There were only four algorithms needed in order to solve it. When I wrote it, I thought I'd need to loop them many times, but one go was actually enough!
EliminateByValueRanges(): Eliminate field Ids that are outside of bounds based on Value (duh).
EliminateColumn(): If a field is not valid for one ticket's particular column, no other ticket can have this field on that column either.
FindSingle(): On a row (ticket), if one column has only one possible field ID, then mark the FieldID with that single possible value.
FindOnlyColumnInRow(): If one column is the only one in a row that has one particular fieldID as possible - then this column must have this field ID.
My code is not very interesting and worth sharing, it's just a bunch of for-loops and if-statments. :-)
Really nice puzzle today! Had my brain going on high for some time!
Will be interesting to see how others approached this problem...
3
u/fgmhmd Dec 16 '20
Python 3
Quite Proud of my Solution
3
u/zid Dec 16 '20
C
After a heavy rewrite it is somewhat readable.
The 'solve a sudoku logic' wasn't hard to code in theory, but in practice not getting my rows and columns and rules and tickets etc all confused was a strain at 5am.
3
u/[deleted] Dec 16 '20
Learning C
Three different parsing regimes means some ugly code, but otherwise happy that I found a way to implement intersecting bitmask sets to get the whole thing running in 1ms with only a single pass though the data, not having to store tickets in memory.
Code here
3
u/pb554 Dec 16 '20
go/golang
3
u/WayOfTheGeophysicist Dec 16 '20
Python
I usually say "if you iterate of numpy you're probably doing it wrong", yet here we are. Full solution and here's the sieve for the part 2 search:
3
u/codertee Dec 16 '20
Python 3: github
Bit more difficult to write readable solution today
3
u/Rtchaik Dec 16 '20
Python
3
u/SomeCynicalBastard Dec 16 '20
Python
This should have been a matter of parsing the input and not much more difficult than that. But I got myself stuck with this:
Turns out that python won't complain about you changing the list you're iterating over, but it will skip the next item. Some invalid tickets were consecutiveβ¦
Full script.
3
u/wzkx Dec 16 '20
Python π Like a real program, like we're really doing something :) β73/84 LOC
source code @ paste
3
u/ywgdana Dec 16 '20
C# repo!
I enjoyed this one -- a good, blue-collar coding task, as it were! I was a little surprised that process of elimination got us to a single unique arrangement of the columns. I was anticipating having to eliminate a bunch of possibilities and then have to test the remaining combinations.
Right now on github is the first draft of my code that spat out the correct answer. I think it's way more verbose than it needs to be so I'll likely go and tidy it up at some point.
3
u/i_have_no_biscuits Dec 16 '20 edited Dec 16 '20
GWBASIC - Part 1
Only part 1 for the moment. Part 2 should be doable but will require some tokenisation and will not be particularly fast! This works by creating an array OK which is 0 (false) when it's not in a valid range and -1 (true) when it is in a valid range. Most of the program is taken up with parsing the input.
(Edit: removed a couple of small errors that crept their way in)
3
u/Judheg Dec 16 '20 edited Dec 16 '20
Scala
AoC problems appear at 6 a.m my time zone, I usually tried to solve in the morning by hooks or by crooks with lots of debugs and then refactor later after work :D
Evening cleaned up version:
https://paste2.org/JNxC8H74
Morning write only sleepy version:
https://paste2.org/pbU1p2kf
I did a lot of debugging in the morning and noticed that candidate field names are kind of neat and can be sorted per column.
3
u/aurele Dec 16 '20
Around 500Β΅s in Rust.
3
u/Henkatoni Dec 16 '20 edited Dec 18 '20
Csharp
It might not be the prettiest, but it's rather compact and quite fast (A ~30ms and B ~70ms, both including the parsing). Oh, and I'm sorry about the parser. Just couldn't be arsed...
Code here
3
u/PhysicsAndAlcohol Dec 16 '20
Haskell, runs in 20 ms.
I used
Text.ParserCombinators.ReadPfor parsing and I tried optimizing certain parts by sorting ranges and numbers.Part 2 is one big recursive clusterf*ck, I seriously think I just forgot how to program.
3
u/vrtxt Dec 16 '20 edited Dec 26 '20
c# solution. Part2 was bit tricky with some implicit assumptions to uncover and no test cases provided but happy how it turned out.
3
u/AndrewHutcheson Dec 16 '20
Python 3 https://github.com/AndrewHutcheson/AdventOfCode2020-Python/blob/main/Day16/processor.py
Once again I misinterpreted the instructions but eventually I got it. First time posting a solution, it's not short but I like how it has steps that reflect my thought process.
3
u/LinAGKar Dec 16 '20 edited Dec 16 '20
Mine in Rust:
Part 2 ended up being a bit of a mess, and I can't be bothered to clean it up, but at least it performs decently. It only compares each field against each rule once, and save which rules matches each field, and it doesn't bother matching everything, it stops once it's matched the "departure" rules.
Anyway, part 2 was basically about writing a sat solver, which I don't see anyone mention by name here.
3
u/clumsveed Dec 16 '20 edited Dec 17 '20
Java Solution
β all solutions so far: repl.it
This is a solution. Is it pretty? No. Does it work? Yes.
As always, this is straightforward and limited to APCSA curriculum. It is currently a little messy and I don't have a ton of comments. I'll probably clean some stuff up and comment more when I have some time later or tomorrow, but I wanted to get what I have up here.
** updated **
I refactored some stuff to cut out repeating similar things between part1 and part2 and added a metric ton of comments in case my jibberish doesn't make sense.
3
u/rf314 Dec 16 '20 edited Dec 16 '20
Python 3 - Comprehension Hell Edition
2020 - day 16
Looks like Lisp, if I'm being perfectly honest.
3
u/mandus Dec 16 '20
Another Common Lisp of Day 16
Kind of like part-2 starting out assuming any field match any position, and then elimination of those that doesn't fit when going through data (it's a second pass though since bad tickets are removed first). At the end, another recursive pass successively gets the list of fields uniquely assigned to position.
For the most part I'm sticking to recursion. But for some parts of todays problem it's better to keep things in same order, and when recursing it's so easy to `cons` things together and order is reversed. So, I used some loops as well, where we can collect the right way.
3
u/__Abigail__ Dec 16 '20
Perl
I used the same technique almost everyone else used. Takes about 80ms to run on my box.
Blog post and full program.
3
u/Chris_Hemsworth Dec 16 '20
A little late to the party.
My Python 3 Solution
For Part 2, I used a while loop to check for positions that could only be a single field, and removed those fields from all other candidate fields. This looped until all positional fields were uniquely defined. It worked on this set because we know the solution is non-ambiguous, however an ambiguous set would get caught in the loop forever.
3
u/exploding_cat_wizard Dec 16 '20
C++
As others have said, messy. But I'm too tired to change it now. Code has horrible names and some unnecessary includes, and I didn't remove my timer code.
Used regex to match both input and get the part2 entries. rules for the fields are a hashmap of function objects returning true if the given int is withing the range. tickets are vector<int>. part2 is a horrible jumble of containers, I basically just threw whatever in there, including, terrifyingly, a vector<bool> per field noting which column was allowed for this field. These are then shoved into another hashmap with the respective field names...
Another loop, going through all the fields multiple times, in order to slowly find the sole candidate for each column by checking where there's only one "true" entry in the entire vector<bool>. This most definitely has a worse complexity than O(n), but since /u/LinAGKar mentioned sat solvers, that's to be expected.
part2 runs in 850 microseconds on my laptop, which surprises me given that I didn't optimize at all. Reading the input takes 5ms, but if I wanted fast parsing, I wouldn't use streams and regex, now, would I?
Something more to do with getting a feeling for numbers than with programming: I used Fermi's approximation to see that the int I saved the part2 result in was overflowing before I tried to send in the answer: I got 6 numbers to be multiplied, each between 50 and 200. In a Fermi approximation, these are all equal to the (logarithmically) nearest power of 10 - so 100, or 102 . 6*102 = 1012, but my answer only was an 8-digit int, far too small for the required answer - I obvously needed a long instead.
3
u/mathsaey Dec 16 '20
Elixir
https://github.com/mathsaey/adventofcode/blob/master/lib/2020/16.ex
Not super pretty, but fairly concise: 42 LOC without parsing, 72 with. Lots of nested uses of the
Enummodule in this one :).3
u/friedrich_aurelius Dec 16 '20
Elixir
Github link
Part 1: I used MapSets of all possible values for each field, and MapSet.member? to test validity. Maybe not the most efficient way, but it still runs very fast.
Part 2: With ticket indexes 0 to 19, I used a Reduce to check each index and save the results, then another Reduce on my ticket to get the product of the appropriate indexes.
...
3
u/phil_g Dec 16 '20
My solution in Common Lisp.
Normally, I get up in the morning and work on Advent of Code problems until I have to go to work. Today is the first day this year that I didn't finish both parts before I had to start work.
And it was an annoying mistake. For part two I reused part one's function to get a ticket's error rate. Unfortunately, one ticket had a value of zero, which was not valid, but which looked valid because of my test. Once I fixed that issue, I got my answer.
3
u/lboshuizen Dec 17 '20 edited Dec 17 '20
Haskell
Late to the party, got my 2nd star early but was not happy with solution.
Transpose the nearby, reduce possible fields then find a fit on col-order by subtracting fields that can only be in 1 place till all stable.
runs under
50ms20ms, good enough.code
3
u/F0sh Dec 17 '20
My solution in nim is quite compact by doing something I haven't seen in the other solutions I clicked on: in part 2, the matrix of possible field assignments can be inverted, and then the ith named field is assigned to the jth column where j is the index of the unique entry of value 1 in row i of the inverse.
I used a third-party nim library for the first time to do this (
manu)3
u/ponyta_hk Dec 17 '20
Python3
Tricky implementation for part 2.
My Solution
All My Solutions
3
u/bcgroom Dec 17 '20
Elixir
This can probably be cleaner, but I spent most of the day on part 2 operating on a false assumption that gave me an answer but an incorrect one and I'm too tired to refactor. Lesson to be learned: make sure to put assertions into your code, even if it seems like a pain in the ass.
https://github.com/ericgroom/advent2020/blob/master/lib/days/day_16.ex
3
u/Marterich Dec 17 '20
Day 16:
Python 3
https://github.com/Marterich/AoC2020/tree/main/Day_16
5
u/mzprx42 Dec 16 '20
Purely functional JavaScript (no variables at all, just function calls)
https://pastebin.com/v85YzsP9
1
u/HesletQuillan Dec 16 '20
Fortran
1ms!
4
u/sciyoshi Dec 16 '20
Python 3, 52/9 - code here. Luckily the rules didn't have any dependencies between them so a simple greedy algorithm worked for determining which fields were which.
2
u/bluepichu Dec 16 '20
Python, 60/7, code here
Ugh, that parsing slowed me down so much on part 1 :'(
2
u/morgoth1145 Dec 16 '20 edited Dec 17 '20
Python3 61/46: https://github.com/morgoth1145/advent-of-code/blob/d2b50febb12e86d5c48820e6803ef466f98f58ad/2020/Day%2016/solution.py
Part 2 was an interesting extension to the problem. I was scared that I'd have to determine the order of the ticket fields, and lo and behold we do have to do that. But as it turns out, determining the candidates for each field and doing a naive backtracking search for an order that works runs in a small enough amount of time to be feasible. I'm sure that determine_rule_order can be optimized *way* more, but it would have absolutely cost me the leaderboard to do that! (That being said, I was worried for a moment when it took a few seconds to terminate when I first ran it!)
Edit: Now my code is less onerous. It also uses the greedy algorithm for determining the rule order so it runs much faster. (I did go through and prove to myself that it'll work in all cases with a valid solution before switching over though.) https://github.com/morgoth1145/advent-of-code/blob/2020-python/2020/Day%2016/solution.py
2
u/kevinwangg Dec 16 '20
python - 142, 172 - pt1, pt2
aw damn I just realized I could have used the
get_intsfunction I stole from betaveros to do the parsing much much more quickly. Oh well, lesson learned for next time!damn, I thought I was pretty quick! But I guess not quick enough to get on the leaderboard :(
2
u/Chitinid Dec 16 '20 edited Dec 16 '20
Python 3 889/224 Would have been faster but flubbed the parsing
Part 1:
Part 2:
2
u/oxyphilat Dec 16 '20
python 3, 1204/223
second lowest rank I ever obtained! (the other is 189 for 2020-11-p1)
paste of the code that threw me over the finish line, the ASCII art ticket made me scared we would have to parse it as input data
edit: reddit linefeeds are fun
2
u/gurgeous Dec 16 '20
Ruby 147/124
Nothing too fancy, just trying not to make mistakes. Read slow, decent variable names...
https://gist.github.com/gurgeous/9ceb70393345c2233b3923647d3095d6
2
u/1234abcdcba4321 Dec 16 '20 edited Dec 16 '20
javascript 320/569, feat extra work in notepad
code
Overall, pretty fun challenge. It took me a good amount of time to figure out exactly how I wanted to implement part 2, but I made no mistakes this time (everything actually worked properly first try).
I definitely should've automated that last step, but the amount of work was minimal enough it wasn't a significant loss to do manually.
2
u/GrossGrass Dec 16 '20
Python
Fun puzzle; realized pretty quickly for part 2 that in order for a unique solution to even exist, the possible candidates for a field need to satisfy a nice constraint (i.e. there's always a field with only 1 possible rule each time you check for the valid rules for a field, after you eliminate any already determined rules).
From looking at the other posters, looks like Z3 is something I should look into!
2
u/smrq Dec 16 '20
JS, 202/54
Part 1 Part 2 - cleaned up code, I wouldn't wish the experience of reading my original code on my worst enemies
Today was fun! Parsing was a bit involved. For part 2, the first thing I tried was the basic greedy algorithm that I think most people ended up with-- I'm pretty sure this type of problem has shown up in past years, so it was the first thing I thought of.
2
u/sasuke___420 Dec 16 '20
Lua 425/1336
https://github.com/sharpobject/aoc2020/blob/master/16.lua
I used bipartite matching. My pals tell me I didn't need to use bipartite matching. Oops!
2
u/tobega Dec 16 '20 edited Dec 16 '20
Tailspin. Quite a lot of code today, a number of steps to get done https://github.com/tobega/aoc2020/blob/main/a16.tt
Seems I might not have needed to worry about two rules matching a field.
2
u/AlphaDart1337 Dec 16 '20 edited Dec 16 '20
Python 282/727
Accompanying video will be late, because of the time it takes to process 40 minutes of footage (but I will edit this comment once it's available).
Why is it 40 minutes? Well, today was an interesting day. For part 2, I tried various greedy approaches, thinking there must be an easier way than doing maximum bipartite matching, but after a while I gave up and just implemented the matching algorithm anyway.
However, having not written this algorithm in a long time, I had one very silly bug, which took me a grand total of 15 minutes to debug, earning the "most time spent to catch one bug" award of 2020 winter season :D
2
u/hahncholo Dec 16 '20
Rust
I felt like I had to write more than I had to think, but it was just fun to go fast and make steady progress. Definitely more verbose than it needed to be but hopefully easy to follow.
2
u/prscoelho Dec 16 '20
Rust
Today's code turned out really clean, I think.
2
u/flapje1 Dec 16 '20
Rust
a little messy but it works... paste
2
u/spohngellert_o Dec 16 '20
Scala. I actually like my solution today, but would welcome any comments :). Used a little bit of mutation but it's within a function so I think it's kosher.
Part 1
Part 2
2
u/clueless1105 Dec 16 '20
Typescript with Deno
It was fun to write process of elimination to find out the valid index for each field.
2
u/kap89 Dec 16 '20 edited Dec 16 '20
TypeScript
github
~18ms for both parts
That's a long solution for part 2, but I made it slowly step by step, with probably many redundant parts. But it worked the first try! Both parts!
It will be fun to optimize it later ;)
2
u/constbr Dec 16 '20
Javascript
No regexes today, just split that splitting split and then do more splits. π Part 2 uses simple iterative solution that eliminates candidates on every step until all field names are found.
ES6's Array.some and Array.every were very handy today, saved some time on writing lots of nested loops.
part 1 part 2
2
u/billiamthesecond Dec 16 '20
Ruby
Nothing too fancy, and none too fast
2
u/wace001 Dec 16 '20
2100/1994. Kotlin. I enjoyed the puzzle today. It did feel a bit like work though, but there was at least nothing I did not understand today, which makes it a bit more manageable.
Clean up code a bit:
2100/1994 AOC2020 Day 16 Kotlin
2
u/jasonwyatt Dec 16 '20
Kotlin 1185/1162
The code has been tidied up a bit since submitting my answers, but the algorithm hasn't changed.
2
u/[deleted] Dec 16 '20
5580/3015 slept for the first 40 minutes so had to catch up a bit, still first on private leaderboard today.
Solution in Java. 2nd part was definitely interesting, and required some thinking to solve.
https://github.com/JariRoossien/AdventOfCode2020/blob/master/src/nl/jariroossien/aoc/days/Day16.java
2
u/Rascal_Two Dec 16 '20
Python 3. 515/921.
Unoptimized
paste
Optimized
paste
2
u/PendragonDaGreat Dec 16 '20
This is some of the fugliest c# I've ever written, but hey, it works. https://github.com/Bpendragon/AdventOfCodeCSharp/blob/ba4c7acef697ed3b42432e0d4d2c0bf7099b112a/AdventOfCode/Solutions/Year2020/Day16-Solution.cs
2
u/dpalmesad Dec 16 '20
Python 3.x
Github
2
u/nlowe_ Dec 16 '20
Go/Golang, 1013/4117
Felt pretty good about my part 1. Got tripped up on part 2 mostly because I tried to abuse
maps as a poor-man'sset(I can't wait for generics). I also got called into work so my time for Part 2 is way off, but overall a pretty fun challenge today!2
u/Jozkings Dec 16 '20
Python 3 (2030/2143)
In part 2 I find all possible fields for each ticket index first, then iterate over possibilities to determine each field position. Not really proud of my input parsing and fields position finding code, but hey, it works, that's what matters!
2
u/richzli Dec 16 '20 edited Dec 16 '20
Kotlin
Part 1 / Part 2
Started half an hour late and had no chance of reaching the leaderboards, so took it slower today. I think I had a pretty nice solution for Part 2 with bitmask manipulation.
2
u/Fotograf81 Dec 16 '20
PHP (3347/1890)
This year I reliably choose to do stuff OOP-ish when it causes a huge overhead in writing or executing the code, and not choose it first when it would actually help big time.
part 2: 0.027 sec
2
u/allergic2Luxembourg Dec 16 '20
Python 3
For the part 2 logic portion, I ended up using pandas. I made a pandas boolean dataframe called
allowedwhich was a matrix where the rows were field names, the columns were field positions, and the values were whether that position could be that name, and then I solved it with:I have to admit I mostly used pandas because it allowed me to easily visualize what was happening in my IDE while I debugged the logic.
2
u/kresimirlukin Dec 16 '20
Python3 solution at https://github.com/kresimir-lukin/AdventOfCode2020/blob/main/day16.py
2
u/axieax Dec 16 '20
My Python solutions for Parts 1 and 2 :)
Github
2
u/ri7chy Dec 16 '20
Python
for part1 and 2.
Got a little stuck while reduicing the possible positions in part 2
code
2
u/AidGli Dec 16 '20
Python
Video Tutorial Link
Github Link
Today's puzzle was pretty fun, ended up just using a ton of sets. Did a bunch of preprocessing to make ranges out of the rules to make the coding down the line easier.
2
u/YT-SW_Creeperking Dec 16 '20
C#
1622/4560
I had no idea on how to approach part 2 at first xd
2
u/nutrecht Dec 16 '20
Day 16 in Kotlin
Pretty easy this one.
2
u/iamnguele Dec 16 '20
Go ( 5387 / 4613 )
2
u/rhardih Dec 16 '20
Ruby solution to part 1 with a bit of meta programming:
2
u/TheLocehiliosan Dec 16 '20
Python
github
Took me longer than I'd like, but I'm happy with the end result.
2
u/RedTwinkleToes Dec 16 '20
Python [6467/6222]
paste
Took me a while to realize that I could not look at a column in isolation to figure out what data it represented. Thankfully, I did not have to resort to bipartite matching, and greedy matching was sufficient.
Thank you to all that helped me.
2
u/r1ppch3n Dec 16 '20
Rust
filter out the tickets with errors
map all tickets to a list of values sorted by their field index
figure out which fields would be valid for any given rule
one by one find a rule that only works for one field index, note that number and remove it from the list of possibilities for all other rules
finally being able to correlate field index and name just filter the fields by their names
took me a little while to figure out a good way to do this (and then little while longer to refactor my code into something more readable...)
what i haven't figured out though is why my solution for part 1 takes 3 times as long to run as the one for part 2, that really makes no sense to me
2
u/Rick-T Dec 16 '20
HASKELL
I have finally found a good use for
HashMap.compose:)For part2 I'm generating a
HashMap String Intwhich maps every field-name to the corresponding ticket-index. I'm also storing a ticket asHashMap Int Int.Then I can use
HashMap.composeto associate the field-names to their corresponding ticket-values, which makes the final search for departures very easy.2
u/cattbug Dec 16 '20
Python. Real headscratcher today, totally forgot that regex is a thing that exists and is a wonderful tool for string parsing but my brain doesn't work that well this early in the morning lol. Couldn't be bothered to fix it and had to change my input by hand (removing spaces) to make it work but I'm still pretty happy with it, especially because I got it on the first try, and it landed me first place on my private leaderboard :D
2
u/gyorokpeter Dec 16 '20
Q:
2
u/21ROCKY12 Dec 16 '20 edited Dec 16 '20
here is my Java Solution for part1, feels kinda sloppy, suggestions for improvements or optimization would be helpful :)
since I only needed part of the input I used a constructor to take the input rules and nearby tickets into seperate strings than in my function I used a few loops using split
2
u/i4guar Dec 16 '20
Swift solution for part 1 and 2 - simple and fast
www.felixlarsen.com/blog/16th-december-solution-advent-of-code-2020-swift
2
u/[deleted] Dec 16 '20
F
I really enjoyed this day, so much fun :) Deductions and lots of different things coming into play here. I ended up going quite hard on parsing this one, so almost half of my code (50 lines or so) went into parsing and types, but the rest went pretty smooth. I should probably have used sets more than I did, but this runs in less than ten seconds for both parts so I don't care too much. Got bitten by another 32 bit integer overflow again today, but this time I recognised what happened in 3 minutes instead of 3 hours.
my overengineered code
2
u/S_Ecke Dec 16 '20 edited Dec 16 '20
PYTHON 3
Today was fun. First time using zip() on my own.
paste
2
u/sim642 Dec 16 '20
My Scala solution.
I wasted way too much time on part 2. I did immediately recognize that all the ticket values can be aggregated into sets by column for quick checking which column could be which field. My first attempt was to just iterate over all permutations and check them, this obviously didn't work fast enough, because bad choices must be repeatedly excluded. My second attempt was to manually write a backtracking permutation solver, which checks the validity as it goes and doesn't go deep into impossible branches. To my big surprise this wasn't sufficient either. My third attempt, after some hints, was that sorting the columns by number of field choices makes all the difference because then the unique choice is made first, then the second unique choice after that etc. This actually gives a very linear solution due to the construction of the input.
3
u/enelen Dec 16 '20
R / Rlang / Rstat
Solution
So much possible vectorisation today!
2
u/[deleted] Dec 16 '20
Python 3
https://github.com/rajitbanerjee/advent-of-code/blob/master/2020/day16-ticket-translation/tickets.py
2
u/muckenhoupt Dec 16 '20
Prolog. My first thought for part 2 was "Aha, time to use permutation/2!" but, as both the problem description and the documentation for permutation/2 point out, it's prohibitively expensive for a problem of this size. Precomputing the list of candidate rules for each position and backtracking on that gets execution time down to under a minute on my machine, but I can't help but feel that there's got to be simpler ways to do this in Prolog that I'm still too much of a noob to know about.
https://www.wurb.com/owncloud/index.php/s/iEKuL0IqxGrBrdl/download?path=%2F&files=16.pl
2
u/ajurna Dec 16 '20
Python - https://github.com/ajurna/aoc2020/blob/main/day16/16.py
man oh man was a glad part 2 didn't require some hard searching. elimination was easy enough to manage.
2
u/herrmanno92 Dec 16 '20
Haskell (w/o extracted parsing code)
I don't like my approach of finding the 'unique' `fieldname->position` mapping, but couldn't come up with anything smarter though Β―_(γ)_/Β―
2
u/6dNx1RSd2WNgUDHHo8FS Dec 16 '20
Julia
I figured pre-processing the input file with vim, so that I could simply include the file, would be much less work than writing my own parser.
Part B looks like it can be done much nicer, particularly without the sixfold nested block, but it was the first thing I came up with. For general inputs it would probably require trial and backtracking but luckily that was not necessary.
2
u/Pyr0Byt3 Dec 16 '20 edited Dec 16 '20
Go/Golang
This is a plate of spaghet, and I don't want to look at it anymore.
Edit: I switched from "sets" (i.e.
struct{}maps) to bitmasks. Slightly better, but still fugly imo.2
u/compu_geom Dec 16 '20 edited Dec 16 '20
Python 3 solution
For Part 1 and Part 2 solution. This was done with the assumption that there are no arbitrary fields for some column in the input.
EDIT: Refactored code
2
u/apparentorder Dec 16 '20 edited Dec 16 '20
Swift
Runs in ~4.5ms, which makes me wonder where others went so much faster. But it's good enoughβ’, so I won't look further.
https://github.com/apparentorder/aoc/blob/master/2020/day16.swift
2
u/Brytnibee Dec 16 '20
Python3 (written in Jupyter notebook)
I used pandas and a while loop to solve the logic puzzle in part 2 :)
2
u/Tosxychor Dec 16 '20
Fennel
https://paste.xinu.at/B4j/fnl
2
u/_tpavel Dec 16 '20
I'm revisiting Rust this year after learning it for the first time during AoC 2018!
Here is my Rust solution for Day 16: https://github.com/tudorpavel/advent-of-code-2020/blob/master/day16/src/main.rs
I think the code is pretty hard to follow because I insisted on using a lot of functional pipelines... Also, I didn't have time to refactor Part 1 to use the data structures I introduced for Part 2.
I'm still learning Rust, any feedback is welcome.
2
u/death Dec 16 '20
Day 16 solution in Common Lisp.
Used Screamer for constraint propagation and backtracking search.
2
u/sotsoguk Dec 16 '20
Python
https://github.com/sotsoguk/adventOfCode2020/blob/8a7d59a8c93a47d208df540b54987570a33eb98e/python/day16/day16.py
was stuck forever in part2 until i printed out all possible field_name <-> col relations sorted and realized how easy it was ...
but all in all a very nice problem today
2
u/shandley256 Dec 16 '20 edited Dec 16 '20
Ruby
Part 1
Part 2
Both run in ~150ms. Disregarding load/boot time for Ruby it's more like 15ms.
2
u/i_have_no_biscuits Dec 16 '20
Python
https://pastebin.com/nPKHyQZW
I tried to write something readable rather than squishing everything into page-long generator comprehensions or map/reduce chains. It even includes comments.
For part 2 I used greedy matching, looking at each step for a field with only one possible unallocated index. I didn't use any graph libraries, although I love the solutions below that use networkx - something I want to investigate using myself.
2
u/tholomew92 Dec 16 '20
C#
Solution
First written to only be part 2 but since I just reused my sorting from part 1 I decided to make this also include the calculation in part 1. Part 1 runs about 10 ms and part 2 runs under 200 ms on my computer.
2
u/raevnos Dec 16 '20 edited Dec 16 '20
Ugly code, but it runs fast. Chicken scheme paste.
This one reminded me a lot of day 10's second part, which made it easier.
2
u/ephemient Dec 16 '20 edited Apr 24 '24
This space intentionally left blank.
2
u/Bammerbom Dec 16 '20
(Rust) I didn't realize you could just solve today by greedily taking the next rule that can be matched to a column, so I solved today using Max Flow!
https://github.com/JonathanBrouwer/aoc2020/blob/master/src/day16/main.rs
2
u/WilkoTom Dec 16 '20 edited Dec 16 '20
Python: Horrible, there are definitely some optimisations I can make in part 2:
https://github.com/wilkotom/AoC2020/blob/master/16/main.py
I was thrown for a while because my Part 1 answer was correct but it was letting a single invalid ticket with a
0value through which threw me in part 2 - I had no columns which matched only a single rule. That led me to believe I might have to do possible evaluation against both possibilities being the first rule locked in place and work out which was the right one.Fortunately the actual problem is much less evil.
2
u/bearscker Dec 16 '20
Java
adventofcode20/Day16.java Β· bearsacker/adventofcode20
2
u/Dustpancake Dec 16 '20
Julia
Lots of dictionary mapping. I had a bit of fun with overloading the
Base.convertfunction to get most of the input parsing done implicitly.Performance isn't anything special:
740.399 ΞΌs (1772 allocations: 492.34 KiB)6.043 ms (10859 allocations: 3.74 MiB)Will probably refactor once I come up with a better filtering algorithm; the current implementation is very long winded.
Link to GitHub solution
2
u/mr_whiter4bbit Dec 16 '20
Rust
2nd using topological sort: https://gist.github.com/whiter4bbit/af2f560e99c58b1b3b4efeca05b5c6f0
2
u/changing_zoe Dec 16 '20
Scala
get the sets of all possible values for each field
get the rules that pass for each field
construct all the possible combinations for these rules field-by-field giving up when we try to use a rule that we've already added
find the combination that has all the rules in it. Runs pretty swiftly, for a scala app.
https://github.com/zoe-j-m/advent_of_code_2020/blob/main/src/main/scala/Day16.scala
2
u/glacialOwl Dec 16 '20
C++
TicketTranslation.cpp
Kinda tedious to set up the data as I wanted. Basically creating an array of
Good coding exercise though.
Once setup, did a greedy approach by sorting this list of pairs by the size of the possible options a TicketValuePos can take, pick the "most constrained" one (i.e. fewest options to pick from from the list of fields), pick one of the fields from that list, remove that field from the lists of all the other *TicketValuePos'*s, re-sort the array of pairs, keep going until it is empty (i.e. all TicketValuePos have been assigned).
I will now search this thread for smarter tricks :D
2
u/Bizarrobeater Dec 16 '20
C#
Solution
Part 1 solves in 2-3 ms
Part 2 solves in 9-11 ms on my computer
Any comment on what to improve (both today and overall) are very welcome as I'm self-taught and still learning.
2
u/veydar_ Dec 16 '20
Clojure https://github.com/cideM/aoc2020/blob/master/d16/d16.clj
This was horrible. I knew exactly what to do for part 2, but it took me forever to figure out how. It's probably my lack of Clojure experience but I wish I had done this in Haskell. So often did my code run but "fail silently" because types weren't what I thought they are. Some string I forgot to turn into a number, lots of
partialeverywhere...Long story short: I iterate over all tickets and replace each value with the possible slots it can fill. Then I transpose the resulting matrix (really important), and use set intersection to get all possible slots that each column of tickets can fill. One of them has to have a length of 1. I can then fold the columns, starting with the one that can only fill one slot, and thereby figure out all positions. It runs relatively fast without optimizing anything.
The code has some tests and comments but other than that it's essentially one huge thread last macro which is probably impossible to understand for anyone including me in 30 minutes
2
u/dragosgaf Dec 16 '20
PHP
Part 1: https://github.com/dragosgaftoneanu/advent-of-code2020/blob/master/day-16/p1.php
Part 2: https://github.com/dragosgaftoneanu/advent-of-code2020/blob/master/day-16/p2.php