Added elementary cellular automata

author: pommicket <leonardomtenenbaum@gmail.com> 2016-07-30 20:39:47 -0400
committer: pommicket <leonardomtenenbaum@gmail.com> 2016-07-30 20:39:47 -0400
commit: 654cb632440886a3d9dda64733cd704cee9afa7a (patch)
tree: 802f30bcbb78cb56e82945162f9d4e7f88196dd2
parent: a5ce3a61c22e6730bc2d161a4a512e9d1e7d51be (diff)
5 files changed, 226 insertions, 1 deletions
diff --git a/all.html b/all.html
index e80f7f3..d463252 100644
--- a/all.html
+++ b/all.html
@@ -101,6 +101,13 @@ maze.
 </p>
 <hr>
 
+<img src="screenshots/ElementaryCellularAutomata.png" width=400 height=400><br>
+<a href="elementarycellularautomata.html">Elementary cellular automata</a><br>
+<p>
+Run <a href="https://en.wikipedia.org/wiki/Elementary_cellular_automaton">elementary cellular automata</a>.
+</p>
+<hr>
+
 <img src="screenshots/h.png" width=200 height=200><br>
 <a href="h.html">H</a><br>
 <p>
diff --git a/elementarycellularautomata.html b/elementarycellularautomata.html
new file mode 100644
index 0000000..92c3970
--- /dev/null
+++ b/elementarycellularautomata.html
@@ -0,0 +1,52 @@
+<html>
+<head>
+<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css">
+<link rel="stylesheet" href="css/style.css">
+
+<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.4/jquery.min.js"></script>
+<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.5.2/p5.js"></script>
+
+<title>Elementary Cellular Automata</title>
+
+<style>
+#start
+{
+    font-family: monospace;
+}
+
+#error
+{
+    color: red;
+}
+
+</style>
+
+</head>
+
+<body>
+<h2>Elementary Cellular Automata</h2>
+<div id="header_links_div"></div>
+<script src="js/header_links.js"></script>
+
+<hr>
+
+<div id="explanation">
+This is a program which runs <a href="https://en.wikipedia.org/wiki/Elementary_cellular_automaton">elementary cellular automata</a>
+like <a href="https://en.wikipedia.org/wiki/Rule_110">Rule 110</a>. Each cell is determined by the 3 cells above it, using
+rules specified by the rule number.
+</div>
+
+Number of iterations: <input type="number" id="time" min="0" value="500"></input><br>
+Size (if the length of the starting configuration is less than the size, zeros will be added to both sides):
+<input type="number" id="size" value="500"><br>
+Starting configuration: <input type="text" id="start" value="101" size="50"></input><br>
+Rule number: <input type="number" id="rule" min="0" max="255" value="110"></input><br>
+<button id="run">Run</button>
+
+<div id="error"></div><br>
+<canvas id="canvas" width="1000" height="500"></canvas>
+
+<script src="js/elementarycellularautomata.js"></script>
+
+</body>
+</html>
diff --git a/js/elementarycellularautomata.js b/js/elementarycellularautomata.js
new file mode 100644
index 0000000..06e0df5
--- /dev/null
+++ b/js/elementarycellularautomata.js
@@ -0,0 +1,159 @@
+function repeatString(string, nTimes)
+{
+    /*
+    Repeats a string n times
+    E.g. repeatString("hi", 10) -> "hihihihihihihihihihi"
+    */
+    return Array(nTimes+1).join(string);
+}
+
+function bin8(x)
+{
+    /*
+    Returns an 8-digit binary representation of x, adding zeros to the start if necessary.
+    E.g. bin8(42) -> "00101010"
+    */
+    var s;
+    for (s = x.toString(2) /* Convert to binary */; s.length < 8; s = "0" + s /* Add zero to start */);
+    return s;
+}
+
+function check(b, msg)
+{
+    /*
+    If b is false, it shows the error message to the user.
+    Returns b.
+    */
+    if (!b)
+    {
+        $("#error").html(msg);
+    }
+    return b;
+}
+
+
+function startingConfigValid(sc)
+{
+    /*
+    Returns true if sc is a valid starting configuration; if all of the characters in sc are 0 or 1.
+    */
+
+    for (var i = 0; i < sc.length; i++)
+    {
+        if (sc[i] != '0' && sc[i] != '1')
+            return false;
+    }
+    return true;
+}
+
+function padConfiguration(config, size)
+{
+    /* Place zeros before and after config so that config.length = size. */
+    for (; config.length < size-1; config = '0' + config + '0');
+    if (config.length < size)
+        config += '0'; /* Add zero at end if the number of zeros must be odd (e.g. padConfiguration("1101", 9) -> 001101000) */
+    return config;
+}
+
+
+function drawState(state, t)
+{
+    /* Draws the states */
+
+
+    var w = $("#canvas").width();
+    var h = $("#canvas").height();
+
+    for (var i = 0; i < w; i++)
+    {
+        if (state[i] === '1')
+            ctx.fillRect(i*2, t*2, 2, 2);
+    }
+}
+
+function getNewValue(rule, a, b, c)
+{
+    /* Get new value of a cell given the three cells above it. */
+    var above = a+b+c;
+    var binUpTo7 = ["111", "110", "101", "100", "011", "010", "001", "000"];
+    return rule[binUpTo7.indexOf(above)];
+}
+
+
+$(document).ready(function() {
+    $("#run").click(function()
+    {
+        $("#error").html("");
+        /* An elementary cellular automaton (e.g. Rule 110 (https://en.wikipedia.org/wiki/Rule_110)) */
+        var time = parseInt($("#time").val()); /* Amount of time to run the automaton for. */
+        var size = parseInt($("#size").val()); /* Size of the starting automaton (bits). */
+        var startingConfig = $("#start").val(); /* Starting configuration for the automaton. */
+        var ruleNumber = parseInt($("#rule").val()); /* Rule number (e.g. 110). (0 <= x < 256) This must be converted to a binary number before use. */
+
+        if (!check(time > 0, "Error - The value " + time + " is an invalid time. Time &gt; 0."))
+        {
+            /* Check for invalid time argument. */
+            return;
+        }
+
+        if (!check(ruleNumber >= 0 && ruleNumber < 256, "Error - Rule number " + ruleNumber +  " does not exist. 0 &le; Rule number &le; 255"))
+        {
+            /* Check for an out-of-bounds rule number. */
+            return;
+        }
+        if (!check(startingConfigValid(startingConfig), "Error - Starting configuration invalid: " + startingConfig))
+        {
+            /* Check for an invalid starting configuration. e.g. 024930283848 */
+            return;
+        }
+
+        if (!check(startingConfig.length <= size, "Error - Starting configuration length is greater than size!"))
+        {
+            return;
+        }
+
+        if (!check(size > 0, "Error - Invalid size: " + size + ". Size > 0"))
+        {
+            /* Check for invalid size argument. */
+            return;
+        }
+
+        var rule = bin8(ruleNumber);
+
+        document.getElementById("canvas").width = size*2;
+        document.getElementById("canvas").height = time*2;
+
+
+        ctx = document.getElementById("canvas").getContext("2d");
+
+        ctx.fillStyle = "#ffffff"
+        ctx.fillRect(0, 0, size, time);
+        ctx.fillStyle = "#000000"
+
+        startingConfig = padConfiguration(startingConfig, size);
+        /* Run the automaton. */
+
+        drawState(startingConfig, 0);
+
+        var lastState = startingConfig;
+
+        for (var t = 1; t < time; t++)
+        {
+            var nextState = [getNewValue(rule, "0", lastState[0], lastState[1])];
+
+            for (var i = 1; i < size-1; i++)
+            {
+                nextState.push(getNewValue(rule, lastState[i-1], lastState[i], lastState[i+1]));
+            }
+            nextState.push(getNewValue(rule, lastState[size-2], lastState[size-1], "0"));
+            drawState(nextState, t);
+            lastState = nextState;
+        }
+
+
+
+
+    });
+
+
+});
diff --git a/mathematical.html b/mathematical.html
index ca09c44..9482b49 100644
--- a/mathematical.html
+++ b/mathematical.html
@@ -56,6 +56,13 @@ Ant. You can find out more about it <a href="https://en.wikipedia.org/wiki/Langt
 </p>
 <hr>
 
+<img src="screenshots/ElementaryCellularAutomata.png" width=400 height=400><br>
+<a href="elementarycellularautomata.html">Elementary cellular automata</a><br>
+<p>
+Run <a href="https://en.wikipedia.org/wiki/Elementary_cellular_automaton">elementary cellular automata</a>.
+</p>
+<hr>
+
 <img src="screenshots/mazesolver.png" width=200 height=200><br>
 <a href="mazesolver.html">Maze Solver</a><br>
 <p>
@@ -117,4 +124,4 @@ approximates π!<br>
 </p>
 
 
-</body>
-\ No newline at end of file
+</body>
diff --git a/screenshots/ElementaryCellularAutomata.png b/screenshots/ElementaryCellularAutomata.png
new file mode 100644
index 0000000..61ca17b
--- /dev/null
+++ b/screenshots/ElementaryCellularAutomata.png
author	pommicket <leonardomtenenbaum@gmail.com>	2016-07-30 20:39:47 -0400
committer	pommicket <leonardomtenenbaum@gmail.com>	2016-07-30 20:39:47 -0400
commit	654cb632440886a3d9dda64733cd704cee9afa7a (patch)
tree	802f30bcbb78cb56e82945162f9d4e7f88196dd2
parent	a5ce3a61c22e6730bc2d161a4a512e9d1e7d51be (diff)