{"id":308,"date":"2012-09-10T12:20:54","date_gmt":"2012-09-10T17:20:54","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=308"},"modified":"2016-11-21T09:31:17","modified_gmt":"2016-11-21T14:31:17","slug":"game-of-life-part-2-sparse-matrices","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2012\/09\/10\/game-of-life-part-2-sparse-matrices\/","title":{"rendered":"Game of Life, Part 2, Sparse Matrices"},"content":{"rendered":"<!DOCTYPE html\r\n  PUBLIC \"-\/\/W3C\/\/DTD HTML 4.01 Transitional\/\/EN\">\r\n<style type=\"text\/css\">\r\n\r\nh1 { font-size:18pt; }\r\nh2.titlebg { font-size:13pt; }\r\nh3 { color:#4A4F55; padding:0px; margin:5px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:11pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }\r\nh4 { color:#4A4F55; padding:0px; margin:0px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:10pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }\r\n   \r\np { padding:0px; margin:0px 0px 20px; }\r\nimg { padding:0px; margin:0px 0px 20px; border:none; }\r\np img, pre img, tt img, li img { margin-bottom:0px; } \r\n\r\nul { padding:0px; margin:0px 0px 20px 23px; list-style:square; }\r\nul li { padding:0px; margin:0px 0px 7px 0px; background:none; }\r\nul li ul { padding:5px 0px 0px; margin:0px 0px 7px 23px; }\r\nul li ol li { list-style:decimal; }\r\nol { padding:0px; margin:0px 0px 20px 0px; list-style:decimal; }\r\nol li { padding:0px; margin:0px 0px 7px 23px; list-style-type:decimal; }\r\nol li ol { padding:5px 0px 0px; margin:0px 0px 7px 0px; }\r\nol li ol li { list-style-type:lower-alpha; }\r\nol li ul { padding-top:7px; }\r\nol li ul li { list-style:square; }\r\n\r\npre, tt, code { font-size:12px; }\r\npre { margin:0px 0px 20px; }\r\npre.error { color:red; }\r\npre.codeinput { padding:10px; border:1px solid #d3d3d3; background:#f7f7f7; }\r\npre.codeoutput { padding:10px 11px; margin:0px 0px 20px; color:#4c4c4c; }\r\n\r\n@media print { pre.codeinput, pre.codeoutput { word-wrap:break-word; width:100%; } }\r\n\r\nspan.keyword { color:#0000FF }\r\nspan.comment { color:#228B22 }\r\nspan.string { color:#A020F0 }\r\nspan.untermstring { color:#B20000 }\r\nspan.syscmd { color:#B28C00 }\r\n\r\n.footer { width:auto; padding:10px 0px; margin:25px 0px 0px; border-top:1px dotted #878787; font-size:0.8em; line-height:140%; font-style:italic; color:#878787; text-align:left; float:none; }\r\n.footer p { margin:0px; }\r\n\r\n  <\/style><div class=\"content\"><!--introduction--><p>The Game of Life, including the infinitely expanding universe, is a gorgeous application of MATLAB sparse matrices.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#cd09dc89-0cd9-4589-a307-4551f5b963e9\">The Code<\/a><\/li><li><a href=\"#84871d15-1235-407f-bec4-add08b52343b\">The Glider<\/a><\/li><li><a href=\"#1066af51-c33a-4bd7-bb5d-b3011b6cc8e4\">Life Lexicon<\/a><\/li><li><a href=\"#2e80a835-0efc-4b40-bb9f-ce5f73526c50\">Achim p144<\/a><\/li><\/ul><\/div><h4>The Code<a name=\"cd09dc89-0cd9-4589-a307-4551f5b963e9\"><\/a><\/h4><p>The universe in the Game of Life is represented by a sparse matrix <tt>X<\/tt> that is mostly all zero. The only nonzero elements are ones for the live cells.  Let's begin by describing the code that implements Conway's Rule:<\/p><div><ul><li>A live cell with two live neighbors, or any cell with three   live neighbors, is alive at the next step.<\/li><\/ul><\/div><p>At any particular step in the evolution, <tt>X<\/tt> represents only a finite portion of the universe.  If any cells get near the edge of this portion, we reallocate storage to accommodate the expanding population. This only involves adding more column pointers so it does not represent a significant amount of additional memory.<\/p><p>A basic operation is counting live neighbors.  This involves an index vector <tt>p<\/tt> that avoids the edge elements.<\/p><pre class=\"codeinput\"><span class=\"comment\">%    m = size(X,1);<\/span>\r\n<span class=\"comment\">%    p = 2:m-1;<\/span>\r\n<\/pre><p>Here is the code that creates a sparse matrix <tt>N<\/tt> with elements between <tt>0<\/tt> and <tt>8<\/tt> giving the count of live neighbors.<\/p><pre class=\"codeinput\"><span class=\"comment\">%    N = sparse(m,m);<\/span>\r\n<span class=\"comment\">%    N(p,p) = X(p-1,p-1) + X(p,p-1) + X(p+1,p-1) + X(p-1,p) + ...<\/span>\r\n<span class=\"comment\">%       X(p-1,p+1) + X(p,p+1) + X(p+1,p+1) + X(p+1,p);<\/span>\r\n<\/pre><p>This is one of my all-time favorite MATLAB statements. With MATLAB matrix logical operations on sparse matrices, this is Conways Rule:<\/p><pre class=\"codeinput\"><span class=\"comment\">%    X = (X &amp; (N == 2)) | (N == 3);<\/span>\r\n<\/pre><h4>The Glider<a name=\"84871d15-1235-407f-bec4-add08b52343b\"><\/a><\/h4><p>Let's see how this works with the glider.<\/p><pre class=\"codeinput\">   X = sparse(7,7);\r\n   X(3:5,3:5) = [0 1 0; 0 0 1; 1 1 1];\r\n   disp(<span class=\"string\">'X'<\/span>)\r\n   t = int2str(X); t(t==<span class=\"string\">'0'<\/span>) = <span class=\"string\">'.'<\/span>; disp(t)\r\n<\/pre><pre class=\"codeoutput\">X\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n.  .  .  1  .  .  .\r\n.  .  .  .  1  .  .\r\n.  .  1  1  1  .  .\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n<\/pre><p>Count how many of the eight neighbors are alive. We get a cloud of values around the glider providing a census of neighbors.<\/p><pre class=\"codeinput\">   m = size(X,1);\r\n   p = 2:m-1;\r\n   N = sparse(m,m);\r\n   N(p,p) = X(p-1,p-1) + X(p,p-1) + X(p+1,p-1) + X(p-1,p) + <span class=\"keyword\">...<\/span>\r\n       X(p-1,p+1) + X(p,p+1) + X(p+1,p+1) + X(p+1,p);\r\n   disp(<span class=\"string\">'N'<\/span>)\r\n   t = int2str(N); t(t==<span class=\"string\">'0'<\/span>) = <span class=\"string\">'.'<\/span>; disp(t)\r\n<\/pre><pre class=\"codeoutput\">N\r\n.  .  .  .  .  .  .\r\n.  .  1  1  1  .  .\r\n.  .  1  1  2  1  .\r\n.  1  3  5  3  2  .\r\n.  1  1  3  2  2  .\r\n.  1  2  3  2  1  .\r\n.  .  .  .  .  .  .\r\n<\/pre><p>Only the nose of the glider is alive and has two live neighbors.<\/p><pre class=\"codeinput\">   disp(<span class=\"string\">'X &amp; (N == 2)'<\/span>)\r\n   t = int2str(X &amp; (N == 2)); t(t==<span class=\"string\">'0'<\/span>) = <span class=\"string\">'.'<\/span>; disp(t)\r\n<\/pre><pre class=\"codeoutput\">X &amp; (N == 2)\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n.  .  .  .  1  .  .\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n<\/pre><p>Four other cells have three live neighbors<\/p><pre class=\"codeinput\">   disp(<span class=\"string\">'N == 3'<\/span>)\r\n   t = int2str(N == 3); t(t==<span class=\"string\">'0'<\/span>) = <span class=\"string\">'.'<\/span>; disp(t)\r\n<\/pre><pre class=\"codeoutput\">N == 3\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n.  .  1  .  1  .  .\r\n.  .  .  1  .  .  .\r\n.  .  .  1  .  .  .\r\n.  .  .  .  .  .  .\r\n<\/pre><p>\"OR-ing\" these last two matrices together with \"|\" gives the next orientation of the glider.<\/p><pre class=\"codeinput\">   disp(<span class=\"string\">'(X &amp; (N == 2)) | (N == 3)'<\/span>)\r\n   t = int2str((X &amp; (N == 2)) | (N == 3)); t(t==<span class=\"string\">'0'<\/span>) = <span class=\"string\">'.'<\/span>; disp(t)\r\n<\/pre><pre class=\"codeoutput\">(X &amp; (N == 2)) | (N == 3)\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n.  .  .  .  .  .  .\r\n.  .  1  .  1  .  .\r\n.  .  .  1  1  .  .\r\n.  .  .  1  .  .  .\r\n.  .  .  .  .  .  .\r\n<\/pre><p>Repeating this three more times moves the glider down and to the right one step.<\/p><h4>Life Lexicon<a name=\"1066af51-c33a-4bd7-bb5d-b3011b6cc8e4\"><\/a><\/h4><p>Life Lexicon is a cultural treasure. It should be listed as a UNESCO World Heritage Site. The primary site is maintained by Stephen A. Silver. He has help from lots of other folks. I gave these two links in part one of the blog last week. Just go poke around.  It's great fun.<\/p><p>Text version: &lt;ht&#8203;tp:\/\/www.argentum.freeserve.co.uk\/lex_home.htm&gt;<\/p><p>Graphic version: <a href=\"http:\/\/www.bitstorm.org\/gameoflife\/lexicon\/\">&lt;http:\/\/www.bitstorm.org\/gameoflife\/lexicon<\/a>&gt;<\/p><p>The lexicon has 866 entries.  About half of them are of historical and computational complexity interest.  Read them to learn the history of the Game of Life.  For example, the starting population known as the \"ark\" takes 736692 steps to stabilize.  Half of them, 447, are matrices that we can use as starting populations.<\/p><h4>Achim p144<a name=\"2e80a835-0efc-4b40-bb9f-ce5f73526c50\"><\/a><\/h4><p><a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/37959-game-of-life\"><tt>life_lex<\/tt><\/a> reads the text version of the lexicon and caches a local copy if one doesn't already exist. It then uses random entries as starting configurations. As just one example, we learn from the lexicon that the following population was found by Achim Flammenkamp, Dean Hickerson, and David Bell in 1994 and that its period is 144.  We're showing every fourth step.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/cleve\/achim_movie.gif\" alt=\"\"> <\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_7e72493b21ef41b4990f941b93c80943() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='7e72493b21ef41b4990f941b93c80943 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 7e72493b21ef41b4990f941b93c80943';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2012 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_7e72493b21ef41b4990f941b93c80943()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.14<br><\/p><p class=\"footer\"><br>\r\n      Published with MATLAB&reg; 7.14<br><\/p><\/div><!--\r\n7e72493b21ef41b4990f941b93c80943 ##### SOURCE BEGIN #####\r\n%% Game of Life, Part 2, Sparse Matrices\r\n% The Game of Life, including the infinitely expanding universe,\r\n% is a gorgeous application of MATLAB sparse matrices.\r\n\r\n%% The Code\r\n% The universe in the Game of Life is represented by a sparse matrix |X|\r\n% that is mostly all zero. The only nonzero elements are ones for the live\r\n% cells.  Let's begin by describing the code that implements Conway's Rule:\r\n% \r\n% * A live cell with two live neighbors, or any cell with three\r\n%   live neighbors, is alive at the next step.\r\n% \r\n\r\n%%\r\n% At any particular step in the evolution, |X| represents only a finite\r\n% portion of the universe.  If any cells get near the edge of this portion,\r\n% we reallocate storage to accommodate the expanding population.\r\n% This only involves adding more column pointers so it does not represent\r\n% a significant amount of additional memory.\r\n\r\n%%\r\n% A basic operation is counting live neighbors.  This involves an index\r\n% vector |p| that avoids the edge elements.\r\n\r\n%    m = size(X,1);\r\n%    p = 2:m-1;\r\n\r\n%%\r\n% Here is the code that creates a sparse matrix |N| with elements between\r\n% |0| and |8| giving the count of live neighbors.\r\n\r\n%    N = sparse(m,m);\r\n%    N(p,p) = X(p-1,p-1) + X(p,p-1) + X(p+1,p-1) + X(p-1,p) + ...\r\n%       X(p-1,p+1) + X(p,p+1) + X(p+1,p+1) + X(p+1,p);\r\n\r\n%%\r\n% This is one of my all-time favorite MATLAB statements.\r\n% With MATLAB matrix logical operations on sparse matrices,\r\n% this is Conways Rule:\r\n\r\n%    X = (X & (N == 2)) | (N == 3);\r\n\r\n%% The Glider\r\n% Let's see how this works with the glider.\r\n   X = sparse(7,7);\r\n   X(3:5,3:5) = [0 1 0; 0 0 1; 1 1 1];\r\n   disp('X')\r\n   t = int2str(X); t(t=='0') = '.'; disp(t)\r\n\r\n%%\r\n% Count how many of the eight neighbors are alive.\r\n% We get a cloud of values around the glider providing a census of neighbors.\r\n   m = size(X,1);\r\n   p = 2:m-1;\r\n   N = sparse(m,m);\r\n   N(p,p) = X(p-1,p-1) + X(p,p-1) + X(p+1,p-1) + X(p-1,p) + ...\r\n       X(p-1,p+1) + X(p,p+1) + X(p+1,p+1) + X(p+1,p);\r\n   disp('N')\r\n   t = int2str(N); t(t=='0') = '.'; disp(t)\r\n\r\n%%\r\n% Only the nose of the glider is alive and has two live neighbors.\r\n   disp('X & (N == 2)')\r\n   t = int2str(X & (N == 2)); t(t=='0') = '.'; disp(t)\r\n\r\n%%\r\n% Four other cells have three live neighbors\r\n   disp('N == 3')\r\n   t = int2str(N == 3); t(t=='0') = '.'; disp(t)\r\n\r\n%%\r\n% \"OR-ing\" these last two matrices together with \"|\" gives the next\r\n% orientation of the glider.\r\n   disp('(X & (N == 2)) | (N == 3)')\r\n   t = int2str((X & (N == 2)) | (N == 3)); t(t=='0') = '.'; disp(t)\r\n\r\n%%\r\n% Repeating this three more times moves the glider down and to the right\r\n% one step.\r\n\r\n%% Life Lexicon\r\n% Life Lexicon is a cultural treasure.\r\n% It should be listed as a UNESCO World Heritage Site. \r\n% The primary site is maintained by Stephen A. Silver.\r\n% He has help from lots of other folks.\r\n% I gave these two links in part one of the blog last week.\r\n% Just go poke around.  It's great fun.\r\n\r\n%%\r\n% Text version: <http:\/\/www.argentum.freeserve.co.uk\/lex_home.htm \r\n% http:\/\/www.argentum.freeserve.co.uk\/lex_home.htm>\r\n\r\n%%\r\n% Graphic version: <http:\/\/www.bitstorm.org\/gameoflife\/lexicon\/\r\n% http:\/\/www.bitstorm.org\/gameoflife\/lexicon>\r\n\r\n%%\r\n% The lexicon has 866 entries.  About half of them are of historical\r\n% and computational complexity interest.  Read them to learn the history\r\n% of the Game of Life.  For example, the starting population known as\r\n% the \"ark\" takes 736692 steps to stabilize.  Half of them, 447, are\r\n% matrices that we can use as starting populations.\r\n\r\n%% Achim p144\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/37959-game-of-life\r\n% |life_lex|> reads the text version of the lexicon and caches a local\r\n% copy if one doesn't already exist.\r\n% It then uses random entries as starting configurations.\r\n% As just one example, we learn from the lexicon that the following population\r\n% was found by Achim Flammenkamp, Dean Hickerson, and David Bell in 1994\r\n% and that its period is 144.  We're showing every fourth step.\r\n%\r\n% <<achim_movie.gif>>\r\n%\r\n\r\n\r\n##### SOURCE END ##### 7e72493b21ef41b4990f941b93c80943\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction--><p>The Game of Life, including the infinitely expanding universe, is a gorgeous application of MATLAB sparse matrices.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2012\/09\/10\/game-of-life-part-2-sparse-matrices\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[6],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/308"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=308"}],"version-history":[{"count":8,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/308\/revisions"}],"predecessor-version":[{"id":2107,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/308\/revisions\/2107"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=308"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=308"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}