I'm stuck on computation on part2, it is way too s...
# advent-of-code
b
I'm stuck on computation on part2, it is way too slow
m
I had to think outside the box. As in, make another box do the thinking because my computer is too slow.
b
hah
found
took a few ms
i
Chinese remainder theorem to the rescue
b
yep that's one way
I found another one
@ilya.gorbunov do you have your solution using the Chinese remainder theorem around?
I'm reading the wikipedia page about it, but i'm not sure how I would apply it here
i
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.
b
Hmm I think my brain is fried for tonight
I'll try to get that approach working tomorrow
i
For example, it's impossible to find the solution for
``2,x,4``
input with CRT, while your approach gives an answer.
k
I forgot the fact it's the negated offset
Ended up reimplementing my crt and still got the same wrong answer
Also there is no way to not use crt, as crt is a theorem saying it's solvable, not an algorithm
a
@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.
n
CRT seems to also depend on co-primality
I'm curious if there is any decent solution that does not depend on all bus ID's being relatively prime
a
@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.
n
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
conceptually my approach is basically to combine buses
a
I thought about that approach. How do you work out the modula for the combined buses?
n
Not quite sure what you mean by the modula
Copy code
``````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
}``````
This is a function designed to be used in fold
the first argument is the first time that works, and the period. The second argument is the bus index, and the ID
Copy code
``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
I think you're right it would still work with the LCM change
would be interesting to test. but wihout coprimality it's possible to not have solutions for some inputs of course
a
I was meaning suppose that you had the following input:
Copy code
``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.
k
There is a formula to figure out x
a
I've been trying to work it out with a pen & paper but I can't see the pattern. Please enlighten me