diff options
| -rw-r--r-- | simspace/.gitignore | 1 | ||||
| -rw-r--r-- | simspace/ChangeLog.md | 5 | ||||
| -rw-r--r-- | simspace/LICENSE | 30 | ||||
| -rw-r--r-- | simspace/Main.hs | 46 | ||||
| -rw-r--r-- | simspace/README.md | 35 | ||||
| -rw-r--r-- | simspace/Setup.hs | 2 | ||||
| -rw-r--r-- | simspace/default.nix | 10 | ||||
| -rw-r--r-- | simspace/shell.nix | 28 | ||||
| -rw-r--r-- | simspace/simspace.cabal | 26 |
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 |