Recording: https://youtu.be/q-T87Ja2DF8

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.

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?

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

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.

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

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

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

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

@U0105JJK1L3 I used this https://www.geeksforgeeks.org/chinese-remainder-theorem-set-2-implementation/?ref=lbp

@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

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

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

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

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.

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

Yeah, I finally got there too

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

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

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 🙂

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

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