Fork me on GitHub
<
2020-12-13
>
plexus06:12:14

Streaming day 13 in a few moments: https://youtu.be/ONclnLu3UqA

š 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
nbardiuk08:12:05

I've given up on brute forcing when it got too warm with laptop on my laps š

fingertoe08:12:50

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

Vincent Cantin09:12:23

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

nbardiuk09:12:36

@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 https://en.wikipedia.org/wiki/Modular_multiplicative_inverse ā¦ the section āApplicationā is giving the exact math formula to our puzzle.

š 3
joppe11:12:16

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: https://github.com/green-coder/advent-of-code-2020/blob/master/src/aoc/day_13.clj#L71-L88

š 3
š 6
Vincent Cantin13:12:33

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

benoit14:12:01

This one required some research in number theory. https://github.com/benfle/advent-of-code-2020/blob/main/day13.clj

š 3
benoit14:12:28

@U076FM90B or not š Trying to understand your solution...

benoit14:12:47

Thanks, looking.

benoit14:12:32

Ok simplified a bit. Number theory is not my friend.

Joe14:12:32

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

benoit15:12:32

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

nbardiuk15:12:10

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
Joe15:12:44

@U963A21SL thanks, that was so much easier to understand

š 3
Joe16:12:36

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
š 3
Joe17:12:13

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.

š 6
ā¤ļø 6
genmeblog00:12:29

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

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 https://clojuredocs.org/clojure.core/bigint and its friends.

pez13:12:16

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

9
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)]
x)
first)``````

pez13:12:33

My friends computer is getting really hot.

3
plexus13:12:43

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

pez14:12:12

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.

pez14:12:47

ā¤ļø

Vincent Cantin14:12:29

[spoilers alert] work on a pair of them, see what you can do to make them one

pez14:12:15

Will do. Thanks!

erwinrooijakkers14:12:02

If your computation for every step takes a millisecond and you have a trillion operations it will take more than 31 years to return

pez20:12:37

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

pez22:12:54

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

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
pez12:12:25

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
thom18:12:47

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

š 9
š 3
thom18:12:55

apologies for any and all crimes against Clojure

Stuart18:12:26

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 :
``561773853149685``
Because
``````(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?

Stuart19:12:34

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

erwinrooijakkers21:12:43

Itās literally the Chinese remainder theorem

erwinrooijakkers21:12:58

Using LCM I donāt know

Stuart21:12:52

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

rfisher23:12:07

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.

rfisher23:12:22

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. š https://github.com/jeff303/advent-of-code-2020/blob/master/src/advent_of_code/day13.clj#L80

Joe21:12:50