I'm stuck on computation on part2, it is way too s...

# advent-of-code

[bjonnh]

I'm stuck on computation on part2, it is way too slow

[Marcin Wisniowski]

I had to think outside the box.
As in, make another box do the thinking because my computer is too slow.

[bjonnh]

hah

[bjonnh]

found

[bjonnh]

took a few ms

[ilya.gorbunov]

Chinese remainder theorem to the rescue

[bjonnh]

yep that's one way

[bjonnh]

I found another one

[bjonnh]

https://github.com/bjonnh/advent_of_code/blob/master/src/main/kotlin/y2020/day13/main.kt

[bjonnh]

@ilya.gorbunov do you have your solution using the Chinese remainder theorem around?

[bjonnh]

I'm reading the wikipedia page about it, but i'm not sure how I would apply it here

[ilya.gorbunov]

It allows to find x in the system of equations
x mod Nk = Rk mod Nk. Here Nk is the number of a bus and Rk is the negated offset in minutes of that bus departure.
The important constraint though, is that all Nk must be co-prime. Perhaps your solution is free from that constraint.

[bjonnh]

Hmm I think my brain is fried for tonight

[bjonnh]

I'll try to get that approach working tomorrow

[ilya.gorbunov]

For example, it's impossible to find the solution for 2,x,4 input with CRT, while your approach gives an answer.

[Kroppeb]

I forgot the fact it's the negated offset

[Kroppeb]

Ended up reimplementing my crt and still got the same wrong answer

[Kroppeb]

Also there is no way to not use crt, as crt is a theorem saying it's solvable, not an algorithm

[andyb]

@bjonnh It looks like you have implemented the Search by Sieving solution to CRT mentioned on https://en.wikipedia.org/wiki/Chinese_remainder_theorem without even knowing it.

[Nir]

CRT seems to also depend on co-primality

[Nir]

I'm curious if there is any decent solution that does not depend on all bus ID's being relatively prime

[andyb]

@Nir I think that the Search by Sieving approach will work if you use Lowest Common Multiples rather than just multiplying the numbers even if the numbers are not co-prime.

[Nir]

I spent some time thinking about that, no sure if my approach is equivalent to sieving or not, wasn't sure if it truly still worked or not

[Nir]

conceptually my approach is basically to combine buses

[andyb]

I thought about that approach. How do you work out the modula for the combined buses?

[Nir]

Not quite sure what you mean by the modula

[Nir]

fun combine(p: Pair<Long, Long>, q: Pair<Long, Long>): Pair<Long, Long> {
    var current = p.first
    while (departureDelay(current, q.second) != (q.first % q.second)) {
        current += p.second
    }

    return current to p.second * q.second
}

[Nir]

This is a function designed to be used in fold

[Nir]

the first argument is the first time that works, and the period. The second argument is the bus index, and the ID

[Nir]

fun departureDelay(time: Long, bus: Long) = ceil(time.toDouble() / bus).toLong() * bus - time

this function is pretty lazy. Inside combine I should really do modular math but this is easier

[Nir]

I think you're right it would still work with the LCM change

[Nir]

would be interesting to test. but wihout coprimality it's possible to not have solutions for some inputs of course

[andyb]

I was meaning suppose that you had the following input:

3,x,x,5,x,7,x,....

Then convert this to busId + offset pairs like
(3,0), (5,3), (7,5), ....
If we combine the first 2 pairs then we know that each possible solution must be 15 (i.e. 3*5) apart but we don't know the offset,(say x) so list could be reduced to :
(15,x), (7,5), ....

If there was a formula to determine x we could solve just by running a reduce() function across the list of pairs and the solution would be the 'x' in the final value. We could also use divide-and-conquer to solve if the number of pairs was large.

[Kroppeb]

There is a formula to figure out x

[andyb]

I've been trying to work it out with a pen & paper but I can't see the pattern. Please enlighten me