8
\$\begingroup\$

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 once f(x): x
  • D: return the first argument applied twice f(x): x(x)
  • T: return the first argument applied thrice f(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
\$\endgroup\$
13
  • 1
    \$\begingroup\$ Is this not the halting problem? \$\endgroup\$ Commented Sep 11 at 18:13
  • 1
    \$\begingroup\$ Spitballing here: if you represent each step as a directed graph all you'd need to do to detect for the unhalting non-extending case is to stop as soon as the first loop is detected. Dunno how'd you do the extending case. I conjecture that unhalting extending programs after a certain point will have the steps that contain a previous step as a prefix. (noting that all the extending examples evolve to have TT and ST(ST) as prefixes, if I'm interpreting them correctly) \$\endgroup\$ Commented Sep 11 at 18:28
  • 1
    \$\begingroup\$ Can we take the input as nested arrays, or is the parsing a part of the challenge? (e.g. [ 'D', [ 'D', [ 'N', 'N' ], 'N' ] ] for D(D(NN)N)) \$\endgroup\$ Commented Sep 11 at 19:44
  • 1
    \$\begingroup\$ Suggested test case: T(T(T(NTDS))) or similar. (Expands and shrinks many times before finally collapsing.) \$\endgroup\$ Commented Sep 11 at 21:19
  • 2
    \$\begingroup\$ @bigyihsuan You are right except for the last part, and a counterexample is TTD. That caused all answers to fail. \$\endgroup\$ Commented Sep 12 at 13:31

6 Answers 6

6
\$\begingroup\$

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

Try it online!

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Hi there and welcome to the Code Golf StackExchange site! That's a very nice first answer! \$\endgroup\$ Commented Sep 12 at 12:48
  • 2
    \$\begingroup\$ TTD should return 2, but don't worry, all other answers also fail (as of now). \$\endgroup\$ Commented Sep 12 at 13:31
  • \$\begingroup\$ Notably, as mentioned by the challenge poster, this answer is currently invalid. Please make sure to attempt to modify your answer to correctly solve the challenge. Thanks! \$\endgroup\$ Commented Sep 15 at 10:34
  • \$\begingroup\$ Thank you @lyxal and Fmbalbuena. Answer edited :) \$\endgroup\$ Commented Sep 15 at 11:10
  • \$\begingroup\$ No worries, and again, welcome to code golf :) \$\endgroup\$ Commented Sep 15 at 13:26
3
\$\begingroup\$

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 were T, 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 output 2.)
  • The i€`R} is as work-around for test cases of the form N.(…), where the dots can be any character or even nested lists (e.g. test case NT(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 of X (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
  • 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).
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES7), 148 bytes

-2 thanks to @l4m2

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,S,...a])=>p?p.map?g([...p,S,...a]):g[x=JSON.stringify([p,S,a])]?1:k--&&g(g[x]=[{S,D:[S,S],T:[S,S,S]}[p]||[],...a]):2)(a)

Try it online!

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
\$\endgroup\$
7
  • \$\begingroup\$ TTD gives infinite loop, doesn't work. \$\endgroup\$ Commented Sep 12 at 13:26
  • \$\begingroup\$ @Fmbalbuena I've rolled back to my initial approach (which wasn't published). \$\endgroup\$ Commented Sep 12 at 14:49
  • \$\begingroup\$ It seems that function goes in problem with string "NSSTT" \$\endgroup\$ Commented Sep 16 at 12:54
  • 1
    \$\begingroup\$ @Rosario That works in theory. It's just too long given the threshold in use. (It would pass with this version.) \$\endgroup\$ Commented Sep 16 at 15:43
  • 1
    \$\begingroup\$ -2 \$\endgroup\$ Commented Oct 16 at 23:52
2
\$\begingroup\$

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]

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ TTD doesn't work, gives infinite loop (to the code). Expected result: 2. \$\endgroup\$ Commented Sep 12 at 13:27
  • \$\begingroup\$ @Fmbalbuena Updated \$\endgroup\$ Commented Sep 12 at 13:34
  • \$\begingroup\$ 340 bytes \$\endgroup\$ Commented Sep 13 at 4:07
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Sorry, I don't understand what you're asking; NSTTNNNNN isn't a valid input. \$\endgroup\$ Commented Sep 16 at 13:08
  • \$\begingroup\$ Yes I make one error in pharentesis \$\endgroup\$ Commented Sep 16 at 13:18
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.