Gummy Bear

From Esolang
Jump to navigation Jump to search
Gummy Bear
Designed by Hakerh400
Appeared in 2020
Computational class Turing complete
Major implementations Interpreter
File extension(s) .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.#~      |
|               |                 |
+---------------------------------+

Interpreters

Interpreter