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

# advent-of-codeb

bjonnh

12/13/2020, 5:29 AMI'm stuck on computation on part2, it is way too slow

m

Marcin Wisniowski

12/13/2020, 6:00 AMI had to think outside the box.
As in, make another box do the thinking because my computer is too slow.

b

bjonnh

12/13/2020, 6:20 AMhah

bjonnh

12/13/2020, 6:20 AMfound

bjonnh

12/13/2020, 6:20 AMtook a few ms

i

ilya.gorbunov

12/13/2020, 6:24 AMChinese remainder theorem to the rescue

b

bjonnh

12/13/2020, 6:28 AMyep that's one way

bjonnh

12/13/2020, 6:29 AMI found another one

bjonnh

12/13/2020, 6:30 AMbjonnh

12/13/2020, 6:33 AMbjonnh

12/13/2020, 6:33 AMI'm reading the wikipedia page about it, but i'm not sure how I would apply it here

i

ilya.gorbunov

12/13/2020, 6:50 AMIt 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

bjonnh

12/13/2020, 6:53 AMHmm I think my brain is fried for tonight

bjonnh

12/13/2020, 6:53 AMI'll try to get that approach working tomorrow

i

ilya.gorbunov

12/13/2020, 7:00 AMFor example, it's impossible to find the solution for

`2,x,4`

input with CRT, while your approach gives an answer.k

Kroppeb

12/13/2020, 7:27 AMI forgot the fact it's the negated offset

Kroppeb

12/13/2020, 7:27 AMEnded up reimplementing my crt and still got the same wrong answer

Kroppeb

12/13/2020, 7:28 AMAlso there is no way to not use crt, as crt is a theorem saying it's solvable, not an algorithm

a

andyb

12/13/2020, 11:01 AMn

Nir

12/13/2020, 3:19 PMCRT seems to also depend on co-primality

Nir

12/13/2020, 3:19 PMI'm curious if there is any decent solution that does not depend on all bus ID's being relatively prime

a

andyb

12/13/2020, 3:22 PMn

Nir

12/13/2020, 3:30 PMI 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

12/13/2020, 3:31 PMconceptually my approach is basically to combine buses

a

andyb

12/13/2020, 3:33 PMI thought about that approach. How do you work out the modula for the combined buses?

n

Nir

12/13/2020, 3:37 PMNot quite sure what you mean by the modula

Nir

12/13/2020, 3:38 PM 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
}
```

Nir

12/13/2020, 3:38 PMThis is a function designed to be used in fold

Nir

12/13/2020, 3:38 PMthe first argument is the first time that works, and the period. The second argument is the bus index, and the ID

Nir

12/13/2020, 3:40 PM 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 easierNir

12/13/2020, 3:42 PMI think you're right it would still work with the LCM change

Nir

12/13/2020, 3:42 PMwould be interesting to test. but wihout coprimality it's possible to not have solutions for some inputs of course

a

andyb

12/13/2020, 5:26 PMI 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

Kroppeb

12/13/2020, 5:49 PMThere is a formula to figure out x

a

andyb

12/13/2020, 5:52 PMI've been trying to work it out with a pen & paper but I can't see the pattern. Please enlighten me

8 Views