11
\$\begingroup\$

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 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)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – caird coinheringaahing Jul 26 '17 at 18:41
  • 2
    \$\begingroup\$ So then if we have a 10 it should print 11011? I think a few more test cases would be helpful \$\endgroup\$ – nmjcman101 Jul 26 '17 at 19:08
  • 2
    \$\begingroup\$ @WheatWizard I would appreciate a clearer explanation, perhaps a table, of the rules \$\endgroup\$ – Alexander - Reinstate Monica Jul 26 '17 at 21:14
  • 2
    \$\begingroup\$ I don't believe this is actually a cellular automaton, but feel free to enlighten me with a definition saying it is. \$\endgroup\$ – feersum Jul 27 '17 at 2:08
  • 2
    \$\begingroup\$ @feersum Indeed, it doesn't preserve number of cells. It's a finite-state transducer. \$\endgroup\$ – Ørjan Johansen Jul 27 '17 at 2:13
5
\$\begingroup\$

V, 26 22 21 bytes

Thanks to @CowsQuack for 4 bytes by combining regexes! And @ØrjanJohansen for another byte with some regex combinations.

Ó1../3
Ó./&1
Ó31/0
A1

Try it online!

Uses substitute multiple times and appends a 1 at the end. Nothing too fancy. I have a version that remaps 1 and 0 in insert mode to get the desired effect, but it's quite a bit longer.

(Multiple replacement version: Try it online!)

\$\endgroup\$
  • \$\begingroup\$ The second and third regexes can merge into Ó1ü0/&1 (ü is \|) \$\endgroup\$ – Kritixi Lithos Jul 26 '17 at 19:47
  • \$\begingroup\$ @Cowsquack genius! \$\endgroup\$ – nmjcman101 Jul 26 '17 at 19:48
  • \$\begingroup\$ It's even shorter to do Ó./&1 followed by Ó31/0. \$\endgroup\$ – Ørjan Johansen Jul 27 '17 at 2:24
3
\$\begingroup\$

JavaScript (ES6), 56 bytes

Takes input as an array of characters. Returns a string, or the number 1 if given an empty array.

f=([v,...a])=>v?(+v&&a[1]?a.splice(0,2)&&'0':v+1)+f(a):1

Demo

f=([v,...a])=>v?(+v&&a[1]?a.splice(0,2)&&'0':v+1)+f(a):1

console.log(f([...'01011111']))
console.log(f([...'10']))

Animated version

Examples of stable inputs: 0101, 010011111

f=([v,...a])=>v?(+v&&a[1]?a.splice(0,2)&&'0':v+1)+f(a):1

s = '1';
setInterval(_=>o.innerHTML=s=''+f([...s]), 200)
<input oninput="s=this.value" value="1" />
<pre id=o style="font-size:32px"></pre>

\$\endgroup\$
2
\$\begingroup\$

Python 2, 88 bytes

I,r=input(),[]
while I:a=I[0]and len(I)>2;b=a<1;r+=[I[0]]*b+[+b];I=I[a*2+1:]
print r+[1]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 89 bytes

x=input()
y=0
k=[]
while x[y:]:v=1-x[y]*(y<len(x)-2);k+=[x[y]]*v+[v];y+=3-2*v
print k+[1]

Try it online!

-4 bytes thanks to Rod
-6 bytes thanks to ovs
-1 byte thanks to micsthepick

\$\endgroup\$
  • \$\begingroup\$ [0]if v else[x[y],1]can be rewritten as [[x[y],1],[0]][v], but you can invert the v value to reach 96 bytes \$\endgroup\$ – Rod Jul 26 '17 at 19:52
  • \$\begingroup\$ 90 bytes \$\endgroup\$ – ovs Jul 26 '17 at 21:24
  • \$\begingroup\$ Parentheses are not needed for print statement in python 2, so you can save one byte \$\endgroup\$ – micsthepick Jul 27 '17 at 0:57
2
\$\begingroup\$

Swift 3, 147 bytes

-1 thanks to @Mr.Xcoder

func g(i:[Int]){var r=[Int]();var s=ArraySlice(i);while let e=s.popFirst(){if 0<e&&2<s.count{r+=[0];s=s.dropFirst(2)}else{r+=[e,1]}};print(r+[1])}

Ungolfed, returning the value rather than printing:

func iterate(state: [Int]) -> [Int] {
    var result = [Int]()

    var inputSlice = ArraySlice(state)

    while let element = inputSlice.popFirst() {
        if 0 < element && 2 < inputSlice.count { 
            result += [0]
            inputSlice = inputSlice.dropFirst(2)
        }
        else {
            result += [element, 1]
        }

        //debugPrint(result.map(String.init).joined(separator: ""))
    }

    return result + [1]
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace 3<=s.count with 2<s.count for -1 bytes. \$\endgroup\$ – Mr. Xcoder Jul 27 '17 at 9:16
  • \$\begingroup\$ @Mr.Xcoder Thanks! I can also detects 1s in the input with 0 < element rather than element == 0 \$\endgroup\$ – Alexander - Reinstate Monica Jul 27 '17 at 16:23
1
\$\begingroup\$

Python 2, 81 bytes

Both input and output are lists (thanks to Erik the Outgolfer)

def f(Z):return Z and((1>Z[0]or 3>len(Z))and[Z[0],1]+f(Z[1:])or[0]+f(Z[3:]))or[1]

Try it online!

Some cases

[0,1,0,1,1,1,1,1] --> [0,1,0,0,1,1,1]
[0] ----------------> [0,1,1]
[1] ----------------> [1,1,1]
[] -----------------> [1]
[0,1] --------------> [0,1,1,1,1]
[1,0] --------------> [1,1,0,1,1]

Python 2, 85 bytes

Both input and output are strings (initial solution)

def f(Z):return Z and(('0'==Z[0]or 3>len(Z))and Z[0]+'1'+f(Z[1:])or'0'+f(Z[3:]))or'1'

Try it online!

Some cases

'01011111'--> 0100111
'0'---------> 011
'1'---------> 111
''----------> 1
'01'--------> 01111
'10'--------> 11011

Explication It is simplily a golf of a recursive method.

\$\endgroup\$
  • \$\begingroup\$ Using lists is shorter. \$\endgroup\$ – Erik the Outgolfer Jul 27 '17 at 12:29
  • \$\begingroup\$ @EriktheOutgolfer thanks :) \$\endgroup\$ – mdahmoune Jul 27 '17 at 13:03
  • \$\begingroup\$ Oh, and you can do 1>Z[0] instead of 0==Z[0]. \$\endgroup\$ – Erik the Outgolfer Jul 27 '17 at 13:06
1
\$\begingroup\$

Perl 5, 62 + 2 (-F) = 64 bytes

$r.=$F[$i]&&$i+2<@F&&($i+=2)?0:"$F[$i]1";++$i<@F&&redo;say$r.1

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Scala, 131+29=160 bytes

This is inside a function taking the string a as parameter and returning the output as a string.

var s=""
var k=0
for(c<-0 to a.length-1)breakable{if(k>0){k-=1
break}
if(a(c)==49&c<a.length-3){s+="0"
k+=2}else s+=a(c)+"1"}
s+"1"

I do have to import util.control.Breaks._, so I need to add those 28 bytes plus a trailing linefeed.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C# (.NET Core), 108 bytes

n=>{var t="";for(int i=0,b=n.Length;i<b;){if(n[i]>'0'&i+2<b){t+="0";i+=3;}else t+=n[i++]+"1";}return t+"1";}

Try it online!

Input taken as a string, and a string is returned as output.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.