Clojurians Log v2

For those interested by the topic, today’s puzzle was related to https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

Kind of feeling let down by the day 25 puzzle. I expected to find that a brute-force approach wouldn’t be feasible. But hey, at least I can tell my wife that it’s over…

https://github.com/rjray/advent-2020-clojure/blob/master/src/advent_of_code/day25.clj

https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_25.clj

I couldn't get part 2 because I started AoC at day 16 so I'm missing stars. here is my solution to part 1: https://github.com/euccastro/advent-of-code-2020/blob/master/src/advent/day25.clj

The optimization was to choose the smaller loop-size when calculating the solution.

I guess I lucked out then, since mine runs fast enough without worrying about that

I even 'cracked' both values unnecessarily

@vincent.cantin come to think about it, why is that an optimization? shouldn't you perform the same number of steps no matter which key you choose to 'crack' (i.e., find the loop size of)? [P.S.: it seems that at least in my implementation it matters which one you pick, because finding the loop size happens to be more expensive than transforming a number by that number of loops]

Pretty straightforward Day 25. https://github.com/abyala/advent-2020-clojure/blob/master/src/advent_2020_clojure/day25.clj

@euccastro The optimization is for the last step, to find the “shared secret”.

but to find the smallest loop size you need to find the loop size of both the door and key, which is actually slower than picking either arbitrarily, find the loop size of that one only, and transform the other with that

yes, you are right.

;; 2437 msecs
(time
 (transform (first input) (crack (second input))))

;; 1751 msecs
(time
 (transform (second input) (crack (first input))))

;; 2980 msecs
(time (do (crack (first input)) (crack (second input))))

;; 3450 msecs
(time
 (do
   (crack (second input))
   (transform (second input) (crack (first input)))))

https://github.com/zelark/AoC-2020/blob/master/src/zelark/aoc_2020/day_25.clj

There is an optimization possible for the last step. It looks like: • If the loop-size is even, square the subject-number, then modulo it. Half the loop-size. • If it is even, do one step as usual.

It will run in O(log_2(loop-size))

But saddly, that is not the bottleneck

Only part 1 for me today 🙂 https://github.com/next-mad-hatter/adventofcode/blob/master/src/aoc_2020/day_25.clj

https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day25.clj

https://github.com/transducer/adventofcode/blob/master/src/adventofcode/2020/day25.clj

For the fun of it: added baby-step giant-step logarithm computation and exponentiation as mentioned by @vincent.cantin to bring the runtime for part 1 from 1300 to 1.3 ~13 msecs 🙂 https://github.com/next-mad-hatter/adventofcode/blob/master/src/aoc_2020/day_25.clj

Solution to part1. https://github.com/benfle/advent-of-code-2020/blob/main/day25.clj

For the last step you can just use .modPow. This (mod-pow pubkey loop-size module) returns an answer instantly!

https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2020/day25.clj

Last year I was one of them

I was also wondering … because it is my first year, I wanted to know how to do everything and not miss something.

oh … wait … it is probably people who did not finish all the previous puzzles.

yep 🙂

“… day 20, you again” 🤣

heheh, in my case I'm missing all up to 15. I'll do them at a more leisurely pace

Yes you need 49 stars so that they give you the 50th for free

but there are people who don't know they need to click

Took me 7 seconds to click but I was faster than 29 other peoples. Going from rank 206 to 177 🤠

> Yes you need 49 stars so that they give you the 50th for free Yes, last year I didn’t have all of them. So I just couldn’t click it.

OK, I just finished bingeing on 1-15, to see the true ending. disclaimer: I'd seen Lambda Island's AoC 2020 videos and I had seen the Chinese Remainder Theorem spoiler https://github.com/euccastro/advent-of-code-2020/tree/master/src/advent

we have a pinned solution thread per day https://app.slack.com/client/T03RZGPFR/C0GLTDB2T/details/pins

thanks!

they won't be there in a month, I am afraid.

https://clojurians-log.clojureverse.org/ for rescue

awesome!