#!/bin/bash

# Demonstrate a variant of 2-tag system can also be computed using
# Computation of Collatz sequences from Wikipedia as an example.
# en.wikipedia.org/wiki/Tag_system#Example:_Computation_of_Collatz_sequences

rm -rf _

# _'s are used as a separtor between states.
mkdir _

# Production rules for an M-tag system given as constants.
M=2
PROD_A="b/c"
PROD_B="a"
PROD_C="a/a/a"

# Initial state (surrounded by _'s).
mkdir -p _/a/a/a/_

S="(/[abc])"

find -regextype posix-extended -empty \( \
    -regex ".*_$S{,1}/_" -prune -o \
    -regex ".*_$S{$M}($S*)/a$S*/_\2" \( -execdir mkdir a/a b/a c/a _/a \; -o -true \) -o \
    -regex ".*_$S{$M}($S*)/b$S*/_\2" \( -execdir mkdir a/b b/b c/b _/b \; -o -true \) -o \
    -regex ".*_$S{$M}($S*)/c$S*/_\2" \( -execdir mkdir a/c b/c c/c _/c \; -o -true \) -o \
    \( \
        -regex ".*_/a$S*/_$S*" \( \
            -execdir find a \; -execdir mkdir -p a/$PROD_A/_ \; -o \
            -execdir find b \; -execdir mkdir -p b/$PROD_A/_ \; -o \
            -execdir find c \; -execdir mkdir -p c/$PROD_A/_ \; -o \
            -execdir find _ \; -execdir mkdir -p _/$PROD_A/_ \; \
        \) -o \
        -regex ".*_/b$S*/_$S*" \( \
            -execdir find a \; -execdir mkdir -p a/$PROD_B/_ \; -o \
            -execdir find b \; -execdir mkdir -p b/$PROD_B/_ \; -o \
            -execdir find c \; -execdir mkdir -p c/$PROD_B/_ \; -o \
            -execdir find _ \; -execdir mkdir -p _/$PROD_B/_ \; \
        \) -o \
        -regex ".*_/c$S*/_$S*" \( \
            -execdir find a \; -execdir mkdir -p a/$PROD_C/_ \; -o \
            -execdir find b \; -execdir mkdir -p b/$PROD_C/_ \; -o \
            -execdir find c \; -execdir mkdir -p c/$PROD_C/_ \; -o \
            -execdir find _ \; -execdir mkdir -p _/$PROD_C/_ \; \
        \) \
    \) \
\) &> /dev/null

# Output each state
find _ -regextype posix-extended -regex "_|.*_$S*/_" \
    -execdir find _ -regextype posix-extended -regex "_$S*/_" -printf "%h\n" \;