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