Problem 2700. Simulate one complete step in the Biham–Middleton–Levine traffic model

Ned Gulley

38 solvers

7 likes

Solve

Solve Later

The Biham–Middleton–Levine traffic model is a simple cellular automata model loosely mimicking traffic flow. In an m-by-n domain, we see white empty space (or 0 in our matrix representation), red cars (1 in the matrix), and blue cars (2 in the matrix).
Assume the space is toroidal. That is to say, the right side connects with the left, and the top connects to the bottom. So a red car that moves off the far right of the matrix re-appears on the far left.
Here is a 4-by-4 version with three red cars and two blue cars.
     0     0     0     2
     1     1     0     0
     0     0     2     0
     0     0     0     1
Red cars always move to the right if they are unblocked. A red car can move either into an empty space or a space being vacated by a moving red car.
After we move the red cars (1s) we will have this matrix.
     0     0     0     2
     0     1     1     0
     0     0     2     0
     1     0     0     0
We're only halfway through the process. After we move the blue cars (2s) we end up here.
     0     0     0     0
     0     1     1     2
     0     0     0     0
     1     0     2     0
This last value of the matrix would be the return value of your function. Assume that red cars always move before blue cars.
For some visualizations of Biham–Middleton–Levine traffic, see this very nice simulation site.