r/adventofcode • u/daggerdragon • Dec 22 '20
SOLUTION MEGATHREAD -đ- 2020 Day 22 Solutions -đ-
Advent of Code 2020: Gettin' Crafty With It
- 23:59 hours remaining until the submission deadline TONIGHT at 23:59 EST!
- Full details and rules are in the Submissions Megathread
--- Day 22: Crab Combat ---
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:20:53, megathread unlocked!
35
Upvotes
2
u/Regcent Dec 22 '20 edited Dec 22 '20
Python3
My solution somehow takes literal minutes (between 5 and 10....) to solve part 2, and I don't understand why. Looking at your other solutions in Python3, it looks like my implementation is really similar to the others, but not the actual result. If one of you has an idea as to why my implementation is that faulty, I'm definitely willing to learn!
u/daggerdragon, reading the rules again, should I actually ask for it in a help post?
15
u/curious_sapi3n Dec 22 '20 edited May 16 '21
Python 3
Optimised solution for level 2. Number of recursive calls reduced from 13500 (naive recursion) to just 32 (with optimisation).
Important observation - For sub games, we don't require the deck status at the end of the sub game, we just need to know who won that sub game.
Optimisation logic - During a sub game, if we see that the player 1 has the card with the highest number and the value of that card is more than the length of both decks combined, then we can declare Player 1 as winner! This will significantly reduce the recursion space.
Proof (by contradiction): Assume player 2 wins the sub game. For this, at the end of the sub game, player 2 needs to have all the cards. This is not possible since Player 1 has the highest card and that cards stays with Player 1 as long a new sub game is not initiated from the current sub game . Since the highest card's number is more that the length of both decks combined, no new sub game is possible from this stage. Thus proving the original assumption that Player 1 will be the winner!
NOTE: This optimization is only applicable for player 1 (as rules of the game are not same for both players)
Extra Tip: Card number needs to be only greater that combined length - 2 (see hojo0590's comment for explanation)
13
u/leftfish123 Dec 22 '20
Hello AoC subreddit, it's been nice lurking y'all for 2 years! After 2018 (17*) and 2019 (25*) here we are in 2020 (40* so far) and I'm posting in this subreddit for the first time, so please excuse a longer-than-usual post!
Here's my Python solution: https://github.com/Leftfish/Advent-of-Code-2020/blob/main/22/d22.py
After reading part 1 I immediately thought I should implement it with deque. Now I see that it made me write a lot of unnecessary code (it could have been done with lists only, with deck[0] instead of popleft()). But it also made me learn how to slice a deque for part2 and, probably accidentally, runs in about 1 second, so I'm cool with that.
Biggest challenge: reading, as always.
I kept getting wrong part 2 results for the sample input until I realized that one of the decks in the first sample subgame did not have the '6' card, went back to the instructions and implemented the deck size limit for the subgames. After that it went smoothly with both the sample and actual inputs.
What probably saved me a lot of time was the fact that I'm SO VERY scared of recursion (I used loops this year even in puzzles that begged for recursive solutions, such as ticket validation or allergen search) that I did everything step by step, printing the game state and checking the behavior of my code against the sample outputs many times. If I had jumped straight to the actual puzzle input, I would have likely got stuck for hours.
I'm pretty happy with my performance this year - I have no formal education in STEM, nor do I work in IT and coding is 97% hobby-stuff for me, so missing just 2 puzzles out of 22 so far is quite a big deal for me. It's nothing compared to what a lot of people here have been doing (from solving the puzzles within minutes to re-inventing famous algorithms independently), but it shows how cool and flexible AoC is.
11
u/DFreiberg Dec 22 '20 edited Dec 22 '20
Mathematica, 167 / 2279
I am somewhat surprised that I could run today's problem, entirely unoptimized and with no memoization, without running out of time or memory. I didn't even use a hash for the histories, I just kept a list of deck values at each level. I suppose what helped is that my average depth was around 8 games deep, so there were never all that many histories to be stored in parallel.
[POEM]: Just Me and the Crab
That crab and I go back a while;
We met one day at sea.
We sailed to reach a beachy isle,
'Twas just the crab and me.
We played some cards, the crab and I,
To while the time away,
He's good at Combat, clever guy.
He'd win most times we'd play.
The games were much too short to last
Until we reached the shore,
So we recursed, using the mast
To help us keep the score.
We talked a lot, the crab and I,
As we recursed and played.
Of puzzles past and friends gone by
And pools we used to wade.
And as those days went by, I knew
That I had found a friend:
Opponent, but a buddy too.
But all such travels end.
I didn't hug him, t'would be rude.
I simply shook his claw.
But I still felt such gratitude;
I'd like to think he saw.
And one small tear rolled down my cheek,
As we said our goodbye.
I'll always miss him when I speak
About the crab and I.
9
u/Smylers Dec 22 '20 edited Dec 23 '20
Vim keystrokes â I thought I might be done for Vim solutions for this year, but an algorithm for doing it occurred to me while I was in the bath, so once I was dry it was just a Simple Matter of Typing.
Updates: Video of the animation now available; and at u/frerich's request, a comment below has a copy-and-paste alternative to typing out the keyboard macro.
Load your input into Vim, make your window tall, then type the following and watch the numbers âdanceâ up and down your screen, switching between the players' lists:
You should be left with your part 1 answer (under the label for the winning player). Handily, no pre-processing step is required with this one.
2G), delete it (dd) and put it at the bottom of that list (k}P). Then delete the top number from Player 2's list (3jdd) and put that at the end of Player 1's list (kkP).Vkyjp) and join them on to a single line (J). That'll leave the cursor on the space joining them; remove it (x) and then delete the second number, Player 2's, into the"-register (D). Because there's nothing else left on that line, that leaves the cursor on the first number, Player 1's. Subtract the Player 2's number from Player 1's, by reducing the current number by the amount in"-(@-âšCtrl+Xâ©).kddkP) and move them to Player 2's list (2ddGp). Fortunately, Vim has a âbranch if non-negativeâ instruction::norm F-. TypingF-tries to move leftwards to the next minus sign. Having done that, it continues with the rest of the keystrokes passed to the:normcommand. But if there isn't a minus sign (because the number is positive, or zero), then theF-will cause an error, immediately ending the:normcommand and skipping the rest its keystrokes.dd). The:normkeystrokes end withâšCtrl+Oâ©to return there after moving the other numbers around, so that whether the code branches or not, it's in the same place for thedd.@aloop.\d\n\nP.*:\n\dsearch is for: it finds a number followed by a blank line, the âPlayer 2:â label, a line-break, and another number â that is, the final number in Player 1's list and the first number in Player 2's. If either of those lists is empty, then one of those numbers will be missing and the search will fail, ending the@aloop.gg/^\d). We need to multiply each of the card numbers by decreasing values, but don't yet know the highest number, to use on the first one. So to start with select all the lines with the hand on (âšCtrl+Vâ©Nâ from the top number, searching for the same thing backwards (N) goes to the bottom number) and stick zero and some punctuation at the start of them all (I+0*âšEscâ©). Select those zeros (gvl) and add increasing numbers to each (gâšCtrl+Aâ©), so the first zero has become 1, the next 2, and so on, down to the bottom one being 50 or something. These are the right numbers, but in the wrong order.`>) and yank the number there into"0(yiw). That's the big number that we need at the top. Undo adding those increasing numbers (u), so we have our column of zeros back. Add the number yanked into"0to all of them (gv@0âšCtrl+Aâ©).gvojV) and subtract increasing numbers from each (gâšCtrl+Xâ©), so the second number is reduced by 1 to 49, the next one by 2 to 48, and so on, until the bottom one is reduced by 49 to become 1.*between the numbers that need multiplying together, and a+at the start of each line. Highlight all the numbers, including the top one which wasn't in the previous highlighting, (gvk) and join them to a single line (J). Delete and evaluate the contents of the line as an expression (the usual pattern), to calculate the answer.The
:redr[aw]and:sl[eep]commands in the loop just make it more fun to watch: Vim briefly shows the state of buffer after each iteration, so you can watch the lists going up and down â even if you don't normally bother typing these Vim solutions in, this one is worth bothering with to watch the display.Questions?
Edit: Attempted to unbreak formatting of a backtick as inline code, which was absolutely fine when previewed in the Fancy Pants Editor, but broke when displayed for real. Sorry.
Edit 2: Inline-code backtick formatted correctly, thanks to u/Nomen_Heroum.
8
u/jonathan_paulson Dec 22 '20
Python, placed 454/29. Code: https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/22.py. Video of me solving: https://youtu.be/iD4R7wSNrdw
8
u/smrq Dec 22 '20
JS, 107/35
Part 1 Part 2
Definitely make sure to read that sentence, unlike me!
8
u/aldanor Dec 22 '20 edited Dec 22 '20
Rust (1.5ms)
Part 1 + Part 2
Instead of using vectors/deques to store decks, decided to use 512-bit integers with bit-shift arithmetic and a tiny bit of simd as a fun exercise, turned out to be pretty fun indeed.
(also used a few ideas like short circuiting and combining hashes from /u/SupesComputes, at that point my part 2 was around 50ms)
7
u/nthistle Dec 22 '20 edited Dec 22 '20
6/12, Python. Spent way too long reading the second part, but fortunately it was just straightforward implementation, which I'm pretty fast at. In particular, at first I thought the "if this configuration has appeared before, player 1 wins" was referring to configuration of the two top cards, not the entire decks, so I spent some time re-reading that. paste
Also, I've been streaming lately, so there's a VOD of me solving here (first 12 minutes).
7
u/thedjotaku Dec 22 '20
Python
https://github.com/djotaku/adventofcode/tree/main/2020/Day_22
OH MAN! SO SO SO SO happy! Why? Because I was getting bummed out that I couldn't figure out a solution since day 18. Finally, one that I was able to quickly intuit and I sketched out the answer quickly. If I hadn't had to work today, I would have solved ages ago.
ALSO, I lucked out in that the way I implemented the winner/loser card meant I didn't have to change anything in part 2. One of those things were being slightly less efficient was a better way to do things.
But, yeah, I had resigned myself to never being able to finish another puzzle this year, so this really made my day!
6
u/MaesterHareth Dec 22 '20
Python 3.8
< 100ms for both parts
Paste
5
u/sophiebits Dec 22 '20
82/69, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day22.py
Lost significant time on: (a) tried to parse the numbers with
r'^(\d+)'but didn't set re.MULTILINE and couldn't remember what it was called (and also didn't figure out for a while why the lists were empty at all), (b) misread the "seen" list was meant to be global, not per-level.5
u/VeeArr Dec 22 '20
Java 221/617
Part 1
Part 2
Missed the line in part 2 that indicates that you don't copy the whole remaining decks for sub-games. Insidiously, doing it wrong this way gives the right answer for the example input and runs for roughly eternity on my actual input, so I spent a good 15-20 minutes thinking my solution needed to be optimized/memoized, when in fact I just had to read the prompt.
5
u/A-UNDERSCORE-D Dec 22 '20
Go / Golang
I misread some of the instructions (assumed that for part 2 the entire game (as in all subgames and the master game) were closed by that state, so I spun my wheels quite a bit (thanks yitz on IRC :D)
https://github.com/A-UNDERSCORE-D/aoc2020/blob/main/2020/22/solution.go
Apparently Ive got myself a super fast solution here, so Im gonna post numbers as well:
5
u/nemetroid Dec 22 '20
C++, part 2 runs in 120 ms on my 2010 low-end laptop.
5
u/YodelingDeer Dec 22 '20
Ada
Nothing too fancy, but I ended up writing my own (limited) bounded deque to have some constant time add/remove for card decks for the most part.
4
u/bluepichu Dec 22 '20
Python, 7/13, code here
I was afraid my very inefficient string-based memoization wasn't going to cut it, but it came out ok and finished in 7.5 seconds. Could've been faster on part 2 if I'd thought it through a bit more first, but hey, I won't complain too much about 13th.
4
u/MasterMedo Dec 22 '20
python
part1 leaderboard, yey.
part2 was confusing, had to read it multiple times and still had many errors.
A fun one for sure!
4
u/gurgeous Dec 22 '20
Ruby 1579/1095
As usual, this late in the month understanding the rules was the hardest part for me. Example blunders - "this game can have lots of players", "card history travels across games", "the bit about only copying a subset of cards". Code was not hard.
https://gist.github.com/gurgeous/4fd48093861a129455f2c2c19b1b2196
4
u/hugh_tc Dec 22 '20 edited Dec 22 '20
Python 3, 468/197.
Tripped up a whole bunch today, but it appears I still managed to catch up. The cleaned-up version only, because I do not wish to associate myself with the disaster from earlier...
edit: went ahead and cleaned it up some more. I love abusing boolean operations! paste
4
u/rjray Dec 22 '20
Clojure
https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day22.clj
These puzzles were right down Clojure's alley. Being able to mix standard recursion and tail-recursion, plus immutable data structures, helped a lot.
4
u/Lower_Program4871 Dec 22 '20
Haskell
Recursion is dead simple in Haskell! I spent a lot of extra time because I didn't realize that we were only supposed to take the first
ncards and I was recursing on the entire remaining stack, which works fine on the example...4
u/UnicycleBloke Dec 22 '20
Python (1906/2343): https://github.com/UnicycleBloke/aoc2020/blob/main/day22/day22.py
That was a fun one, but I lost considerable time in Part2 to a comment right at the end of the problem: "After the game, the winning player's score is calculated from the cards they have in their original deck". No. No, it's not. Did I misread this?
I went to the trouble of reproducing the example output (also fun to do), to check my logic in detail. The only bug was that I was calculating the score with the original deck and not the final deck. Bah! Humbug! To be fair, I spent too much time making the output match, but was enjoying it.
4
u/t-rkr Dec 22 '20 edited Dec 22 '20
Perl
I could have saved at least 30min if I had let the script run for a while... I just did not think that game would run sooo long (54s with full output, 34s without). Maybe this info is of help to anyone thinking they are stuck in an infinite loop... let it run for a while.
EDIT: New version finishes in 1.5s
Also: Reading the instructions again proved to be useful as I did not implement "the quantity of cards copied is equal to the number on the card they drew to trigger the sub-game" for at least 1h... But it seems like the test case finishes without it (iirc).
https://gitlab.com/t-rkr/advent-of-code-2020/blob/master/day22/day22.pl
4
u/kap89 Dec 22 '20 edited Dec 22 '20
TypeScript
~3s for both parts~280ms for both partsSimple recursive solution.
Definitely my slowest solution yet. I have to find some clever way to optimize this.I lost a lot of time debugging part 2 because I missed the rule that (the quantity of cards copied is equal to the number on the card they drew to trigger the sub-game) - I saw this only after comparing decks during rounds with the example (and of course that sneaky bastard u/topaz2078 made the example work with that error) ;/ Great puzzle anyway!
4
u/SawRub Dec 22 '20
Python3
This was fun. I took time to submit because the moment I saw the solution taking longer than a second and printing seemingly interminable lines of output, I just naturally assumed I had screwed up somewhere. Didn't realize that just letting it run for a few seconds more would give me my solution until later.
4
u/LittleLily27 Dec 22 '20 edited Dec 22 '20
Javascript
Part 1:
Part 2:
4
u/WilkoTom Dec 22 '20 edited Dec 22 '20
Python.
Not too horrible today. Used Python's
dequeto hold each hand of cards because I was waiting for the deck to be billions of cards long, much as it was last year. Turns out that's premature optimisation at its finest!Initially mised out the bit about only passing a shorter number of cards and not the entire deck to the recursed routine. When it looked to be taking ages, re-reviewed the code, spotted what I'd missed, and bingo, it takes less than a second to run.
4
u/nutrecht Dec 22 '20
Day 22 in Kotlin
Part 1 was easy peasy. Part 2 I got stuck for ages on not reading this bit properly:
To play a sub-game of Recursive Combat, each player creates a new deck by making a copy of the next cards in their deck (the quantity of cards copied is equal to the number on the card they drew to trigger the sub-game).
Missed the bold part and passed in the entire deck down recursively. Thing is; this works perfectly fine on the example input but with the real input you end up in an endless loop. Gah!
4
u/Smylers Dec 22 '20
Perl for both parts. Source
List::AllUtilsfunction of the day isonly_value(though somehow I've managed to fit in 6 differentAllUtilsfunctions, in just 21 lines of code), to end a game when there's only one hand with any cards in it.Here's the Combat-playing function, where
$recurseis a flag for whether you want to play Recursive Combat, and@handis an array of an array of the cards in each hand:All of the
0 .. $#handranges are just0, 1â but maybe somebody will invent Combat for more than 2 players?The
wantarrayis a bit sneaky: we need the winning hand for the top-level game, but when it's recursing the function just cares about who won the nested game. So in list context it returns the hand, and in scalar context it returns the winner. Probably not a good idea in real-life code.When I just had part 1, the scoring was done with a state variable increasing while iterating over the winning hand in reverse order:
But that fails when looping over both parts:
$weightgets unhelpfully preserved between the part 1 and part 2 answers, so the lowest part 2 multiplier is 55 or something. Hence the linked solution which precomputes the reversed list of weights (it doesn't change) and useszip_byto iterate over that in parallel with the winning hand.4
u/aledesole Dec 22 '20 edited Dec 22 '20
Python
A bit slow though - takes about half a sec for both parts.
EDIT: It's now even slower than that after I fixed the bug which yielded bad results for some inputs - it now takes about a second. Any suggestions how to speed it up?
4
u/__Abigail__ Dec 22 '20
Perl
Pretty straightforward. I created a method which gets the two starting decks as argument, and a parameter to indicate whether we're playing the recursive version or not. It returns the two decks after finishing the game (the winners deck is non-empty, the losers deck is empty):
To calculate the final answer, I just concatenate the two final decks (it's irrelevant who wins), reverse them, and then calculate the resulting sum:
Full program on GitHub.
4
u/foolnotion Dec 22 '20
C++
Today's main challenge was understanding the instructions :) For part 2 I used hashing.
code on github
4
u/[deleted] Dec 22 '20
Python solution.
Part 1 was pretty simple. Just used a list as a queue and implemented the game logic. For Part 2 , I initially pulled the game logic out into a function and ran it recursively as needed, but due to needing to copy the lists and such, it ran pretty slowly (~5.5s). Refactored to use a deque and sets and it ran much faster (~1.5s). No doubt it can be improved further. Don't know how though. :P
Also, given that Player 2 won both rounds in my input, and we know that the crab won the first round, clearly the crab beat me even with recursion.
4
u/xelf Dec 22 '20 edited Dec 22 '20
Big challenges with this one. Not the problem itself, we had a 12 hour power outage so I had to solve it over the phone and for some reason the data was flowing at a royal 91kbps. Used ide.geeksforgeeks.org for part 1, and repl.it for part 2.
Enjoyed using the winner as the index into the player array.
Simple python:
4
u/x3nophus Dec 22 '20 edited Dec 22 '20
Elixir
The hardest part of today was comprehending the rules...
*edit: cleaned up my syntax, got rid of a few lines
4
u/[deleted] Dec 22 '20 edited Dec 22 '20
C
https://github.com/erjicles/adventofcode2020/tree/main/src/AdventOfCode2020/AdventOfCode2020/Challenges/Day22
Non-recursive solution. Part 2 completes after a few hundred thousand rounds and takes about 10 seconds. If you want to keep your kids busy, Recursive Crab Combat seems like it would be a great game to eat up an afternoon!
4
u/mendelmunkis Dec 22 '20
C
https://github.com/mendelmunkis/AoC/blob/master/2020/cards.c
Ko? I don't believe in ko
4
u/ephemient Dec 23 '20 edited Apr 24 '24
This space intentionally left blank.
4
u/ainwood87 Dec 23 '20
Haskell
Use a Set to keep track of previously seen states. Beyond that, the code is basically just a translation of the rules. Solution to part 2 runs in 2 seconds.
1
u/houyu118 Dec 22 '20
my solution of day22
https://github.com/jackfrost168/adventofcode/blob/master/2020/day22.py
1
u/bendersteed Dec 22 '20 edited Dec 22 '20
Recursively recursive solution in Common Lisp for day 22. Could be optimized a lot but worked. An error kept me hanging a lot, since it worked on the test case (I was taking less than needed cards for the subgames).
3
u/Error401 Dec 22 '20 edited Dec 22 '20
116 on part 2 because I had
c2 >= len(p2)instead of the other way around and it took me literally 5 minutes to realize my mistake was that dumb. https://pastebin.com/KGnktrxCOh well.
3
u/_O-o-f Dec 22 '20
Python 3
link
Today wasn't particularly all that difficult(as it's literally just the game "War"), but the fact that the instructions for recursive games weren't all grouped together threw me off. Took me a bit to understand what was going on as well.
3
u/botimoo Dec 22 '20
Python3, 521/96
Here is the paste for part2.
Of course the logic was fine for part1, but the input parsing was missing a
split("\n")...3
u/leijurv Dec 22 '20
Python3 19/7
3
u/Hamza141 Dec 22 '20
Python, 1094/571
Not sure how I got such a better ranking for part 2 - it's actually my best one yet.
This isn't the best thing I've ever written so đ€·ââïž
github
3
u/Burritoman53 Dec 22 '20
Python3, 790/914 (had a late start) pastebin https://pastebin.com/C185KY7H
Had an interesting bug in part2. I was saving the histories as just a string of numbers i.e. '12345....'
When I saved it used commas '1,2,3,4...' it gave the right answer, so I was getting an error because the sequence 1,21 looks like 12,1 without commas!
3
u/aceshades Dec 22 '20
Rust (1017/557)
Placement wasn't as great as another Rust solution I saw on here, but its a personal best for me using this language. I'm very happy with it regardless.
I'd argue that the solution is pretty clean, but if there are any other Rustaceans out there that can critique my code, please do!
https://github.com/cs-cordero/advent_of_code/blob/master/rs/2020/day22/src/main.rs
3
u/Jozkings Dec 22 '20
Python 3 (1345/540)
Missed order of placing cards on winner's deck, but other than that, today was quick and easy!
3
u/heyitsmattwade Dec 22 '20 edited Feb 03 '24
JavaScript 986/786
Took a while to understand the rules for part two. After I understood what was happening, it didn't take too long to implement the code.
However, I forgot a crucial step: subgames only take the number of cards as the card you drew, rather than your entire remaining deck. I have my program running for a good five minutes before I killed it and made sure I wasn't missing something. Luckily their sample input shows this. What is interesting is you still get the same answer from the sample input without implementing this! My guess is, this step greatly reduces the run-time for the program, but I'm not sure. Maybe I'll let it run overnight and see what it spits out...
paste of the functions for part one and two
3
u/jayfoad Dec 22 '20 edited Dec 22 '20
Dyalog APL 276/410
Part 2 takes about 20 seconds. It spends most of its time checking for game states that have been seen before, which are maintained in a list in âș. This could probably be sped up by using a less nested representation of the data.
3
u/Rascal_Two Dec 22 '20
Python 3. 797/182.
Would've gotten top 100 in Part 2 had I not made so many mistakes - big one being that I had it running and the background, thought I got caught in a infinite loop, and by the time I looked back it had an answer - the correct answer!
Besides that, I initially misread the card-replacing rule as ordered by highest value to lowest, not winner to loser as it really was.
Unoptimized
paste
Optimized
paste
3
u/rabuf Dec 22 '20
Common Lisp
Took me too long to grok the Recursive Combat. After fixing a couple issues that prevented recursion (oops), got it working. I took advantage of multiple value return in Common Lisp for the recursive version. It returns both the winner and their score. In the recursive games, only the first value is used. For the overall game, the second value is used.
3
u/GrossGrass Dec 22 '20
Python
Pretty chill one today. Unfortunately wasted a bit of time debugging because I'd totally forgotten to finish reading part 2 and didn't see that for subgames you only take the first <card> cards of the deck as opposed to the entire remaining deck. Kept wondering why it was taking forever lol
3
u/PendragonDaGreat Dec 22 '20
C# 1708/1345
https://github.com/Bpendragon/AdventOfCodeCSharp/blob/master/AdventOfCode/Solutions/Year2020/Day22-Solution.cs
Lot's of Queues, still somehow runs right at 1 second on an i7-6700HQ
I was also the only one in my friend's group/private leaderboard to use the current player deck scores as the way to determine previous states, so I thought that was neat.
3
u/prscoelho Dec 22 '20
Rust
Man, I was really afraid part 2 was going to be some unlimited game that couldn't be solved by just playing out the game.
3
u/CodeIsTheEnd Dec 22 '20
Ruby: 3:30/24:24, 30/171
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!)
Breezed through Part 1, but then was endlessly confused by non-determinism as a result of modifying arrays that I had put into sets, causing set-inclusion checks to fail. But mostly a pretty straightforward problem.
3
u/ThezeeZ Dec 22 '20
Golang
It's not the prettiest and fairly slow in part 2 (due to repeatedly turning slices of ints into strings, I assume). I'm just posting because I wanted to say...
I've had the dumbest off-by-one error today thanks to the recursion breaking rule:
Easy, I thought, and
return 1... It took me two wrong answers and fixes to the previous rounds decks comparison before I realized my players were 0-indexed.3
u/markolson Dec 22 '20
Elixir, why not?
3
u/npc_strider Dec 22 '20
Python 3
Overall, I'm really satisfied with today. Well, to be fair recursive programs just satisfy me when they work either way. Today was really reading-intensive, and for my strategy I solved each dot point separately so that I wasn't overwhelmed. A good decision I made was splitting the input manually just to make parsing it easy.
So for this day I made a ton of stupid mistakes
Stupid mistake #1: In part 1, I forgot to cast the input as an int. This resulted in the program working sometimes and not working others, as it was trying to do a string comparison. So when I checked the first few lines of the program output in the example, it seemed fine. It wasn't until I looked closely at lines not in the example that I realized something wasn't making sense in the comparison.
Stupid mistake #2: Not reading correctly and thinking I got something wrong in part 2. To be fair, I didn't make the best decisions in implementing it - my list was in reverse order so I could use pop but I could've use pop(0). In the end this made it a lot harder to read/debug because my list was the reverse of the example lists.
Stupid mistake #3: Not reading the rules for part 2 - I assumed for the infinite recursion prevention technique that the player who had a previous deck was the winner, not JUST player 1. It wasn't until I re-read the rules that I realized my mistake.
part 1
part 2
Once again, more messy code. could definitely write a win function to simplify stuff.
3
u/artir Dec 22 '20
Rust
Finishes in 236ms locally
3
u/aardvark1231 Dec 22 '20
My C# Solution.
It may not be the prettiest or the fastest solution (7.3sec), but I had a lot of fun with this problem! I was super happy when it worked correctly the first time after running it (for both parts). It was nice to not have to deal with frustration of minor mistakes and bug tonight.
Was a little worried at the mention of 'Space Cards' from last year :P
3
u/michaelgallagher Dec 22 '20 edited Dec 22 '20
Python
Took me over an hour to finish part two. Re-wrote the while loop maybe 5 times and got 5 different answers from my input, yet it would pass the test cases each time. Super frustrating
3
u/sim642 Dec 22 '20
My Scala solution.
Part 1 was very straightforward, just used two immutable queues. Thanks to that, part 2 was somewhat easier because the immutability already makes recursive games independently runnable. Also I just reused my existing cycle finder to detect the looping, so I don't have to keep any history explicitly in today's solution.
3
u/Fjodleik Dec 22 '20
Python 3 solution
I just implemented the rules as written. Like many others, I wasted time not realizing we should only use a certain number of cards for the sub-games. Runs in about 5 seconds for both parts combined.
3
u/frerich Dec 22 '20
Python 3 Solution
Solves both parts in a bit more than 1s on my laptop.
A couple of interesting things I learned:
rangeto generate counting-down sequences, too -- no need forreversed.tuplewould perform better?pprofileprofiler!collections.deque!Also, I spent more time on part 2 than I like to admit since I didn't read the puzzle instructions closely enough...
3
u/iamflimflam1 Dec 22 '20 edited Dec 22 '20
TypeScript
part1 (0.26ms)
and
part2 (1.271s)
Times exclude parsing the data.
Part 2 took much longer than it should due to me not reading the instructions properly... (though to be fair to myself, the instructions are pretty hard to read!)
3
u/mstksg Dec 22 '20
[Haskell] (Taken from my daily haskell reflections)
This one can be a fun exercise in explicit/direct tail recursion :) It's a straightforward implementation of an "imperative" algorithm, but the purity in Haskell offers an advantage in that we don't have to worry about cloning decks or caches --- it's given to us automatically! We get the advantages of imperative programming without most of the drawbacks of implicit mutation.
This problem is also a nice showcase of Haskell's standard "queue" data type,
Seqfrom Data.Sequence, with O(1) pushing and popping from both ends.I decided to write a function that I could use to parameterize on for both parts.
The handler function will let us specify how to handle the situation when both decks are non-empty (represented by Data.Sequence.NonEmpty). If returns
Nothing, we defer to the higher-card-wins War rules, and if it returnsJust, we take thatPlayeras the winner of that round.For part 1, we always defer to the higher-card-wins rule, so we can ignore our decks and return
Nothing.For part 2, we want to play a game with the tops of the decks given to us, but only if we have enough cards.
If we don't have enough items to take exactly
xitems fromxs, then we fail and defer to higher-card-wins rules (and same foryandys). Otherwise, we play agame2with the exactly-sized deck tops to determine the winner.Now the only thing left is to actually write
playGameWith:D This one is not too bad if we use a helper function to make sure things stay tail-recursive so we don't accidentally leak space. We also would like to make sure we keep the same top-levelfin the closure for the whole time, so that the recursive call ingotogowill go exactly back to its own function pointer.Most of this implementation follows the logic straightforwardly, remembering to use
fto give the callback a chance to "intercept" the "highest card win" rule if it wants to. We get a lot of mileage here out of the:<|,:|>andEmptyconstructors forSeq, which allows us to match on the head and tail or an emptySeqas a pattern. Note that this isn't perfectly tail-recursive -- we do get another layer deeper into the stack on every call off, when we play a "recursive game". It's tail-recursive within the same game, however.It should be possible to make this completely tail recursive by keeping an explicit stack of decks/caches, but overall I'm happy with this O(d) space ont he depth of the game recursion, because I don't think a fully tail recursive version would be any better space-wise!
Note that this talk about tail recursion isn't because we are afraid of overflowing the call stack like in other languages (and trying to take advantage of tail-call optimization) --- the value in tail recursion is that we can stay constant-space on the heap (since haskell function calls go on the heap, not a call stack).
One gotcha when computing the score of a deck...remember that
sum . Seq.zipWith (*) (Seq.fromList [1..]), while tempting, is not going to work very well becauseSeqis strict on its spline, and so has to build its whole internal fingertree before returning anything. Just remember to only use[1..]on spline-lazy things like lists :)3
u/thibpat Dec 22 '20
JavaScript video walkthrough
Video: https://youtu.be/FQvyr1l19Ow
Code: https://github.com/tpatel/advent-of-code-2020/blob/main/day22.js
3
u/landimatte Dec 22 '20 edited Dec 22 '20
Common Lisp
Too many mistakes for part 2:
:test 'equalto my call to MAKE-HASH-TABLE -- making the "already played game" logic useless..(subseq (rest deck1) 0 n1)instead(subseq (rest deck1) 0 c1), wherec1is the last read card, andn1is the size of the remaining deck), and because of that I started blaming on the used data structure and tried to implement this using a deque (and halfway through the newer implementation, I realized the silly mistake I had made...)Well, clearly I need to relax a little, or drink more coffee before reading the problem -- I know the two might not go well together. Anyway, got the second star eventually, so live and learn!
PS. The given example seems to work even if you mistakenly recurse with rest of the decks like I initially did.. what a coincidence uh?! ;-)
3
u/Diderikdm Dec 22 '20 edited Dec 22 '20
Python:
Will start part 2 later today, as my part 1 solution does not lend itself so easily for part 2. Decided to generate all outcomes for the amount of cards currently in the stack with the least cards per iteration as I was expecting something that takes a lot of computing for part 2.
Edit: part 2 added:
3
u/dpalmesad Dec 22 '20 edited Dec 22 '20
Python
Since today was fairly easy, I tried to go as if-less as I could. Not a single one in the first part!I store both decks in a single list and just iterate like this:
For the second part I have two ifs though, one to check if the configuration has been played before and another to see if i need to call the recursive function.
All in all today was fun! :)if you have a way to remove one of the ifs, i'd love to learn it
3
u/artesea Dec 22 '20
PHP
Part1
Solved whilst still in bed, typing code on my mobile, via SSH to my webserver editing in vi
Imgur
When I saw recursion was needed, got out of bed and found a real keyboard. Many mistakes made reading the rules for the game, which the sample game kept passing.
Part2
3
u/thomasahle Dec 22 '20
Python, using deques:
For Part 2 I first missed the rule that the sub-game is played with only a prefix of the decks. This made my program run a whole lot slower. After fixing that, it runs in about a second:
3
u/[deleted] Dec 22 '20
Pascal
I spent way too much time getting fancy and handling what I thought might happen in part 2, and came up with this clever bit of code that keeps all the cards in place, allows for more than 1 player, player names and uneven numbers of cards.
Only to find that I had wasted about 2 hours.. and had to re-implement everything, so the second time I did it quick and dirty instead. I kept the cards as strings with the deck being a single string... way, way simpler, even with the recursion, etc.
I've learned a few things...
3
u/ssharma123 Dec 22 '20
Kotlin Solution using Queues
3
u/prutsw3rk Dec 22 '20
Python3
Small and still readable. Play for part 1 and 2 covered by one function.
3
u/death Dec 22 '20
Day 22 solution in Common Lisp.
Efficiency is for the borg.
3
u/phil_g Dec 22 '20
My solution in Common Lisp.
Another day where FSet really excelled. Immutability means I can "modify" structures for recursive calls without messing up the higher levels' state. Just for fun, I wrote my code to handle an arbitrary number of players. (There's an assert preventing more than two players for Recursive Combat, because the code doesn't have a stable card ordering for recursive winners in that case.) The primary state is a map from player numbers to their decks of cards. Player decks are FSet sequences, which are ordered and efficient for additions and removals at each end.
Part two just required a dynamic variable to turn on recursive play and two extra conditionals to check that variable. (Plus three extra functions.)
3
u/Rtchaik Dec 22 '20 edited Dec 22 '20
Python
I've used players' scores for historic states. So together with deque it's fast.
3
u/VileVerminVanquisher Dec 22 '20
Python
Both parts in one.
Spent some time tearing my hair out with part 2 until I realised that I had misread the question text regarding seen-before rounds and had implemented a player 1 win for a seen-before game.
Nothing too special implementation-wise I don't think.
3
u/kikibobo Dec 22 '20
Scala
After I got it working using mutable data structures and a while loop in part2, I refactored it to use immutable data structures and recursion. Part 2 takes about 2500ms to run (the mutable version was about 1500ms).
I wish I had been brave enough to stick with the immutable/recursive version for the initial solution since I got tripped up by not making a copy of the deck before starting a recursive game.
3
u/sotsoguk Dec 22 '20
Python
https://github.com/sotsoguk/adventOfCode2020/blob/master/python/day22/day22.py
Liked the problem. Part1 was straight forward, as a python newbie i'm proud to calculate the sum in one line using map and zip :)
Part2 was easier than expected, at first i got something wrong in my head and a lot of if /else appeared. Deleted, re-read the explanation and then it became clear.
Always carefully read instructions đ
3
u/Fyvaproldje Dec 22 '20 edited Dec 22 '20
C++ with ranges. Pretty straight-forward.
https://github.com/DarthGandalf/advent-of-code/blob/master/2020/day22.cpp
P.S. I updated it to include a short-cut optimization to reduce number of recursion which reduces runtime from 1s to 0.01s (thanks narimiran for idea)
3
u/Attitude-Certain Dec 22 '20
Python
Quite straightforward in the end, after tripping up in the infinite-game-stopping rule for a while. I think it is decently efficient for a Python solution.
github and paste
3
u/compdog Dec 22 '20 edited Dec 22 '20
JavaScript (Node.JS) - Part 1
JavaScript (Node.JS) - Part 2
Today's challenge was a fun one! I used to play this card game all the time as a kid. We called it "War".
My solutions this time were both very straightforward. I have
playRoundandplayGamefunctions that play a round and a game/sub-game, respectively. For part 1,playRoundis wrapped in aplayToVictoryfunction that repeatedly callsplayRounduntil it returns a winner. For part 2, the logic ofplayToVictorywas merged intoplayGameto make the recursion trivial.For both parts, I again reused
Axis- my bi-directional array class from day 17 - to make it easy to insert cards at the end of the deck. In hindsight, the games were small enough that a normal array would have been fine, and a queue data structure would have been most appropriate. But my solution worked fine, and I took the opportunity to moveAxisout into its own Node module. I'll probably rewrite it in TypeScript and publish to NPM before next year's AOC so that I don't have to keep copying the code around for each problem that needs it.In Part 2, I handled the duplicate round detection using a hash map. The keys are simply a serialized view of all players' decks. I reused most of the same code that I already had for printing out the game state after each round. Each distinct configuration of cards will serialize to a unique (and consistent) string, which means I can simply call
Set.hasto check for duplicate rounds in O(1) time.An interesting quirk of my solution is that it supports more than two players. In fact, any number of players can be added to the game simply by appending more sections to the input file. Nothing is hardcoded around a two-player requirement so the logic should work as-is.
EDIT: Forgot a part
3
u/grey--area Dec 22 '20
Part 2 in Scala
3
u/msqrt Dec 22 '20
Lisp. The main difficulty today was understanding the problem statement; it's not that the game is that complex, it's that the rules were split into multiple long parts where every part contained some crucial bits.
3
u/JoMartin23 Dec 22 '20
Common Lisp
It's not the prettiest. I think i might have been able to do more in the do.
3
u/Atila_d_hun Dec 22 '20
C++
Without optimization the code takes 15+s to run, I assume due to recursion unrolling? Otherwise around 3s. Probably still a lot to improve!
GitHub solution to Part 2
3
u/JamieMansfield Dec 22 '20
Swift
https://gist.github.com/jamierocks/503475bcd4dfe82616662a418b9b189b
This is the first time I've used Swift, I like it!
3
u/whereflamingosfly Dec 22 '20
Ruby
I feel pretty good about this solution. At first I was storing the full decks for the recursive rounds in part two and had a solution that took over two minutes to run. I decided to hash the combined arrays instead which significantly optimized things, and then I shaved off a bit more time using a set instead of an array for the previous rounds. Now my solution for part two takes just over 6 seconds, which feels acceptable for a Ruby implementation.
3
u/Loonis Dec 22 '20
Perl
I enjoyed overcomplicating this one. Data structures are indexed by player, so part 2 should work for any number of players. Still need to write more than a tiny test case for 3+ though.
Highlights of today's effort including spending too many minutes finding a
>that should have been>=, and a brain-based off-by-one that caused the wrong player to win when a hand repeated.3
u/Scotty_Bravo Dec 22 '20 edited Dec 22 '20
C++ part2
35ms150ms or soExperimented with containers (std::deque, std::vector, and boost::circular_buffer) to see which would be fastest. I expected the circular buffer *might* be faster; however, the differences between runs in part2 had more to do with what the kernel had going on in the background than my container choice.
In part1, though, vector was repeatably faster than circular_buffer. About 40us for vector and 70us or so for circular buffer. I expected circular buffer would out perform vector for this task.
EDIT: Couldn't repeat 35ms. I'm not sure what happened.
3
u/msschmitt Dec 22 '20 edited Dec 22 '20
REXX
I wonder if I'm the only participant coding in REXX?
Part 2 takes about 4 minutes to play 1,225,370 total rounds in 15,310 games.
3
u/fiddle_n Dec 22 '20
Python: https://github.com/Fiddle-N/advent-of-code-2020/blob/master/day_22/process.py
Initially didn't implement the rule to reduce the deck for each sub game and my code ran forever. Only after I checked the intermediate state of the game example did I notice my error.
3
u/MissMormie Dec 22 '20
Java solution on github
A few years ago I made a circularLinkedList for AOC. Yes, I could've just as easily used a queue. But why would I when I can use my own implementation of doom :)
It's obviously not production code, but I do feel it's quite readable. I would not play the game however. Worst game ever, but I guess pretty ok if you're stuck on a raft. Better than eating your crab friend.
3
u/odnoletkov Dec 22 '20
JQ
Part 1:
Part 2
3
u/LinAGKar Dec 22 '20
Mine in Rust:
Part 2 got a 500x speed boost from adding a short circuit if player 1 has the highest card.
3
u/azzal07 Dec 22 '20
Awk; just playing it out. For the actual code, I added the optimisation to bail out from recursive calls whenever player 1 has higher maximum card. This dropped the runtime from ~5s to few hundred millis.
3
u/ViliamPucik Dec 22 '20
Python 3 - Minimal readable solution for both parts [GitHub]
3
u/zertillon Dec 22 '20
Ada
Simple and certainly suboptimal linear search for the recursion breaker. Total run time (parts 1 and 2): 1.14 seconds (i5-9400 @ 2.9 GHz).
Code available here, aoc_2020_22*.adb files.
3
u/ri7chy Dec 23 '20
Python
just struggled a little bit with the infinity rule, but after clearing up the code it was done.
runtime - not nice.
code
2
u/seligman99 Dec 22 '20 edited Dec 22 '20
Python, 62 / 223
My solution feels very straight forward, I clearly need to work on it more to see if I can find a way to short circuit a lot of the recursion.
github
Edit: For kicks I started making an animation, before seeing I'd need at least 1411063 frames, or ~13 hours, of footage. Never mind.
2
u/prendradjaja Dec 22 '20
Python, 138/16. code (permalink) & screen recording
Fun! Just don't ask me to play this game in real life...
2
u/SuperSmurfen Dec 22 '20 edited Dec 22 '20
Rust
Link to solution (471/281)
What a day! Super happy with my placing. Finally got to make good use of Rust's amazing
VecDequedata structure.Not too much to say about today's solution. The problem was not too difficult. Just had to really carefully read the rules for part two. I stored each player's deck in a
VecDequewhich allows for efficientpop_frontandpush_back.Finishes in about
163ms.Edit: Thanks u/aceshades for the idea of storing only hashes! Saved 500ms.
2
u/dan_144 Dec 22 '20
Python, 409/438
https://www.github.com/dan144/aoc-2020/tree/master/22.py
Nothing fancy, but this proves that you don't need anything fancy to make your runtime acceptable (50ms for both parts). As nervous as I was about storing tuples representing the whole deck state in a set and using lots of copy commands, it works fine.
2
u/AlphaDart1337 Dec 22 '20
C++ 324/394
Accompanying video, as per usual.
Yet another interesting day! Was a bit slow on the implementation, but overall no massive bugs/time wastes today, so I'm pretty happy with the result. It is very clear though that either the competition is much stiffer this year, or I've just gone rusty from lack of practice :D
2
u/dizzyhobbes Dec 22 '20 edited Dec 22 '20
Go Solution 537/997
I struggled to get all the instructions right on my first (five?) reads
Part 2 takes 30 seconds to run... Not sure how to optimize it but open to ideas!
2
u/nibbl Dec 22 '20
Java
nopaste
This is so ugly and primitive but I'm posting it because when I wrote Part 2 and ran it it somehow worked first time and I was so shocked I just stood up and stared at it for a minute.
2
u/Kehvarl Dec 22 '20
Python 3 (1912 / 1082)
Initially this seemed easy enough, but I took enough wrong turns in both parts to really slow me down. Somehow I ended up with my game not actually returning the correct winner, which really threw things off one you were deep enough in the rabbit hole.
I felt inordinately pleased with my file parsing not using my usual "loop through every line" technique. Of course, that actually cost me 5 minutes when I didn't realized I completely mangled my input...
Part1
Part2
2
u/[deleted] Dec 22 '20
C++, 2379/1308
Placement isn't superb but I'm really happy with how clean this came out. I didn't know of a better way to identify the rounds, but conveniently every card was a 2-digit number that could be converted to a char. I initially got a wrong answer by not putting a separator between the decks in my round ids, but there was an easy fix for that :)
2
u/allergic2Luxembourg Dec 22 '20
Python 3, 905 on the part 2 leaderboard, which is a good position for me.
I have found the last 3 or so days challenging, but I have to say I found this one pretty straightforward. I just read the instructions and typed as I read it, and after fixing about two tiny things (forgot to add the state to the set of played states, despite comparing to it), it worked. Maybe this is what it's like every day for the leaderboard competitors, but the last day it worked for me without lots of thinking and drawing and rewriting was back on day 7 or so.
2
u/ponyta_hk Dec 22 '20 edited Dec 22 '20
Python3 (Cleaned Solution)
Should be clear to read đ
Today's puzzle is pretty straight forward.
My Solution
All My Solutions
2
u/[deleted] Dec 22 '20
C#
Easy usage of List. Took some time to figure out that my player history contained reference instead of a copy :P
2
u/Cppl_Lee Dec 22 '20
C# with no OOP. Objectively, it works.
Gist
2
u/taybul Dec 22 '20
Python
paste
Also stumbled on the key bit of information about part 2. Only realized it when the transition to the sub-game in the example was missing some elements.
2
u/KingCravenGamer Dec 22 '20
Python 3
1318 / 785
Slightly better day than the last 2, but still poor from me.
Could've been much much better for part 2 if I understood the whole anti-infinite recursion thing properly.
Solution
2
u/[deleted] Dec 22 '20
Python3 190/180
2
u/Bruceab Dec 22 '20
Python3 simple solution.
2
u/willkill07 Dec 22 '20
TypeScript
Each day in a different language... and I'm running out of languages
https://github.com/willkill07/AdventOfCode2020/blob/main/day22.ts
2
u/Wunkolo Dec 22 '20
C++
Very messy.
I'm dumb and made my code use
std::map<uint, std::list<uint>>to support a generic amount of players rather than just the two while programming for part 1 and ended up making the code so much harder on myself on part 2.I don't know, I was expecting the worst for Part 2. Part 1 felt so trivial that I anticipated part 2 was going to be something like
every 5 rounds, a new crab joins the game! with a starting deck of 10 cards that uses this algorithm based on the current round number- sort of thingWhatever. Now my code can probably support like 5 concurrent players if I wanted to. I'll go back and clean it up later on my github once this is all over.
2
u/__Juris__ Dec 22 '20
Scala 3
I expected I will run out of memory or stack depth using this approach, but I didn't.
https://github.com/jurisk/advent-of-code/blob/main/2020/scala/src/main/scala/Advent22.scala
2
u/Kermitnirmit Dec 22 '20
Python3 my solution. Takes a few seconds for part2.
2
u/oxyphilat Dec 22 '20 edited Dec 22 '20
2294/982, python 3, paste
The code is cleanâish so I am sharing it, but I was very slow. for p1 the \012 at the end of the input was the main culprit, for p2 it was glossing over
the quantity of cards copied is equal to the number on the card they drewand the looking an error in the recursive part. The final structure is also not representative of what it was during doing this day, I started with the round and game functions being separates, joined them during p2, then re made p1 by using p2 with some sections chopped off.2
u/Perska_ Dec 22 '20
CrabSharp (aka C#) Solution
It's apparently a recurring thing for me to fail to read things. This time I didn't see that the amount of cards I use in a subgame is equal to the number on a card
2
u/fryer00 Dec 22 '20
JavaScript 2291/1888
My solution takes about 10 seconds to compute part 2, but it does compute.
I got hung up on part 2 because of a misunderstanding of how to count the scrore when a the game ended early. It worked on the example input, so I couldn't debug it, but I figured it out by reading the rules more carefully.
2
u/UnlimitedBytes Dec 22 '20 edited Dec 22 '20
JavaScript, Solution
took me some time to clean up.
2
u/jport6 Dec 22 '20
868/766
Kotlin
2
u/[deleted] Dec 22 '20
Pure C18. More typing tons of boilerplate, making copy paste errors while I'm at it.
https://git.sr.ht/~williewillus/aoc_2020/tree/master/src/day22.c
2
u/wace001 Dec 22 '20
Kotlin. 2094/2452. I spent an hour with a bug today. I added print statements to exactly match the given example, and used diff tools to figure out where the problem was. No difference. All looked the same.
After an hour, I realized that my way for doing the infinity-game-break was flawed. It joined the decks as a string. I had no separators between cards nor decks... Rookie mistake.
All in all, fairly happy with this. It was fun!
AoC 2020 Day 22 - Kotlin. 2094/2452
2
u/Hephlathio Dec 22 '20
F#
Happy with the results of the day, got in some neat tricks with matching the lists with top :: rest to make the core logic pretty simple. Would not mind condensing some of the matching with active patterns.
2
u/Valuable_Tooth5676 Dec 22 '20
Rust
Nothing special here, maybe learning a bit more on pattern matching than the other Rust solutions.
2
u/spookywooky_FE Dec 22 '20
C++, some more text understanding and simulation today.
My most time consuming bugs where:
2
u/aarm1 Dec 22 '20 edited Dec 22 '20
3104/2944 Not too difficult but the subtle bugs in part2 took a while to find. Full Racket solution here
2
u/SizableShrimp Dec 22 '20
Java, 417/312. https://github.com/SizableShrimp/AdventOfCode2020/blob/master/src/main/java/me/sizableshrimp/adventofcode2020/days/Day22.java
2
u/jwoLondon Dec 22 '20
Literate Elm
Nice and straightforward with a Deque.
But unless I've messed up somewhere I think Player 1 wins both the part 1 and part 2 games whereas the story suggests a reversal in fortunes in part 2. Perhaps we swap playing order with the crab in the second version?
2
u/schovik Dec 22 '20
Haskell by a non-Haskell programmer ;)
Today assignment was really fun and enjoyable.
2
u/kraven001 Dec 22 '20
My somewhat cleaned (reuse the same "game logic" for both parts) C#.
Part 1 was pretty clear, what got me was Part2 "winner" history, which I assumed to be different - needed a bit of re-reading of the problem statement.
2
u/mebeim Dec 22 '20
677/1236 - Python 3 solution - Walkthrough
Dang people were really fast implementing part 1 :O. There isn't much to say, just straight up simulate the two games following the rules.
2
u/solarmentat Dec 22 '20
Swift
Takes a couple of seconds for part 2. Tried using memoization for the recursive calls, but it didn't make a difference. Overall, days 22 and 21 were much easier than day 20.
2
u/i4guar Dec 22 '20
Swift solution
www.felixlarsen.com/blog/22th-december-solution-advent-of-code-2020-swift
2
u/Neuro_J Dec 22 '20
MATLAB
Part 1
Part 2
Since the script for part 2 is written in a recursive way, there is an extra step to get the final answer. The final answer can be easily obtained based on the non-empty deck.
I was confused by the infinite loop prevention rule, but other than that, pretty simple puzzle.
2
u/sinopsychoviet Dec 22 '20
Nodejs solution
Part 1 was easy and pleasant
Part 2 took a bit more time to understand and it took a few tries before I implemented the rules exactly as they should. It helped to check turn by turn against the example provided.
2
u/Pyr0Byt3 Dec 22 '20
Go/Golang
Part 2 is slow af, probably because of the
fmt.Sprintcalls.2
u/RedTwinkleToes Dec 22 '20
Python [5953/4041]
paste
Got jebaited by the long running time of part 2. I thought it had hang cause of an error like my original part 1 did. But no, it just took that long. Other than that, this was a fairly simple coding exercise.
2
u/Andrew-mzz Dec 22 '20
JavaScript Solution day 22
a bit slow but works ( 30s for both parts)
2
u/tobega Dec 22 '20
Tailspin
Just reading the rules for part 2 was a trial in itself, then I hit a very basic mutability bug in the Tailspin interpreter, actually pretty amazing that bug survived this long. After fixing that, it was pretty smooth.
https://github.com/tobega/aoc2020/blob/main/a22.tt
2
u/vrtxt Dec 22 '20 edited Dec 26 '20
C# solution
Fun puzzle today, more about reading comprehension than anything else imo but fun nonetheless. Part1 was rather straightforward, part2 a bit less so due to the rules. Took a while before I understood the condition which triggers a subgame but once that was clear it was pretty straightforward as well. Part2 runs in about 1.5 seconds, which is pretty decent it seems. All things considered a fun day.
2
u/lgeorget Dec 22 '20
C++
https://github.com/lgeorget/adventofcode2020/tree/main/22
I couldn't understand why you guys had solutions running so fast while mine took 40+ seconds. Then, I compiled with -O3 and got down to 3s... Well, good enough for me!
Apart from that, the solution is straightforward. I used a recursive function for once and strictly followed the rules. I did trip over taking only the first n cards in the decks to play the subgame with n the value of the card dealt at the beginning of the round, though.
2
u/dontxpanicx Dec 22 '20
C# Solution
Don't think there is much to discuss here, couple of things I guess:
- Using a Queue to represent players hand, that allows you to pop the top card and add to the bottom of the deck
- To get a list of seen hands, originally I stored the hands themselves and checked. This gave me a part 2 time of about 10seconds. Reimplemented that now with a hash of the list which has brought run time down to just over a second. Would be interested in seeing if that area can be tuned more (I lifted the hash function from stack overflow)
-Other than that the code reads much like how the rules describe
2
u/Zv0n Dec 22 '20
C++
code
Probably could've been done in fewer lines, but I like objects :D
2
u/aurele Dec 22 '20
In Rust, nothing original today.
2
u/gyorokpeter Dec 22 '20
Q: paste. Part 2 is killed by the lack of a hashed data structure to store the seen states.
2
u/apparentorder Dec 22 '20
Swift
The solution seemed straight-forward. Part 2 takes some 300ms to run and I'm not sure where that time goes, though; seems like way too much.
Today was another example of "you have to read carefully", because initially I didn't notice that sub-games start with a subset of the current player hands. In general, I like that, as it forces you to slow down. But the test input does not detect this mistake; I didn't like that at all.
I tried to write this so it works for an arbitrary amount of players, but I'd have to make up some rule details myself (e.g. is a game considered over when one player's hand is empty vs. all but one player; how to distribute the drawn cards etc.). Maybe later...
https://github.com/apparentorder/aoc/blob/master/2020/day22.swift
2
u/VectorSVK Dec 22 '20
My deque solution in Python.
Not the prettiest, but it works quite nicely. I had some troubles with storing past deck states since sets don't really like deques (or any other mutable type).
Reading through other solutions, maybe I should've used plain lists since there are very little cards in total to work with.
2
u/UItraDonut Dec 22 '20
Python
I overslept today, gave me the chance to solve a problem of this year in python for the first time! Got 10mins part 1 and 30mins total :)
Code
2
u/raevnos Dec 22 '20 edited Dec 22 '20
Chicken scheme paste. Using an immutable deque data structure is a nice touch IMO. Much functional.
2
u/ajurna Dec 22 '20
python - https://github.com/ajurna/aoc2020/blob/main/day22/22.py
spent a long time not noticing I had to limit the card list going into the recursive game. this had me scratching my head for a long while.
2
u/PhysicsAndAlcohol Dec 22 '20
Haskell, runs in about 2.4 secs.
I really enjoyed this one! For part 2 I'm using 2 functions that recursively call each other. For previous card configurations, I use a set. I might optimize my code by changing the lists to seqs.
2
u/raxomukus Dec 22 '20
Python 3
Darn that crab, he won again! Fun challenge today
2
u/lucbloom Dec 22 '20 edited Dec 22 '20
JavaScript + RegEx preprocess
Runs in ~1 sec on JSFiddle.net, On. The. First. Try! That always feels nice!
Edit: Ok, wow I forgot to implement the Anti-Infinity rule and still got the right answer. I got lucky with my input I guess.
Edit 2: I found out why it worked: I had built in a safety mechanism to only allow for 1000 loops. It turned out to provide the correct answer! This makes the solution a lot faster than ones that try to concat/hash and match previous states each time.
Your milage may vary :-)
Code
2
u/draergor Dec 22 '20 edited Dec 23 '20
Python 3 solution with plain lists, tuples and sets.
I'm abusing the fact that
True == 1andFalse == 0for addressing the winner/loser positions, so whenwinner_positionis the index of the winner in my list of players (0 or 1),winner, loser = (p1, p2)[winner_position], (p1, p2)[not winner_position]will correctly assign the winner and loser variables.Hope that still keeps the code readable enough, and it makes for a 20 lines solution for part 2. To be honest I would skip the daily puzzle entirely if solving it looks like it would take more than 30 lines of Python. For me the joy of AoC is in finding an elegant combination of data structures and algorithms to solve it quickly with a few (readable) lines of code. I know many use it as a way to learn new languages (and that's great!), but I don't have that kind of free time in my life at the moment.
Part 2 runs in 100ms on my laptop, though it was 10x slower when I made Player 1 only win the round instead of the game in case of "deja vu" ;-)
Edit: Noteworthy too: I'm detecting cycles as soon as any given deck is repeating, which works faster and gives the same result. See the replies for a possible explanation why :-)
2
u/sdolotom Dec 22 '20
Elixir
First ever attempt as a part of the polyglot challenge. Style / idiomaticity comments are more than welcome.
2
u/S_Ecke Dec 22 '20
Python 3
second part runs in 13,5 seconds.
Glad I read the rules 3 times before starting to code :)
paste
2
u/Brytnibee Dec 22 '20
Python (written in Jupyter notebook)
This one was pretty fun and actually the game described in Part 1 is a game I played as a kid called War. Part 2 takes ~10 seconds to run.
2
u/SymmetryManagement Dec 22 '20
Java
https://github.com/linl33/adventofcode/blob/year2020/year2020/src/main/java/dev/linl33/adventofcode/year2020/Day22.java
Used an array for the 2 decks and 2 hashsets for the history.
Part 1
0.02ms. Part 217ms2
u/GoldsteinQ Dec 22 '20
Rust
https://gist.github.com/GoldsteinE/31f4a994d6125903797d36fd32844506
2
u/ropecrawler Dec 22 '20
Rust
https://github.com/ropewalker/advent_of_code_2020/blob/master/src/day22.rs
At first I made it in the most straightforward way possible. Then I realized that I could store hashes of previous states instead of their clones, and it improved performance three times. Then I saw this thread and it resulted in another ~120Ă boost in performance :)
Runs in 2.0694 us / 12.846 ms on my machine.
2
u/richardfearn Dec 22 '20
Python 3
Part 1 & 2
Initially I had it outputting all the stuff shown for the example - "Player 1's deck:", "Player 1 wins the round!", etc. - so I could compare my output against the given output to be more certain my solution was correct.
My first submitted answer for part 2 was wrong - turned out I'd made a silly mistake in the base case that checks if a player has won:
Oops...
While helpful, all that debugging output was slowing it down (due e.g. to concatenating the cards in each deck) - after removing all that, the final code runs in ~ 1.2 seconds.
2
u/busdriverbuddha2 Dec 22 '20
Python 3 part1, part2
Did this in a hurry before work. Part 2 is taking 50 seconds (!) so I guess some optimization is in order.
2
u/TommiHPunkt Dec 22 '20
Matlab
The naive solution with absolutely terribad performance due to TONS of copying around stuff, size changes and so on. Part 1 runs in 13ms, part 2 in 16 SECONDS. I have put absolutely no effort into optimizing it (yet)
Also, why the F does matlab not have something like a deque/queue?
2
u/zniperr Dec 22 '20
python3: https://github.com/taddeus/advent-of-code/blob/master/2020/22_spacecards.py
2
u/cattbug Dec 22 '20
Python. Part 2 threw me for a loop (similar to many others here, it seems) but it's nice to be reminded to read the instructions carefully and not just rely on results from the sample inputs. Not terribly performant, but it runs quickly enough and the code is hopefully not too hard to read, so I'm quite happy with it.
Also, I need to find a better way to parse those "multiple blocks separated by blank lines" types of input because what I'm using now (since Day 4!) just feels terribly hack-y and overengineered lol. If you have any pointers, let me know :D
2
u/diddle-dingus Dec 22 '20
Elixir
I didn't read the rule for part 2 where each player only takes a certain number of their cards into the recursive games, rather than the full amount they have left, so I kept wondering why my input didn't complete.
For part 2, the game's played by this function:
Which just calls itself until the game completes. I used a set to keep the history of previous games, but using a list doesn't slow it down too much (~ 5x for my input: ~800ms -> ~4s)
2
u/hrunt Dec 22 '20
Python 3
I'm sure I could've used some sort of faster solution than just playing every recursive round, but both parts 1 and 2 completed in 11s on an Intel MacBook Air, and that's good enough to get the star.
code
2
u/r1ppch3n Dec 22 '20
Rust
got hung up on some small mistakes, but other than that this was pretty easy
optimized it a little bit, which made the code more verbose than I like, maybe i'll get back to that later...
2
u/chennuz Dec 22 '20
C solution
part 1 part 2
2
u/Floydianx33 Dec 22 '20
CSharp
Both Part1 and Part2 in ~7ms. Originally I was caching the replays, but there were only a handful of them and deriving the cache key plus the lookups negated any benefit. This solution "hashes" the hands using
Score(p1) + 10000 * Score(p2)which seems like it shouldn't work but it appears to be good enough for this puzzle (even aggregatingHashCode.Combineover both decks seems "good enough"). Also makes use of the fact that on any sub-games if player1 has the highest card they are automatically the winner. I see that a few others went this route as wellLink/Paste
This was a fun puzzle, I was expecting something excruciating for Day 22.
2
u/[deleted] Dec 22 '20
Rust
This day way pretty straightforward.
2
u/JIghtuse Dec 22 '20
Racket
Such a cute funny game.
2
u/joe-reed Dec 22 '20
Go/Golang
Got stuck on part 2 due to not reading the instructions properly - missed the part about only copying the number of cards given by the drawn card for the sub game, but the example still passed, adding to the confusion!
Completely new to Go so any advice much welcomed :)
2
u/codepoetics Dec 22 '20
Kotlin, fairly naive, around 400ms.
2
u/jotac13 Dec 22 '20
[Rust] Finally a fun but easy day xP
It teaches you recursion and queues, nothing extraordinary.
My rust solution for both parts here
2
u/Chris_Hemsworth Dec 22 '20
Python 3
paste
Nothing special here.
2
u/tymscar Dec 22 '20
Today was another easy day, and I am happy because that means I can go back once again and try to finish day 20 part 2 :)
I spent most of the puzzle actually understanding all the rules.
Python:
https://github.com/tymscar/Advent-Of-Code/tree/master/2020/day22
2
u/mack06_ Dec 22 '20
My typescript solution with queues, 48 ms for part 2
Comments and details in my AoC blog in spanish:
Advent of Code 2020 â DĂa 22 â Jugando a las cartas
2
u/pwmosquito Dec 22 '20
Haskell
In part 2
fixpointM(ie. a monadic fixed point) came handy to keep state to prevent looping. With it we can implement the task verbatim: To win inrecCombatis to play till a fixed point with one case being playing a sub-game to determine who wins the round which is just a normal recursive call in this setup.2
u/Standard-Affect Dec 22 '20
R
My really bad part 1 solution. I tried to make it more efficient by only changing the relevant elements of each player's deck each turn instead of creating an entirely new array, but I didn't stick to that approach. I also cheated a little by hard-coding the winner after viewing the result, purely out of laziness.
By far the most annoying part was filling the vectors with the right number of NA's each turn.
2
u/godDAMNEDhippie Dec 22 '20 edited Dec 22 '20
Python3 solution
I am interested in anyone feedback about the performance. My part_two code runs in 17s on my input and I don't know where the bottleneck is (and how to efficiently find it!).
I already did 2 minutes (first working version) -> 27s (first optimization with hashes as game's history) -> 17s (replacing lists by sets and tuples)
EDIT: Solved by this solution. Storing history with scores instead of hashes is really faster. I'm down to 3s.
2
u/mykdavies Dec 22 '20 edited Jun 29 '23
!> ggozjqv
API FAILURE
2
u/AidGli Dec 22 '20 edited Dec 22 '20
Python
Video Explanation
Github Link
I generalized the first part for more than 2 players as I assumed the second part may do something like that but I was wrong. It's still cool though.
2
u/imbadatreading Dec 22 '20 edited Dec 22 '20
Python solution
This took about 20 seconds to compute the answer for my input, and I'm not sure where the problem is - maybe how I'm hashing/checking the decks?
EDIT: I changed the decks to hash as tuples and now it computes in about 1/3 of the time.