Post History

Implement Rule 110 [FINALIZED]

[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:

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

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 <span class="badge is-tag">code-golf</span>, 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: "----+++++------"
```

**Note:** Please verify the test cases; I've evaluated them by hand, so I might have made a mistake.


[Rule 110]: https://en.wikipedia.org/wiki/Rule_110

Implement Rule 110

[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:

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

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 <span class="badge is-tag">code-golf</span>, 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: "----+++++------"
```

**Note:** Please verify the test cases; I've evaluated them by hand, so I might have made a mistake.


[Rule 110]: https://en.wikipedia.org/wiki/Rule_110