Fork me on GitHub
<
2020-12-25
>
Vincent Cantin05:12:48

Vincent Cantin05:12:10

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

👍 12
rjray05:12:13

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…

😁 12
6
euccastro05:12:59

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

🎉 9
Vincent Cantin05:12:52

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

🙌 3
euccastro05:12:16

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

euccastro05:12:23

I even 'cracked' both values unnecessarily

euccastro05:12:18

@U8MJBRSR5 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]

☝️ 6
👍 3
Vincent Cantin05:12:33

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

euccastro05:12:57

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

Vincent Cantin05:12:29

yes, you are right.

euccastro06:12:00

``````;; 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)))))``````

👍 9
Vincent Cantin06:12:58

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.

💪 9
Vincent Cantin06:12:08

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

Average-user07:12:41

But saddly, that is not the bottleneck

Max Deineko10:12:14

For the fun of it: added baby-step giant-step logarithm computation and exponentiation as mentioned by @U8MJBRSR5 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

🚀 9
alekszelark15:12:01

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

👍 9
📎 3
Vincent Cantin05:12:17

The stats are funny … so many people trying to find a way to get a problem for part2

alekszelark05:12:09

Last year I was one of them

Vincent Cantin05:12:30

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

Vincent Cantin05:12:30

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

Vincent Cantin06:12:13

“… day 20, you again” :rolling_on_the_floor_laughing:

euccastro06:12:49

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

Alexandre Grison06:12:11

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

Alexandre Grison06:12:28

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

Alexandre Grison06:12:51

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

🎉 9
alekszelark06:12:00

> 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.

euccastro03:12:34

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

erwinrooijakkers08:12:40

Thank you! 🙂 Merry Christmas :mother_christmas:

erwinrooijakkers09:12:20

was a joy to learn from your solutions

erwinrooijakkers09:12:23

and to be part of this community

🎄 15
nbardiuk09:12:51

Marry Christmas 🦌 It was fun journey

15
Alexandre Grison09:12:52

are the solutions archived somewhere ? I'd like to read some of them in a month or so, since I didn't solved the challenges with Clojure this year

Vincent Cantin10:12:04

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

peterc10:12:15

Thanks to everyone for their code solutions and feedback. It was a wonderful learning experience and see you all next year!

9
Joe11:12:52

I haven't finished yet, but it was fun solving all the problems, and great seeing how other people did things. I learned a lot, thank you!

15
❤️ 6
misha19:12:17

and as usual "never again"

😀 6
misha19:12:10

@a.grison https://akovantsev.github.io/corpus/clojure-slack/adventofcode.html#t1608887152 piggybacking on clojureverse's logs: all 5 years of logs in a single offline html page with filtering

🙏 3