11
0
I was playing around with cellular automaton and I found one that had some interesting behavior. Here's how it works:
It reads a binary string from left to right, if it encounters a 1
followed by 2
other values it will append a 0
to the result and continue reading. If it encounters a 0
(or there are less than 3 values left) it will append the current value and a 1
and continue reading. At the end of the string it will append a single 1
to the result.
Here's a worked out example of one generation
01011111
^
We first encounter a 0
so we append 01
to our result
01011111
^
01
Now we encounter a 1
so we append a zero and skip the next two values
01011111
^
010
We encounter another 1
so we do the same
01011111
^
0100
We now have another 1
but not enough space to jump so we append the current cell and a 1
(in this case 11
)
01011111
^
010011
We are at the end so we append a single 1
and terminate this generation
01011111
^
0100111
Task
Given input in any reasonable format you must create a function or program that computes one generation of the automaton.
This is a code-golf question so answers will be scored in bytes, with fewer bytes being better.
Sample implementation
Here is a sample implementation in Haskell (defines a function d
, but the program prints a iterations indefinitely):
d('1':_:_:x) = "0" ++ d x
d(a:x) = a:'1':d x
d x = "1"
r x = x:map d(r x)
In your question you state *We now have another 1 but not enough space to jump so we append the current cell and a 1 or 11*. Is it 1 or 11? – caird coinheringaahing – 2017-07-26T18:41:37.853
Ah its just an
11
thats a case where english could use parens read it as(we append the current cell and a 1) or 11
I'll try to make this clearer with an edit. – Post Rock Garf Hunter – 2017-07-26T18:42:46.9832So then if we have a
10
it should print11011
? I think a few more test cases would be helpful – nmjcman101 – 2017-07-26T19:08:40.337@nmjcman101 That is correct. The sample program is comprehensive. – Post Rock Garf Hunter – 2017-07-26T19:13:54.917
@WheatWizard my fault should have seen the link! – nmjcman101 – 2017-07-26T19:14:42.900
2@WheatWizard I would appreciate a clearer explanation, perhaps a table, of the rules – Alexander - Reinstate Monica – 2017-07-26T21:14:43.377
"an" automaton. SCNR. – AnoE – 2017-07-26T22:19:55.120
2I don't believe this is actually a cellular automaton, but feel free to enlighten me with a definition saying it is. – feersum – 2017-07-27T02:08:01.957
2
@feersum Indeed, it doesn't preserve number of cells. It's a finite-state transducer.
– Ørjan Johansen – 2017-07-27T02:13:18.970