3 ms·

Excuse me, what? You don't need to know CRT or indeed anything about the number theory except that you can divide numbers, the solution is simply: for each

Excuse me, what? You don't need to know CRT or indeed anything about the number theory except that you can divide numbers, the solution is simply: for each ID in list: next_departure = round_up_to_next_integer(earliest_time / ID) * ID delay[ID] = next_departure - earliest_time nearest_bus = ID with lowest delay return nearest_bus * delay[nearest_bus] That's it. I can think of only two other algorithms: the one that replaces division on the second line by repeated subtraction, and the one that uses repeated increments and checking whether the result is divided by the ID without a remainder. How do you even use CRT to solve this?

Jtsummers 5y ago
Are you looking at part 1 or part 2? GP is talking about part 2.
- Joker_vD 5y ago
  Can't find part 2 on the site, had to google... result = 0 addend = 1 for divisor, desired_offset in [(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]: # keep trying numbers until we find the one that, with # the desired offset added to it, would divide without # remainder while (result + desired_offset) % divisor != 0: result += addend # adding another addend should not break previous results # so make it divisible by all previous divisors addend *= divisor print(result % (7*13*59*31*19)) This algorithm self-evidently works and is indeed "fast enough" if done by the computer.
  - Jtsummers 5y ago
    The key insight that many people, particularly those without the stronger math background, miss is that you can increase the addend like you (and I, in my solution) have done. So they either leave it at 1 (and the solution is around 1-2 trillion, IIRC, so that's not happening quickly) or they do one optimization which is to set it to the first divisor (7 in your example, which still leaves you with hundreds of billions of loop executions), but don't adjust it with each newly matched bus line. And instead of talking down to people, it can be more productive if you walk through a solution instead of stating "This algorithm self-evidently works" like a jerk. Also, the last modulo isn't needed.
    - Joker_vD 5y ago
      > walk through a solution instead of stating "This algorithm self-evidently works" like a jerk. After every iteration, "result" gives correct remainders for all divisors considered so far, so if the loop ends, the "result" will give correct remainders for all divisors. The only problem is whether it will end or not, and that I just tried experimentally: it stopped, so ok. Not really sure how to explain it further. > Also, the last modulo isn't needed. Good to know, I was not sure if I wouldn't step past it due to constantly increasing addend. I knew about this modular reduction from that one time when I needed to align/move/scroll things on a 80x25 grid.

Jtsummers 5y ago

Are you looking at part 1 or part 2? GP is talking about part 2.

Joker_vD 5y ago
Can't find part 2 on the site, had to google... result = 0 addend = 1 for divisor, desired_offset in [(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]: # keep trying numbers until we find the one that, with # the desired offset added to it, would divide without # remainder while (result + desired_offset) % divisor != 0: result += addend # adding another addend should not break previous results # so make it divisible by all previous divisors addend *= divisor print(result % (7*13*59*31*19)) This algorithm self-evidently works and is indeed "fast enough" if done by the computer.
- Jtsummers 5y ago
  The key insight that many people, particularly those without the stronger math background, miss is that you can increase the addend like you (and I, in my solution) have done. So they either leave it at 1 (and the solution is around 1-2 trillion, IIRC, so that's not happening quickly) or they do one optimization which is to set it to the first divisor (7 in your example, which still leaves you with hundreds of billions of loop executions), but don't adjust it with each newly matched bus line. And instead of talking down to people, it can be more productive if you walk through a solution instead of stating "This algorithm self-evidently works" like a jerk. Also, the last modulo isn't needed.
  - Joker_vD 5y ago
    > walk through a solution instead of stating "This algorithm self-evidently works" like a jerk. After every iteration, "result" gives correct remainders for all divisors considered so far, so if the loop ends, the "result" will give correct remainders for all divisors. The only problem is whether it will end or not, and that I just tried experimentally: it stopped, so ok. Not really sure how to explain it further. > Also, the last modulo isn't needed. Good to know, I was not sure if I wouldn't step past it due to constantly increasing addend. I knew about this modular reduction from that one time when I needed to align/move/scroll things on a 80x25 grid.