# Implement a strange automaton

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


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!

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

# V, 2622 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!)

• The second and third regexes can merge into Ó1ü0/&1 (ü is \|) Commented Jul 26, 2017 at 19:47
• @Cowsquack genius! Commented Jul 26, 2017 at 19:48
• It's even shorter to do Ó./&1 followed by Ó31/0. Commented Jul 27, 2017 at 2:24

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

# 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!

# 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

• [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
– Rod
Commented Jul 26, 2017 at 19:52
• 90 bytes
– ovs
Commented Jul 26, 2017 at 21:24
• Parentheses are not needed for print statement in python 2, so you can save one byte Commented Jul 27, 2017 at 0:57

# 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]
}

• You can replace 3<=s.count with 2<s.count for -1 bytes. Commented Jul 27, 2017 at 9:16
• @Mr.Xcoder Thanks! I can also detects 1s in the input with 0 < element rather than element == 0 Commented Jul 27, 2017 at 16:23

# Nim, 70 bytes

import re,sugar
x=>x.multiReplace([(re"1..","0"),(re"(.)","$#1")])&"1"  Try it online! multiReplace allows us to do substitutions simultaneously. The index of the tuple within the sequence acts as the priority if there is a situation where more than one substitution can be made. The priority rises the lower the index is. # 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. • Using lists is shorter. Commented Jul 27, 2017 at 12:29 • @EriktheOutgolfer thanks :) Commented Jul 27, 2017 at 13:03 • Oh, and you can do 1>Z[0] instead of 0==Z[0]. Commented Jul 27, 2017 at 13:06 # 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!

# Ruby, 47 bytes

This is a direct port of the sample implementation Haskell code.

f=->s{s=~/^1../??0+f[$']:s=~/./?$&+?1+f[$']:?1}  Attempt This Online! ## More readable $& is the matched text from the previous regexp match (=~) and $' is the text after the match. f = ->s{ if s =~ /^1../ then "0" + f[$']
elsif s =~ /./ then $& + "1" + f[$']
else "1"
end
}


# Julia 0.6, 69 65 bytes

~s=s>""?s<"1"?"01"*~s[2:end]:length(s)>2?"0"*~s[4:end]:s*"11":"1"


Try it online!

Ungolfed and commentated algorithm:

function ~(s)

# Return "1" on the empty string
# (End case for automata ending in "0" or "1..")
if s == ""
return "1"

# "0" always becomes "01"
elseif s[1] == '0'
return "01" * ~s[2:end]

# "1.." always becomes "0"
elseif length(s) > 2
return "0" * ~s[4:end]

# Otherwise, append "11"
# (End case for automata ending in "1" or "1.")
else return s * "11"

end
end


Try it online!

• -3 bytes thanks to MarcMush: Test the value of s instead of s[1]
• -1 byte thanks to MarcMush: Rewrite with s>"" instead of s==""
• 65 bytes Commented Aug 11, 2023 at 7:29

# 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!

# 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.