This page is not created by, affiliated with, or supported by Slack Technologies, Inc.

## 2020-12-13

## Channels

- # adventofcode (69)
- # announcements (1)
- # babashka (68)
- # beginners (37)
- # calva (3)
- # cider (4)
- # cljdoc (4)
- # cljsrn (1)
- # clojure (73)
- # clojure-europe (13)
- # clojure-nl (15)
- # clojure-switzerland (11)
- # clojure-uk (6)
- # clojurescript (14)
- # code-reviews (1)
- # conjure (1)
- # cryogen (3)
- # fulcro (32)
- # lambdaisland (8)
- # pathom (13)
- # reagent (6)
- # releases (1)
- # reveal (43)
- # shadow-cljs (9)
- # tools-deps (2)
- # vim (2)

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

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

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!

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

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

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

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

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

**[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

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

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

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

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

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.

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

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

Thanks. I got it figured out