Clojurians Log v2
adventofcode
Streaming day 13 in a few moments: https://youtu.be/ONclnLu3UqA
Recording: https://youtu.be/q-T87Ja2DF8
Looks like today's 2nd part might need some Modular arithmetic to solve 🙈
“In life, there are 92319243542196534129765432175643216314925319 kinds of people … those who can solve the math problems, and the others.”
I've given up on brute forcing when it got too warm with laptop on my laps 🙂
Brute force? or remember basic HS math from thirty years ago? Maybe my high schooler is up.. If only I was a CS major instead of MIS.. Maybe it will be debits and credits next?
Good morning !
Day 13 answers thread - Post your answers here
this was the hardest for me this year so far https://github.com/nbardiuk/adventofcode/blob/master/2020/src/day13.clj
I find it fantastic that we found similar, yet different ways to calculate the result. Interesting.
@vincent.cantin oh, I didn't notice that bus cycles are primes, so I don't need LCM, multiplication is enough, nice catch!
I guess it depends which data you got, mine were all primes
There must be a way to speed up our solutions using https://en.wikipedia.org/wiki/Modular_multiplicative_inverse … the section “Application” is giving the exact math formula to our puzzle.
I used the chinese remainders theorem in my solution https://github.com/Yopi/advent-of-code/blob/master/src/adventofcode/2020/day13.clj
But maybe it would have been easier to use modular multiplicative inverse straight away 😄
I implemented the solution from the Wikipedia article on invert-modulo, here is the source with benchmark: https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_13.clj#L71-L88
@brann.jesper Clojure has (clojure.core/long n)
This one required some research in number theory. https://github.com/benfle/advent-of-code-2020/blob/main/day13.clj
@nbardiuk or not 🙂 Trying to understand your solution...
@me1740 there is a gcd function in https://github.com/clojure/math.numeric-tower
and there is a .modInverse in the JDK https://clojuredocs.org/clojure.core/bigint#example-59fa5422e4b0a08026c48c8f
Thanks, looking.
Ok simplified a bit. Number theory is not my friend.
Does anyone have a more thorough example of using inverses to solve systems of linear congruences? I can't figure out how you'd generalize the formula on the applications section of https://en.wikipedia.org/wiki/Modular_multiplicative_inverse to anything other than 3 equations...
@allaboutthatmace1789 I used this https://www.geeksforgeeks.org/chinese-remainder-theorem-set-2-implementation/?ref=lbp
@nbardiuk Nice solution, I didn't realize that each partial solution was also cyclic and you could progress towards the solution for all buses like this.
Yes, the partial solution repeats with least common multiple of bus cycles. As Vincent noticed all busses have prime cycle so lcm becomes just multiplication
@me1740 thanks, that was so much easier to understand
Pretty easy after you've spent 6 hours reading about modular arithmetic 😵
(defn- linear-congruence-solve [pairs]
(let [remainders (map first pairs)
modulos (map second pairs)
prod (apply * modulos)
pp (map #(/ prod %) modulos)
inv (map #(.modInverse (biginteger %1) (biginteger %2)) pp modulos)]
(mod (apply + (map * remainders pp inv)) prod)))A https://redpenguin101.github.io/posts/2020_12_13_mod_mult.html I took on the math in case they will be helpful for anyone else.
So much energy went to figure out such short solution (0.5ms execution time) for part 2: https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2020/day13.clj#L34-L44
I thought maybe today they want us to brute force it and I waited for 20 minutes for the brute force to complete before giving up 🙈
I tried brute forcing, but then I read the text again and I stopped torturing my 2011 mac book air.
https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_13.clj
https://github.com/lambdaisland/aoc_2020/blob/main/src/lambdaisland/aoc_2020/puzzle13.clj
I think that those numbers large enough to fear a math overflow are a good hint that we need to be prepared to use https://clojuredocs.org/clojure.core/bigint and its friends.
How long will a really naïve solution take for step 2? Asking for a friend.
Haha, I took it quit literally and it guided me to my gold star, which isn’t always easy to find on overcast days.
Tell your friend that his chances will be better if he tries the “leap of faith” approach:
(-> (for [x (repeatedly (long (* (rand) Long/MAX_VALUE)))
:when (valid? x)]
x)
first)My friends computer is getting really hot.
So my input had 9 bus ids, and up to 6 or 7 my initial approach would still run within a few seconds, but after that it really blew up
@pez It was not meant to be solved this way. https://moddr.net/uploads/2008/10/computer-bbq.jpg
Yeah, I must find a better approach. That’s what friends are for, right?
[spoilers alert] I can give your friend a hint: find a way to reduce the constraints by combining them.
❤️
[spoilers alert] work on a pair of them, see what you can do to make them one
Will do. Thanks!
If your computation for every step takes a millisecond and you have a trillion operations it will take more than 31 years to return
Only just found this channel and running a bit behind, but I've been putting up marginalia versions of my solutions at: https://lemonwatcher.com/advent.html
apologies for any and all crimes against Clojure
Bit stuck on part 2 today, not sure what I'm missing: Given the busses in positions
19 is pos 0
41 is pos 9
37 is pos 13
367 is pos 19
13 is pos 32
17 is pos 36
29 is pos 48
373 is pos 50
23 is pos 73561773853149685(mod 561773853149685 19)
=> 0
(mod 561773853149685 41)
=> 32 (41 - 9 = 32)
(mod 561773853149685 37)
=> 24 (37 - 13 = 24)
(mod 561773853149685 367)
=> 348 (367 - 19 = 348) as 367 is in the 19th pos.
(mod 561773853149685 13)
=> 7 (13-32 mod 13 = 7) as 13 is in the 32nd pos
(mod 561773853149685 17)
=> 15 (17 - 36 mod 17) as 17 is in the 36th pos.
(mod 561773853149685 29)
=> 10 (29 - 48 mod 29)
(mod 561773853149685 373)
=> 273 (373 - 50)
(mod 561773853149685 23)
=> 19 (23 - 73 mod 23)I think my entire idea on how I can solve this doesnt work at all. damn
I managed to trial and error my way to a solution with @vincent.cantin’s hints. It runs in slightly less than 31 years. Now I am quite wasted. Not looking forward to tomorrow, even.
it recommends starting at 15 places (100000000000000). Is this a good starting place?
and is there some smart math form of this (using LCM?). I couldn't figure one out given the offsets
Agreed with the above. There are times when the “math puzzle” piece is interesting, but at least for me, personally, I’m trying to build up my Clojure skills through this exercise. I managed to Google my way to the Chinese remainder theorem (and this thread), and happy to see others are in the same boat. This is one case where I was happy to copy/paste some code. 😆 https://github.com/jeff303/advent-of-code-2020/blob/master/src/advent_of_code/day13.clj#L80
It’s literally the Chinese remainder theorem
Using LCM I don’t know
oh, @vincent.cantin are you saying. find the "step size" that the first 2 numbers must be apart to line up. then combine that with the 3rd number to find a bigger step count, then ...
@ryan072 check out the day 13 answers thread - plenty of advice in there.
Well, all my buses are primes. So the least common multiplier between any 2 buses is just bus 1 * bus 2
I think that’s what he said. 😃 My reductions look like so:
({:bus 29, :offset 0}
{:bus 1073, :offset 754}
{:bus 438857, :offset 379523}
{:bus 7460569, :offset 5645807}
{:bus 96987397, :offset 50409221}
{:bus 1842760543, :offset 923295794}
{:bus 42383492489, :offset 32250225025}
{:bus 14961372848617, :offset 4312982966414}
{:bus 613416286793297, :offset 408270049879073})finally! Got a solution that works for part 2. I had 12 failed attempts at this one!
Thanks. I got it figured out
Yeah, I finally got there too
I enjoy these when they're programming puzzles. It's not so much fun when I have to try (and fail) to independently work out some mathematical theorem I've never heard of.
That's not a moan, other than at myself for never learning mathematics 🙂