diff options
Diffstat (limited to 'anonco')
| -rw-r--r-- | anonco/.gitignore | 1 | ||||
| -rw-r--r-- | anonco/ChangeLog.md | 5 | ||||
| -rw-r--r-- | anonco/LICENSE | 30 | ||||
| -rw-r--r-- | anonco/Main.hs | 62 | ||||
| -rw-r--r-- | anonco/README.md | 35 | ||||
| -rw-r--r-- | anonco/Setup.hs | 2 | ||||
| -rw-r--r-- | anonco/anonco.cabal | 26 | ||||
| -rw-r--r-- | anonco/default.nix | 10 | ||||
| -rw-r--r-- | anonco/shell.nix | 28 |
9 files changed, 199 insertions, 0 deletions
diff --git a/anonco/.gitignore b/anonco/.gitignore new file mode 100644 index 0000000..1521c8b --- /dev/null +++ b/anonco/.gitignore @@ -0,0 +1 @@ +dist diff --git a/anonco/ChangeLog.md b/anonco/ChangeLog.md new file mode 100644 index 0000000..5b7cb24 --- /dev/null +++ b/anonco/ChangeLog.md @@ -0,0 +1,5 @@ +# Revision history for anonco + +## 0.1.0.0 -- YYYY-mm-dd + +* First version. Released on an unsuspecting world. diff --git a/anonco/LICENSE b/anonco/LICENSE new file mode 100644 index 0000000..fccd105 --- /dev/null +++ b/anonco/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/anonco/Main.hs b/anonco/Main.hs new file mode 100644 index 0000000..891fcf7 --- /dev/null +++ b/anonco/Main.hs @@ -0,0 +1,62 @@ +module Main where + +import System.Environment +import Control.Monad +import System.Random (newStdGen, randomRs) +import Data.List.Split + +main :: IO () +main = do + args <- getArgs + case args of + [] -> putStrLn "Needs one argument" + (n:_) -> run (read n :: Int) + +-- | Run the cellular automata with a random seed. +run :: Int -> IO () +run n = do + g <- newStdGen + let init = take n $ randomRs (0,1) g + run' init + +-- | Version of 'run' that allows for entering your own initial seed. +run' :: [Int] -> IO () +run' init = do + let n = length init + 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) + +-- Here I'm using a sequence-based computation to find the next step. There is +-- an arithmetic way to calculate it, but I can't find a good explanation of the +-- arithmetic online. So, until I get a copy of Wolfram's book, I'll just stick +-- with this; unfortunately I think the source of my bug is in the sequence +-- logic :( + +next :: Int -> [Int] -> [Int] +next n state = [left, center, right] + where + center = translate $ getLast n' state + right = translate $ getLast (n'+1) state + left = translate $ getLast (n'-1) state + n' = n+n + +getLast :: Int -> [a] -> [a] +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 _ = 0 diff --git a/anonco/README.md b/anonco/README.md new file mode 100644 index 0000000..d97846e --- /dev/null +++ b/anonco/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/anonco/Setup.hs b/anonco/Setup.hs new file mode 100644 index 0000000..9a994af --- /dev/null +++ b/anonco/Setup.hs @@ -0,0 +1,2 @@ +import Distribution.Simple +main = defaultMain diff --git a/anonco/anonco.cabal b/anonco/anonco.cabal new file mode 100644 index 0000000..d586527 --- /dev/null +++ b/anonco/anonco.cabal @@ -0,0 +1,26 @@ +-- Initial anonco.cabal generated by cabal init. For further +-- documentation, see http://haskell.org/cabal/users-guide/ + +name: anonco +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 anonco + main-is: Main.hs + -- other-modules: + -- other-extensions: + build-depends: base >=4.10 && <4.11 + , random + , split + -- hs-source-dirs: + default-language: Haskell2010 diff --git a/anonco/default.nix b/anonco/default.nix new file mode 100644 index 0000000..9472b73 --- /dev/null +++ b/anonco/default.nix @@ -0,0 +1,10 @@ +{ mkDerivation, base, random, split, stdenv }: +mkDerivation { + pname = "anonco"; + version = "0.1.0.0"; + src = ./.; + isLibrary = false; + isExecutable = true; + executableHaskellDepends = [ base random split ]; + license = stdenv.lib.licenses.bsd3; +} diff --git a/anonco/shell.nix b/anonco/shell.nix new file mode 100644 index 0000000..56160f4 --- /dev/null +++ b/anonco/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 = "anonco"; + 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 |