Fork me on GitHub

Streaming day 13 in a few moments:

👍 6
oxalorg (Mitesh)06:12:40

Looks like today's 2nd part might need some Modular arithmetic to solve 🙈

Vincent Cantin06:12:18

“In life, there are 92319243542196534129765432175643216314925319 kinds of people … those who can solve the math problems, and the others.”

😆 6
oxalorg (Mitesh)06:12:30

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 🙈

Vincent Cantin06:12:33

I tried brute forcing, but then I read the text again and I stopped torturing my 2011 mac book air.

😆 3

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?

😆 3
Vincent Cantin06:12:52

Day 13 answers thread - Post your answers here

Vincent Cantin09:12:23

I find it fantastic that we found similar, yet different ways to calculate the result. Interesting.


@U8MJBRSR5 oh, I didn't notice that bus cycles are primes, so I don't need LCM, multiplication is enough, nice catch!

Vincent Cantin09:12:40

I guess it depends which data you got, mine were all primes

👍 3
Vincent Cantin10:12:05

There must be a way to speed up our solutions using … the section “Application” is giving the exact math formula to our puzzle.

👍 3

But maybe it would have been easier to use modular multiplicative inverse straight away 😄

Vincent Cantin13:12:28

I implemented the solution from the Wikipedia article on invert-modulo, here is the source with benchmark:

👍 3
👏 6
Vincent Cantin13:12:33

@UAWTW2REE Clojure has (clojure.core/long n)


This one required some research in number theory.

👍 3

@U076FM90B or not 🙂 Trying to understand your solution...


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 to anything other than 3 equations...


@U076FM90B 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

👍 3

@U963A21SL thanks, that was so much easier to understand

👍 3

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

👍 6
🚀 3

A I took on the math in case they will be helpful for anyone else.

👍 6
❤️ 6

So much energy went to figure out such short solution (0.5ms execution time) for part 2:

Vincent Cantin09:12:11

I think that those numbers large enough to fear a math overflow are a good hint that we need to be prepared to use and its friends.


How long will a really naïve solution take for step 2? Asking for a friend.

Vincent Cantin13:12:32

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)]


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


Yeah, I must find a better approach. That’s what friends are for, right?

Vincent Cantin14:12:35

[spoilers alert] I can give your friend a hint: find a way to reduce the constraints by combining them.

Vincent Cantin14:12:29

[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


I managed to trial and error my way to a solution with @U8MJBRSR5’s hints. It runs in slightly less than 31 years. Now I am quite wasted. Not looking forward to tomorrow, even.

🙏 3
🎉 3
bananadance 3
bubblebobble 3
ryan echternacht21:12:01

oh, @U8MJBRSR5 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 ...


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})

ryan echternacht23:12:40

Yeah, I finally got there too

metal 6
Vincent Cantin01:12:39

> work on a pair of them, see what you can do to make them one I was just making a Buddhist joke, but I am glad it helped 😉

😃 3

Haha, I took it quit literally and it guided me to my gold star, which isn’t always easy to find on overcast days.

🙂 3

Only just found this channel and running a bit behind, but I've been putting up marginalia versions of my solutions at:

👍 9
😍 3

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 73
I have calculated the answer to the problem I think I've to solve as :
(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)
What am I misunderstanding?


I think my entire idea on how I can solve this doesnt work at all. damn

ryan echternacht21:12:58

it recommends starting at 15 places (100000000000000). Is this a good starting place?

ryan echternacht21:12:21

and is there some smart math form of this (using LCM?). I couldn't figure one out given the offsets


It’s literally the Chinese remainder theorem


Using LCM I don’t know


Well, all my buses are primes. So the least common multiplier between any 2 buses is just bus 1 * bus 2


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 🙂

ryan echternacht02:12:15

I agree @U0132B7P7C6. While it might literally be the Chinese remainder theorem, that's not the part of programming I enjoy/use often

Jeff Evans18:12:44

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


@ryan072 check out the day 13 answers thread - plenty of advice in there.


finally! Got a solution that works for part 2. I had 12 failed attempts at this one!

metal 18
ryan echternacht23:12:54

Thanks. I got it figured out