13
\$\begingroup\$

Dotcomma is a simple esolang I made a while ago that only uses four operators: [.,]. In this challenge, you'll determine if a dotcomma program consisting only of [.] halts. Without ,, there is no input, output, or queue, making this challenge possible.

Blocks:

Any code wrapped in [] is a block. All blocks and operators (.) have a return value. The inputted program will always consist of a single block, and the brackets will always be properly nested.

Operators:

The . operator's return value depends on what it is preceded by:

  • Any number of blocks: The sum of the blocks' return values
  • A dot: The previous .'s return value will be kept
  • The beginning of a block ([): 1

If a . is followed by a block, it will be treated as a loop. The loop will run only if the .s return value is not 0, and if the block being looped returns 0 at any point it will terminate.

If a . is followed by the end of a block (]), the .'s return value will be used as the block's. Otherwise, a block's return value is 0.

Examples:

[]

Returns true. There are no loops.

[[].[]]

Returns true. The . takes the return value of the first nested block, which is 0, skipping the second.

[.[]]

Returns true. The . returns 1, but the loop terminates immediately as the block returns 0.

[.[.]]

Returns false. The . returns 1, and the block being looped returns 1, creating an infinite loop.

[[.][].[.]]

Returns false. The [.] returns 1, which is added to the 0 returned by the [], resulting in 1 and causing the loop body to be run.

Other:

You may return a truthy/falsy value in your language (representing either whether it halts or does not, your choice), or two consistent values for halting and non-halting.

This is . Shortest answer in bytes (per language) wins.

\$\endgroup\$
7
  • \$\begingroup\$ what is the return value of [.[].]. \$\endgroup\$
    – tsh
    Apr 28, 2021 at 4:52
  • \$\begingroup\$ May a dot comes first in program? \$\endgroup\$
    – tsh
    Apr 28, 2021 at 4:58
  • \$\begingroup\$ @tsh [.[].] would return 0, because the [] would return 0 (and only be run once). This isn't an [interpreter] challenge, though, so you only need to worry about whether it halts or not. For [.[].], it would halt, because the [] only runs once. The program will always start with [ and end with ], but the character after the first [ can be a .. Hope this helps! \$\endgroup\$ Apr 28, 2021 at 5:04
  • 1
    \$\begingroup\$ @tsh It'll always be 0 if it's not an infinite loop. So [.[].[.]] would halt. \$\endgroup\$ Apr 28, 2021 at 12:27
  • 1
    \$\begingroup\$ @Zolastro No, because this subset of dotcomma is not turing complete. It's possible to, rather easily, determine if any program using just . and [] contains an infinite loop. \$\endgroup\$ Feb 24, 2022 at 14:27

2 Answers 2

6
\$\begingroup\$

Python 3, 215 bytes

m,v,*d=-1,[],
L,*l=0,
for c in input():
	if c>"[":a=v.pop();l.pop()*a and exit(1);d.pop();d or exit(0);v[m]=v[m]*(d[m]%2)+a;d[m]=1
	elif c>"Z":l+=[L and v[m]];v+=0,;d+=0,
	else:v[m]=v[m]if d[m]else 1;d[m]=2
	L=c<"A"

Try it online!

Exit code 0 if it will halt, 1 otherwise.

This is just a naive implementation of the interpreter, but golfed down. Here's a ungolfed version with debug output.

+12 bytes to fix a bug
-8 bytes thanks to Unrelated String

\$\endgroup\$
6
  • 1
    \$\begingroup\$ My understanding is that [[.].[].[.]] should not halt, but your program returns 1. (I'm not completely confident in my understanding, though...) \$\endgroup\$
    – kops
    Apr 23, 2021 at 20:33
  • 1
    \$\begingroup\$ @kops i return 1 if it will not halt \$\endgroup\$
    – hyper-neutrino
    Apr 23, 2021 at 20:34
  • 1
    \$\begingroup\$ Oops, typo in my comment... my understanding is that that program should halt, sorry. \$\endgroup\$
    – kops
    Apr 23, 2021 at 20:35
  • 1
    \$\begingroup\$ it should halt tho. i'll fix that when i get home \$\endgroup\$
    – hyper-neutrino
    Apr 23, 2021 at 20:35
  • 1
    \$\begingroup\$ @UnrelatedString Oh, thanks. That golf actually saves me an additional byte after I fixed the bug :P \$\endgroup\$
    – hyper-neutrino
    Apr 25, 2021 at 19:46
1
\$\begingroup\$

05AB1E, 37 bytes

„[.Å?·.$Δ„..¤:„[]0:…[.]1:DS„0.ìK}„1]å

Outputs 0 if it halts; 1 if it does not halt.

I'm not 100% sure if my approach is correct. It does work for all test cases, including those mentioned in the comments of the challenge and the Python answer. If there is any test case it'll fail for, I'll delete and try to fix it.

Try it online or verify all test cases. (NOTE: Wrap the input of the singular TIO in """ quotes, otherwise it'll interpret the input as a list and gives an error.)

Explanation:

          # If the input starts with "[.", remove it:
„[.Å?     #  Check if the (implicit) input-string starts with "[."
     ·    #  Double this (0 if falsey; 2 if truthy)
      .$  #  Remove that many leading characters from the (implicit) input
Δ         # Keep doing the following until the result no longer changes:
          #  Collapse all multiple adjacent "." to a single ".":
 „..      #   Push string ".."
    ¤     #   Push its last character (without popping): "."
     :    #   Keep replacing all ".." to "." until none are left
 „[]0:    #  Replace all "[]" with a 0
 …[.]1:   #  Replace all "[.]" with a 1
          #  Remove all "0.x" substrings, where `x` can be any character
 D        #   Duplicate the string
  S       #   Convert it to a list of characters
   „0.ì   #   Prepend a "0." in front of each
       K  #   Remove all those substrings from the string
}„1]å     # After the loop: check if the string contains "1]"
          # (after which the result is output implicitly)

I could also add an additional remove of all "1." within the loop, and then check if the final result contains a 1, but just checking if it contains a "1]" is shorter.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.