Traffic Lights

Have you ever wondered what the probability is of making it through a sequence of traffic lights without stopping? Me neither. But some people do so let’s try and solve that problem. It’s something that appears in everyday life for example my walk from home to DroneDeploy taken me through 16 traffic lights.

Screenshot 2020-01-14 15.51.25.png

Let’s say we begin at position X=0 at time T in seconds and start walking as 1 meter per second right. Let’s say T is uniformly randomly distributed in the range [0, 1e100] to account for all manner of late starts. Then let’s say there are N traffic lines as positions X1, X2, … ,XN for each of these they are red for Ri seconds, then green for Gi seconds after which they repeat their cycles. At time T= 0 all traffic lights have just turned red. So givens the lists or X, R and G let’s try and compute the probability that we hit each of the red lights and thus the probability that we make it all the way through. The images above shows 4 traffic lights with periods 8, 22, 6 and 10. Let’s also say R + G <= 100.

Our first attempt could be to samples start times T and for each sample compute which traffic light we stop at (if any) and report the probabilities.

Light = namedtuple('Light', ['x', 'r', 'g'])

lights = [
 Light(3, 1, 3),
 Light(5, 2, 7),
 Light(9, 4, 4),
]

def simulate(t, lights):
    for index, light in enumerate(lights):
        at = (light.x + t) % (light.r + light.g)
        if at < light.r:
            return index
    return len(lights)

def solution(lights):

    N = len(lights)
    SAMPLES = 1000000
    P = 1
    for light in lights:
        P = lcm(P, light.r+light.g)

    ret = [0] * (N + 1)

    for _ in range(SAMPLES):
        T = np.random.uniform(0, 1e100)
        i = simulate(T, lights)
        ret[i] += 1

    count = sum(ret)
    return [ i / count for i in ret]

Here’s what a few samples might look like. The solution is easy to code but it’s really slow and unlikely to converge to something useful in a reasonable amount of time.

Screenshot 2020-01-14 15.44.02.png

Let’s hunt for a more effective solution. Let’s look at the periods of the traffic lights Pi = Ri+Gi. Given that the lights start having just turned red the system will start repeating at some point in time. Computing the lowest common multiple of the periods Pi gives the amount of times for the system to repeat. So a better solution would be instead of trying random start time to try each start time in the range [ 0 … LCM([P1, P2, ... , PN]) ] and then compute the probability.

def gcd(a, b):
    if b > 0:
        return gcd(b, a%b)
    else:
        return a

def lcm(a, b):
    return a * b // gcd(a, b)

def solution(lights):

    N = len(lights)
    P = 1
    for light in lights:
        P = lcm(P, light.r+light.g)

    ret = [0] * (N + 1)

    for T in range(P):
        i = simulate(T, lights)
        ret[i] += 1

    count = sum(ret)
    return [ i / count for i in ret]

This works and gives us a O ( LCM([P1, P2, ... , PN]) ) solution. Here’s what it look like for the same system:

Screenshot 2020-01-14 15.48.28.png

On the y-axis we have all possible start times modulo LCM([P1, P2, ... , PN]), as we don’t need to consider any others. The arrows represent which traffic like we would hit starting at that time. The final probabilities are correct so let’s look at the worst case of having traffic lights of all the periods between 1 and 100. What is the LCM of the numbers 1 .. 100. Uh oh, it’s 69,720,375,229,712,477,164,533,808,935,312,303,556,800. That’s not going to work. Can we do better?

Let’s look at the system of period 3 and 5 traffic lights. The system will repeat with a period of LCM(3, 5) = 15. But in addition the periods are co-prime as they share no prime factors GCD(3, 5) = 1. Which means knowing what state the period 3 traffic light is in tells us nothing about what state the period 5 traffic light is in. Essentially the probabilities are independent and the probability of making it through both lights is just the probability of making it through the first light multiples by the probability of making it through the second light, G1 / (R1+G1) * G2 / (R2+G2). Maybe R2G2 will feature in the new Star Wars. Anyway, this is true for a set of traffics lights with co-prime periods like. This yields a nice O(N) solution with the caveat that the periods must be co-prime.

a.png

Here’s what things look like if we add another light of period 2 to the system.

b.png

Now what happens if we introduce a period 6 light into this set. In this case 6 is a multiple of the existing period.

a.png

This is the same as repeating the existing period 2 and 3 traffic lights. So it’s the same as this system.

b.png

Thus for a set of periods which are either co-prime or multiples of each other we can solve the system in O(N * P) where P in the largest period, by considering each time 0 … P-1 and keeping track of which times modulo that period would hit a red light. We can do this by computing for each light which light to it’s left have periods which are multiples of itself, or where current light is a multiple of a previous one and instead use the period of that light.

Great! But what about these two lights, 8 and 12. They are neither co-prime nor integer multiples of each other as they share a factor GCD(8, 12) = 4. Let’s pick another number Z and consider start times modulo Z: { T+Z, T+2Z, …. }. If we only consider these times a traffic light with period P will still be periodic but will have a period of P / GCD(Z, P). For the example let’s pick Z as 4 and create a system of reduced periods 2 and 3, (originally 8 and 12). These are co-prime so we can use our initial algorithm. The problem is now a matter of finding the suitable value Z that for a set of periods transforms them to a set of reduced periods where each is either co-prime or a multiple of another period. Here some code to compute one of those numbers experimentally:

def findZ():

    nums = list(range(100))

    again = True
    factors = []

    while again:
        again = False
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):

                if nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0:
                    continue

                z = gcd(nums[i], nums[j])
                if z != 1:
                    for k in range(len(nums)):
                        if nums[k] % z == 0:
                            nums[k] = nums[k] // z

                    factors.append(z)
                    again = True

    return factors

The result is the factors [2, 2, 2, 2, 3, 3, 5, 7] the product of which is 2520. That’s the key we’ve been looking for. This leads us to the following solution which runs in a very manageable O(N * X * P).

def solution(lights):

    Z = 2520
    N = len(lights)

    fn = [ ]
    filters = []
    for i, light in enumerate(lights):
        period = (light.r+light.g) // gcd(Z, light.r+light.g)
        for j in range( len(filters) ):

            if period % len(filters[j]) == 0:
                filters[j] = [-1] * period

            if len(filters[j]) % period == 0:
                fn.append(j)
                break
        else:
            fn.append( len(filters) )
            filters.append( [-1] * period )


    ret = [0] * (N + 1)

    for base in range(Z):
        cur = 1.0 / Z
        for i, light in enumerate(lights):
            filter = filters[fn[i]]
            total = 0
            hits_red = 0
            t = Z + base + light.x
            for j in range(len(filter)):
                if filter[j] < base:
                    total += 1
                    if t % (light.r + light.g) < light.r:
                        filter[j] = base
                        hits_red += 1
                t += Z
            entering = cur
            if (total):
                cur *= (total - hits_red) / total
            ret[i] += entering - cur
        ret[N] += cur

    return ret

It’s really cool to see a seemly intractable problem dissolve in the presence of a seemingly magic number that disconnects all the primes. So what’s the probability of making is through a sequence of traffic lights? Wonder no more. This question is based on ICPC World Finals 2019 Problem K.

 
59
Kudos
 
59
Kudos

Now read this

General Collector’s Problem

Some time ago at work we wanted a way to represent each person with an avatar to track what they were working on on a board. We were using a sort of Kanban in software engineering and I though it might be fun to get some LEGO... Continue →