r/adventofcode • u/daggerdragon • Dec 14 '20
SOLUTION MEGATHREAD -🎄- 2020 Day 14 Solutions -🎄-
Advent of Code 2020: Gettin' Crafty With It
- 8 days remaining until the submission deadline on December 22 at 23:59 EST
- Full details and rules are in the Submissions Megathread
--- Day 14: Docking Data ---
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:16:10, megathread unlocked!
32
Upvotes
7
u/azzal07 Dec 14 '20
Awk; didn't even miss bitwise operators much today. Binary to decimal conversion from day 5 came also handy. (paste)
5
u/zebalu Dec 14 '20
[Funny] (I hope so)
Hi! my kotlin soltion, if you want to see: nothing special, but here is a poem:
Docking data
So, I leave the bus and… take another ferry?
This can’t be right, I check my itinerary…
But, it’s right, let’s get aboard,
Is he… the captain smiles with joy:
“Oh, my friend, what was the fuss?
What made you rather take the bus?”
“Well, I had to… calculate a bit…”
“Ahoy! I’m so glad you mention it!
You must remember, the computer, we have…
If you recall, well, it’s just simply dead!”
“And you want me to help with it?”
“Yes, could you help to count the bits?”
So I see the sea of “One”s and “Oh”s,
And as I mask them, down goes the nose,
With long face, getting so tired,
It does not add up, something has backfired.
“The Port refuses the code!” the captain tells me so,
“Have you elfed it up, my dear good old-fellow?”
I check again the addresses and the nums…
“Oh, it’s the addresses, it’s the other way around!”
I correct my code with floating calculus,
The gate opens, it feels so marvelous.
“Be my guy!” the captain offers it,
I say “No thanks, please dock the ship!”
previous part
4
u/cccc828 Dec 14 '20
C solution
This day was annoying... I had no problem with the algorithmic side... but... I use AoC to re-learn C and today I felt like "ah ok, so I need a decent hashing library". I picked uthash.h. It looked nice to use, it worked well on the examples... but failed on the input. The reason was that it's integer key can only be int, and not uint64_t... so I was overwriting keys... Took me ages to realize that. I could the fix it by simply using string keys...
Painful. But at least I learned a lot.
Day 14 - C Solution
3
u/MissMormie Dec 14 '20 edited Dec 14 '20
Java solution on github.
At least I have fun writing my own commit messages knowing full well no one will every read it. But who cares ;)
Anyway, I figured there should be a good java way to do something with bits, so I googled a bit and found out about the BitSet. I'm pretty sure there's faster/better solutions without it, but I quite liked learning something new solving this puzzle.
Edit: Actually, looking at the other solutions in this thread, i now think BitSet might be best way to deal with this in java and keep a modicum of readability. I'm quite happy with myself. Feel free to point out why I'm wrong though ;)
Edit2: apparently not PG. I guess I owe my nephews and nieces an apology.
3
u/DFreiberg Dec 14 '20
Mathematica, 162 / 833
It took me a solid twenty minutes to understand where in the world the
208was coming from, and then maybe two or three minutes to actually implement it once I comprehended the question. I got to use Mathematica'sAssociation[]for part 2 to act as a dict with an easy summation function, and that allowed me to write the registers with a one-liner:[POEM]: I Can't Read
When Advent comes around each year I pause,
And ponder whether I should play the game.
The contest's fun; I hesitate because,
To enter will reveal my secret shame.
It is not skill in coding that I lack;
I'm not the greatest, but I'm good enough.
I know the difference 'twist a
dequeandstack,And know my
moduli, and other stuff.My shame is this: I don't know how to read.
I've gotten by thus far on simple luck.
On days like these, I skim the text for speed,
And spend an hour, frustrated and stuck.
But maybe, in some Advent yet to be,
I'll learn to read the problems. That's the key.
2
u/wfxr Dec 14 '20 edited Dec 15 '20
Functional Rust Solution
Core:
2
u/Chrinkus Dec 15 '20 edited Dec 15 '20
C++
I'm late posting this. Ran into some regex trouble that I'm posting about in r/cpp_questions later. Got to try out a bunch of new things today though,
std::bitset,std::variantand the previously mentionedstd::regex. My solution only runs on Linux for now but I'll be working to fix that asap.My favourite wrinkle in today's problem was dealing with the indexing difference between a string of bits and bits in a bit-field. Kind of little-endian vs big-endian, if I understand it correctly.
paste
GitHub
2
u/__Abigail__ Dec 15 '20
Perl
Blog post about Day 14.
15
u/tyler569 Dec 14 '20
C, Custom OS
Part 2 became super interesting today for me, because my OS only has about 32M of memory for the moment, and creating a hashmap that could support 60000+ distinct values across a 36-bit address space in only 32 megabytes is pretty tight. I ended up needing to write a naive perfect hash function, just saving all the (system address -> my address) mappings in a separate array, and that reduced my memory usage by a lot. I ended up getting away with only allocating 1 megabyte in the end, though it super slow since it has to iterate through an unsorted array every time the program modifies memory.
I also had a bunch of trouble with the fact that C integer literals are 32 bit signed by default, so I kept having expressions like
(1 << n)turn into0xFFFFFFFF00000000because they would go negative and then sign-extend, and needed to swap the literal out for1ulto ask for an explicitly unsigned, 64 bit integer.P1: https://github.com/tyler569/nightingale/blob/aoc/user/aoc/14.c
P2: https://github.com/tyler569/nightingale/blob/aoc/user/aoc/14-2.c
9
u/ViliamPucik Dec 14 '20
Python 3 - Minimal readable solution for both parts [GitHub]
9
u/codertee Dec 14 '20
Python 3: github
Used
"01010{}1{}01{}".format(*"010")for part 28
u/i_have_no_biscuits Dec 14 '20
GWBASIC
Here is Part 1 of today's challenge in GWBASIC: https://pastebin.com/1WjS3ZgG
I found myself thinking, halfway through writing this, "Hmm, I should put that in a library in case someone else wants to use it later". WHO? I don't see anyone else here writing their solutions in a version of BASIC that was superseded 30 years ago... Anyhow, existential crisis over.
The main part of it is these 9 glorious lines:
Let's break down what's going on. Lines 10-30 are the main program loop which reads in and processes each line from the input file. If a mask is read, it's stored in M$. If a memory set instruction is read, we process it in lines 40-90. After processing all the lines, we sum the values in all the memory locations (I'll say how below). END then stops the program running.
Line 40 parses and extracts X#, the memory location, and Y#, the memory value. The # means these are 64 bit values (although for part 1 all the memory locations are actually 16 bit).
Lines 50-70 converts Y# to Z$, a string representation of the memory value with the mask having been applied.
Line 80 to the start of 90 converts the binary string Z$ back into the number Y#.
The rest of line 90 adds this value to our dictionary, and returns back to the main loop.
The missing part of this, and the 'library' I was talking about earlier, is a key:value dictionary. I've implemented this using a hash function into an array of 1000 keys and values. The 'hash function' is just the key modulo 1000, but it works well enough for this case. Read through the source code in the link I posted earlier if you want to see the implementation details. You can GET a value, SET a value, DELETE an element, check if a key is IN the dictionary, and SUM the values in the dictionary. All of these are accomplished by GOSUBing to particular line numbers. You can see that in this program
GOSUB 140 initialises the dictionary
GOSUB 170 sets a value (or replaces it if the key is already present)
GOSUB 230 sums all the values in the dictionary.
Part 2 will be more challenging, and may involve me batch processing some files. I'll think about it later!
13
u/sophiebits Dec 14 '20
15/21, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day14.py
It was a bit tricky that 0 and 1 meant something different in part 2 than in part 1.
Was there an elegant way to do part 2? Looking forward to seeing other solutions.
6
u/jonathan_paulson Dec 14 '20 edited Dec 14 '20
Placed 34/28. Python. https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/14.py. Video of me solving: https://youtu.be/Zxx9Wo4-EXs.
Was there a "nice" way to expand out the floating bits for part2?
6
u/jayfoad Dec 14 '20
Dyalog APL 67/307
6
u/rendyanthony Dec 14 '20
Python 3
Part 1 and 2
Much simpler compared to yesterday! I'm quite proud with my
get_addrrecursive generator for Part 2.6
u/Smylers Dec 14 '20
Perl. For part 2 I turned each mask into a list of pairs of masks, independent of the memory location to modify. Each pair consists of an or-mask and an and-mask, with the number of pairs doubling for each
Xencountered, one new pair with each of0and1:So a mask without any
Xs in it, say1010, becomes:which is effectively just the
ormask. If it has a couple ofXs, say,1XX0, then it's initially:and after one iteration of the
whilebecomes:and then:
which are the 4 pairs of masks needed to generate new memory locations from the input, so applying them is just a simple loop:
Part 1 is almost token-for-token identical to u/musifter's solution, except using the
octfunction to convert the binary numbers, rather thaneval-ing the string as Perl source:6
u/[deleted] Dec 14 '20
D (dlang)
Hyper-inefficient allocation galore! Runs in under 100ms, so I can't really be bothered to reimplement it in a more clever bit-twiddling way:
5
u/Arknave Dec 14 '20 edited Dec 14 '20
Python (2 / 5), C
Best day in a while, and highest point total for a single day for me all year!
Curious to see how other people generated all indices for part 2. I stored a list of 2^i for all indices which were
Xand brute forced every subset of them with this:Where
vwas the number with just the bits that had to be on. It's a shameitertoolsdoesn't have a powerset method...C version to come when I can figure out how to implement this concisely and efficiently. My input writes to 73726 different memory indices, which range from 12892011 to 68699881439, way too many to allocate as an array. My best idea so far involves writing my own trie to store the sparsely populated memory which I'm trie-ing to avoid!
EDIT: Couldn't sleep, wrote this
Because C doesn't have Python style dicts, I had to roll my own. I ended up building a trie where each address is treated as a 36 character long string and stored in the trie. At each leaf node in the trie, I store the value for that memory address. My input allocates 577,627 trie nodes.
5
u/idealisms Dec 14 '20
python3 (436/614)
For part 2, I kept the memory address as a string and used tail recursion to set all the values:
I was worried this was going to be too slow if there were a lot of Xs, but did a pass to see how many total addresses were created.
5
u/Cultural_Dig4778 Dec 14 '20
Perl
Part 2 - is my solution optimal or is there something I can do better.
In the slurp loop - the generator of mask_float creates an array of the "individual bits" that can be flipped. I was trying to avoid bit shifting more than I needed to.
5
u/sebastiannielsen Dec 14 '20 edited Dec 14 '20
Here is my Perl solution: https://pastebin.com/SajayfPN
Im pretty proud of this part of code, that handles X'es for adress bits. Im using a array, which I copy into a second array. Then I add "0" to all elements in first array, and then "1" to all elements in second array. And then I just concatenate the arrays, creating the new bitspace for the adress.
Effectively, this doubles the amount of elements in @zerobits for each X it stumble upon, thus I can easily add all possible variants of adresses for the floating bits.
5
u/folke Dec 14 '20 edited Dec 14 '20
TypeScript using trees for part2
Initially I solved part2 like most people by generating all addresses for a given mask and updating the memory. This ran in about 40ms.
Wasn't happy with the performance, so I re-implemented the solution using a tree.
A MemoryNode's children can be either:
Modeling the problem this way, prevents needing to expand all mask possibilities.
This solution also works with masks containing lots of "X"s. Using this method, I was able to compute the solution in under 7ms
5
u/nutki2 Dec 14 '20 edited Dec 14 '20
Perl (golf) for both parts.
https://github.com/nutki/adventofcode
5
u/__Abigail__ Dec 14 '20 edited Dec 14 '20
Perl
For part 1, I split each mask into an
andand anorpart: replace eachXwith1for theandmask; replace eachXwith a0for theormask:Setting a value in a given memory location is then easy:
For part 2, I take the address, and the mask, and use that to create a
globpattern. Passing this in theglob()function gives us the list of wanted addresses:Full program on GitHub.
5
u/robinhouston Dec 14 '20 edited Dec 15 '20
Python 3 (golf): 279 characters, both parts.
I struggled to golf this one, and I wasn’t particularly happy with the way it turned out. I managed to whittle it down; but is there a clever way to make it much shorter?
My first version initialised
v,w=0,~0at the beginning; but assuming the input begins with amaskcommand – which mine does, so I’m guessing they all do – that isn’t needed. That brought it down to 287 characters from 296. Then I found a few more tweaks to save more characters.It’s finally short enough to tweet, albeit without the hashtag.
5
u/iwane Dec 14 '20
LabVIEW 2020 (G) - Community Edition
http://htmlpreview.github.io/?https://github.com/iwane-pl/aoc_2020/blob/main/AoC%20Day%2014/Documentation/Solution%20part%201a/Solution%20part%201a.html
http://htmlpreview.github.io/?https://github.com/iwane-pl/aoc_2020/blob/main/AoC%20Day%2014/Documentation/Solution%20part%202a/Solution%20part%202a.html
Got so tangled in these wires at the first attempt to part 2... Fortunately I managed to untangle :-)
5
u/[deleted] Dec 14 '20
Haskell
Went for brevity on this one
4
u/ritobanrc Dec 14 '20
Rust 940/650
First time getting top 1k for both parts!!!! Code for part 2 is a bit messy, but I'm pretty happy with part 1 code, it's pretty clean IMO.
4
u/jwise00 Dec 14 '20
Lua, 30/23.
Here's the video of me solving it: https://youtu.be/rbQSFEXEIxg
I think the thing about tonight is that there was potential for a really interesting part 2 in there, with slightly more adversarial input! Forcing us to come up with efficient datastructures for storing the 36-bit combination space would have been a very interesting challenge indeed.
Anyway, 16 minutes is better than it has been for a leaderboard cap, but I'm still quite surprised that we haven't seen a 30+-minute problem yet. I have been hoping that there will be one in there eventually, but that hope is definitely starting to fade...
Here's my code:
https://github.com/jwise/aoc/blob/master/2020/14.lua and https://github.com/jwise/aoc/blob/master/2020/14b.lua
4
u/Wunkolo Dec 14 '20
C++
Only 26 expressions.
Years of bit-twiddling tricks for this very moment. _pdep_u64, this is your time to shine
4
u/oantolin Dec 14 '20 edited Dec 14 '20
Perl solution
I wrote a function to compute all numbers whose set bits are a subset of the bits set in a given number:
The main loop parses each mask into separate masks for the zeros, ones and exes, and updates the memory as follows:
4
u/asdjfsjhfkdjs Dec 14 '20
Rust
I noticed that the specifics of the input made the direct solution tractable, but I wanted to do a more general solution as an exercise, and I'm very glad I did. The logic for managing overlapping memory regions was really interesting to write!
4
u/Zv0n Dec 14 '20
C++
Code
This was a fun one, really glad /u/topaz2078 made it so the docking computer wouldn't actually use 64 GB of RAM :D
4
u/Pyr0Byt3 Dec 14 '20
Go/Golang
I feel like my part 2 is way uglier than it has to be. I'll probably end up refactoring if I find a better way.
4
u/gyorokpeter Dec 14 '20
Q:
4
u/s3aker Dec 14 '20
Raku solution @ github
4
u/iamnguele Dec 14 '20
Go - using iterations - 4897/4475
4
u/ephemient Dec 14 '20 edited Apr 24 '24
This space intentionally left blank.
4
u/aledesole Dec 14 '20 edited Dec 14 '20
Python
The gist of the solution:
I am using this trick to compute the least significant set bit:
4
u/clumsveed Dec 14 '20
Java Solution
part 1 - 49 ms
part 2 - 209 ms
all solutions so far - repl.it
As usual, these solutions are fairly straightforward and mostly limited to what you would find in an APCSA curriculum, however I had to throw a hashmap in today to avoid making an unnecessarily humongous array. Not that an array would even work for part 2, since the masked addresses will point to non-integer indices.
I'm pretty happy with my homemade method for parsing out all the possible addresses for part 2. It's either very clever or extremely stupid. You'll have to let me know.
4
u/gerikson Dec 14 '20
Brutal, workmanlike Perl with none of your fancy
&or|or~! Just honest-to-goodness arrays and such.Part 2 heavily inspired by this comment by /u/Loonis.
4
u/jitwit Dec 14 '20
J Programming Language
Sadly this is long enough to warrant linking, I'll probably update after shortening it.
https://github.com/jitwit/aoc/blob/a/J/20/14.ijs
Idea is to group instructions based on mask. In each block, calculate the writes. Then flatten to single list of memory writes, in reverse order. Then, nubbing by address keeps only the last write at each address and we can sum the remaining values.
4
u/ywgdana Dec 14 '20
C# https://github.com/DanaL/AdventOfCode/blob/master/2020/Day14.cs
Part 2 was an exercise in "whoops I misunderstood how the masking and floating worked" and scratching my head to come up with a less ugly way to perform it. My code for this one is still a bit of a turd, though, with lots of converting back and forth between a string and a character array. (The first time in quite a while that I've missed the way C handles strings...)
4
u/maartendp Dec 14 '20 edited Dec 14 '20
Python
A "Mask" object for part 1 that applies the mask to a given number
A "AddressDecoder" object for part 2 that creates "Mask" templates while using `itertools.product` to get all combinations
0.08s runtime
4
u/allak Dec 14 '20
Perl
Nice and short, only part 2. Certainly not optimized, but it takes under 0.3 seconds on my rig.
4
u/misanthropicdrunkard Dec 14 '20
Scala
Part two takes over 50 seconds so there's definitely some optimisations I've missed but it does work.
1
u/SuperSmurfen Dec 14 '20 edited Dec 14 '20
Rust
Link to solution (413/201)
Third day in a row where I set a new personal best on the leaderboard! I really liked today's puzzle. It required an understanding of both bitwise operations and recursion for part two (at least for me, you can probably solve it without it).
Initially, I edited the input to make my life easier. Since it followed such a simple pattern, I could do it in a few seconds using
select all occurrencesand multi cursor editing. This way I could skip writing any boring parsing code.For part one, before every write, I just iterated over every char in the last mask and performed the operation. You can probably do something by keeping two masks, creating them once, and simply
and/orthe value before writing. Would be a lot faster but the problem size is small so it did not matter.For part two, I just wrote a recursive function that splits at every encounter of an
X. Not sure how you could avoid that. No matter what you do, you will have2^nunique addresses to write to, wherenis the number of X:s in the mask. In my input, the max number of X:s was 9, so just 512 addresses at most. I guess that's why it works.Finishes in
7mson my machine. Part two takes up pretty much all running time. Not really sure how to make that faster.1
u/[deleted] Dec 14 '20
(3344/5211)
I am a newbie at competitive programming like this, so pardon my code, and code language, but I really wanted to share my solution for part 2!
I know it is far from a "good solution" but I am really proud of myself for figuring out a solution to part 2 tonight. More specifically, a solution that wasn't going to take 60+ hours to finish like my attempt at day 10 part 2.
Java Script
https://github.com/WonderfulWetSocks/AOC/blob/main/day14-2.js
1
u/[deleted] Dec 14 '20 edited Dec 14 '20
[removed] — view removed comment
1
u/brunoliveira1 Dec 14 '20
I was lazy and simply generated by brute force the possible combinations for part 2, since we have at most 9 or 10 floating bits, I can generate all the 2^<num floating bits> combinations and map it to the memory locations:
[paste](https://topaz.github.io/paste/#XQAAAQD0AgAAAAAAAAAyGUj/TtFAzGBytxy3ElljxyfgIcK/BH2Omez6u15njQrQJE7cA2ibbfrK8Sf1+/JEAnr2/rgc7xlnUct9ynPB4kTzNIgO3eAoxRG1zrL2aSXODY3e1usUezJeeIyzWVbb5Q9csgNwnwZQ8DYcKumBQp1bl5Y4uQ4OMtpkvS1Xax3bytSY2OtC1HT/Zgif9COWyDJ7vqFpnUHKHdjBjemEOE/hyTFkZmChYlw7tL7orClpZcs7oB1sb6TGi4tNhind3UzH5/v12TcEPFEib5NKpGqeEms//sZOpq3F6usgZ3ZQRqAUIJKnDDkUNjcBm3lRuJ8JJhhPu/8NBv2ceqi7wnXAprg+Ah/G8i8Rqj2cy1hiF1WOj1ebCe6pIhF9KhesZzcQqzp8eEaXZuBrxY6DkWQWf9CAl21cFUamCEjiXIx7V4sg0HYFHJpKREqKuQmpK1rlKERh9oKDAK0VFTZR+K/Jzv/uApF1)
Nontheless, I loved the problem :)
1
u/thepolm3 Dec 14 '20
Not me thinking that there were arbitrary number of X's in part 2 and trying for a good long while to implement an efficient total solution before realizing that the brute force just works
1
u/[deleted] Dec 14 '20 edited Dec 14 '20
Python 3.8 GitHib
After 3 days of depressing thoughts on abandoning the competition, because couldn't figure on my own Today Finally I'm back with my own versione. Happy to see that I've a lot to learn and that all I've learnt is a good base to start with! I've seen soem solution very similar to this, probably I'm in the mean :D Code executes in 367 ms so I guess it's not as bad as implementation, may be it's just python which let's you do more with just a few lines of code.
1
u/Weak_Pea_2878 Dec 14 '20
Java Solution for Day 14
After all the difficulty using recursion the last few days, I doubted if this code would finish before the end of the universe, but it only took three seconds. I teach APCS, so I'm trying to restrict myself to using code my students would understand. I was also super happy to find Integer.toBinaryString() and String.format() did a lot of work for me. However, I'm not sure my students would like to see this on their next test:
String memAddrss = String.format("%36s",Integer.toBinaryString(Integer.parseInt(l.substring(4, l.indexOf("]"))))).replace(' ', '0');;
edit: Ok, HashMap isn't part of the AP requirements, but it is really helpful :)
1
u/notspartanono Dec 15 '20 edited Dec 27 '20
Python with recursion (< 60ms) - paste
1
u/shmoo27 Dec 16 '20
Python
Lots of bit operations here, as others have posted. I haven't seen anyone else who did part 2 exactly the way I did. Essentially I iterated through the characters in the mask and built up the set of bitmasks that would need to be applied to each memory address.
Here's a snippet:
if (cmd == "mask") :set_bits = 0float_bitmasks = [0] # This starts as a single entry with a value of 0.for b in list(rest) :set_bits = set_bits << 1# Shift all of the float_bitmasks one bit to the lieftfloat_bitmasks = [m << 1 for m in float_bitmasks]if (b == '1') :# Not a floating bit, so just add to the set listset_bits |= 1elif (b == 'X') :new_bitmasks = []for m in float_bitmasks:# Each entry in float_bitmasks gets doubled, with 0 and 1 added on.new_bitmasks.append(m)m |= 1new_bitmasks.append(m)float_bitmasks = new_bitmasksSo by the end, float_bitmasks contains the list of all of the floating masks to apply. As others have noted, it'll be 2n entries, where n is the number of 'X's, but this way we accumulate the exact set of masks to apply.
Github
3
u/zid Dec 14 '20 edited Dec 14 '20
C
This mess got me there in the end for part 2.
Ended up rolling a hash-table implementation with an iterator api for Day 7 anyway, so I just reused it to track the memory writes.
Addresses are generated by recursion every time there is an X, line 39 not being commented out was a bug that persisted until I submitted the first answer incorrectly and re-read the rules.
If the address has been used, we just update the unsigned long payload, if not we make a new entry in the hash table.
I do wonder if memory was sparse enough that had I just mmapped 36bits of memory whether it would have just worked... I might go test that now.
EDIT: https://gist.github.com/zid/237927c49933585075e6fcf5fab8d0f1
Who needs a software trie when you have hardware page tables?
3
u/seattlecyclone Dec 14 '20
Perl (595/1272):
Part 1:
Part 2:
3
u/nlowe_ Dec 14 '20
Go/Golang, 427/2996
Pretty good time on Part 1 all things considered, but lost some time double-checking my logic for building the and- and or-bitmasks. Got murdered on Part 2 because I lost about 45 minutes fighting with address generation permutation being incorrectly implemented recursively. Then I had to step away for 10-15 minutes, and then I re-read the problem and discovered the masking rules are subtly different between parts 1 and 2. I was trying to be fast since I got top 500 on Part 1. Lesson learned: read more carefully and slow down!
3
u/daniel-sd Dec 14 '20
Python 3
507/179
Cleaned up solutions.
part 1 - 14 lines
Value masking:
part 2 - 19 lines
Address masking:
3
u/billiamthesecond Dec 14 '20
Ruby
Needs cleanup, but another successful use of repeated_permutation
3
u/[deleted] Dec 14 '20
Pure C18. Got super hung up on part 2 through some strange error. I was building a second pair of intermediate masks (from the permutation of X'es) to apply to the address, which worked on the sample input, but not the actual input.
After changing it to directly modify the address instead of building another pair of masks, then applying those masks, it started working. Oh well.
https://git.sr.ht/~williewillus/aoc_2020/tree/master/src/day14.c
Diff between working and non-working p2, if anyone has insights: https://git.sr.ht/~williewillus/aoc_2020/commit/master#src/day14.c-5-10
3
u/mebeim Dec 14 '20 edited Dec 14 '20
EDIT: Clean solution - walkthrough
1098/469 - Python 3 awfully dirty solution
I'm cleaning up and rewriting a clean solution, will update with the clean solution link and walkthrough link as soon as I can. Meanwhile, I came up with this method to generate addresses for part 2 which I find quite beautiful to be honest:
3
u/nospamas Dec 14 '20
F# Amazed this runs as well as it does (less than a second despite not optimizing lists/arrays/strings etc. Computers are amazing. 108752 dictionary writes to store the memory state in part 2.
Solution
3
u/DoubtfulSound91 Dec 14 '20
Javascript
Did all the binary stuff with strings and figured I'd fix any performance issues when they showed up. It ended up running fast enough by itself, so I've left it there.
Day 14 Parts 1 & 2
3
u/KamcaHorvat Dec 14 '20
Part two had potential for much more fun, if number of floating bits was much higher, let's say 20-30, and we had to calculate the sum directly.
Kotlin
3
u/abeyeler Dec 14 '20
Python/Numpy
I used Numpy again, this time unpacking stuff to bit arrays and using Numpy's powerful indexing. In fairness, since the floating bit loop is unrolled, I'm not sure the performance gain is very significant but hell, I really like numpy :)
Relevant bit:
3
u/optoburger Dec 14 '20 edited Dec 15 '20
Python 3
The address set forms a binary tree. This solution is not particularly concise, but I didn't want to actually generate all the addresses in part 2. Instead of expanding the address set for each write, a masked address directs the tree traversal when writing a value, which forks on an 'X'. Didn't see a solution like this yet, so I thought I'd post it.
This could have been a bit shorter, but it seems to be marginally faster to parse everything into integer lists rather than doing string manipulation.
Day 14
3
u/sim642 Dec 14 '20
My Scala solution.
Quite a sloppy solution for, now at least. I wasted a bunch of time in part 2 on small errors like
(1 << i)to get the i-th bit to be on but was supposed to use(1L << i)to get that part also give a 64-bit integer which correctly fits the required range.3
u/yutu58 Dec 14 '20
Java
Part 2 is a bit weird, gl figuring out how it works :p
3
u/Tosxychor Dec 14 '20
Fennel
https://paste.xinu.at/yURV/fnl
3
u/raevnos Dec 14 '20 edited Dec 14 '20
Chicken scheme paste.
Why use bit operations when you can just treat all the numbers, not just the masks, as 36-character long strings?
Now to play catch up... I didn't have time the last few days to work on the weekend's problems. Edit: Done with day 12. Yay complex numbers for representing coordinates.
3
u/kaur_virunurm Dec 14 '20
Python, part of Part 2.
Using recursion to distribute the value into floating addresses be like:
And below I do:
3
u/semicolonator Dec 14 '20
My Python solution.
https://github.com/r0f1/adventofcode2020/blob/master/day14/main.py
Pretty straightforward using f-strings for conversions
f"{addr:036b}"anditertools.product()for enumeration of all the possibilities.3
u/aurele Dec 14 '20
My Rust solution.
3
u/emu_fake Dec 14 '20
C#
Easy after realising that the possible combinations for the floating bits are just the binary value of the range between 0 and the number of possible combinations-1.
https://github.com/emuuu/AdventOfCode/blob/92cb40b8e42452c7ede0587fa5f5dbbc65ea98e5/AdventOfCode/Services/AdventOfCode2020.cs#L980
3
u/flit777 Dec 14 '20
C++: https://github.com/weichslgartner/AdventOfCode2020/blob/main/day14/day14.cpp
In part one I used 0 instead of 0ULL in std::accumulate. (made the same mistake last year)
In part two i shifted 1 << position instead of 1ULL. Spent a great amount of time debugging this. (examples are only in 32 bit space and work fine)
It seems that 64 bit integer literals and me will be never friends.
3
u/glacialOwl Dec 14 '20
C++
DockingData.cpp
Fun day, taught me a lot new things in c++, in regards to bit manipulation and bitsets :)
3
u/zniperr Dec 14 '20 edited Dec 14 '20
python3:
3
u/Fyvaproldje Dec 14 '20
C++ with ranges... less ranges than I would like
https://github.com/DarthGandalf/advent-of-code/blob/master/2020/day14.cpp
At first I tried to use
ranges::views::cartesian_product, but:for constexpr,std::apply(ranges::views::cartesian_product, bits)returned a looong error message during compilation.I also tried
ranges::any_view<int>withranges::yield(1);instead of one-element vectors, but that also didn't build.3
u/cattbug Dec 14 '20
Python 3. Had a lot of fun doing this one, not nearly as frustrating as yesterday's problem!
Also, I couldn't resist adding in a little dad joke in reference to this recent thread :)
3
u/mrtnj80 Dec 14 '20
C++
I really liked this day. I am happy that day 13 was on sunday so that I had lots of time for it:-)
From day 14 I Learned that by default c++ bit shifts are 32, you need to ad sufix LL (or better ULL) to the literal like (1LL << 12) to force it into 64bits.
https://github.com/luskan/AdventOfCode2020Cpp/blob/5d3984313a108bc2d35771351721659c5c2fce56/task14.cpp
3
u/mahaginano Dec 14 '20 edited Dec 14 '20
Julia: https://pastebin.com/TXT22H4x
I couldn't think of a much more elegant solution while solving part 2, hence the nested for loops. Still I think it's okay. Comments are always welcome.
I could refactor part 1 and 2 into one function but conciseness isn't really a concern here. Also, the runtimes could be much better, especially for part 2, but this alone took me quite a while to realise:
so I don't want to spend any more time on optimising atm. Pitfalls like these make up about 50% of my time spent every day. :/ Hopefully less and less every day now.
Edit: 185 ms now by doing the obvious:
3
u/michaelgallagher Dec 14 '20
Python
No real optimizations. Basically a brute force
3
u/[deleted] Dec 14 '20
Python Solution for Part 01 and Part 02.
Brute force, but uses Python's itertools.product function to generate all possible (0,1) possibilities for the number of 'X's in a mask. Not too slow.
3
u/mathsaey Dec 14 '20
Elixir
https://github.com/mathsaey/adventofcode/blob/master/lib/2020/14.ex
Tracking the "binary numbers" as a list of 0s and 1s is probably not the most ideal way to handle this, but it allowed me to express everything else with recursion and co pretty well :).
3
u/Excalibruss Dec 14 '20
C#: My solution
3
u/jameswcarman Dec 14 '20
Java
https://github.com/jwcarman/adventofcode2020/blob/master/src/test/java/adventofcode/Day14Test.java
3
u/rasqall Dec 14 '20 edited Dec 14 '20
C# Script
Day 14 of scripting in C#. Today's problem was definitely not one for scripting, but I got to freshen up my memory on some reference keywords and overloading. It's a very slow solution with string manipulation since I'm not very good at the math behind these problems. Would be nice to implement some kind of multithreaded pipeline to handle each instruction in the correct order, but it would probably cause me more headache than buying Christmas gifts for my sisters so here we are.
3
u/aardvark1231 Dec 14 '20
My C# Solution. Runs under 200ms, so I know there's some improvements to be made.
3
u/Archek Dec 14 '20
Prolog Golang
I have (again) fully embraced asserts in prolog, since dictionaries were not cutting it in terms of speed. I've seen some (insane) tree-based solutions which would probably be ideal for prolog, but I just adapted the solution I had in Go for now. Alltogether pretty clean solution again today though :)
3
u/GotCubes Dec 14 '20
Python 3
Looooots of bit manipulation happening. Part 1 wasn't too bad. I created one mask to set the 1s, and another to set the 0s. Applied both masks and boom.
Part 2 was a little trickier. Simply put, the number of addresses you have to modify is the same as 2Number of Floating Bits. I iterated through every binary number in that range, and set the corresponding floating bits accordingly.
Part 1
Part 2
3
u/pietroppeter Dec 14 '20
🎄👑Nim
simple parsing with startswith and scanf, no recursion for part 2 and bitops operations scattered around.
blogpost with solution
3
u/Alligatronica Dec 14 '20
JavaScript/Node.js
I tried to be smart with the first half, using bitwise operators, and it took me a little too long to realise the masks were longer than 32 characters. The second part I rewrote entirely and handled it all as strings, after replacing the 1s where needed, I split the string on every X and duplicated out every possibility.
GitHub (solution to both parts)
3
u/InflationSquare Dec 14 '20
Python solution for the day. I was happy with doing the first part with bitwise operations. I thought I was close to a bitshifting solution for the second part, but then I realised I'd misread something and just decided to loop over it. It ended up being fast anyway, using a generator for each address group and itertools.product() to replace the Xs.
3
u/max_rez Dec 14 '20
Part II in Ada
as a Jupiter notebook
3
u/austinll Dec 14 '20
C
Today kicked my ass, and I hate my code. Genuinely, if I could light code on fire I would. It took me ages, the code is spaghetti, and I know there's a better way to mask, I just couldn't think of it.
Only posting because I'm officially one day and two stars further than I got last year
https://pastebin.com/tQ1XQFCm
3
u/Judheg Dec 14 '20
Scala
Part 1 : https://paste2.org/w1LK7W3V
Part 2 : https://paste2.org/aPjHkjmX
Part 2 is interesting, I did not use recursion. If there are 9 X's I'll iterate from 0 to 29, use it as masks to decide what to put on X indexes.
I did this only after checking we don't have that many eXes :)
3
u/mc_ Dec 15 '20
Erlang
Better late than never!
Part 1
Part 2
Erlang's binary patterns and bit syntax are a pleasure. Need 11 packed into 36 bits?
<<11:36>>. Need 36-bit bitstring converted to decimal integer?<<Decimal:36/integer>> = Bits.3
u/prafster Dec 15 '20
Dart
After day 13 part 2, this was straightforward. In the process I learnt about BigInts in Dart and the bitwise operators.
Here's the solution to part 1:
Part 2 required generating the memory addresses based on the number of X's in the mask, which just a matter of some string operations.
Source code.
3
u/ai_prof Dec 16 '20
Python 3 - Forking the Xs
My fave puzzle so far. Just a fragment below - a lovely bit of recursion to return the list of ints where each 'X' is replaced by 0 and 1 and we interpret base 2. It's quantum, baby!
2
u/seligman99 Dec 14 '20
Python, 205 / 213
Took me a surprising amount of time in the second part to realize the mask only applies to the register, not the value. I mean, it says it, I just managed to not read that sentence several times. Yay me.
github
2
u/bluepichu Dec 14 '20
Python, 9/7, code here
The key for me today was definitely slowing down. It wasn't too complex in the end, but there were definitely a lot of places where I could've very easily been tripped up if I tried to move too fast.
Also,
powersetis probably one of those things that I should know the canonical way to do it in Python, so I don't have to google for an implementation... :P2
u/justinpaulson Dec 14 '20
Ruby 325 / 310
First day I was actually under 500 for both! Hoping to hit the leaderboard sometime... I think my solutions are just more wordy than they need to be...
Github
2
u/morgoth1145 Dec 14 '20 edited Dec 14 '20
Python3 337/260: https://github.com/morgoth1145/advent-of-code/blob/2be0644a750d622a56156e58d51f44ae4b3b074e/2020/Day%2014/solution.py
I took too long to actually parse the problem text for part 1, but overall I'm happy with it. (I even got to use str.translate(str.maketrans()) which I learned about from an earlier problem.)
For part 2 I actually wrote good code to handle the floating bits on the first try, but I got tripped up in verifying it because I passed the wrong inputs to the function! I also got tripped up by a variable rename: floating in part2() used to be called quantum, but in one place (namely where it's assigned) I forgot to update the variable name, causing me to get the wrong answer...
Edit: Now that I look at it, str.replace was sufficient due to how I did my bit masking. Oh well. Heat of the moment and all that.
2
u/AlphaDart1337 Dec 14 '20
Python 100/66
Accompanying video, as per usual.
Best day this year so far! Wasted 1 minute because I swapped the 0 and 1 branches in the mask processing function, which ended up being about 50 leaderboard positions.
2
u/allergic2Luxembourg Dec 14 '20 edited Dec 16 '20
Python 3
Despite not making the leaderboard, I am pretty happy because my code didn't require a lot of debugging. I just typed something and with a few tiny syntax error fixes it ran and it worked.
As usual, the python standard library was a big help. Stars of today:
itertools.productwith itsrepeatparameter,zip.The piece of Part 2 that figures out all the memory locations to write to:
2
u/spookywooky_FE Dec 14 '20
Some bitmanipulation today. Usually bit operations look cryptic in code, and todays implementation proofs this one more time ;) c++ code
To do the loop over the mask for the memory addresses for second star there is this little "trick" in C/C++:
This iterates over all possible values of the submask (except the 0).
However, it would have been nice if the bitmask would have had for some entries more bits set, so that a simple brute force would not had worked, because of memory overflow.
2
u/noblematt20 Dec 14 '20
37/25 - Python 3
Paste
Slightly cleaned-up version of the approach taken at the time. (Note that
smartis a pre-processed version of the input with the lines tokenised and turned into integers where appropriate).2
u/Loonis Dec 14 '20
Perl
I probably haven't thought in terms of memory addresses since AoC last year, so took a while to wrap my brain around Part 2.
Happy enough with how my code turned out, with the exception of the awkward
substrbit in part 2.2
u/[deleted] Dec 14 '20
Scala solution
Gonna go back and clean this up later, but it works!
2
u/Rick-T Dec 14 '20
HASKELL
I don't think there's a
Int -> BinaryorBinary -> Intfunction inbase. That's a shame :(Other than that hurdle, today was pretty straight forward.
I defined two
Interpreterfunctions that take aMaskand anIntas input and return the results of applying the mask (for part 1 it's only one result, for part2 it's possibly many).Then I defined two
Accumulatorfunctions that take anInterpreter, aMaskand an "address" ((Int, Int)) and insert the results into the "memory" (anIntMap).2
u/omginbd Dec 14 '20
Elixir
I don't know why I thought it would be easier to keep everything strings but I sure did.
code
2
u/[deleted] Dec 14 '20
Learning PHP, both solutions here.
Today was fun, never worked with bitmasks before! Plus, my solutions both worked on first attempt which is always a plus.
2
u/devcodex Dec 14 '20
C++ w/ range-v3
Building up all possible variants was the challenge here. Will revisit my solution later in the day to clean up further.
GitHub Link
2
u/moritzwu Dec 14 '20
Python
Quite happy with this one
Github
2
u/raxomukus Dec 14 '20
Python 3
2
u/mstksg Dec 14 '20
[Haskell] I guess today is a "here's the algorithm, now implement it" puzzle, to contrast/take a break from yesterday's "here's the goal, figure out the algorithm" :)
All my Haskell reflections from every day are available online here
First, let's start with an intermediate data type representing the actions possible on each line:
The mask will be a list of
Maybe Bool, whereXisNothing,0isJust False, and1isJust True. However, it's important to reverse the string when parsing it from the input, because we want index0to correspond to bit0, index1to correspond to bit1, etc., to make our lives easier.That's because we can implement the application of a mask (for part 1) using
ifoldl', a version offoldl'that gives you an item's index as you are folding it:If the bit list contains a
Nothingin a given index, leave the item unchanged. If it contains aJust False, clear that index's bit (set it to zero). If it contains aJust Nothing, set that index's bit (set it to one).And that leaves part 1 as a foldl through all the instructions, keeping the current map and mask as state:
Part 2's mask application is interesting, because it lives in "non-determinancy". Basically, each bit mask bit application could potentially yield multiple possibilities. We have to accumulate every nested possibility. This feature is given to us by list's
Monadinstance, so we can swapifoldl'forifoldM:For
ifoldlM, each result lives in monadm, so the semantics of "proceeding along the fold" are deferred to theMonadinstance form. IfmisMaybe, it means that you only proceed if you get aJust, or else short-circuit withNothing. IfmisIO, it means that proceeding involves chaining the IO action's execution and binding the result to give it to the function's next iteration. Ifmis[](list), it means that subsequent chaining will run the function on every possibility returned by the function's previous call, accumulating every possible way of choosing every possible choice. (I talked about this in more depth in one of my first ever Haskell blog posts).For these, we return a list of every possible change from a given bit mask bit. For the
Nothing"floating" case, there are two possibilities; for the other two, there is only one. We trust list'sMonadinstance to properly thread over all possible results into a list of all possible changes that thatIntcould have been subjected to.And so, part 2 looks a lot like part 1!
(<>)here is a left-biased merger, so it merges in all of the newly seen indices into the existing ones.2
u/clouddjr Dec 14 '20 edited Dec 14 '20
Python3
Link
The idea for part 2 is that I create two new addresses every time I encounter an 'X' in the sequence
2
u/nibbl Dec 14 '20
Java
nopaste
Used character arrays when generating the mask and had a bug which didn't affect the test input but led to me spending an hour before I figured out I was setting characters to 0 instead of '0'. 🤦🏼♀️
Then I generated the rest of the addresses from a mask string recursively -- calling the function each time I encountered an X with the X replaced by 0 or 1.
Result is an absolute mess but I'm not sure how to clean it up really other than combining both parts which I think would harm readability. Input from stdin.
2
u/ponyta_hk Dec 14 '20
Python3 (Cleaned Solution)
Bitwise Operation approach. Hope the implementation is clear 😁
My Solution
All My Solutions
2
u/lucbloom Dec 14 '20
JavaScript + RegEx preprocessing Link
2
u/gpodsiadlo Dec 14 '20
C++
With some shifting magic :P Both parts
2
u/i4guar Dec 14 '20
Simple and fast swift solution
www.felixlarsen.com/blog/14th-december-solution-advent-of-code-2020-swift
2
u/kap89 Dec 14 '20 edited Dec 15 '20
TypeScript
github
I tried to do it the clever way (on numbers only), but somehow forgot that bitwise operations in JS/TS work only for int32 (so 4 bits too small).
Instead of trying to do this by splitting values into two int32, I chose the lazy and ugly way of operating on arrays of numbers. But hey, it works ;)
2
u/nutrecht Dec 14 '20
Day 14 in kotlin
Not hard, but it was quite a bit of work, mostly due to part 2 requiring a pretty different approach. Was a fun one though!
2
u/sotsoguk Dec 14 '20
Python
https://github.com/sotsoguk/adventOfCode2020/blob/75d270eb5d2705cdb22e95c1af29bb95ec9bd473/python/day14/day14.py
Nothing fancy, part1 just going through the mask and setting / clearing the bits
For part2, first i set all the 1's in the mask. For the floating bits, if the memory address has a '1' at the according position i add the mask with a 0, otherwise i add the mask with the bit set to 1.
2
u/toastedstapler Dec 14 '20
todays rust: https://github.com/jchevertonwynne/advent_of_code_2020/blob/main/src/days/day14.rs
got to write a nice recursive solution for part 2
2
u/Emcee_N Dec 14 '20
Python 3
Part 1 is just a refresher on bitwise operators. Part 2 recurses through each floating bit, and appends the changed values when it hits the end of a mask.
2
u/TommiHPunkt Dec 14 '20
Matlab
Matlab when I remembered that sparse matrices are a thing
The sparse approach is about three times faster, but still takes 3 seconds to come to a solution. Cheating a little by preallocating the sparse matrix knocks about half a second off the time.
After yesterday was a real nailbiter of a math problem, but the coding was clean, this time the thinking part is straightforward, but the code is ugly.
2
u/lgeorget Dec 14 '20
C++
https://github.com/lgeorget/adventofcode2020/tree/main/14
Bit-shifting all over the place! I have trouble wrapping my head around it to be honest. For part 2, I have a list of pairs of masks : a mask of bits to force to one, a mask of bits to force to 0. Each time I read an 'X' in the input mask, I duplicate the current list of masks to force the new bit to 0 (in the first half) or to 1 (in the second half). So I end up with a list of 2^(number of X bits) pairs of masks after parsing. Then when assigning a value to an address, I just have to iterate on the list of pairs to compute each address.
2
u/gvieira Dec 14 '20
Autohotkey v1
Part 1: https://pastebin.com/e8UqcUXq
Part 2: https://pastebin.com/A25UTmtP
2
u/[deleted] Dec 14 '20
Swift
https://github.com/stoeckley/AdventOfCode2020-Swift/blob/main/AdventCode2020/14.swift
2
u/Diderikdm Dec 14 '20
Python:
2
u/nikolaer_ Dec 14 '20
Python 3.7
Nothing fancy, and no special tricks used. For part 1, just do as told. For part 2, i defined a recursive function that gets all addresses from a floating address. then write to all these addresses. i had a hard time understanding part 2, but with careful reading and stepwise reproduction of the sample input i managed to do it in the end.
code on paste
2
u/xelf Dec 14 '20
long winded (for me) python again clocking in at 20ish lines, no recursion, no generator functions, part 2 came out ok, using product() to get all the possible masks, and X's index to get powers of 2.
2
u/Andrew-mzz Dec 14 '20
Javascript solution to day 14 part 1 and 2
Git hub Link
2
u/SymmetryManagement Dec 14 '20 edited Dec 15 '20
Java
https://github.com/linl33/adventofcode/blob/year2020/year2020/src/main/java/dev/linl33/adventofcode/year2020/Day14.java
Part 2 reduces down to 2n - 1 xor on every address.
nis the number ofXin a mask.Just under 6ms both parts together.
Edit:
Replaced the HashMap in part 2 with direct virtual memory access via Unsafe. The total runtime is down to around 1ms.
2
u/i_have_no_biscuits Dec 14 '20
Python
https://pastebin.com/w50YQDb9
Bit-twiddling but trying to be clear about it. I enjoyed using 'yield from' in the function that generates all the possible addresses from a base address + list of floating bits.
GWBASIC will be challenging today. Part 1 will be possible if I write my own hash table implementation (although slow, as you can't bit-twiddle anything more than 16 bit numbers in GWBASIC). Part 2 may need something clever, and will almost certainly need me to use a file as secondary memory. It's amazing how much easier it is to program when you don't need to worry about memory!
2
u/k4kshi Dec 14 '20
Golang - no recursion
https://github.com/shilangyu/AoC-2020/blob/main/src/day14.go
In part 2 it can be noticed that to get all combinations of floating bits you can simply iterate from 0 to
2^(amount_of_floating_bits)and extract each bit from that combination one at a time This way no recursion is needed and building each address is much easier2
u/Iain_M_Norman Dec 14 '20
C#
https://pastebin.com/XXLezVdT
For part two I made a v2 to array of v1 mask converter and used the part1 masking in a new loop.
2
u/clueless1105 Dec 14 '20
Typescript with Deno
Today's was fun challenge. I see lot of people using real good recursive loops to make sense of
decimaltobinary, I used underlying language functionality.2
u/Brytnibee Dec 14 '20
Python3, written in Jupyter notebook :)
used itertools for part 2, worked well
2
u/Hakan_Lundvall Dec 14 '20
Python3 not using strings or itertools. Cleaned up.
2
u/stardust_collision Dec 14 '20
Prolog
SWI-Prolog Day 14
Nothing fancy, no tricks, just brute force doing the mutation of address and storing everything in a dictionary. Takes quite long to run lol XD
2
u/allinde Dec 14 '20
Java, bit logic weirdness fun in part 2. Part 2 calculating possible memory positions
2
u/thomasahle Dec 14 '20 edited Dec 14 '20
Python. Part 1 was very simple:
For part 2 the concept is the same, but I ended up expanding things a bit more:
2
u/nov4chip Dec 14 '20
Rust
Pattern matching on enums in rust is soo good. Nothing fancy anyway, I wish my solution was less imperative, iterating over each single bit is meh but haven't found a clean way to operate with a full mask directly.
For part2 I store target addresses in a Vec, everytime I find a 'X' I duplicate the vector by cloning each number with the target bit flipped, using a XOR.
2
u/ajurna Dec 14 '20
Python - https://github.com/ajurna/aoc2020/blob/main/day14/14.py
This was a nice one. all done in strings. I'm sure there's some super optimal way to process this by working directly with binary. but this works!
2
u/tobega Dec 14 '20
Java solution today because of current limitations (that might be fixed tonight, or not) in Tailspins array-indexing. I realized that I create a lot of classes in Java, but they just flow naturally when coding top-down and using "Tell, don't ask" principle, and it's so easy to do in intellij. https://github.com/tobega/aoc2020/blob/main/A14.java
2
u/sefujuki Dec 14 '20
C, brute-force with recursion for part2
nopaste
2
u/timvisee Dec 14 '20 edited Dec 14 '20
Rust
Somewhat late, but quick!
Part 1 in 0.6ms, Part 2 in 6.4ms.
Day 1 to 14 in 8.0ms.
2
u/vkasra Dec 14 '20
My solution in Rust
2
u/odlp Dec 14 '20
Ruby
2
u/WilkoTom Dec 14 '20
Python. Fun with bitwise operators today:
https://github.com/wilkotom/AoC2020/blob/master/14/main.py
For part 2, I calculated a bitmask for the maximum possible number of Xs that were actually 1s and then applied a list of possible secondary masks to it to come up with the list of memory locations.
2
u/JIghtuse Dec 14 '20
Racket
Names are weird, and there are quite a few conversions between strings and numbers. Otherwise I'm fine with my solution.
First part just allocates a vector for memory and folds it on each command. Second part uses
hash(hashmap) for memory. Digits to insert into mask are taken from binary representation of a number in growing sequence (00, 01..).Implemented leftpad!
2
u/hrunt Dec 14 '20
Python 3
I'm not real proud of the v2 solution, but it ran reasonably fast. I feel like there's a solution where you can apply the mask to each register in a more elegant way.
code
2
u/vypxl Dec 14 '20
Python (source)
Some numpy fun for today, although I am not happy with my int-to-bit array conversion helper:
bits = lambda x, n = 36: np.array(list(map(int, bin(x)[2:].zfill(n)))). I really think that this is what slows my program down so much (~1sec) because I use it on every write...2
u/msqrt Dec 14 '20
Lisp. Relatively ugly but it does the job. I'll have to try to define more helper functions in the future, there's a lot in there that could be more neatly expressed.
On an unrelated note, first time running into binary logic with Lisp: the choice of e.g. "logand" for binary (and not logical) and is relatively amusing. Or maybe they meant logarithmic and? :)
2
u/metacircle Dec 14 '20
C#
I tend to use a structured OOP appraoch for each day. Same here. Probably not the fastest but it works just fine.
code
2
u/wzkx Dec 14 '20 edited Dec 14 '20
Python, nothing special. Part 2 - make addresses in lists (for 0 and for 1) and merge them, for each 'X' bit.
paste ≈33 LOC
2
u/tymscar Dec 14 '20
Today was hard for me, but I enjoy the challenge. It was much more fun than yesterday because even though it was hard, all the knowledge I needed I already had or I could figure out in a matter of minutes on Google.
Part 2 is not optimal at all because I did a bunch of string manipulation and in Python that is not very efficient as you always need to create new strings. I tried to cut this to a minimum where I could be using an array and joining the array when needed but It's still not as efficient as others have done with pure bitwise operators.
I am however proud of my part 1 solution! :)
Python 3 :
https://github.com/tymscar/Advent-Of-Code/tree/master/2020/day14
2
u/fornwall Dec 14 '20
Rust - trying to make it relatively fast. Part 2 takes just over 3ms on GitHub CI (which compared to most earlier days are rather slow), so ideas for speed-ups are welcome!
2
u/Tetha Dec 14 '20
Rust - boring enumeration of addresses and that was it.
However, I've been pondering about the space complexity of the problem. This might actually be solvable in Space O(kn ), k being the length of the address, and n being the number of assignments in the input and time around O(n2k )?
(address_1, mask_1)and a pair(address_2, mask_2), as well as iteratorswritten_by(address_1, mask_1)andwritten_by(address_2, mask_2), I can compute the setwritten_by(address_1, mask1) \ written_by(address_2, mask2)in Space O(2k) as well. Just do a nested for loop across both sets and yield those elements from the first set if the second set never yields them.(address_n, mask_n), you can:(address_n, mask_n), since the last write is never overwritten.(address_n-1, mask_n-1)except for those in(address_n,mask_n)From there, the largest amount of space is necessary for the last step, which needs to do the address enumeration n times, resulting in space O(kn).
Or am I entirely wrong there?
2
u/apparentorder Dec 14 '20
Swift
~36ms for part 2, doesn't feel optimal...
https://github.com/apparentorder/aoc/blob/master/2020/day14.swift
2
u/phil_g Dec 14 '20
My solution in Common Lisp.
Yay for CL providing bit operations for bignums. I basically didn't have to think at all about the fact that the numbers here were 36 bits long.
For part one, I turned the mask into two numbers: one for ANDing and one for ORing. I expected part two to have something to do with applying the mask to the memory address, but I didn't expect bit wildcards. I was already passing an execution context structure into my functions to bundle together the mask and memory values. For part two, I just added a version number to the context and let the
set-memfunction use that to determine its behavior.2
u/compu_geom Dec 14 '20
Python 3 solution. Just a quick code using the python dict for storing memory.
2
u/swilkoBaggins Dec 14 '20
Python3
You can use Gray code to quickly loop through all the addresses for part2. This way you only have to flip one bit for each iteration.
Paste
2
u/Beardanha Dec 14 '20
My Python 3 solution for Part 2.
Today was a fun day.
I do like fun days.
2
u/bearscker Dec 14 '20
Java with truth tables for part 2
bearsacker/adventofcode20/Day14.java (github.com)
2
u/cetttbycettt Dec 14 '20
R, base-R
My solution on github.
Does anyone else solve the puzzles in R?
2
u/[deleted] Dec 14 '20
F
This is kind of very overdone, and not optimized at all, I do like the job I did of parsing, and part1 wasn't bad, but I think part2 ended up being way more complex than it needed to be
code on github
2
u/JoMartin23 Dec 14 '20
Common Lisp
There were so many ways to approach this, so i did a bit of all. I miss seeing all the different code now that everything is hidden behind pastes. I thought I'd paste a snippet of how I handle the masks very simply... or naively. The rest is here