Challenge:
NSDT is like a calculus model invented by me that contains only 4 commands and grouping. Your task is to check in which way the program ends. The program is read from left to right. There are three ways in which a program runs:
- Halting program: The program will end in some way
- Unhalting non-extending program: The program will not end but will repeat the same state.
- Unhalting extending program: The program will not end and will not repeat the same state.
And there are four commands; they are
N: get the first argument and return nothing:f(x):S: return the first argument applied oncef(x): xD: return the first argument applied twicef(x): x(x)T: return the first argument applied thricef(x): x(x)(x)
For example, SS returns S and TS returns SSS
The commands are groupable; for example, D(TS)D has (TS) grouped, it returns (TS)(TS)D which is the same as TS(TS)D.
Your task is to determine in which way the program runs. The input must be infix, but you don't have to manually parse from strings to lists, so something like ['D', ['D', 'N']] or ["D", ["DN"]] is fine. The output can be anything as long as the program outputs it consistently like 0, 1 and 2. The shortest code in bytes wins.
I will give an example for each way:
Halting
T(NTDS)T
NTDS(NTDS)(NTDS)T
DS(NTDS)(NTDS)T
SS(NTDS)(NTDS)T
S(NTDS)(NTDS)T
NTDS(NTDS)T
...
NTDST
DST
SST
ST
T
(halted)
Unhalting non-extending
S(TSD(TSD))
TSD(TSD)
SSSD(TSD)
SSD(TSD)
SD(TSD)
D(TSD)
TSD(TSD)
... (repeating)
Unhalting extending
ST(ST)
T(ST)
ST(ST)(ST)
T(ST)(ST)
ST(ST)(ST)(ST)
T(ST)(ST)(ST)
ST(ST)(ST)(ST)(ST)
... (extending)
And that's it. These are all the examples. All of the above can be used as test cases. More test cases are introduced below:
Test cases:
Halting
N
NT
SS
S(TNT)
D(D(NN)N)
TN
TS
TNT
T(NTDS)T
T(T(T(NTDS)))
Unhalting non-extending
DD
D(SD)
TDD
D(NSDD)
DD(TT)
T(TN)
S(TSD(TSD))
Unhalting extending
TT
ST(ST)
NTTT
NT(DT)
ST(ST)N
TTD
D(T(TT)T)NSNS
TTandST(ST)as prefixes, if I'm interpreting them correctly) \$\endgroup\$[ 'D', [ 'D', [ 'N', 'N' ], 'N' ] ]forD(D(NN)N)) \$\endgroup\$T(T(T(NTDS)))or similar. (Expands and shrinks many times before finally collapsing.) \$\endgroup\$TTD. That caused all answers to fail. \$\endgroup\$