What Colour At That Second
A traffic light repeats a fixed cycle forever: green for g seconds, then
yellow for y, then red for r, then green again. At second 0 the light has
just turned green.
For each query, print the colour at second t.
``` g = 5, y = 2, r = 3
t = 0 -> GREEN green runs over seconds 0, 1, 2, 3, 4 t = 5 -> YELLOW yellow runs over seconds 5 and 6 t = 7 -> RED red runs over seconds 7, 8, 9 t = 10 -> GREEN the cycle repeats ```
## What most people try first
Step a counter forward one second at a time until it reaches t. Correct, and
O(t) per query: with t up to 10^9 and 10^5 queries that is 10^14
steps.
## One modulo answers it
The light has no memory, so the only thing that matters is where t sits inside
one cycle:
``` cycle = g + y + r p = t mod cycle
p < g GREEN p < g + y YELLOW otherwise RED ```
The comparisons must be in that order and must use strictly-less-than. Green
occupies seconds 0 through g - 1, so at p = g the light has ALREADY turned
yellow. Writing p <= g makes green one second too long and shifts every
boundary after it.
## Why it is correct
The argument is that the light is a function of t mod cycle alone, and that
needs showing rather than assuming. Let C(t) be the colour at second t. The
specification says the light repeats the same three phases forever starting at
second 0, which is exactly the statement that C(t + cycle) = C(t) for every
t. Applying that equality k times gives C(t) = C(t - k * cycle) for any
k with t - k * cycle >= 0. Choose k as the number of whole cycles inside
t; what is left is p = t mod cycle, which lies in [0, cycle), so C(t) =
C(p). Two different times therefore cannot disagree once reduced, and one
cycle of three phases covers [0, cycle) exactly: green takes [0, g), yellow
takes [g, g + y), red takes [g + y, cycle). Those three ranges are disjoint
and their lengths add to cycle, so every p falls in exactly one of them and
the chain of two comparisons picks that one.
## Where the boundaries are
This is the whole problem, so it is worth being exact. With g = 5, y = 2,
r = 3:
p: 0 1 2 3 4 5 6 7 8 9
colour: G G G G G Y Y R R R
Second 5 is the first yellow, not the last green. Second 7 is the first red. The
declared tests check t = 5 and t = 7 for exactly this reason, along with
t = 9 and t = 10 on another cycle to catch the wrap.
## A one-second phase is legal
Every duration can be 1, giving a cycle of 3 where each colour lasts a single second. A solution that assumes a phase is at least two seconds long, or that special-cases "the middle of a phase", fails there. That is a declared test.
## Overflow
Each duration on its own is well inside the signed 32 bit range, but their sum
g + y + r reaches 3 * 10^9, past the signed 32 bit limit of 2147483647, so
the cycle length must be accumulated in a 64 bit type.
It is worth being honest about what that buys you on this particular problem,
because the declared tests cannot show it. Since t never exceeds 10^9, any
cycle long enough to overflow 32 bits is already longer than every possible
t, so t mod cycle is just t, and a wrapped 32 bit sum still happens to
print the right colour on every input the constraints allow. The overflow is
real, the code is wrong, and no test here will tell you so. That is the usual
shape of an overflow bug: it survives the test suite and then does not survive
the day someone widens a constraint.
## Cost
O(1) per query: one modulo and at most two comparisons.