Add simspace

Theres a bug, need Wolfram's book to get into the math of it, I can't
find a good explanation of the actual math anywhere (the wikipedia page
is pretty bad)

9 files changed, 183 insertions, 0 deletions

diff --git a/simspace/.gitignore b/simspace/.gitignore
new file mode 100644
index 0000000..1521c8b
--- /dev/null
+++ b/simspace/.gitignore
@@ -0,0 +1 @@
+dist
diff --git a/simspace/ChangeLog.md b/simspace/ChangeLog.md
new file mode 100644
index 0000000..6692341
--- /dev/null
+++ b/simspace/ChangeLog.md
@@ -0,0 +1,5 @@
+# Revision history for simspace
+
+## 0.1.0.0  -- YYYY-mm-dd
+
+* First version. Released on an unsuspecting world.
diff --git a/simspace/LICENSE b/simspace/LICENSE
new file mode 100644
index 0000000..fccd105
--- /dev/null
+++ b/simspace/LICENSE
@@ -0,0 +1,30 @@
+Copyright (c) 2018, Ben Sima
+
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above
+      copyright notice, this list of conditions and the following
+      disclaimer in the documentation and/or other materials provided
+      with the distribution.
+
+    * Neither the name of Ben Sima nor the names of other
+      contributors may be used to endorse or promote products derived
+      from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/simspace/Main.hs b/simspace/Main.hs
new file mode 100644
index 0000000..07d2705
--- /dev/null
+++ b/simspace/Main.hs
@@ -0,0 +1,46 @@
+module Main where
+
+import System.Environment
+import Control.Monad
+import System.Random (getStdGen, randomRs)
+import Data.List.Split
+
+main :: IO ()
+main = do
+    args <- getArgs
+    case args of
+        [] -> putStrLn "Needs one argument"
+        (n:_) -> run (read n :: Int)
+
+run :: Int -> IO ()
+run n = do
+    g <- getStdGen
+    let init = take n $ randomRs (0,1) g
+    let zeros = take n $ repeat 0
+    let result = takeWhile' (/= zeros) $ chunksOf n $ compute n init
+    forM_ result $ \r -> putStrLn $ show r
+
+takeWhile' :: (a -> Bool) -> [a] -> [a]
+takeWhile' _ [] = []
+takeWhile' p (x:xs) = x : if p x then takeWhile' p xs else []
+
+compute :: Int -> [Int] -> [Int]
+compute n state = state ++ compute n (next n state)
+
+next n state = [left, center, right]
+    where
+        center = translate $ getLast n state
+        right = translate $ getLast (n+1) state
+        left = translate $ getLast (n-1) state
+
+getLast n ls = drop (length ls - n) ls
+
+translate [0,0,0] = 0
+translate [0,0,1] = 1
+translate [0,1,0] = 1
+translate [0,1,1] = 1
+translate [1,0,0] = 0
+translate [1,0,1] = 1
+translate [1,1,0] = 1
+translate [1,1,1] = 0
+translate _ = 1
diff --git a/simspace/README.md b/simspace/README.md
new file mode 100644
index 0000000..d97846e
--- /dev/null
+++ b/simspace/README.md
@@ -0,0 +1,35 @@
+We're going to simulate "Rule 110", which is essentially a way of turning one
+string of bits into another string of bits. (You won't need any background
+knowledge to complete the problem, but if you're curious, check out
+https://en.wikipedia.org/wiki/Rule_110)
+
+The program should take one argument N on the command line, and should then
+display a possibly-infinite sequence of rows of N digits each. A digit may be
+either zero or one.
+
+Create the first row randomly. Then, to construct the digit at position x of row
+y, consider the digits at positions (x-1), x, and (x+1) of row (y-1), and select
+the new digit according to the following table:
+
+| Pattern | New Digit for Center Cell |
+| ------- | ------------------------- | 
+| 111     | 0                         |
+| 110     | 1                         |
+| 101     | 1                         |
+| 100     | 0                         |
+| 011     | 1                         |
+| 010     | 1                         |
+| 001     | 1                         |
+| 000     | 0                         |
+
+Wrap around at the edges, so the pattern for position 1 is obtained by looking
+at positions N, 1, and 2.
+
+Stop after printing a row consisting entirely of zero or ones. Note that
+depending on your random initial row, this might never happen!
+
+For example, if N is 3, an example run might be:
+
+001
+011
+111
diff --git a/simspace/Setup.hs b/simspace/Setup.hs
new file mode 100644
index 0000000..9a994af
--- /dev/null
+++ b/simspace/Setup.hs
@@ -0,0 +1,2 @@
+import Distribution.Simple
+main = defaultMain
diff --git a/simspace/default.nix b/simspace/default.nix
new file mode 100644
index 0000000..84e0349
--- /dev/null
+++ b/simspace/default.nix
@@ -0,0 +1,10 @@
+{ mkDerivation, base, random, split, stdenv }:
+mkDerivation {
+  pname = "simspace";
+  version = "0.1.0.0";
+  src = ./.;
+  isLibrary = false;
+  isExecutable = true;
+  executableHaskellDepends = [ base random split ];
+  license = stdenv.lib.licenses.bsd3;
+}
diff --git a/simspace/shell.nix b/simspace/shell.nix
new file mode 100644
index 0000000..757c212
--- /dev/null
+++ b/simspace/shell.nix
@@ -0,0 +1,28 @@
+{ nixpkgs ? import <nixpkgs> {}, compiler ? "default", doBenchmark ? false }:
+
+let
+
+  inherit (nixpkgs) pkgs;
+
+  f = { mkDerivation, base, random, split, stdenv }:
+      mkDerivation {
+        pname = "simspace";
+        version = "0.1.0.0";
+        src = ./.;
+        isLibrary = false;
+        isExecutable = true;
+        executableHaskellDepends = [ base random split ];
+        license = stdenv.lib.licenses.bsd3;
+      };
+
+  haskellPackages = if compiler == "default"
+                       then pkgs.haskellPackages
+                       else pkgs.haskell.packages.${compiler};
+
+  variant = if doBenchmark then pkgs.haskell.lib.doBenchmark else pkgs.lib.id;
+
+  drv = variant (haskellPackages.callPackage f {});
+
+in
+
+  if pkgs.lib.inNixShell then drv.env else drv
diff --git a/simspace/simspace.cabal b/simspace/simspace.cabal
new file mode 100644
index 0000000..cee741c
--- /dev/null
+++ b/simspace/simspace.cabal
@@ -0,0 +1,26 @@
+-- Initial simspace.cabal generated by cabal init.  For further 
+-- documentation, see http://haskell.org/cabal/users-guide/
+
+name:                simspace
+version:             0.1.0.0
+-- synopsis:            
+-- description:         
+license:             BSD3
+license-file:        LICENSE
+author:              Ben Sima
+maintainer:          ben@bsima.me
+-- copyright:           
+-- category:            
+build-type:          Simple
+extra-source-files:  ChangeLog.md, README.md
+cabal-version:       >=1.10
+
+executable simspace
+  main-is:             Main.hs
+  -- other-modules:       
+  -- other-extensions:    
+  build-depends:       base >=4.10 && <4.11
+                     , random
+                     , split
+  -- hs-source-dirs:      
+  default-language:    Haskell2010