Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read
Challenges

Implement Rule 110

+4
−0

[Rule 110] is a Turing complete cellular automaton. It is defined as follows:

Take as initial value a sequence of symbols that's infinite to both sides, which consists only of two different symbols (I'm going to use $+$ and $-$ here). This sequence can be seen as a function that maps the integers to the set $\{+,-\}$.

Then in each iteration, calculate a new such sequence as follows:

To determine the new value at position $n$, look at the old values in the cells $n-1$, $n$ and $n+1$, and then look up the new value in the following table:

\begin{align} \begin{array}{c|cccccccc} \text{old} & +++ & ++- & +-+ & +-- & -++ & -+- & --+ & ---\\ \hline \text{new} & - & + & + & - & + & + & + & - \end{array} \end{align}

Your task is to implement Rule 110. In particular, your program shall take as input:

  • A non-empty string that represents a pattern which is periodically repeated to both sides, starting at position 0 (so if the string is +-, then there's a + on all even positions, and a - on all odd positions.

  • A second (empty or non-empty) string that represents a local deviation from that pattern, again starting at position 0. for example, with the above background pattern, if the second string is ---+++, then the initial state of the cellular automaton is

...+-+-+-+----++++-+-+-...
           ↑
       position 0
  • A number of iterations, which may be zero or positive.

It then outputs the relevant part resulting state of the state space as string. More exactly, if your pattern has length $p$ your local disturbance has length $l$, and the number of iterations is $n$, then you need to print the output space from position $-2p-n$ up to position $l+2p+n-1$ inclusive.

You may use arbitrary sequence types (such as list or tuples) instead of strings. Also you may use arbitrary characters instead of + and -, or values of other types (e.g. integers or logical values), as long as you have exactly two of them and state clearly which of them corresponds to $+$ and which to $-$.

This is code-golf, thus the shortest code wins.

Test cases:

Pattern: "-"
Local: ""
Iterations: 0
----
Output: "----"

Pattern: "-"
Local: "+"
Iterations: 0
----
Output: "--+--"

Pattern: "-"
Local: "-"
Iterations: 0
----
Output: "-----"

Pattern: "+-"
Local: "-"
Iterations: 0
----
Output: "+-+---+-+"

Pattern: "-+"
Local: "-"
Iterations: 0
----
Output: "-+-+-+-+-"

Pattern: "+"
Local: ""
Iterations: 1
----
Output: "------"

Pattern: "+-"
Local: ""
Iterations: 1
----
Output: "++++++++++"

Pattern: "-"
Local: "+"
Iterations: 1
----
Output: "--++---"

Pattern: "-"
Local: "+"
Iterations: 3
----
Output: "--++-+-----"

Pattern: "+---"
Local: ""
Iterations: 3
----
Output: "++-+++-+++-+++-+++-+++"

Pattern: "+-"
Local: "-"
Iterations: 3
----
Output: "----+++++------"
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

1 answer

+2
−0

JavaScript (Node.js), 160 bytes

(r,d,n,l=r.length,s=d.length,p=(n,i)=>n?"01110110"[4*p(--n,i-1)+2*p(n,i)+1*p(n,i+1)]:i>=0&i<s?d[i]:r[(i%l+l)%l])=>[...Array(4*l+s+2*n)].map((_,i)=>p(n,i-2*l-n))

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »

This community is part of the Codidact network. We have other communities too — take a look!

You can also join us in chat!

Want to advertise this community? Use our templates!

Like what we're doing? Support us! Donate