I'd like to introduce a new? programming language I call Shue (Simplified Thue). It has very simple syntax.
Here is a program that checks if an input is divisible by three:
yes
no
3=0
4=1
5=2
6=0
7=1
8=2
9=0
00=0
01=1
02=2
10=1
11=2
12=0
20=2
21=0
22=1
0=yes
1=no
2=no
At the top we can see two lines. These are the output strings, "yes" and "no".
Next are the replacement rules. Let's look at 3=0
. This means that whenever we see a 3
we can replace it by 0
(but not the other way round). 12=0
means that the string 12
can be replaced with the string 0
.
Then these replacements are performed non-deterministically on the input string until we reach an output state.
For example, if we have the input 14253
, it can be reduced to an output state like so:
14253
11253 - 4=1
11223 - 5=2
2223 - 11=2
2220 - 3=0
210 - 22=1
00 - 21=0
0 - 00=0
yes - 0=yes
Here the answer is yes
, and it's pretty easy to prove that yes
is the only output state reachable using these rules and this input. This means that the program is well-defined. A program is well-defined if there is at most one output state reachable for every input.
That's it! There are basically no other rules or syntax. There is no way to restrict where or when a substring is replaced (as long as it's possible it will happen). There are no special characters or patterns that match the start or end of the string. Shue is Turing-complete, but only capable of having a finite output set. If the syntax or execution of a Shue program is not completely clear, there are more formal and more precise rules later.
Here are some possibly useful example programs:
Recognize the string "a"*x+"b"*x
yes
no
=|
a|b=|
|=yes
=L
=R
a|R=|R
L|b=L|
a|R=no
L|b=no
ba=#
#a=#
#b=#
a#=#
b#=#
#=no
Semi-recognize the string "a"*x+"b"*y+"c"*(x+y)
yes
=|
=!
a|=|b
b!c=!
|!=yes
Recognize the string "a"*x+"b"*y+"c"*(x+y)
yes
no
=|
=!
a|=|b
b!c=!
|!=yes
b!=!B
BB=B
|!c=C|!
CC=C
C|!=no
|!B=no
ba=#
ca=#
cb=#
#a=#
#b=#
#c=#
a#=#
b#=#
c#=#
#=no
Semi-recognize the string "a"*x+"b"*x+"c"*x
yes
=|
=!
a|b=|>
>b=b>
>!c=!
|!=yes
Exact definition of Shue
The source code is interpreted as a list of bytes. The only characters with special meaning are the newline, the equals sign and the backslash. \n
corresponds to a literal newline, \=
to a literal equals sign and \\
to a literal backslash. Any other use of \
is an error. Every line must contain 0 or 1 unescaped equals signs.
Or in other words, to be syntactically valid, the program has to match the following regex: /([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?(\n([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?)*/
Here is the mathematical definition of a Shue program:
A Shue program is a set of terminator strings \$T_e\$, and a set of transformation rules \$T_r\$, which are pairs of strings.
The execution of a Shue program on a input string \$i\$ is defined as follows. Let \$U\$ be the minimal set, so that \$i\in U\$ and \$\forall a,x,y,b: axb \in U \land (x,y) \in T_r \rightarrow ayb \in U\$. Let \$S=U\cap T_e\$.
If \$S=\{x\}\$, then the program will terminate, and \$x\$ will be printed to stdout.
If \$S=\emptyset\$ and \$|U|=\aleph_0\$, then the program will enter an infinite loop.
In all other cases, the behavior is undefined (yes, Shue isn't memory safe).
A compiler
Speaking of not being memory safe, here is the Optimizing Shue Transpiler (osht) version 0.0.2. This is a python program that transpiles a Shue program to C. I wouldn't recommend reading the source code (it even contains some debug prints). But the binaries produced are faster than the interpreter, and seem to work just fine with most inputs.
The actual challenge
Your task is to make a program that checks if a unary input (string matching regex /1*/) is prime in this programming language. That is, is the length of the input string a prime. You must have two output states, one for yes and the other one for no. Shortest code wins.
Test cases (You can use other strings for yes and no)
"" -> "no"
"1" -> "no"
"11" -> "yes"
"111" -> "yes"
"1111" -> "no"
"11111" -> "yes"