Собачка

Собачка

Paradigm(s)	String-rewriting
Designed by	User:Hakerh400
Appeared in	2022
Computational class	Unknown
Major implementations	Implemented
File extension(s)	.txt

Собачка is a string-rewriting esolang invented by User:Hakerh400 in 2022.

Overview

Source code consists of a list of decimal digits. The interpreter rewrites the list until the program halts. The output is a single digit.

Rewriting rules

Repeat this until the program halts. If the list is empty, output digit 0 and halt. If the list contains exactly one digit, output that digit and halt. Otherwise, rewrite the list using the following algorithm.

For each two consecutive digits $a$ and $b$:

• If $a+b\leq 9$, produce list [a + b]
• Otherwise, if $a=b$, produce list [a]
• Otherwise, if $a<b$, produce list [1, a + b - 10]
• Otherwise produce an empty list

Concatenate all productions in order. It represents the new list of digits.

Example

Program:

4866857774615622223321

Computation steps:

4866857774615622223321
12614127710761184445653
38755397817729889118
1158121598791181729
2613933614162998911
874126975578119172
5381551215921089
81196563361431817
9210119697574998
3112101512139
4233116633412
656427696753
116915138
271566411
98611652
7277
997
9

The output is 9.

Implementation

Implementation in Haskell:

type N = Integer
infixr 0 #
(#) = id

xs :: [N]
xs = [1, 2, 3, 4, 5]

f :: N -> N -> [N]
f a b = let c = a + b in
  if c <= 9 then [c] else
  if a == b then [a] else
  if a < b then [1, c - 10]
  else []

step :: [N] -> [N]
step xs = concat # zipWith f xs # tail xs

run :: [N] -> [[N]]
run xs = if null xs then [[0]] else
  xs : if length xs == 1 then [] else run # step xs

main :: IO ()
main = mapM_ (putStrLn . (>>= show)) # run xs

Computational class

We conjecture that this language is total.