12 Dec 2014

The tall, dark, handsome man stood atop Bernal Heights and looked out over San Francisco, the wind gently tousling his perfect bedhead of hair. The man had loads of friends, but tonight he needed solitude. It wasn’t that he didn’t have options for other things to do that evening, he had turned down like five different invitations to five really cool parties. He could have easily gone to a bar and scored with a 6, maybe even a 7 if he could be bothered. But sometimes you need the perspective and quietude that only a nighttime panorama can give.

He looked out over the Mission District. Guerrero Street. Valencia Street. Mission Street. South Van Ness Street. Fulsom Street. Harrison Street. The street after Harrison Street. Traffic lights blinked from red to green to orange to red to green, and people obeyed.

He considered the Valencia Street Green Wave, its traffic lights set so that a cyclist traveling at 13mph would hit green lights from start to finish, shielded from all hardship or challenge. Was such a cyclist really even alive?

He meditated on how interesting it was that it was possible to create Green Waves along both directions of the same street at the same time, and how interesting he was for finding this interesting. He thought that he could probably craft a thrilling blog post out of this. He was right.

My friends, that man was me, and this is that blog post.

As you may have already worked out, it is actually incredibly trivial to create Green Waves along both directions of the same street. But the real, related and very interesting question is:

How can you create Green Waves along every single road of a completely irregularly spaced grid of roads, where each road has a completely different speed limit?

Using some simple maths, let’s find out.

We define a Green Wave to be a set of rules for deciding traffic light colors and initial bike placement such that:

- All bikes are always moving at a fixed speed
- 50% of the road in each direction is covered with bikes
- Each traffic light is green 50% of the time

Before town planners start contacting me with offers of fame and stardom, I should note that we will make several typically mathematical assumptions.

- Roads are 1-D lines
- Bikes and traffic lights are 0-D point particles that can pass straight through each other
- Bikes can stop and start instantaneously, with no acceleration time
- Bikes never turn corners and only travel in straight lines
- And no doubt several others assumptions that I haven’t noticed

We will start simple and work our way up. The real world practicalities of some of our solutions may get a little stupid, but the proofs are elegant as balls, so we elect to not care.

This is the trivial base case upon which all else depends. The lights are spaced a distance `d`

apart, and the Green Wave speed limit is `v.

The solution, which can be shown to be correct by simple inspection, is:

At `t=0`

:

- Consecutive lights start alternately red and green
- Lines of bikes of length
`d`

stretch backwards from each green light to the previous red light

Then every `T = d/v`

, all traffic lights switch colour.

At `t=T`

, the first bike in each line will have just reached the next light, which will be turning green, and the last bike in each line will have just passed their first light, which will be turning red. This works in both directions, and we have our first Green Wave.

At first glance, this case appears much less straightforward. But it is no match for our desire to promote alternative forms of transport.

Notice that, regardless of the arrangement, it will always be possible to add additional imaginary lights until we have a regularly spaced line. These real and imaginary lights will be separated by a distance `d_eff`

, equal to the Highest Common Factor (HCF) of all of the distances between consecutive real lights.

For example, say we have lights at positions `{0, 4, 6, 12}`

, giving us distances between lights of `{4, 2, 6}`

. The HCF of these distances is 2, so we add imaginary lights at `{2, 8, 10}`

, and now have a road of equally spaced lights, separated by a distance `d_eff`

of 2.

We know that this has a Green Wave solution as outlined in case 1. But notice that this new configuration is strictly more constrained than the configuration that we started with. This means that any solution for the new, regular configuration will also give us a solution for the initial, irregular configuration that we are solving for. The solution for the new configuration is, per case 1:

At `t=0`

:

- Lights at 0, 4, 8, 12 set to green, lights at 2, 6, 10 set to red
- Lines of bikes of length 2 stretch backwards from each green light to the previous red light

Then every `T = d_eff/v = 2/v`

, all traffic lights invert color.

To solve for the irregular, real case, we simply set the real lights to be whatever they are required to be in the regular, imaginary case, and throw away the imaginary lights that we added.

In our example, this means:

At `t=0`

:

- Lights at 0, 4, 12 set to green, light at 6 set to red
- Lines of bikes of length 2 arranged as above, even though there are no lights next to some of these lines

and once again all traffic light invert color after every `T = 2/v`

.

We have solved for an arbitrary single road. Now let’s start combining these roads into a good old-fashioned American city grid. We will start with a regular grid, again with a distance `d`

between lights and a universal target speed of `v`

. Instead of referring to a light as “green” or “red”, we will now refer to it as either “vertical” or “horizontal”, depending on which direction it is allowing traffic through.

This basic grid has the solution, again easily verifiable by inspection:

At `t=0`

:

- Lights alternate vertical and horizontal across the grid in a checkerboard pattern
- Lines of bikes of length
`d`

stretch backwards from each green light to the previous red light along the direction of travel

Then every `T = d/v`

, all traffic lights switch direction.

Each individual road is clearly a case 1 Green Wave, and thus the entire grid is also a Green Wave.

As you might guess, the solution and proof is very similar to that for an irregular single road. We can add imaginary roads to create a regularly spaced grid, and since we know that this imaginary grid has a solution (given by case 3) and that our actual configuration is less restrictive than this, this solution also works for it. The imaginary roads should be added at spacing `d_eff`

equal to the HCF of all of the distances between consecutive lights on all roads.

Detailed example left as an exercise for the reader.

Finally, the holy grail. We now take an irregular grid, as in case 4, but remove the restriction of a single universal Green Wave speed. Some streets may want to cater for Lance Armstrong, others for Lance Armstrong not tripping his face off. The solution is surprisingly simple, although unsurprisingly kind of stupid.

Notice that a Green Wave that allows bikes to continuously travel at a constant speed `v`

also allows them to travel at `v/2`

, `v/3`

, `v/4`

and so on. Conceptually these “harmonics” arise because by the time a bike traveling at `v/4`

has travelled from green light to green light, exactly 4 whole inversion cycles have occurred in front of it. It is therefore exactly lined up to take advantage of the 5th cycle, and continue on its steady way.

Therefore, for a __regular__ grid with varying speed limits, we simply need to oscillate a checkerboard pattern (as in case 3) at a frequency that caters for a speed `v_eff`

that has all of the different speed limits on the grid as harmonics. This speed is the Lowest Common Multiple (LCM) of all of the individual Green Wave speeds. Since `v_eff`

is an integer multiple of all individual `v`

, all `v`

must be harmonics of `v_eff`

and therefore able to travel along a Green Wave set for `v_eff`

. The entire grid is therefore covered in Green Waves.

For example, say we have Green Wave speeds of `{10, 20, 50, 80}`

. The LCM, or `v_eff`

of these is `400`

, and so we invert the direction of all lights every `T = d/v_eff = d/400`

. The initial bike arrangement is different to that for a regular grid, since it has to cater for an effective speed of `400`

. The lights will invert every `d/400`

, and so the lengths of each group of bikes on each street should be the maximum length that can pass through a green light in this time, given `v_street`

, the Green Wave speed for that street. This length is `v_street * T = v_street * d/v_eff`

. In the case where all speeds are the same and `v_eff = v_street`

(case 3), this reduces to `d`

, as expected.

We now generalise this solution to an irregular grid, in exactly the same way as in case 4. We add imaginary roads at a spacing of `d_eff`

, where `d_eff`

is the HCF of all of the distances between consecutive lights on all roads. We then calculate `v_eff`

as above - the LCM of all speeds on the grid. This gives us a `T = d_eff/v_eff`

, and bikes arranged in alternating lines of length `v_street*deff/v_eff`

. As always, we use our imaginary checkerboard to assign initial light colours and bike placements, and then oscillate directions accordingly. We sit back and admire our handiwork.

Some sample numbers:

For a grid with Green Wave speeds of `{10, 13, 15, 20, 35}`

mph, the LCM `v_eff = 5640`

And with blocks of length `{30, 22, 20, 15, 14}`

hundredths of a mile, the HCF `d_eff = 1 hundredth of a mile`

So the lights must be oscillated every `T = d_eff/v_eff = 0.01/5640 = 0.0000017 hours`

, or `0.006 seconds`

And taking the 20mph street as an example, bikes must be arranged in lines of length `v_street*d_eff/v_eff = 20*0.01/5640 = 0.000036miles`

, or `5cm`

.

Assuming your city is made up of bikes and people of no more than 5cm in length, has lights capable of switching between green and red a thousand times per second, and has pedestrians capable of navigating this terrifying combination, you may want me to design your traffic system. My rates are unreasonably expensive, especially given the appalling results, and my Twitter handle can be found below.

*Thanks to Sidd and Kiran for their help with this puzzle.*