| Bytes | Lang | Time | Link |
|---|---|---|---|
| 132 | JavaScript ES7 | 250911T232937Z | Arnauld |
| 380 | APLNARS | 250915T074504Z | Rosario |
| 226 | Python 3 | 250912T102159Z | A. Helme |
| 086 | Charcoal | 250914T072709Z | Neil |
| 062 | 05AB1E | 250912T170723Z | Kevin Cr |
| 362 | Python3 | 250912T023212Z | Ajax1234 |
JavaScript (ES7), 132 bytes
Expects the input as a nested array, such as ['D',['D',['N','N'],'N']] for D(D(NN)N).
Returns 0, 1 or 2 for extending, non-extending and halting respectively.
a=>(k=3**(a+0).length,g=([p,q,...a])=>p?p.map?g([...p,q,...a]):g[x=p+q+a]?1:k--&&g(g[x]=[{S:q,D:[q,q],T:[q,q,q]}[p]||[],...a]):2)(a)
Characterization
This code uses the following characterization:
- If the list of commands is exhausted, the program is halting.
- If we reach a step \$S\$ which is exactly equal to a previous step \$P\$, the program is non-halting and non-extending.
- If we do more than \$T\$ iterations, the program is non-halting and extending.
The threshold \$T\$ is set to \$3^N\$ where \$N\$ is the length of the serialized input. (What really matters is that \$N\$ is greater than the initial number of commands.)
Commented
a => ( // a[] = input array
k = 3 ** (a + 0).length, // k = counter
g = ([ // g is a recursive function taking:
p, // p = next entry from the input
q, // q = entry after next
...a // a[] = remaining entries
]) => //
p ? // if p is defined:
p.map ? // if p is an array:
g([...p, q, ...a]) // do a recursive call with p flattened
: // else:
g[x = p + q + a] ? // define x is as the current key
// if already encountered:
1 // return 1
: // else:
k-- && // return 0 if k is 0
// (decrement it afterwards)
g( // otherwise, do a recursive call:
g[x] = [ // set g[x]
{ //
S: q, // use q for 'S'
D: [q, q], // use [q, q] for 'D'
T: [q, q, q] // use [q, q, q] for 'T'
}[p] //
|| [], // or [] for 'N'
...a // followed by the remaining entries
] //
) // end of recursive call
: // else:
2 // return 0
)(a) // initial call to g
APL(NARS), 380 chars
r←f w;a;b;i;l;c;t;p;q;np;G
G←⍬
w←,w⋄r←G⍳⊂w⋄→4×⍳r≤≢G⋄G,←⊂w⋄→6
r←0⋄→0
r←1⋄→0
r←2⋄→0
np←i←1⋄p←q←r←a←b←''⋄l←≢w
→3×⍳i>l⋄a←w[i]⋄i+←1⋄→10×⍳a='('
→3×⍳i>l⋄c←w[i]⋄i+←1
→12×⍳∼c='('
p←'('⋄q←')'
→3×⍳i>l⋄c←w[i]⋄i+←1⋄np+←c=p⋄np-←c=q⋄→13×⍳np=0⋄b,←c⋄→11
b←,c
t←b⋄→15×⍳a='('⋄→5×⍳(np=1)∧(a='T')∧'T'=↑,b⋄→5×⍳(a='T')∧'ST'≡b
t←{a='N':''⋄a='S':b⋄a='D':b,p,b,q⋄a='T':b,p,b,q,p,b,q⋄'Fail'}
w←t,(i-1)↓w⋄→2
// +/ 27 4 30 7 7 7 25 31 20 12 12 55 5 61 62 15=380
f function has as input one string of chars, and return 0 for function terminate, 1 if function meets a repeat state (this means a loop), 2 if the function find a loop with no repeat state, this means that if f is not stopped it will go of out of memory in a future time.
f function puts in an array G, the state, that is each input, that would be the string array in w in each loop inside f function. If some state is repeated (find the w is already in G) than retun 1 because there is detected an infinite loop. If else function terminate it return 0. Else return 2 in the case it finds in the start of w the strings TT or T(ST) that it seems generate always differents states tha will have as effect the go out of memory in the future. I don't know if these string are the only one that generate always differents states.
The only test fail for 'T(TN)' that here result 0 instead than 1.
Here expand 'T(TN)' as
T(TN) TN(TN)(TN) NNN(TN)(TN) N(TN)(TN) (TN) TN NNN N
test:
f¨('N')('NT')('SS')('S(TNT)')('D(D(NN)N)')
0 0 0 0 0
f¨('TN')('TS')('TNT')('T(NTDS)T')('T(T(T(NTDS)))')
0 0 0 0 0
f¨('DD')('D(SD)')('TDD')('D(NSDD)')
1 1 1 1
f¨('DD(TT)')('T(TN)')('S(TSD(TSD))')
1 0 1
f¨('TT')('ST(ST)')('NTTT')('NT(DT)')('ST(ST)N')('TTD')('D(T(TT)T)NSNS')
2 2 2 2 2 2 2
f 'TTD'
2
f ungolfed with label numbers
r←f w;a;b;i;l;c;t;p;q;np;G
1: G←⍬
2: w←,w⋄r←G⍳⊂w⋄→4×⍳r≤≢G⋄G,←⊂w⋄→6
3: r←0⋄→0
4: r←1⋄→0
5: r←2⋄→0
6: np←i←1⋄p←q←r←a←b←''⋄l←≢w
7: →3×⍳i>l⋄a←w[i]⋄i+←1⋄→10×⍳a='('
8: →3×⍳i>l⋄c←w[i]⋄i+←1
9: →12×⍳∼c='('
10: p←'('⋄q←')'
11: →3×⍳i>l⋄c←w[i]⋄i+←1⋄np+←c=p⋄np-←c=q⋄→13×⍳np=0⋄b,←c⋄→11
12: b←,c
13: t←b⋄→15×⍳a='('⋄→5×⍳(np=1)∧(a='T')∧'T'=↑,b⋄→5×⍳(a='T')∧'ST'≡b
14: t←{a='N':''⋄a='S':b⋄a='D':b,p,b,q⋄a='T':b,p,b,q,p,b,q⋄'Fail'}
15: w←t,(i-1)↓w⋄→2
Python 3 - 226 bytes
def f(S):
R,H=S,[]
while(len(R)>1):
a,b,*q=R;n="NSDT".index(a)
if n:R=list(b)+[b]*(n-1)+q
elif q:R=list(q[0])+q[1:]
else:R=q
if R in H:return 1
for h in H:
if h in[R[1:],R[:len(h)]]:return 2
H+=[R]
return 0
Explanation
R is the result, H is an history of all the steps. The code runs each step, extracts the 2 first elements of the list and applies the N/S/D/T rules.
- If the result is found in the history, it returns 1 (loop)
- If something in the history is a prefix or a suffix of the result, it returns 2 (expanding)
- otherwise, the loop will end and return 0 (halting)
Update
Replaced
if h==R[:len(h)]:return 2
by
if h in[R[1:],R[:len(h)]]:return 2
to handle the case where the code expands to the left, for example with TTD.
Charcoal, 86 bytes
≔X³LΦ⭆¹θ№αιηW∧‹¹Lθ∧¬№υθ‹Lυη«⊞υθ≔⁺E⌕NSDT§θ⁰§θ¹✂θ²Lθ¹θW∧θ⁼§θ⁰⁺⟦⟧§θ⁰≔⁺§θ⁰Φθμθ»I∧‹¹Lθ∨№υθ²
Try it online! Link is to verbose version of code. Takes input as a nested character array and outputs 0 for halting, 1 for repeating and 2 for extending. Explanation:
≔X³LΦ⭆¹θ№αιη
Estimate the number of steps needed as 3ⁿ where n is the number of letters in the input. This does make the program exponentially slow for large n but fortunately not so slow that TIO can't handle the last test case.
W∧‹¹Lθ∧¬№υθ‹Lυη«
Repeat until either a) the length of the input drops below 2 b) the input repeats a previous state c) the number of previous states reaches 3ⁿ.
⊞υθ
Save the current state.
≔⁺E⌕NSDT§θ⁰§θ¹✂θ²Lθ¹θ
Use the first element to decide how many times to repeat the second.
W∧θ⁼§θ⁰⁺⟦⟧§θ⁰≔⁺§θ⁰Φθμθ
While the new first element is a list, unwrap it.
»I∧‹¹Lθ∨№υθ²
Output the final characterisation.
05AB1E, 62 bytes
[ÐDˆ˜gD_#I[€Ð€`é¤g#}g›i2q}gi€`R}ćUć¸"NSDT"Xkи渀`RììD¯€»s»åi1q
Input as a nested list of characters.
Outputs 0 for halting; 1 for unhalting repeating; 2 for unhalting extending.
Try it online or verify all test cases.
Explanation:
[ # Start an infinite loop:
ÐD # Repeat the current state four times
# (which will use the implicit input-list in the first iteration)
ˆ # Pop one copy, and add it to the global array
˜ # Pop another copy, and flatten it
g # Pop and push its length
D # Duplicate that length
_ # Pop the copy, and if this length is 0:
# # Stop the infinite loop
# (after which this 0 is output implicitly as result)
I # Push the input-list again
[ # Start an inner infinite loop:
€Ð # Repeat each inner item three times
€` # Flatten one level down
é # Sort by length, so the inner lists are at the end
¤ # Push the last value (without popping)
g # If it's length is 1:
# # Stop the inner infinite loop
}g # After this loop: pop and push the length
›i # If the length of the current flattened list is larger:
2 # Push a 2
q # Stop the program, after which this 2 is output implicitly
} # Close this if-statement
g # Pop the last copy, and push its length
i # If it's length is 1:
€`R # Flatten it one level down
} # Close the if-statement
ć # Extract the head of the current state
U # Pop and store this character in variable `X`
ć # Extract the head again
¸ # Wrap it into a list
"NSDT"Xk # Get the 0-based index of char `X` in "NSDT"
и # Repeat the wrapped list that many times
ć # Extract its head
¸ # Wrap it into a list
€`R # Flatten it one level down
ì # Prepend it back to the list
ì # Prepend this list back to the remainder of the state
D # Duplicate this next state
¯ # Push the global array
€» # Convert each inner list to a prettified string
s # Swap to get the current next state at the top again
» # Convert it to a similar prettified string
åi # If this string is in the list:
1 # Push 1
q # Stop the program, after which this 1 is output implicitly
Some notes:
- I use
[€Ð€`é¤g#}to get the maximum possible size of the input if almost all wereT, by simply triplicating every character, keeping in mind potential nested lists. (If the state ever reaches beyond the length of this list, it means it's extending and we'll output2.) - The
i€`R}is as work-around for test cases of the formN.(…), where the dots can be any character or even nested lists (e.g. test caseNT(DT)), since we want to correct[["D","T"]]to["D","T"]before continuing. ¸"NSDT"Xkи渀`Rìcan be split into two parts:¸"NSDT"Xkиrepeats the current character/list based on the index ofX(N=0, S=1, D=2, T=3). Then渀`Rìcorrects the first item if necessary, which is a shorter alternative of the more readablećDaišëì}(extract head; if its a character, prepend it withš; else (it's a list), merge-prepend it instead withì). Here a TIO to show the I/O for the different use-cases based on the index and current character/list/nested-list. But in short,¸"NSDT"Xkи渀`Rìbasically accomplishes the following:- If the index is 0 (
X=N), it will result in an empty list; - If the index is 1 (
X=S), it will:- Wrap the current character into a singleton-list
- Keep the current list as is
- If the index is 2 (
X=D), it will:- Repeat the current character two times as list
- Add the current list once to itself as last item
- If the index is 3 (
X=T), it will:- Repeat the current character three times as list
- Add the current list twice to itself as last items
- If the index is 0 (
- 05AB1E's contains builtin
ådoesn't work when we want to check if a nested list contains a list. So we'll use the€»on the global array and»on the current state-list first before usingå, where»basically joins each inner list with a space-delimiter, and then all strings with a newline-delimiter, resulting in a prettified string (and deeper nested list are stringified as is).
Python3, 362 bytes
T=lambda j,r:j==r[:len(j)]and all(j[-1]==i for i in r[len(j):])
def f(s):
q,s=[s],[]
for i in q:
if len(i)<2:return 0
a,b,*c=i;V=b if str(b)[0]=='['else[b]
if'N'==a:r=[]if[]==c else(c if str(c[0])[0]!='['else c[0]+c[1:])
else:r=V+[b]*['S','D','T'].index(a)+c
if r in s:return 1
if any(T(j,r)or T(j[::-1],r[::-1])for j in s):return 2
q+=[r];s+=[r]