27
\$\begingroup\$

Introduction

Decide whether a Hexagony program composed solely of the characters .)_|\/><@ will halt using least bytes.

Challenge

Hexagony is a language developed by Martin Ender in which the source code is presented in the form of a hexagon. It has been extensively used in PPCG and there has been many impressive submissions using this language. Your task is to take a Hexagony program in its short form (one liner) that contains the characters .)_|\/><@ only and decide whether it will halt.

Since a challenge should be self-contained (per comment by @Mr.Xcoder), the language specifications related to this challenge is given in the appendix. If there is anything unclear you can refer to the document itself, which I believe is pretty clear.

You can use a set of output values as truthy and another set as falsy provided that the intersection of the two sets is empty, and at least one of them should be finite (Thanks@JonathanAllan for fixing the loophole). Please indicate in the answer which sets you will use.

You can use TIO to check whether a Hexagony program halts within 60 seconds.

Bonus point for solutions in Hexagony!

Test cases

Input
Hexagonal Form
Output

.
.
False

.....@
 . .
. . .
 @ .
False

)\..@
 ) \
. . @
 . .
True

.\|<..@
 . \
| < .
 . @
False

)\|<..@
 ) \
| < .
 . @
True

..\...@|.<.\....>._ 
  . . \
 . . . @
| . < . \
 . . . .
  > . _
False

Specs

  • The input is a string or an array of characters of a Hexagony program in its short form

  • The length of the program will be less than or equal to 169 characters (side length of 8)

  • To reiterate, please clarify the truthy/falsy value sets you use in the answer

  • Your program should halt for all valid inputs. Halting with error is fine as long as a truthy/falsy value is written to stdout or its closest equivalent in your language. (Thanks @moonheart08 for pointing out this)

  • This is , the lowest number of bytes wins.

  • As usual, default loopholes apply here.

Appendix: Hexagony language specs related to this challenge

Overview

Source code

The source code consists of printable ASCII characters and line feeds and is interpreted as a pointy-topped hexagonal grid, where each cell holds a single-character command. The full form of the source code must always be a regular hexagon. A convenient way to represent hexagonal layouts in ASCII is to insert a space after each cell and offset every other row. A hexagon of side-length 3 could be represented as

  . . .
 . . . .
. . . . .
 . . . .
  . . .

Within the scope of this challenge, the source code is padded to the next centered hexagonal number with no-ops (.s) and rearranged it into a regular hexagon. This means that the spaces in the examples above were only inserted for cosmetic reasons but don't have to be included in the source code.

For example, abcdefgh and abcdef will be padded to

  a b c
 d e f g            a b
h . . . .   and    c d e  ,   respectively.
 . . . .            f .
  . . .

Control flow

Within the scope of this challenge, the IP of Hexagony start at the top left corner of the hexagon moving to the right. There are commands which let you change the directions of IP movement based on its current direction and the value in the memory.

The edges of the hexagon wrap around to the opposite edge. In all of the following grids, if an IP starts out on the a moving towards the b, the letters will be executed in alphabetical order before returning to a:

   . . . .          . a . .          . . k .          . g . .   
  a b c d e        . . b . .        . . j . .        . h . . a  
 . . . . . .      g . . c . .      . . i . . e      . i . . b . 
. . . . . . .    . h . . d . .    . . h . . d .    . j . . c . .
 f g h i j k      . i . . e .      . g . . c .      k . . d . . 
  . . . . .        . j . . f        f . . b .        . . e . .  
   . . . .          . k . .          . . a .          . f . .   

If the IP leaves the grid through a corner in the direction of the corner there are two possibilities:

-> . . . .   
  . . . . .  
 . . . . . . 
. . . . . . . ->
 . . . . . . 
  . . . . .  
-> . . . .   

If value in the memory is non-zero, the IP will continue on the bottom row. If it's zero, the IP will continue on the top row. For the other 5 corners, just rotate the picture. Note that if the IP leaves the grid in a corner but doesn't point at a corner, the wrapping happens normally. This means that there are two paths that lead to each corner:

      . . . . ->   
     . . . . .  
    . . . . . . 
-> . . . . . . .
    . . . . . . 
     . . . . .  
      . . . . ->

Memory model

In the scope of this challenge, the memory is a single cell containing an unbounded unsigned integer, and is initialized to zero before the start of the program.

Command list

The following is a reference of all commands relevant to this challenge.

  • . is a no-op: the IP will simply pass through.
  • @ terminates the program.
  • ) increments the value in the memory
  • _, |, /, \ are mirrors. They reflect the IP in the direction you'd expect. For completeness, the following table shows how they deflect an incoming IP. The top row corresponds to the current direction of the IP, the left column to the mirror, and the table cell shows the outgoing direction of the IP:

    cmd   E SE SW  W NW NE
    
     /   NW  W SW SE  E NE
     \   SW SE  E NE NW  W
     _    E NE NW  W SW SE
     |    W SW SE  E NE NW
    
  • < and > act as either mirrors or branches, depending on the incoming direction:

    cmd   E SE SW  W NW NE
    
     <   ?? NW  W  E  W SW 
     >    W  E NE ?? SE  E
    

    The cells indicated as ?? are where they act as branches. In these cases, if the value in the memory is non-zero, the IP takes a 60 degree right turn (e.g. < turns E into SE). If the value is zero, the IP takes a 60 degree left turn (e.g. < turns E into NE).

Example

This is a program taken from the test case: )\..@. Its full form is

 ) \
. . @
 . .

And here is how it executes before coming to a halt. To make it terse I will number the cells in the hexagon and use the notation 1E) if the IP is currently at cell 1, executes the instruction ) and is heading east after execution of the instruction.

 1 2
3 4 5
 6 7

The IP starts from cell 1 heading east. The memory cell was initialized to 0.

  1. 1E), memory cell is now 1
  2. 2\SW, the IP is reflected
  3. 4SW., no-op.
  4. 6SW., no-op. Then it branches, as the memory cell is nonzero, it wraps to cell 1 instead of cell 5.
  5. 1SW), memory cell is now 2.
  6. 3SW., no-op.
  7. 2E\, the IP is reflected then wrapped.
  8. 3E., no-op.
  9. 4E., no-op.
  10. 5E@, the program halts.

Credits to @MartinEnder, @FryAmTheEggman and @Nitrodon for their helpful comments.

@FryAmTheEggman brought the issue of decidablity of halting problems of programs with both ( and ) to attention.

@MartinEnder pointed out that if ( and ) cannot appear in the same program then ( can be dropped entirely.

@Nitrodon gave a simple proof for the decidability of the halting problem for programs with both ( and ).

\$\endgroup\$
  • 3
    \$\begingroup\$ The version with both ( and ) is decidable. In a program that doesn't halt, the memory edge will flip its sign either finitely often or infinitely often, and both cases lead to a loop that can be detected. \$\endgroup\$ – Nitrodon Feb 28 '18 at 17:49
  • 1
    \$\begingroup\$ Maybe useful, if someone feels like going the extra <s>mile</s> parsec... \$\endgroup\$ – Khuldraeseth na'Barya Mar 1 '18 at 12:11
  • 2
    \$\begingroup\$ @WeijunZhou No, the entire program looks like a flat-topped hexagon, but the grid itself is pointy-topped (because there are horizontally adjacent cells, but no vertically adjacent cells). \$\endgroup\$ – Martin Ender Mar 1 '18 at 17:10
  • 3
    \$\begingroup\$ @moonheart08 Unless the challenge allows it explicitly, all answers have to terminate. \$\endgroup\$ – Martin Ender Mar 2 '18 at 15:51
  • 5
    \$\begingroup\$ Theorem: If a Simplified Hexagony doesn't halt after (full program size) * 12 steps (= 12 * ((side length) * (side length - 1) * 3 + 1)), it will run forever. For side length 8, that is 2028 steps. \$\endgroup\$ – user202729 Mar 8 '18 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.