# Gummy Bear

Paradigm(s) String-rewriting User:Hakerh400 2020 Turing complete Interpreter `.txt`

Gummy Bear is a string-rewriting esolang.

## Overview

Source code consists of zero or more rules.

Each rule consists of four strings of bits, separated by dots. For example:

```101.1111..1
```

This is a single rule. It has four strings of bits: `101`, `1111`, `(empty)` and `1`. It is also allowed to have four empty strings in a single rule:

```...
```

The first string in a rule may optionally start with `#` character.
The second string in a rule may optionally end with `#` character.
Instead of third and fourth string, a single `~` character can appear (for example `10.1~` is a valid rule).

## I/O format

Input is a string of zero or more bits. Output is also a string of zero or more bits.

## Computation

First, we take the input string and prepend a single dot `.` character. For example, if the input string is `101`, we will have

```.101
```

This is our main string. Computation consists of rewriting the main string until program halts.

There will always be a single dot in the main string. The dot divides the main string into left and right part.

### Iteration

We perform these steps iteratively.

First, find the first rule whose first string represents the end of the left part of the main string and whose second string represents the start of the right part of the main string. If such rule cannot be found, terminate the program. If the found rule has `~` instead of third and fourth string, remove the matched substring from the main string and terminate the program.

#### Example 1

Given the rules:

```101.11.0.10 // First rule
101.10.1.11 // Second rule
```

and the main string:

```1101.10010
```

we will pick the second rule, because the second string of the first rule does not represent the start of the right part of the main string.

Once such rule is found, in the main string replace the matched substrings corresponding to the first and second rule strings with the third and fourth rule strings, respectively.

In the example above, after this iteration the main string will be

```11.11010
```

because `101` is replaced with `1` and `10` is replaced with `11`.

#### Example 2

Rules:

```1.0~
01.000.0.11
```

Main string:

```0101.000
```

The first rule will be picked (both rules can be matched, but we pick the one that appears first in the source code). The rule has `~` character, so we remove `1.0` from the main string and terminate the program. The output is

```01000
```

### Start/end patterns

If the first string of a rule starts with `#`, it means that the first string of that rule can be matched only on the start of the main string.
If the second string of a rule ends with `#`, it means that the second string of that rule can be matched only on the end of the main string.

For example, given the following two rules:

```#0... // First rule
0...  // Second rule
```

and the following main string:

```10.0010
```

Only the second rule can be matched, because the first rule can be matched only on the beginning of the main string, but because the main string has extra `1` on the beginning, the first rule cannot be applied.

## Output

Once program halts (no rules can be applied, or explicitly terminated by a `~` rule), the output is the main string without the dot character.

## Examples

In each example we provide the source code, sample input and output, and finally the computation steps for that particular input.

### Cat

Source code:

```// noop
```

Input: `110101`
Output: `110101`

Explanation: if there are no rules in the source code, nothing can be applied and the program terminates immediately. Since the main string is the input prepended with a single dot character and the output is the main string without the dot character, therefore the output is the same as input.

### Invert bits

Source code:

```.0.1.
.1.0.
```

Input: `0101110`
Output: `1010001`

Computation steps:

```+----------------------------+
|             |              |
| Main string | Rule applied |
|             |              |
|============================|
|             |              |
|  .0101110   |    .0.1.     |
|             |              |
|-------------|--------------|
|             |              |
|  1.101110   |    .1.0.     |
|             |              |
|-------------|--------------|
|             |              |
|  10.01110   |    .0.1.     |
|             |              |
|-------------|--------------|
|             |              |
|  101.1110   |    .1.0.     |
|             |              |
|-------------|--------------|
|             |              |
|  1010.110   |    .1.0.     |
|             |              |
|-------------|--------------|
|             |              |
|  10100.10   |    .1.0.     |
|             |              |
|-------------|--------------|
|             |              |
|  101000.0   |    .0.1.     |
|             |              |
|-------------|--------------|
|             |              |
|  1010001.   |      /       |
|             |              |
+----------------------------+
```

### Reverse bits

Source code:

```#..00.
00.0.0000.
00.1.0100.
00.#.01.
001..01.0
101..01.1
#01..10.
10.0000.0010.00
10.0001.0110.00
10.0100.0010.01
10.0101.0110.01
10.001.01.101
10.011.01.111
10.00#.01.10
10.01#.01.11
10.1.11.1
10.#~
11.10.011.
11.11.111.
11.#~
```

Input: `11001`
Output: `10011`

Computation steps:

```+---------------------------------+
|               |                 |
|  Main string  |  Rule applied   |
|               |                 |
|=================================|
|               |                 |
|    .11001     |     #..00.      |
|               |                 |
|---------------|-----------------|
|               |                 |
|   00.11001    |   00.1.0100.    |
|               |                 |
|---------------|-----------------|
|               |                 |
|   0100.1001   |   00.1.0100.    |
|               |                 |
|---------------|-----------------|
|               |                 |
|  010100.001   |   00.0.0000.    |
|               |                 |
|---------------|-----------------|
|               |                 |
|  01010000.01  |   00.0.0000.    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0101000000.1  |   00.1.0100.    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 010100000100. |    00.#.01.     |
|               |                 |
|---------------|-----------------|
|               |                 |
| 010100000101. |    101..01.1    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01010000001.1 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0101000001.01 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 010100001.001 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01010001.0001 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0101001.00001 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 010101.000001 |    101..01.1    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01001.1000001 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0101.01000001 |    101..01.1    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 001.101000001 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01.0101000001 |    #01..10.     |
|               |                 |
|---------------|-----------------|
|               |                 |
| 10.0101000001 | 10.0101.0110.01 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0110.01000001 | 10.0100.0010.01 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 010010.010001 | 10.0100.0010.01 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01000010.0101 | 10.0101.0110.01 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0100000110.01 |  10.01#.01.11   |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0100000101.11 |    101..01.1    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 010000001.111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01000001.0111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0100001.00111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 010001.000111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01001.0000111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0101.00000111 |    101..01.1    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 001.100000111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01.0100000111 |    #01..10.     |
|               |                 |
|---------------|-----------------|
|               |                 |
| 10.0100000111 | 10.0100.0010.01 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0010.01000111 | 10.0100.0010.01 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 000010.010111 | 10.0101.0110.01 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 00000110.0111 |  10.011.01.111  |
|               |                 |
|---------------|-----------------|
|               |                 |
| 00000101.1111 |    101..01.1    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0000001.11111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 000001.011111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 00001.0011111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0001.00011111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 001.000011111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01.0000011111 |    #01..10.     |
|               |                 |
|---------------|-----------------|
|               |                 |
| 10.0000011111 | 10.0000.0010.00 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0010.00011111 | 10.0001.0110.00 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 000110.001111 |  10.001.01.101  |
|               |                 |
|---------------|-----------------|
|               |                 |
| 000101.101111 |    101..01.1    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 00001.1101111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0001.01101111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 001.001101111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01.0001101111 |    #01..10.     |
|               |                 |
|---------------|-----------------|
|               |                 |
| 10.0001101111 | 10.0001.0110.00 |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0110.00101111 |  10.001.01.101  |
|               |                 |
|---------------|-----------------|
|               |                 |
| 0101.10101111 |    101..01.1    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 001.110101111 |    001..01.0    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01.0110101111 |    #01..10.     |
|               |                 |
|---------------|-----------------|
|               |                 |
| 10.0110101111 |  10.011.01.111  |
|               |                 |
|---------------|-----------------|
|               |                 |
| 01.1110101111 |    #01..10.     |
|               |                 |
|---------------|-----------------|
|               |                 |
| 10.1110101111 |    10.1.11.1    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 11.1110101111 |   11.11.111.    |
|               |                 |
|---------------|-----------------|
|               |                 |
| 111.10101111  |   11.10.011.    |
|               |                 |
|---------------|-----------------|
|               |                 |
|  1011.101111  |   11.10.011.    |
|               |                 |
|---------------|-----------------|
|               |                 |
|  10011.1111   |   11.11.111.    |
|               |                 |
|---------------|-----------------|
|               |                 |
|   100111.11   |   11.11.111.    |
|               |                 |
|---------------|-----------------|
|               |                 |
|   1001111.    |      11.#~      |
|               |                 |
+---------------------------------+
```