{"id":245,"date":"2013-06-10T06:53:20","date_gmt":"2013-06-10T06:53:20","guid":{"rendered":"http:\/\/cto.dyalog.com\/?p=245"},"modified":"2014-07-10T09:30:14","modified_gmt":"2014-07-10T09:30:14","slug":"elementary-cellular-light-emitting-automaton","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2013\/06\/elementary-cellular-light-emitting-automaton\/","title":{"rendered":"Elementary Cellular Light-Emitting Automaton"},"content":{"rendered":"<p>In response to an <a title=\"Fun with APL on the Raspberry Pi (without a Robot)\" href=\"http:\/\/www.dyalog.com\/blog\/2013\/05\/fun-with-apl-on-the-raspberry-pi-without-a-robot\/\" target=\"_blank\">earlier post<\/a>\u00a0on driving an 8-bar LED using the Raspberry Pi,\u00a0<a title=\"Roger Hui on Wikipedia\" href=\"http:\/\/en.wikipedia.org\/wiki\/Roger_Hui\" target=\"_blank\">Roger Hui<\/a> commented that 8 lights should be\u00a0sufficient to display the output of a <a title=\"Elementary Cellular Automaton (Wikipedia)\" href=\"http:\/\/en.wikipedia.org\/wiki\/Elementary_cellular_automaton\" target=\"_blank\">1-d Game of Life<\/a>. The code snippets displayed in this post are based on some working code that Roger was also kind enough to forward to me.<\/p>\n<p>The following two functions provide the basic building blocks for the computation of the next generation of a 1-d cellular automaton:<\/p>\n<pre><code class=\"language-apl\">bits\u2190{(8\u23742)\u22a4\u2375} \u00a0 \u00a0 \u00a0 \u00a0   \u235d Encode a number as 8 binary bits\r\nneighbors\u2190{\u2191\u00af1 0 1\u2218.\u233d\u2282\u2375} \u235d Map vector =&gt; 3-row matrix with neighbors<\/code><\/pre>\n<p>These allow us to perform the following transformations:<\/p>\n<pre><code class=\"language-apl\">      bits 5\r\n0 0 0 0 0 1 0 1\r\n      bits 110\r\n0 1 1 0 1 1 1 0\r\n      neighbors b\u21900 1 0 0 1 1 1 1\r\n1 0 1 0 0 1 1 1\r\n0 1 0 0 1 1 1 1\r\n1 0 0 1 1 1 1 0\r\n      2\u22a5neighbors b \u235d base-2 decode of each column\r\n5 2 4 1 3 7 7 6<\/code><\/pre>\n<p>With these, it is now easy to define a function to compute the next generation of a pattern for a given <a title=\"Elementary Cellular Automaton (Wikipedia)\" href=\"http:\/\/en.wikipedia.org\/wiki\/Elementary_cellular_automaton\" target=\"_blank\">Wolfram Code <\/a>(and test it with a couple of arguments):<\/p>\n<pre><code class=\"language-apl\">\u00a0 \u00a0 \u00a0 wc\u2190{(bits \u237a)[8-2\u22a5neighbors \u2375]}\r\n      110 wc b\r\n1 1 0 1 1 0 0 1\r\n      110 wc 110 wc b \u235d 3rd generation\r\n0 1 1 1 1 0 1 1<\/code><\/pre>\n<p>We subtract the result of the base-2 decode from 8, because the least significant bit (bit 0) is the 8th element of the vector returned by the bits function. Next, we define an operator which returns a matrix containing a number of generations:<\/p>\n<pre><code class=\"language-apl\">    \u2207 r\u2190gens(rule wcgm)pattern;i\r\n[1] \u235d Wolfram Code Generations\r\n[2]\r\n[3] r\u2190(gens,\u2374pattern)\u2374pattern\r\n[4] :For i :In 1\u2193\u2373gens\r\n[5]    r[i;]\u2190rule wc r[i-1;]\r\n[6] :EndFor\r\n    \u2207\r\n\r\n    5 (110 wcg) b \u235d 5 generations of code 110\r\n0 1 0 0 1 1 1 1\r\n1 1 0 1 1 0 0 1\r\n0 1 1 1 1 0 1 1\r\n1 1 0 0 1 1 1 1\r\n0 1 0 1 1 0 0 0<\/code><\/pre>\n<p>Finally, we can add 1 to the boolean matrix and use it to index into a 2-element character vector, to get better &#8220;visualization&#8221; of the result (10 generations of Wolfram code 20):<\/p>\n<pre><code class=\"language-apl\">      '-*'[1+10 (20 wcgm) b]\r\n-*--****\r\n-**-----\r\n---*----\r\n---**---\r\n-----*--\r\n-----**-\r\n-------*\r\n*------*\r\n-*------\r\n-**-----<\/code><\/pre>\n<p>The function also works with longer inputs &#8211; in the example below a random input of length 60 (20 generations of Wolfram code 18, this time using just blank and asterisk for the display):<\/p>\n<pre><code class=\"language-apl\">     ' *'[1+20 (18 wcgm) 1=?60\u23742]\r\n*****    * ***** *** ** *  * ***    *  *** *  ***  ** ***** \r\n     *  *                **     *  * **     **   **         \r\n    * ** *              *  *   * **    *   *  * *  *        \r\n   *      *            * ** * *    *  * * * **   ** *       \r\n  * *    * *          *        *  * **        * *    *      \r\n *   *  *   *        * *      * **    *      *   *  * *     \r\n* * * ** * * *      *   *    *    *  * *    * * * **   *    \r\n              *    * * * *  * *  * **   *  *        * * *  *\r\n*            * *  *       **   **    * * ** *      *     ** \r\n *          *   ** *     *  * *  *  *        *    * *   *   \r\n* *        * * *    *   * **   ** ** *      * *  *   * * *  \r\n   *      *     *  * * *    * *       *    *   ** * *     **\r\n* * *    * *   * **     *  *   *     * *  * * *      *   *  \r\n     *  *   * *    *   * ** * * *   *   **     *    * * * **\r\n*   * ** * *   *  * * *          * * * *  *   * *  *        \r\n * *        * * **     *        *       ** * *   ** *      *\r\n    *      *      *   * *      * *     *      * *    *    * \r\n   * *    * *    * * *   *    *   *   * *    *   *  * *  * *\r\n* *   *  *   *  *     * * *  * * * * *   *  * * * **   **   \r\n   * * ** * * ** *   *     **         * * **        * *  * *<\/code><\/pre>\n<p>&nbsp;<\/p>\n<p>Finally, we can light the lights using the BarLED class from our <a title=\"BarLED Examples (GitHub)\" href=\"https:\/\/github.com\/APLPi\/libi2c-com\/tree\/master\/examples\" target=\"_blank\">GitHUB repository<\/a> &#8211; and the Quick2Wire interface board and LED Bar &#8211; see the <a title=\"Fun with APL on the Raspberry Pi (without a Robot)\" href=\"http:\/\/www.dyalog.com\/blog\/2013\/05\/fun-with-apl-on-the-raspberry-pi-without-a-robot\/\" target=\"_blank\">original post<\/a> for an explanation. The video below shows the output resulting from the following APL expressions<\/p>\n<pre><code class=\"language-apl\">      ]load \/home\/pi\/BarLED\r\n      bl\u2190\u2395NEW BarLED \u236c\r\n      0.2 bl.Play \u219350(20 wcg) 0 1 0 0 1 1 1 1\r\n      0.2 bl.Play \u219350(18 wcg) 0 1 0 0 1 1 1 1<\/code><\/pre>\n<iframe loading=\"lazy\"  id=\"_ytid_24021\"  width=\"584\" height=\"329\"  data-origwidth=\"584\" data-origheight=\"329\"  src=\"https:\/\/www.youtube.com\/embed\/psd1rv-hRrM?enablejsapi=1&autoplay=0&cc_load_policy=0&iv_load_policy=1&loop=0&modestbranding=0&rel=1&fs=1&playsinline=0&autohide=2&theme=dark&color=red&controls=1&\" class=\"__youtube_prefs__  no-lazyload\" title=\"YouTube player\"  allow=\"autoplay; encrypted-media\" allowfullscreen data-no-lazy=\"1\" data-skipgform_ajax_framebjll=\"\"><\/iframe>\n<p>Many thanks to Roger for the inspiration to take this one step further (and the code)! For a 2-dimensional implementation of Conway&#8217;s classic Game of Life, see the video by John Scholes at\u00a0<a title=\"Game of Life in APL (TouTube)\" href=\"http:\/\/www.youtube.com\/watch?v=a9xAKttWgP4\" target=\"_blank\">http:\/\/www.youtube.com\/watch?v=a9xAKttWgP4<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In response to an earlier post\u00a0on driving an 8-bar LED using the Raspberry Pi,\u00a0Roger Hui commented that 8 lights should be\u00a0sufficient to display the output of a 1-d Game of Life. The code snippets displayed in this post are based &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2013\/06\/elementary-cellular-light-emitting-automaton\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,12,9],"tags":[],"class_list":["post-245","post","type-post","status-publish","format-standard","hentry","category-apl-language","category-cto","category-raspberry-pi"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/245","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=245"}],"version-history":[{"count":25,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/245\/revisions"}],"predecessor-version":[{"id":460,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/245\/revisions\/460"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=245"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=245"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=245"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}