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

Created by Ned Gulley

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Biham%E2%80%93Middleton%E2%80%93Levine_traffic_model\"><w:r><w:t>Biham–Middleton–Levine traffic model</w:t></w:r></w:hyperlink><w:r><w:t> 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).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Here is a 4-by-4 version with three red cars and two blue cars.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 0 0 2\n 1 1 0 0\n 0 0 2 0\n 0 0 0 1]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>After we move the red cars (1s) we will have this matrix.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 0 0 2\n 0 1 1 0\n 0 0 2 0\n 1 0 0 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>We're only halfway through the process. After we move the blue cars (2s) we end up here.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 0 0 0\n 0 1 1 2\n 0 0 0 0\n 1 0 2 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This last value of the matrix would be the return value of your function. Assume that red cars always move before blue cars.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For some visualizations of Biham–Middleton–Levine traffic, see this very nice</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.jasondavies.com/bml/#0.61/769/512\"><w:r><w:t>simulation site</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

The <a href = "http://en.wikipedia.org/wiki/Biham%E2%80%93Middleton%E2%80%93Levine_traffic_model">Biham–Middleton–Levine traffic model</a> 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.<pre> 0 0 0 2
 1 1 0 0
 0 0 2 0
 0 0 0 1</pre>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.<pre> 0 0 0 2
 0 1 1 0
 0 0 2 0
 1 0 0 0</pre>We're only halfway through the process. After we move the blue cars (2s) we end up here.<pre> 0 0 0 0
 0 1 1 2
 0 0 0 0
 1 0 2 0</pre>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 <a href = "http://www.jasondavies.com/bml/#0.61/769/512">simulation site</a>.

Solve

Solution Stats

96 Solutions
36 Solvers

Last Solution submitted on Jun 30, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 540224

2 Comments

2 Comments

Jan Orwat on 4 Dec 2014

minor bug there. crashes for vectors and return incorrect answers for some input, for example a_in=[0 1 1 1; 0 0 0 0], a_out=[1 1 0 1; 0 0 0 0] instead of a_correct=[1 0 1 1; 0 0 0 0]. Ned, could you extend the test suite to 'kill' this answer?

Ned Gulley on 4 Dec 2014

Done. Thanks for the comment!

Problem Recent Solvers36

Problem Tags

automata

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

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers36

Suggested Problems

More from this Author49

Problem Tags

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

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers36

Suggested Problems

More from this Author49

Problem Tags

Players