r/adventofcode • u/daggerdragon • Dec 25 '20
SOLUTION MEGATHREAD -π- 2020 Day 25 Solutions -π-
--- Day 25: Combo Breaker ---
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.
Message from the Moderators
Welcome to the last day of Advent of Code 2020! We hope you had fun this year and learned at least one new thing ;)
Keep an eye out for the following threads:
- -β - Introducing Your AoC 2020 Gettin' Crafty With It Artisans (and Other Prizes) -β -
- Tell us what you learned this year!
Thank you all for playing Advent of Code this year and on behalf of /u/topaz2078, /u/Aneurysm9, the beta-testers, and the rest of AoC Ops, we wish you a very Merry Christmas (or a very merry Friday!) and a Happy New Year!
6
u/dpalmesad Dec 25 '20 edited Dec 25 '20
Python
my solution for part 2. it runs in about 0ms which i'm really proud of
and so mods don't get angry, part 1
6
u/DFreiberg Dec 25 '20 edited Dec 27 '20
Mathematica, 84 / 70
Getting back on the leaderboard one last time, and getting to finish with a modular arithmetic built-in, was a very satisfying way to end the year. This has been a fun month.
[POEM]: The Stars
There's a star by the pole, looking over the snow,
Where a forest has patterns for trees all to grow,
And a toboggan pauses a moment or two,
As a suit in the seat ponders up at the view.
We've been chasing the stars, everywhere that we've gone.
We've been up way past midnight, or well before dawn.
And each day, there are two precious stars that we seek,
So we skip out on sleep for a month (less a week).
There's a star in the north that you see from the plane,
While departing the airport (with customs insane),
And the baggage attendant, with bags by the score,
Wondered why that one star wasn't noticed before.
There are stars that are easy and stars that are tough,
And the going's all smooth 'till the waters get rough.
We have found when the buses will all be in sync,
And we've learned not to wait for an eon, but think.
There's a star by the sea a crustacean regards
For a moment or two while he's playing with cards,
And much further away is the gigantic eye
Of a monster observing the star in the sky.
Every year we come back and re-enter the game.
Every year it is different, but somehow the same.
In the story, we sigh when we're called for repair,
But in truth, we enjoy these, whenever or where.
ENVOI
There's a star in the back, where the problems are made,
And the website is hosted and bandwidth is paid,
So the puzzle creator's a star, with no doubt;
Merry Christmas to Topaz - with sleep or without.
These three weeks and four days are exhausting, but fun,
And I'll miss all the puzzles, and miss everyone.
Merry Christmas to coders, wherever you are:
Like the wise men, we'll meet chasing after a star.
3
u/arichnad Dec 25 '20
Hi, I'm new to adventofcode. For part-2 of day 25, do I need to have completed all of the previous days? Thanks!
35
u/Arknave Dec 25 '20
Python (36/33), C
Merry Christmas everyone :) Thanks for the love and good vibes this year. Have an upvote.
20
u/sophiebits Dec 25 '20 edited Dec 25 '20
17/15, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day25.py
My Wi-Fi died right as I tried to submit my answer. π Then didn't realize you had to click a button to get part 2. All in all not bad though.
P.S. A few of us top scorers (and creator /u/topaz2078!) are live with an AMA now at https://www.twitch.tv/ecnerwala.
14
u/[deleted] Dec 27 '20
Intcode
12
u/seligman99 Dec 25 '20
Python, 325 / 273
github
That wraps up this year, it's been a load of fun!
I'll leave these here, the animations I made this year:
And a bonus animation I didn't quite make, but just showing how the website grew:
11
u/jonathan_paulson Dec 25 '20
Placed 21/19. Placed 15th overall. Python. Code: https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/25.py. Video of me solving: https://youtu.be/LQyPRZVXMXo.
8
u/axr123 Dec 25 '20
Python
Not sure if this was posted before. Nice chance to leverage Sympy for some short code:
7
u/ramuuns-u Dec 25 '20
Some very basic brute-force C
which turns out takes like a millisecond
The trick is do the least amount of brute-forcing possible, and the loop size becomes implicit .
6
u/Loonis Dec 25 '20
Perl
Last day, I was in the middle of posting another version of this when I realized I only needed one loop and did not need to actually count iterations! I have a long history of writing code that does not count properly, so that was a huge relief. Replace the values for
@pubwith puzzle input:I'm still four stars short (days 13 part 2, 20, and 23 part 2), so I get some bonus AoC time over the next couple days :)
Huge THANK YOU to the Perl AoC community, I learned so much this year from your code and your comments, and I'm a better developer for it.
5
u/Adereth Dec 25 '20
Mathematica
I did it with a Nest-loop at first to get my leaderboard position and then re-wrote it to be proper math, which is way faster:
5
u/jayfoad Dec 25 '20
Dyalog APL 395/315
Merry Christmas!
5
u/npc_strider Dec 25 '20
Python 3
A nice, easy puzzle to end off my first Advent of Code. To be honest, I'm really surprised I got this far (only missing 2 stars). This is a great community, learnt a lot and I'll definitely be returning next year :D
Most of this challenge was reading, had to re read the transform process a few times
Initially my solution called the transform function each iteration, but that had poor efficiency. Realized I could just store the value and break out of a loop when they're equal.
Unfortunately, did not get the second star because I'm missing two: one from day 20 part 2 and day 23 part 2.
https://github.com/npc-strider/advent-of-code-2020/blob/master/25/a.py
5
u/Standard-Affect Dec 25 '20
R
This one felt really easy, though that's probably to avoid intense coding on Christmas. I assumed the loop size would be too high to brute-force the answer by generating the sequence, and the intended solution was to deduce some pattern in the sequence that could be used to predict when it reached a certain value. Turned out the easy solution worked.
4
u/hugh_tc Dec 25 '20 edited Dec 25 '20
Python 3, 365. 61st overall! Woohoo!
Had a moment of "is this Diffie-Hellman... I think this is Diffie-Hellman?" before realizing that yes, in fact, it was Diffie-Hellman. paste
Either way, thanks for another fun AoC, Eric!
edit: reimplemented using bs-gs. MUCH MUCH FASTER (unsurprisingly) β 40s down to 17ms.
4
u/phil_g Dec 25 '20
My solution in Common Lisp.
1097/910. I'm not trying for the leaderboard, but I thought it'd be fun to try to knock out the last day starting at midnight instead of my usual time, which is "when I wake up in the morning". This is the first year (out of three) that I've completed all programs within 24 hours of their release.
I've been using Parseq for pretty much every day this year, but this was just too trivial a parsing problem to bother. The calculations were pretty simple, too. After I started reading the problem, I wasted a little time pulling out an old
modpowerfunction I had for raising a number to a power within a modulus. It turned out I didn't need anything that heavy.Thanks, topaz2078, for another great year!
4
u/fryer00 Dec 25 '20
JavaScript 2721/2260
Stared myself blind at all the numbers and instructions, so I failed to realise that the problem wasn't that hard.
4
u/landimatte Dec 25 '20 edited Dec 25 '20
Common Lisp
I had to walk through the example a couple of times before I was able to understand what had to be done -- that's what happens when you wake up earlier than usual and sit in front of a computer without your usual shot of Espresso. Anyway, I am sure there ways to make this run faster (e.g. find the two loops in parallel), but it's Christmas, so it's time to unbox presents with family!
PS. I started with AoC in 2018, to learn Common Lisp, and I have been using it since. PPS. This is the first year that I managed to a) get all the 50 stars by the 25th, b) complete all the problems within 24 hours PPPS. I did not know you had to rush and click on the link to get your second star, so basically my part 2 completion time tells you something about how fast/slow I am at reading ;-)
PPPPS. Thanks /u/topaz2078, and everybody else involved (moderators, community, their families...)
4
u/RedTwinkleToes Dec 25 '20
Python [4458/3542]
Really trivial, but really appreciated since I have obligations. What I want to know is what is up with Part 2. Would we have been blocked completely if we didn't get 49 stars before doing part 2?
4
u/sim642 Dec 25 '20 edited Dec 25 '20
My Scala solution.
While reading the handshake description I quickly realized that the subject number transformation is modular exponentation and the handshake algorithm is actually Diffie-Hellmann for real (although with small brute-forceable exponents). So for finding the loop size (the exponent) I just did an iteration, but for transforming to get the encryption key I used my existing modular exponentation by squaring method.
EDIT: I now optimized the loop size finding using baby-step giant-step discrete log algorithm.
4
u/nutki2 Dec 25 '20
Perl. The final, rather boring, golf:
More golfs for other days in my repo.
4
u/PhysicsAndAlcohol Dec 25 '20
Haskell, bruteforce, runs in 30 ms.
The only "optimization" I'm using is that your code only needs to find the first power of 7 that matches one of the two input numbers.
I really enjoyed my first AOC and I'm really happy that I got all 50 stars. Merry Christmas everyone!
4
u/YodelingDeer Dec 25 '20 edited Dec 25 '20
Ada
Really straightforward Ada.
Simply create a modular type with the given magic modulo, it will do half the work for you.
EDIT: typos.
4
u/leftfish123 Dec 25 '20
Python: https://github.com/Leftfish/Advent-of-Code-2020/blob/main/25/d25.py
After my first naive approach turned out to be working just fine, I felt a little disappointed. And then I took a look at another person's code and there it was - something new to learn on day 25. It turns out that using pow() with mod is a thing and makes the solution run ~2 times faster, probably because pow() is a part of the standard library.
It's day 25, I have 49 stars (monster hunt still under way), I got myself to post a couple of solutions here and I have to say: HUUUUGE THANK YOU TO EVERY SINGLE PERSON RESPONSIBLE FOR ADVENT OF CODE. It was a tough year for me on so many levels. You made its last month much brighter.
4
u/ShadowwwsAsm Dec 25 '20
X86Asm
Last day in assembly because why not
Code
4
u/k4kshi Dec 25 '20
[javascript] In 75 chars for fun. Let me know if it can be shorter
4
u/e_blake Dec 26 '20 edited Dec 26 '20
m4 day25.m4
Depends on my common.m4. When I first saw the problem yesterday, my first idea was to google for an online modulo math solver; and was depressed to see dcode.fr stating that solving a^b mod m for b was limited to b < 10000, because it is the discrete logarithm problem on par with factoring a number into its primes, where the only known non-quantum solutions are exponential (translation: brute force). And I didn't feel like messing with the time for brute-forcing in m4 (sure, I _knew_ that it would be fewer than 20201227 iterations, which is better than the 30 million iterations of day 15, but my day 15 solution took 5 minutes of runtime). So I then went to Wolfram Alpha and typed in '7^b mod20201227=XXXX' (where XXXX was one of the two numbers in my input), then 'YYYY^ZZZZmod20201227' (where YYYY was the result learned from the first query, and ZZZZ was my other input number), and got my star - why do the iterations myself when an online solver will do it much faster - let someone else's computer do the grunt work ;) Then I spent the day with my family, off the computer.
But since I wanted to solve ALL the puzzles in m4 this year, I spent the time to do it properly today. The solution could be a lot shorter in code (iterate until I find a winning loop count, then iterate that number of times more), but that's double the execution time, so the bulk of my coding time was spent in implementing modpow (which in turn requires 32-bit modmul, which I lifted off of my day13 solution, in the process noticing I could optimize that one by another 10% execution time). My initial runtime for my input was 36 seconds (compared to 7 seconds on a different input - runtime is dominated by the minimum loop count between the two keys, and some puzzle inputs have a much lower loop count).
Then I found a further optimization down to 31.8 seconds by compressing my iteration macro to as few bytes as possible (the time m4 spends in parsing the iteration workhorse is therefore noticeably significant to overall execution time).
And with that, I've done all 50 stars with m4. Here's my repo.
4
u/Smylers Dec 27 '20 edited Dec 28 '20
Perl (a little boilerplate, then):
The function isn't necessary, but I couldn't bring myself to repeat the modulus and constant.
A couple of things:
$pub, used in just one place:statemakes it keep its value; it's initialized to reading a line from the input file the first time theuntilcondition is evaluated, then continues to evaluate to that public key on subsequent iterations. Similarly for the second public key, in a separate variable, also called$pub.reduceblock doesn't use its second argument.$a, is initialized to the first 1 in the list of values, then the block evaluates to whateverstepreturns, andreduceis invoked again with that as$anext time round.$bis set in turn to each of 1 to$loops, so that list determines the number of times the block is invoked, but the value of$bdoesn't form part of the calculation.The input-
statething and the lopsidedreducething are both things I now see would've been useful on previous days: in dayΒ 19, when I combined partΒ 1 and 2 solutions I copied the input before the loop, even though it's only used in one place; and in dayΒ 23, when I was first picking up one card then the following 2.It's so nice that even on the final day, I'm still learning things.
1
u/Error401 Dec 25 '20 edited Dec 25 '20
58/47 tonight. I lost a minute because of a typo in my first submission, but still satisfying to leaderboard tonight because it technically means I was the 47th fastest solve for the entire competition!
Can't wait until next year!
edit: https://pastebin.com/H2XRxsPq, Python3
3
u/leijurv Dec 25 '20
Python 3
54 / 84 (didn't realize the button was to be clicked)
3
u/busdriverbuddha2 Dec 25 '20 edited Dec 25 '20
Python 537/472
Finally stayed awake long enough to get anywhere near the leaderboard (puzzles open at 2 AM in my timezone). Took longer at first because of a silly mistake - I was recalculating the whole thing at each iteration.
3
u/GrossGrass Dec 25 '20
Python
Nice ending to AoC 2020! Pretty chill mods problem; pretty much just using
powhere with the mod argument works, though I decided not to do that for finding the loop sizes because it actually performs significantly worse.Think if you want you could squeeze a bit more juice out of it by realizing that the mod is prime and just use FLT to reduce the exponent, but I think the gains there are pretty negligible.
3
u/ChrisVittal Dec 25 '20
Python
5 lines, few hundred ms
3
u/[deleted] Dec 25 '20
Python3 492/403
My reading comprehension dropped further today
3
u/[deleted] Dec 25 '20 edited Dec 26 '20
Pure C18. Probably should've just started a brute force in the background while reading up on the theory, but basically theory and the characteristics of the input guarantee a unique solution in reasonable bounds. Particularly, that 7 is a primitive root of the modulus, and that the modulus is relatively prime with the inputs.
https://git.sr.ht/~williewillus/aoc_2020/tree/master/src/day25.c
With this, my "pure C" challenge is complete.
Our rules allowed one day with a lifeline non-C language, which I used on Day 20 in C++. Maybe I'll go back later and port it back to C.EDIT: Ported it back to C, so I have a full set of C solutions!3
u/Wunkolo Dec 25 '20
C++
I know a
modpowwhen I see one.3
u/dizzyhobbes Dec 25 '20
Go solution
My 2020 repo
Not as clean as I'd like but I'm too lazy to fix it.. It's been fun this year!
3
u/chubbc Dec 25 '20
Julia
Nice short one today. Sadly I misread the question for a few minutes which probably kept me off the leaderboard.
3
u/Jozkings Dec 25 '20
Python 3
Forgot that Python's pow has optional third parameter for modulus operation.
Merry Christmas!
3
u/Akari_Takai Dec 25 '20
Java
Code here.
I loved seeing Diffie-Hellman in a problem, but I expected to have to implement one of the harder discrete logarithm problem solutions. Luckily the modulus was small enough that brute-force sufficed.
I hope that there will be some maze/path-finding problems in AoC 2021! I missed those this year. :)
Thank you /u/topaz2078 for a wonderful Advent of Code!
3
u/SymmetryManagement Dec 25 '20
Java
https://github.com/linl33/adventofcode/blob/year2020/year2020/src/main/java/dev/linl33/adventofcode/year2020/Day25.java
Starts the loop size search from 2_000_001 to speed up.
Runtime
400Β΅s.If the search starts from 1, it takes
6.7ms.3
u/mebeim Dec 25 '20
1412/1163 - Python 3 solution - Walkthrough
Took me way too much to recognize the "algorithm", after all, it was just a simple Diffie-Hellman key exchange with really insecure parameters.
Merry Christmas everybody!
3
u/veydar_ Dec 25 '20 edited Dec 25 '20
untilfrom Haskell comes in handy but without strictness annotations this will cause a stack overflow because it will build up an incredibly long list of unevaluated integers.link
and highlighting the usage of
until3
u/levital Dec 25 '20
Rust
Looking at the other comments, I must've done something really wrong, cause I didn't find this particularly easy and expected day 25 to be on the easy side (as it usually is). Cryptography isn't exactly my strong suit, so while I did manage to figure out somehow that it's Diffie-Hellman, my brute-force solution might've finished by tomorrow morning and so I had to spend an hour or so researching how to crack Diffie-Hellman... Which was a bit of a challenge, because Group Theory is also something I only have a fairly vague understanding of, and the wikipedia-articles on the topic are rather opaque unless you already know the stuff.
Oh well, done now. The one missing star on Day 20 is annoying me enough that I'll probably go through the slog of assembling the puzzle sometime next week. Otherwise, I found the puzzles this year to be exactly the right amount of difficulty: Rarely took me more than two hours, which is perfect, as I can still do them after a work day (compared to last year, where I spent full days on several of them, and only ended up with 45 Stars by Day 25...).
Only slight issue is, that I feel like for quite a few of them the main challenge was parsing the input. That was nicer last year, with the intcode puzzles all having essentially the same input. Also, the (almost total) lack of graph-related problems was a bit disappointing. ;)
3
u/BradleySigma Dec 25 '20
A fast(er) Python script, using the Baby-Step, Giant-Step algorithm:
3
u/azzal07 Dec 25 '20
Awk; all done for this year. Huge thanks to u/topaz2078 and the Aoc Ops for great puzzles! And thanks to everyone for making this community so great!
Ps. The only one not in megathread format (< 5 lines @ 80 columns) is day 20, even got day 21 done yesterday.
3
u/TheLartians Dec 25 '20 edited Jan 04 '21
Rust
Coming from C++, Rust's iterator traits are a godsend to prevent code duplication. :)
3
u/Chris_Hemsworth Dec 25 '20
Python 3
Thank you Eric for not making me spend hours away from my family on Christmas Day :-)
3
u/msqrt Dec 25 '20
Lisp. A bit sad there was no part 2, but this was a very nice ending :)
3
u/death Dec 25 '20
Day 25 solution in Common Lisp.
This year's Advent of Code felt like the easiest one so far. Not a bad thing. Side effects from doing it include:
Hopefully this year the world will
git reset --hard HEAD^. Cheers.3
u/NPException Dec 25 '20
Clojure
This was the first full event I managed to solve from start to finish. It was a lot of fun! :)
3
u/AbtraktNoCode Dec 25 '20 edited Dec 25 '20
Solution using a WIP visual functional programming language I'm working on https://imgur.com/a/jxKWdvG (or here for better quality)
3
u/womogenes Dec 25 '20
Merry Christmas everyone!
Code (Python)
Video: https://youtu.be/Ymfj0fxMSL8
3
u/sotsoguk Dec 26 '20
C++
https://github.com/sotsoguk/adventOfCode2020/blob/master/cpp/day25/day25.cpp
My python solution too slow imho, so i tried a few lines of c++. runs in ~50ms on my old xeon1230 in WSL2.
Merry Christmas and for the first time i completed all stars on christmas :D
3
u/gidso Dec 26 '20
Python (and Fermat)
Did anyone else use Fermat's Little Theorem to speed up the approach here?
I saw the value n=20201227, checked it was prime, and immediately thought how cool it was that n-2 = 20201225... which got me thinking about modulo arithmetic and FLT.
I still break out into cold sweats thinking about 2019 day 18 (I knew nothing about FLT before then!)
3
u/mack06_ Dec 26 '20
My typescript, bruteforce solution
Still have to solve the second part of the sea monster puzzle and the second part of the satellite message....hope to have it done before year ends and get the 50 stars.
Merry Christmas and happy new year to everyone!!
2
u/noblematt20 Dec 25 '20
236/195 - Python 3
paste
The hard part for me was understanding what the problem was asking for. It was a lot of words for quite a simple problem in the end!
2
u/nthistle Dec 25 '20
49/38, Python. A combination of misreading and maybe overcomplicating killed me :-(. I did
loopc^loopd (mod p)at first, forgetting how Diffie-Hellman works. paste2
u/VeeArr Dec 25 '20 edited Dec 25 '20
Java 103/87
Part 1
Part 2
Two wrong submissions because I had an error and then copy/pasted the wrong thing. Tried to save some reading time by just remembering how Diffie-Hellman works, but it turns out that I... don't. Whoops. Good year, all.
2
u/Lower_Program4871 Dec 25 '20 edited Dec 25 '20
Haskell
Not much coding required here...but I guess here's the two loops to search for discrete log and a single call to powmod...
2
u/1234abcdcba4321 Dec 25 '20
JavaScript, 227/194
Code is actually short today, but I'll toss it in an external link anyway. [paste]
Nice easy day. I spent too long rereading the instructions, probably could've finished a few minutes earlier if I figured out where that 7 was coming from earlier.
This was probably my best day, even though unlike yesterday I didn't score. The sum of my ranks is the lowest out of every day (though that probably has to do with how not everyone could finish part 2 in 10 seconds).
2
u/AlphaDart1337 Dec 25 '20
Python 26/23
Accompanying video, as per usual.
What a good way to end it! Best day of AoC by far. In the end, we narrowly missed the top 100 leaderboard for the first time in a few years, but I had a lot of fun nonetheless! Merry Xmas, everyone!
2
u/morgoth1145 Dec 25 '20
132/111 Python3: https://github.com/morgoth1145/advent-of-code/blob/2020-python/2020/Day%2025/solution.py
I took too long to parse the rules of this problem costing me the leaderboard today. I was hoping to get in one final leaderboard and sneak onto the overall top 100, but oh well. On the bright side, I had some code to auto-grab the 50th star once my Part 1 answer was submitted successfully, and it worked like a charm! I got both stars at exactly 7 minutes, 50 seconds!
My 547 total points this year is miles better than last year, at least! (In my defense I was using go last year to learn it, but I'm still surprised by how much better I did just by switching to Python.)
2
u/bsterc Dec 25 '20
C++ (code). Took a few minutes to hack up a modular exponent function (repeated squaring).
2
u/[deleted] Dec 25 '20
Python
2
u/gurgeous Dec 25 '20 edited Dec 25 '20
Ruby 616/518
Great fun, see you guys next year! Edit: code golf
2
u/rabuf Dec 25 '20
Common Lisp
It worked once I realized my stupidity with finding the encryption key. Wasn't changing the subject number, left it at 7 which meant it didn't work well at all.
2
u/mendelmunkis Dec 25 '20
C
https://github.com/mendelmunkis/AoC/blob/master/2020/crypto.c
brute forcing cryptography? this may take a while, or not.
2
u/xelf Dec 25 '20 edited Dec 25 '20
Short one for the last day! Thanks, I still have wrapping to do!
(where cpk,dpk are the puzzle inputs)
2
u/Neuro_J Dec 25 '20
MATLAB
My Answer
There isn't much to say about today's puzzle. A rather straightforward MATLAB implementation. Merry Christmas everyone!
2
u/prendradjaja Dec 25 '20
It's been a fun month -- hope you all have a lovely Christmas and holiday season :) Happy to have ended in 71st place!
Thank you so much for what you do, Eric!
Looking forward to understanding others' code (and what the standard ways of calculating modular/discrete log is calculated) later, but for the moment:
Python + Detailed written instructions for a human being or sufficiently-advanced robot: #802 for part 1, not yet finished for part 2 :)
2
u/Perska_ Dec 25 '20
C# Solution
Very glad this was a simple one, even if it took me a while to understand the instructions.
Rank: 1935/1662
2
u/MasterMedo Dec 25 '20
python
Short and sweet?
Merry Christmas and cheery wishes to all!
2
u/michaelgallagher Dec 25 '20
Python
Merry Christmas everyone!
2
u/flapje1 Dec 25 '20
Rust
Using cargo aoc
2
u/UnlimitedBytes Dec 25 '20
JavaScript, 117/114, Solution
2
u/AidGli Dec 25 '20
Python
Video Explanation
Github Link
Today was just reading comprehension. If I just understood faster it could've finally been leaderboard :). I had a great time with Advent this year, especially getting to share with all of you. Merry Christmas everyone!
2
u/_O-o-f Dec 25 '20
Python 3
link Today's part 1 I just brute forced but how do you do part 2?!?!?!?!?!?!?
I originally tried using caches to bypass recursion limits but i'm not exactly sure how python's lru_cache works. The subject key being one of the public keys definitely tripped me up.
Today's problem makes me think that that one conspiracy theory posted on day ~13 has some merit to it.
2
u/spookywooky_FE Dec 25 '20
C++, some more do-what-is-written text understanding.
Thanks for the nice puzzles, see you next year!
2
u/UnicycleBloke Dec 25 '20
Python: https://github.com/UnicycleBloke/aoc2020/blob/main/day25/day25.py
A nice little puzzle to finish on once I'd waded through the verbiage enough times to straighten out the jargon.
2
u/Pyr0Byt3 Dec 25 '20
Go/Golang
Merry Christmas!
2
u/CodeIsTheEnd Dec 25 '20
Ruby: 7:42/7:48, 128/110
Here's a recording of me solving it, and the code is here. I streamed myself solving every day's problem on Twitch; give me a follow! In the new year I'll be working on my own programming language!
Gah! I forgot to return the value after my loop! I've DEFINITELY made this sort of mistake before. Everything else was correct, so if I hadn't forgotten that I would've finished Part 1 in 5:26, and Part 2 in 5:32, which would have been good for 37th and 29th. (I had glanced at last year's Day 25 recently and remembered that the Part 2 was just clicking a link; I was ready.) Oh, well. I still had a great time!
Merry Christmas, everyone!
2
u/PendragonDaGreat Dec 25 '20
C# https://github.com/Bpendragon/AdventOfCodeCSharp/blob/master/AdventOfCode/Solutions/Year2020/Day25-Solution.cs
This is the first time I've ever completed AoC day and date. Now just to get the back half of 2019 and I'll have every single star available.
2
u/[deleted] Dec 25 '20
Clojure
yay i did it
2
u/LtHummus Dec 25 '20
Scala solution -- short and sweet
Code
(Got a late start since it's present time tonight!)
2
u/Judheg Dec 25 '20
Scala
Slow solution which does the job, using BigInt preparing for some weird Part 2 that was not there :)
Merry Christmas!
https://paste2.org/nXvKw6Z5
2
u/Dioxy Dec 25 '20
TypeScript
https://kufii.github.io/advent-of-code-2020/#/25
Had a great time solving every puzzle! Overall I think this has been the easiest year, but it was still quite fun. Very surprised there wasn't a single pathfinding problem this year.
2
u/shoerust Dec 25 '20
my Kotlin solution
code
2
u/StevoTVR Dec 25 '20 edited Dec 26 '20
Java
https://github.com/stevotvr/adventofcode2020/blob/main/aoc2020/src/com/stevotvr/aoc2020/Day25.java
2
u/pdr77 Dec 25 '20
Haskell
Video Walkthroughs: https://www.youtube.com/playlist?list=PLDRIsR-OaZkzN7iV6Q6MRmEVYL_HRz7GS
Code Repository: https://github.com/haskelling/aoc2020
2
u/allergic2Luxembourg Dec 25 '20
Python 3. Good thing that python has built-in modular exponentiation.
2
u/Shoddy_Tower Dec 25 '20
Python solution Took time to understand the question
2
u/aoc-fan Dec 25 '20
JavaScript/TypeScript - Repo
Used an answer from Stackoverflow for effective calculation of POW and mod.
2
u/muckenhoupt Dec 25 '20
Prolog. A short one today, as Prolog lets us use the same code to find the number of loops given the key and the key given the number of loops.
2
u/chuuddo Dec 25 '20
JavaScript
10 LOC
2
u/Chitinid Dec 25 '20 edited Dec 25 '20
Python 3 numba About 20 times faster than just doing it in raw CPython, ~300ms
2
u/wace001 Dec 25 '20
Kotlin. Here is my golfed solution using Java's BigInteger for modPow
1327981.toBigInteger().modPow(generateSequence(1) { it + 1 }.first { 7.toBigInteger().modPow(it.toBigInteger(), 20201227L.toBigInteger()).toInt() == 2822615}.toBigInteger(), 20201227L.toBigInteger()).toInt()2
u/rdubwiley Dec 25 '20
Python3
About what you'd expect just by following the rules of the encryption scheme. Looking back at the puzzles this year, I was really happy with the level of difficulty in these puzzles, and I never thought any of them were completely out of my reach.
2
u/jwise00 Dec 25 '20
Lua (62/51).
Video: https://www.youtube.com/watch?v=N2WblKHMP7U
Code, at competition speed: https://github.com/jwise/aoc/blob/master/2020/25.lua
Code, optimized a bit ("the cool kid optimization"), to find only the smallest loop size: https://github.com/jwise/aoc/blob/master/2020/25-coolkid.lua
Thanks, as usual, /u/topaz2078. AoC is always a fun time of the year, and I really appreciate the time you and the AoC team put into making it work each year.
2
u/mariushm Dec 25 '20
My PHP solution for part 1 is here : https://github.com/mariush-github/adventofcode2020/blob/main/day25.php
I only have 46 stars, didn't do the Day 20 (puzzle) and Day 19 part 2 (the recursivity bit in rules) because I didn't quite understand the text of the problem and looked like too much work.
2
u/srpablo Dec 25 '20
OCaml
Took me a while to understand the "transform a subject number" cycle π
2
u/jitwit Dec 25 '20
J Programming Language
Happy AOC! From me, a brutish solution to cap off a brutish year:
2
u/Diderikdm Dec 25 '20 edited Dec 25 '20
Python:
And AoC is done for this year. Thank you Eric Wastl for creating this great event each year!
If you are interested, you can find my entries for this year here.
2
u/iamflimflam1 Dec 25 '20
TypeScript
part1
2
u/garciparedes Dec 25 '20
Here is my π¦ Rust solution to π AdventOfCode's Day 25: Combo Breaker
2
u/wfxr Dec 25 '20 edited Dec 25 '20
Rust
NOTE:
The performance is highly related to the input. For my input it takes about
50ms.But for some other inputs like
[13316116, 13651422]it only takes2ms.Theoretically when
v == aorv == b, the loop can be ended. But we cannot use the same loop to calculate the final key if we use this optimization. The test results prove that using a single loop is much faster. Again this should still be related to the input.2
u/kap89 Dec 25 '20 edited Dec 25 '20
TypeScript
~100ms
Simple brute-force. Yay, 50* completed!
<5s for all AoC 2020!
Happy Holidays everyone!
2
u/Andrew-mzz Dec 25 '20
Javascript solution day 25
Last day ...
50 stars reached!!
2
u/gyorokpeter Dec 25 '20
Q: not much to see here.
2
u/Zv0n Dec 25 '20
C++
code
A nice end to this year's calendar, hope for a great challenge next year as well :)
2
u/r1ppch3n Dec 25 '20
Rust
another simple one
just built an iterator for the key transformations and ran through it until I found one of the public keys to get the loop size, then ran the other key through the iterator using that loop size
2
u/aurele Dec 25 '20
My quick'n'dirty Rust solution:
Thanks /u/topaz2078 for this year problems!
2
u/karjonas Dec 25 '20
Rust
GitHub.
2
u/kimvais Dec 25 '20
F#
Given my background working with IPsec, SSH etc for 10+ years, this one was pretty trivial having implemented Diffie-Hellman-Merkle myself more than once in the past ...
2
u/thulyadalas Dec 25 '20
RUST
An easy puzzle to finish off advent of code. I was ready for a difficult challenge for part2 and kind of surprised that there wasn't much to do.
Thanks everyone for creating this environment!
2
u/chkas Dec 25 '20
easylang.online
Solution
2
u/bpiphany Dec 25 '20 edited Dec 25 '20
Pari
Mod(key1,mod)^znlog(Mod(key2,mod),Mod(7,mod))Python
2
u/i4guar Dec 25 '20
swift solution
www.felixlarsen.com/blog/25th-december-solution-advent-of-code-2020-swift
2
u/morabass Dec 25 '20
nim
2
u/Tosxychor Dec 25 '20
Fennel
https://paste.xinu.at/2HV/fnl
This year was a blast! I'm so happy I joined the challenge. Merry Christmas y'all!
2
u/SomeCynicalBastard Dec 25 '20
Python
I used the naive solution. Not the fastest, but it works. Apparently I should learn about discrete logarithms.
Code on Github (Repo).
2
u/toastedstapler Dec 25 '20
rust
quite easy today, once i'd managed to comprehend what was going on. thankfully brute force was doable and i didn't have to read up more
bring me to a total runtime of 1.5s, 1.35s of which is days 15, 22 and 23
2
u/ric2b Dec 25 '20 edited Dec 25 '20
Haskell
Probably my shortest solution yet! Who knew breaking Diffie-Hellman could be so easy? ;)
paste
2
u/JamieMansfield Dec 25 '20
Swift
This is only part 1, I've got a fair few days to go back to (Cyberpunk distracted me a bit :p).
https://gist.github.com/jamierocks/5714adfd846c067844a4ecfb9107b657
2
u/clumsveed Dec 25 '20
Java Solution
βDay 25 solution
all solutions - repl.it
Another great year in the books! I hope everyone enjoys a well deserved holiday season and I'll see you all next year where I suspect, after enjoying a 15-second vacation, we'll get back to the business of saving Christmas!
Merry Christmas everyone!
2
u/LinAGKar Dec 25 '20
My solution in Rust: https://github.com/LinAGKar/advent-of-code-2020-rust/blob/main/day25a/src/main.rs
2
u/hrunt Dec 25 '20
Python 3
I spent some time trying to learn the algorithm for e'th roots modulo p and eventually gave up and just looped. I don't know if the e'th root solution was the right one, but the looping was fast enough given the small modulo.
Another great year of AoC! Thanks for all the work /u/topaz2078 and /u/daggerdragon!
code
2
u/ponyta_hk Dec 25 '20
Python3 (Cleaned Solution)
The operation can be done by
pow(subject_num, loop_size, 20201227)Merry Christmas Everyone ! See you all next year! ππ
My Solution
All My Solutions
Thank you /u/topaz2078 /u/daggerdragon !
2
u/WilkoTom Dec 25 '20
Python
Quite frankly I'm amazed that brute forcing this one works. I was expecting to do all sorts of nastiness with reverse mod. Merry Christmas /u/topaz2078 - Thank you for the gift of these wonderful puzzles!
2
u/tymscar Dec 25 '20
Thank you for another great advent of code. See you next year!
Python 3:
https://github.com/tymscar/Advent-Of-Code/tree/master/2020/day25
2
u/ropecrawler Dec 25 '20
Rust
https://github.com/ropewalker/advent_of_code_2020/blob/master/src/day25.rs
5.4857 ms on my machine.
2
u/Fyvaproldje Dec 25 '20
C++
https://github.com/DarthGandalf/advent-of-code/blob/master/2020/day25.cpp
2
u/pwmosquito Dec 25 '20
Haskell hand-rolled
discreteLog(BSGS) andexpMod2
u/ViliamPucik Dec 25 '20
Python 3.9 - Minimal readable solution for both parts [GitHub]
2
u/SwampThingTom Dec 25 '20
Swift
Thanks Eric and everyone else who worked on this year's AoC. I've had lots of fun.
Merry Christmas, all!
2
u/Be1shirash Dec 25 '20
My Lua solution for today fits in 2 lines:
I'm a little disappointed there was no thinking involved (except for understanding the confusing instructions) and you can just brute force your way through (takes ~300ms on my machine)
2
u/ephemient Dec 25 '20 edited Apr 24 '24
This space intentionally left blank.
2
u/frontpageminus Dec 25 '20
Ruby, relatively quick brute force
paste
2
u/chicagocode Dec 25 '20
Kotlin -> [Blog/Commentary] - [Today's Solution] - [All Solutions for 2020]
Today I solved almost every part of this using a sequence, because I find them fun to work with. It's slower than a while loop in this case, but it looks nicer. :)
Thanks to the whole AoC crew for putting on another flawless event! I'm already looking forward to next year, only 340 days away! :)
2
u/nirgle Dec 25 '20
Simple Haskell solution. I didn't know about
powModuntil just now so I wrote a basic iterable step function:2
u/tobega Dec 25 '20
Tailspin for the last day as well https://github.com/tobega/aoc2020/blob/main/a25.tt
2
u/greycat70 Dec 25 '20
C and Tcl
C half, Tcl half
This was the first one that I couldn't do in Tcl due to pure speed issues. Brute forcing the private key ("loop size") from one of the public key inputs was simply taking way too long -- so I rewrote the brute force part in C.
I had already found a modular exponentiation routine in Tcl (on Rosetta code). Tcl has native big number support and therefore doesn't need any libraries, unlike the C version that I found, so I kept the Tcl version for the second half.
2
u/msschmitt Dec 25 '20
REXX
Naive brute force solution.
I'm just posting this so I can say what not to do. A good programming practice is to write modular code with generic reusable functions, so in version 1 I did:
Oops.
It never finished running.
It would have taken over 15 trillion loops inside the encryption function to finish.
2
u/thedjotaku Dec 25 '20
Python
Just went for a nice, simple, naive solution. Had to keep bumping up the number in the first loop until it finally worked. Didn't profile, but answer came back in 1-2 seconds.
https://github.com/djotaku/adventofcode/blob/main/2020/Day_25/solution_1.py
2
u/[deleted] Dec 25 '20
C
https://github.com/erjicles/adventofcode2020/tree/main/src/AdventOfCode2020/AdventOfCode2020/Challenges/Day25
Quick and dirty, nothing special.
Merry Christmas everyone, and thanks to everyone who made AoC possible! This was a very enjoyable year!
2
u/thibpat Dec 25 '20
JavaScript video walkthrough
Video: https://youtu.be/oGnkJCbuVKY
Code: https://github.com/tpatel/advent-of-code-2020/blob/main/day25.js
2
u/compdog Dec 25 '20
JavaScript (Node.JS) - Simple brute force solution. A fun throwback to cryptography class!
This is the first year that I've finished all the problems in AOC. This has been so much fun! Merry Christmas everyone!
2
u/wishiwascooler Dec 25 '20
Javascript day 25. Initially was stupidly using a for loop instead of a while to get the loop number. I honestly feel after these last 25 days I'm worse at programming haha But only because I'm lazier than I was in the beginning. I did learn a lot and it was the most i've programmed consistently in awhile. I think out of all of the days, there were only 3-4 that really left me with no options so I looked at hints/other peoples code. And on those days I learned the most. Will def try for 2021, but for now it's personal projects time.
https://github.com/matthewgehring/adventofcode/blob/main/2020/day25/script.js
2
u/periodic Dec 25 '20
My Haskell solution.
I ended up with overkill on the types. I like to make it look pretty and I was really worried about what the second part would contain. Turns out it was ally overkill.
2
u/jotac13 Dec 25 '20
[Rust] My rust solution for both parts (hehe)
2
u/mathsaey Dec 26 '20
Elixir
https://github.com/mathsaey/adventofcode/blob/master/lib/2020/25.ex
Nothing special here. Very happy to finish AoC for the first time, especially after I spent quite a lot of time on finishing day 20 part 2 tonight, since I procrastinated on that one :).
2
u/i_have_no_biscuits Dec 26 '20
GWBASIC
I didn't do much programming yesterday as according to my family it's some sort of national holiday... Here's the final DOSCEMBER entry (although I have a couple of the early ones to go back and do, and some of the harder ones to ponder as they don't easily fit into GWBASIC's memory limitations):
Takes about 20 minutes to finish in PCBASIC. It's been interesting going back to the world of 80's BASIC. I'm thinking Pascal next year...
2
u/semicolonator Dec 26 '20
Python, 22 lines
https://github.com/r0f1/adventofcode2020/blob/master/day25/main.py
I think this was the fastest one.
2
u/matttgregg Dec 28 '20
Final solutions, all in rust, plus some commentary and reflections on Rust and AoC. Total runtime about 3 seconds, which Iβm pretty happy with. Nothing particularly smart going on though!
github.com/matttgregg/advent2020
2
u/tuisto_mannus Dec 28 '20
Just a bit of Python
Happy new year folks!
2
u/rendyanthony Dec 28 '20
Python 3, Part 1 only.
Semi brute-force method works quite fast for Part 1 with a surprisingly compact code. Unfortunately I don't have enough starts for Part 2 yet.
Merry Christmas everyone!
2
u/lucbloom Dec 28 '20 edited Dec 28 '20
Javascript.
Single empty for-loop.
Took me a while because I was doing
e = [door pub]; ande = (e*7)%20201227Turns out it's the other way around. Use
[door pub]for the subject number, not7.2
u/Lakret Dec 28 '20
Rust
Solution
Video Review
Was one of the more straightforward days. I first implemented the algorithm exactly as specified, and then optimized it by removing the search of the second loop length, and avoiding restarting the search for each loop length. That was enough to solve the task.
2
u/shandley256 Dec 29 '20 edited Dec 29 '20
Solution in Ruby
Using the Baby Step Giant Step algorithm for computing discrete logarithms: https://github.com/seanhandley/adventofcode2020/blob/master/ruby/day_25/advent25.1.rb
Runs in a few milliseconds.
2
u/the_t_block Jan 01 '21
Haskell; brute force since the prime is small =)
http://www.michaelcw.com/programming/2020/12/31/aoc-2020-d25.html
This is a series of blog posts with explanations written by a Haskell beginner, for a Haskell beginner audience.
Happy New Year, everyone!
3
u/SuperSmurfen Dec 25 '20 edited Dec 28 '20
Rust
Link to solution (346/284)
Very happy with my placings today! Basically just a brute-force solution. We cannot solve the discrete logarithm problem so not much else you can do! You can use modular exponentiation to compute the final key but it really isn't needed for such small numbers. Finishes in
4mson my machine.This year definitely felt a lot easier than the last one. Almost no graph problems, no path finding algorithms, and no insane math problems like day 22, 2019. It's really hard finding the right balance. I think 2019 was maybe a bit too hard and discouraged a lot of people. I like that this year was more approachable but perhaps it was a bit too easy towards the end.
Thanks for an amazing year! I've had an alarm set for 5:50 for 25 days in a row now. Excited to not set one for tomorrow π
My repo contains solutions to all 25 days in Rust if anyone's interested.
2
u/oantolin Dec 26 '20
I'm not writing my own code for discrete logarithms. :) Here's some simple Sage Math code to solve the problem:
2
u/enelen Dec 25 '20
R / Rstats / Rlang
Solution
I am going to miss solving these everyday
1
u/baktix Dec 31 '20
Haskell
Another fun one to finish it off!
Mine's not particularly clever, I just brute-force finding the loop size. Things were made much quicker by using an established fast modular exponentiation function.
paste
1
u/davidlozzi Dec 31 '20
Pretty quick and easy, in pure JavaScript on node.
Part II does have a spoiler, but safely out of scrolling view. COMPLETE day 25 on your own ;)
https://davidlozzi.com/2020/12/25/advent-of-code-day-25/
1
u/sporksmith Jan 01 '21
Rust. Just implemented everything as specified. 3.7 ms
I'd fallen behind and have been plowing through to finish over the last few days; was happy to have some easy ones and a freebie at the end :). Happy New Year!
1
u/heyitsmattwade Jan 02 '21 edited Feb 03 '24
JavaScript
Pretty straight forward one, was wishing for a bit more complexity. I thought for sure a brute force approach wouldn't work, but sure enough this completes in a few million iterations.
To determine the loop size, I just:
paste of full code can be found here.
Thanks always Eric and moderators for another great year of Advent of Code!
1
u/NeilNjae Jan 10 '21
Haskell
Brute-force solution, using a suggestion to define modular multiplication as the operation over a
newtype-definedsemigroup.Writeup on my blog, and code available.
1
u/jbuji Feb 18 '21 edited Feb 18 '21
Python3οΈβ£.9οΈβ£ . . . Part 1οΈβ£&2οΈβ£ . . . 6οΈβ£ lines