One-dimensional cellular automata: Difference between revisions
→{{header|Python}}: Added a generalised variant (any Wolfram rule) constructed as a composition of pure functions.
(→{{header|Haskell}}: Dropped liftM2 and ap for the more current Applicatiive liftA2 and <*>) |
(→{{header|Python}}: Added a generalised variant (any Wolfram rule) constructed as a composition of pure functions.) |
||
Line 3,915:
=={{header|Python}}==
===Procedural===
====Python: Straightforward interpretation of spec====
<lang python>import random
Line 3,953 ⟶ 3,954:
Generation 9: __##________________</pre>
====Python: Using boolean operators on bits====
The following implementation uses boolean operations to realize the function.
<lang python>import random
Line 3,972 ⟶ 3,973:
a = ((a&((a<<1) | (a>>1))) ^ ((a<<1)&(a>>1))) & endmask</lang>
====Python: Sum neighbours == 2====
This example makes use of the observation that a cell is alive in the next generation if the sum with its current neighbours of alive cells is two.
<lang python>>>> gen = [ch == '#' for ch in '_###_##_#_#_#_#__#__']
Line 3,992 ⟶ 3,993:
__##________________
>>> </lang>
===Composition of pure functions===
Interpreting the rule shown in the task description as Wolfram rule 22, and generalising enough to allow for other rules of this kind:
<lang python>"""Cellular Automata"""
from itertools import (islice, repeat)
# ruleSample :: Int -> String
def ruleSample(intRule):
'''16 steps in the evolution of a specified Wolfram rule.'''
return 'Rule ' + str(intRule) + ':\n' + (
unlines((map(
showCells,
take(16)(
iterate(nextRowByRule(intRule))(
onePixelInLineOf(64)
)
)
)))
)
# nextRowByRule :: Int -> [Bool] -> [Bool]
def nextRowByRule(n):
'''A row of booleans derived by Wolfram rule n
from another boolean row of the same length.'''
# step :: (Bool, Bool, Bool) -> Bool
def step(l, x, r):
return bool(n & 2**intFromBools([l, x, r]))
# go :: [Bool] -> Bool
def go(xs):
return [False] + list(map(
step,
xs, xs[1:], xs[2:]
)) + [False]
return lambda xs: go(xs)
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Samples of Wolfram rule evolutions.'''
print(
unlines(map(ruleSample, [22, 30, 110]))
)
# boolsFromInt :: Int -> [Bool]
def boolsFromInt(n):
'''List of booleans derived by binary
decomposition of an integer.'''
def go(x):
return Just((x // 2, bool(x % 2))) if x else Nothing()
return unfoldl(go)(n)
# intFromBools :: [Bool] -> Int
def intFromBools(xs):
'''Integer derived by binary interpretation
of a list of booleans.'''
def go(b, pn):
power, n = pn
return (2 * power, n + power if b else n)
return foldr(go)([1, 0])(xs)[1]
# nBoolsFromInt :: Int -> Int -> [Bool]
def nBoolsFromInt(n):
'''List of bools, left-padded to given length n,
derived by binary decomposition of an integer x.'''
def go(n, x):
bs = boolsFromInt(x)
return list(repeat(False, n - len(bs))) + bs
return lambda x: go(n, x)
# onePixelInLineOf :: Int -> [Bool]
def onePixelInLineOf(n):
'''A row of n (mainly False) booleans,
with a single True value in the middle.'''
return nBoolsFromInt(n)(
2**(n // 2)
)
# showCells :: [Bool] -> String
def showCells(xs):
'''A block string representation of a list of booleans.'''
return ''.join([chr(9608) if x else ' ' for x in xs])
# GENERIC -------------------------------------------------
# Just :: a -> Maybe a
def Just(x):
'''Constructor for an inhabited Maybe (option type) value.'''
return {'type': 'Maybe', 'Nothing': False, 'Just': x}
# Nothing :: Maybe a
def Nothing():
'''Constructor for an empty Maybe (option type) value.'''
return {'type': 'Maybe', 'Nothing': True}
# foldr :: (a -> b -> b) -> b -> [a] -> b
def foldr(f):
'''Right to left reduction of a list,
using a binary operator.'''
def go(v, xs):
a = v
for x in xs:
a = f(x, a)
return a
return lambda acc: lambda xs: go(acc, xs[::-1])
# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
'''An infinite list of repeated applications of f to x.'''
def go(x):
v = x
while True:
yield v
v = f(v)
return lambda x: go(x)
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.'''
return lambda xs: (
xs[0:n]
if isinstance(xs, list)
else list(islice(xs, n))
)
# unfoldl(lambda x: Just(((x - 1), x)) if 0 != x else Nothing())(10)
# -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# unfoldl :: (b -> Maybe (b, a)) -> b -> [a]
def unfoldl(f):
'''Dual to reduce or foldl.
Where these reduce a list to a summary value, unfoldl
builds a list from a seed value.
Where f returns Just(a, b), a is appended to the list,
and the residual b is used as the argument for the next
application of f.
When f returns Nothing, the completed list is returned.'''
def go(v):
xr = v, v
xs = []
while True:
mb = f(xr[0])
if mb.get('Nothing'):
return xs
else:
xr = mb.get('Just')
xs.insert(0, xr[1])
return xs
return lambda x: go(x)
# unlines :: [String] -> String
def unlines(xs):
'''A single newline-delimited string derived
from a list of strings.'''
return '\n'.join(xs)
# MAIN -------------------------------------------------
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>Rule 22:
█
███
█ █
███ ███
█ █
███ ███
█ █ █ █
███ ███ ███ ███
█ █
███ ███
█ █ █ █
███ ███ ███ ███
█ █ █ █
███ ███ ███ ███
█ █ █ █ █ █ █ █
███ ███ ███ ███ ███ ███ ███ ███
Rule 30:
█
███
██ █
██ ████
██ █ █
██ ████ ███
██ █ █ █
██ ████ ██████
██ █ ███ █
██ ████ ██ █ ███
██ █ █ ████ ██ █
██ ████ ██ █ █ ████
██ █ ███ ██ ██ █ █
██ ████ ██ ███ ███ ██ ███
██ █ █ ███ █ ███ █ █
██ ████ ██ █ █ █████ ███████
Rule 110:
█
██
███
██ █
█████
██ █
███ ██
██ █ ███
███████ █
██ ███
███ ██ █
██ █ █████
█████ ██ █
██ █ ███ ██
███ ████ █ ███
██ █ ██ █████ █</pre>
=={{header|R}}==
| |||