15
\$\begingroup\$

A Hamiltonian path in a graph is a path that visits each vertex exactly once; a Hamiltonian cycle is a Hamiltonian path that is a cycle – the path forms a simple closed loop. In this challenge the graph will be a n x n grid, where n is an even number greater than 2. Here is an example of a Hamiltonian cycle on 12x12 rectangular grid:

+---------------+   +-----------------------+
|               |   |                       |
+-----------+   |   +---+   +-----------+   |
            |   |       |   |           |   |
+-------+   |   +---+   |   +-------+   |   |
|       |   |       |   |           |   |   |
|   +---+   |   +---+   |   +-------+   +---+
|   |       |   |       |   |               
|   +-------+   +---+   |   +---------------+
|                   |   |                   |
+---+   +-------+   |   |   +-----------+   |
    |   |       |   |   |   |           |   |
+---+   +---+   |   +---+   +---+   +---+   |
|           |   |               |   |       |
+---+   +---+   |   +-----------+   +---+   |
    |   |       |   |                   |   |
+---+   +---+   |   +---+   +-------+   |   |
|           |   |       |   |       |   |   |
+-------+   |   +-------+   +---+   |   |   |
        |   |                   |   |   |   |
+-------+   |   +---------------+   +---+   |
|           |   |                           |
+-----------+   +---------------------------+

The path visits each vertex exactly once and forms a simple closed loop that do not intersect or touches itself. The grid points are not shown so that the ASCII graphic is not cluttered. There are three - (---) between two horizontally connected vertices or 3 spaces if the vertices are not connected. A single | connects two vertically adjacent vertices, spaces are used otherwise. Since the grid is not visible, the + is used only where the path takes a turn. The path will never be broken - if a segment connects two vertices, it will be --- and never - -.

Task:

You will be given an ASCII representation of a path and you need to check if it is a Hamiltonian cycle on a grid. Write a full program or a function that solves this problem.

Input:

ASCII representation of a path. It can be: - A mutliline string; - A list of strings - A list/array of characters or any format that is convenient for you. You can have an optional parameter n for the size of the grid. You can use alternatve ASCII representation, just explain it.

Output:

  • A consistent value indicating that the path is a Hamiltonian cycle on a grid
  • A consistent value indicating that the path is not a Hamiltonian cycle on a grid. There can be several reasons for this: The path doesn’t visit all vertices; the path crosses/touches itself; there are two or more paths and not a single one. You don’t need to specify the reason – just return/print a consistent falsy value.

Test cases:

Truthy:

Optional `n` = 6

+-----------+   +---+
|           |   |   |
|   +-------+   |   |
|   |           |   |
|   +-----------+   |
|                   |
+---+   +-------+   |
    |   |       |   |
+---+   +---+   |   |
|           |   |   |
+-----------+   +---+

+-------------------+
|                   |
|   +---------------+
|   |               
|   |   +-----------+
|   |   |           |
|   |   |   +---+   |
|   |   |   |   |   |
|   +---+   |   |   |
|           |   |   |
+-----------+   +---+

+---+   +-----------+
|   |   |           |
|   |   |   +-------+
|   |   |   |       
|   |   |   +-------+
|   |   |           |
|   +---+   +-------+
|           |       
|   +---+   +-------+
|   |   |           |
+---+   +-----------+


Optional `n` = 8

+---------------------------+
|                           |
+---+   +-----------+   +---+
    |   |           |   |   
+---+   +---+   +---+   +---+
|           |   |           |
|   +---+   |   +---+   +---+
|   |   |   |       |   |   
+---+   |   +---+   |   +---+
        |       |   |       |
+---+   +-------+   +---+   |
|   |                   |   |
|   +-------------------+   |
|                           |
+---------------------------+

+-------------------+   +---+
|                   |   |   |
+-------+   +---+   |   |   |
        |   |   |   |   |   |
+---+   |   |   |   +---+   |
|   |   |   |   |           |
|   |   +---+   |   +---+   |
|   |           |   |   |   |
|   +-----------+   |   |   |
|                   |   |   |
+---+   +-----------+   |   |
    |   |               |   |
+---+   +-----------+   |   |
|                   |   |   |
+-------------------+   +---+

+---+   +-------------------+
|   |   |                   |
|   |   +---+   +-----------+
|   |       |   |           
|   +---+   |   +-----------+
|       |   |               |
|   +---+   +---+   +---+   |
|   |           |   |   |   |
|   +-----------+   |   |   |
|                   |   |   |
|   +-------+   +---+   |   |
|   |       |   |       |   |
|   |   +---+   +---+   |   |
|   |   |           |   |   |
+---+   +-----------+   +---+


Optional `n` = 12

+---+   +-----------+   +-------------------+
|   |   |           |   |                   |
|   |   +-------+   |   +---+   +-----------+
|   |           |   |       |   |           
|   +-------+   |   +-------+   +---+   +---+
|           |   |                   |   |   |
|   +-------+   +---+   +-------+   |   |   |
|   |               |   |       |   |   |   |
|   +---------------+   |   +---+   +---+   |
|                       |   |               |
|   +-------+   +-------+   +-----------+   |
|   |       |   |                       |   |
|   |   +---+   |   +-------------------+   |
|   |   |       |   |                       |
|   |   +-------+   +-----------------------+
|   |                                       
|   +-------------------------------+   +---+
|                                   |   |   |
+-------+   +-------+   +---+   +---+   |   |
        |   |       |   |   |   |       |   |
+-------+   +---+   |   |   |   +-------+   |
|               |   |   |   |               |
+---------------+   +---+   +---------------+

+---+   +---------------------------+   +---+
|   |   |                           |   |   |
|   |   |   +-------+   +-----------+   |   |
|   |   |   |       |   |               |   |
|   |   |   +---+   |   +-------+   +---+   |
|   |   |       |   |           |   |       |
|   |   +---+   |   |   +---+   |   |   +---+
|   |       |   |   |   |   |   |   |   |   
|   +-------+   |   +---+   |   +---+   +---+
|               |           |               |
+---+   +---+   |   +---+   +-------+   +---+
    |   |   |   |   |   |           |   |   
+---+   |   |   +---+   +---+   +---+   +---+
|       |   |               |   |           |
|   +---+   +---------------+   +---+   +---+
|   |                               |   |   
|   +-----------+   +---+   +-------+   +---+
|               |   |   |   |               |
|   +-------+   |   |   |   |   +-------+   |
|   |       |   |   |   |   |   |       |   |
|   |   +---+   |   |   +---+   +---+   |   |
|   |   |       |   |               |   |   |
+---+   +-------+   +---------------+   +---+

+---------------------------+   +---+   +---+
|                           |   |   |   |   |
|   +---------------+   +---+   |   +---+   |
|   |               |   |       |           |
|   |   +---+   +---+   +-------+   +---+   |
|   |   |   |   |                   |   |   |
|   +---+   |   +---------------+   |   |   |
|           |                   |   |   |   |
+-------+   +---+   +-----------+   |   |   |
        |       |   |               |   |   |
+---+   |   +---+   |   +-----------+   |   |
|   |   |   |       |   |               |   |
|   +---+   |   +---+   |   +-----------+   |
|           |   |       |   |               |
|   +-------+   +---+   |   |   +-------+   |
|   |               |   |   |   |       |   |
|   |   +-----------+   |   |   |   +---+   |
|   |   |               |   |   |   |       |
|   |   |   +-------+   |   +---+   +---+   |
|   |   |   |       |   |               |   |
|   |   |   |   +---+   +-------+   +---+   |
|   |   |   |   |               |   |       |
+---+   +---+   +---------------+   +-------+

Falsy:

Optional `n` = 6

; Two paths
+-------------------+
|                   |
|   +-----------+   |
|   |           |   |
|   +-----------+   |
|                   |
+-------+   +-------+
        |   |       
+-------+   +-------+
|                   |
+-------------------+

; Two paths
+-------+   +-------+
|       |   |       |
|   +---+   +-------+
|   |               
|   +---------------+
|                   |
|   +-----------+   |
|   |           |   |
|   +---+   +---+   |
|       |   |       |
+-------+   +-------+

; The path doesn't visit each vertex
+-----------+   +---+
|           |   |   |
|           |   |   |
|           |   |   |
+-------+   +---+   |
        |           |
+---+   +---+   +---+
|   |       |   |   
|   +-------+   +---+
|                   |
+-------------------+

; The path doesn't visit each vertex and touches itself
; (so visits some points more than once)
+-------------------+
|                   |
|   +-----------+   |
|   |           |   |
|   |   +-------+   |
|   |   |           |
|   |   +-------+   |
|   |           |   |
+---+-----------+   |
    |               |
    +---------------+

; The path doesn't form a loop and touches itself
+---+   +---+   +---+
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   |
|   |   |   |   |   | 
+---+---+   +---+---+

Optional `n` = 8

; Two paths
+-------------------+   +---+
|                   |   |   |
|   +-----------+   |   |   |
|   |           |   |   |   |
|   +-------+   |   +---+   |
|           |   |           |
+-------+   |   +-----------+
        |   |               
+---+   +---+   +-----------+
|   |           |           |
|   |   +---+   |   +-------+
|   |   |   |   |   |       
|   +---+   +---+   +-------+
|                           |
+---------------------------+

; The path doesn't visit each vertex
+---------------+   +-------+
|               |   |       |
|   +-------+   +---+       |
|   |       |               |
|   |   +---+   +---+       |
|   |   |       |   |       |
|   |   +-------+   +-------+
|   |                       
|   |   +-------------------+
|   |   |                   |
|   +---+   +---+   +---+   |
|           |   |   |   |   |
|   +---+   |   |   |   |   |
|   |   |   |   |   |   |   |
+---+   +---+   +---+   +---+


; The path doesn't visit each vertex
+---------------+   +-------+
|               |   |       |
|   +-----------+   +---+   |
|   |                   |   |
|   +---+   +-----------+   |
|       |   |               |
+---+   |   +-------+   +---+
    |   |           |   |   
+---+   +-------+   |   |    
|               |   |   |    
|   +-----------+   |   |    
|   |               |   |   
|   +---------------+   +---+
|                           |
+---------------------------+

; Two paths
+-----------+   +-----------+
|           |   |           |
|   +---+   |   |   +-------+
|   |   |   |   |   |       
|   |   |   |   |   +-------+
|   |   |   |   |           |
+---+   |   |   +-------+   |
        |   |           |   |
+---+   |   +-----------+   |
|   |   |                   |
|   |   |   +-----------+   |
|   |   |   |           |   |
|   +---+   +-----------+   |
|                           |
+---------------------------+

; The path touches itself (so visits some points more than once)
+---+   +-------------------+
|   |   |                   |
|   |   |   +---+   +-------+
|   |   |   |   |   |       
|   +---+   |   |   |   +---+
|           |   |   |   |   |
+---+   +---+   |   |   |   |
    |   |       |   |   |   |
+---+   +-------+---+---+   |
|               |   |       |
+-------+   +---+   +---+   |
        |   |           |   |
+-------+   +-----------+   |
|                           |
+---------------------------+

; The path doesn't form a loop
+---------------+   +-------+
|               |           |
+-------+   +   +-------+   |
        |   |           |   |
+-------+   +-----------+   |
|                           |
|   +-------------------+   |
|   |                   |   |
|   +---+   +-----------+   |
|       |   |               |
|   +---+   +-----------+   |
|   |                   |   |
|   +---------------+   |   |
|                   |   |   |
+-------------------+   +---+

Wining criteria:

The shortest solution in bytes in each language wins. I'll highly appreciate if you add explanation of the code and the algorithm you used.

\$\endgroup\$
  • \$\begingroup\$ Do we have to use the ASCII representation given? Or can we use an alternative ASCII representation? \$\endgroup\$ – Nick Kennedy Oct 26 at 12:44
  • \$\begingroup\$ Are we allowed to take inputs drawn with only a single - (rather than ---) as the horizontal connector? \$\endgroup\$ – Jonah Oct 26 at 12:55
  • \$\begingroup\$ @Nick Kennedy Yes, you can. \$\endgroup\$ – Galen Ivanov Oct 26 at 13:44
  • \$\begingroup\$ @Jonah Yes, you can. \$\endgroup\$ – Galen Ivanov Oct 26 at 13:45
5
\$\begingroup\$

Charcoal, 63 55 46 bytes

AM↗ W⁼№KV#¹«✳⊗⁻¹⌕KV#¦ ¿¬∨﹪ⅈ⁴﹪ⅉ²⊞υω»¿‹LυXN²⎚«⎚¹

Try it online! Link is to verbose version of code. Edit: Saved 8 bytes by using a more cumbersome but still acceptable input format. Saved 9 bytes by requiring the path only uses #s. Explanation:

Copy the path to the canvas.

M↗ 

Print a space one square in from the bottom-left corner (the print command left the cursor one square below the bottom-left corner). This should break the loop of #s into a line.

W⁼№KV#¹«

Try to follow the line to its end, following the path of #s that used to have two neighbours.

✳⊗⁻¹⌕KV#¦ 

Overwrite the line as we go.

¿¬∨﹪ⅈ⁴﹪ⅉ²⊞υω»

Keep track of how many vertices we meet along the way.

 ¿‹LυXN²⎚

Check whether we managed to visit every vertex. If not, then just clear the canvas.

«⎚¹

If we visited every vertex then output 1 as a truthy value (which actually prints as -).

\$\endgroup\$
  • \$\begingroup\$ You can use alternatve ASCII representation. \$\endgroup\$ – Galen Ivanov Oct 26 at 13:49
  • \$\begingroup\$ @GalenIvanov Would this be acceptable? \$\endgroup\$ – Neil Oct 26 at 19:19
  • \$\begingroup\$ Yes, it is acceptable. \$\endgroup\$ – Galen Ivanov Oct 26 at 19:21
  • \$\begingroup\$ @GalenIvanov How about this? \$\endgroup\$ – Neil Oct 26 at 19:28
  • 1
    \$\begingroup\$ @GalenIvanov Thanks, but I think it would be possible to fool the algorithm in that case. \$\endgroup\$ – Neil Oct 26 at 20:05
5
\$\begingroup\$

Jelly, 34 bytes

Ø1©ȧn⁶µŒṪạ®SỊƊƇḢ©Wḟ@ƲƬṖṪ<3Ȧȧm2m€4Ȧ

A monadic Link accepting a list of lists of characters (the lines) which yields 1 for a Hamiltonian or 0 otherwise. Uses the layout in the question (any non-space chars as path parts will work).

Try it online! Or see the test-suite.

How?

Starts at the top-left, [1,1], and finds a neighbouring non-space until no neighbours can be found, then checks if the final position is the neighbour below the top-left, [2,1], (to confirm the path was a loop) and that no other non-spaces remain (to confirm there were not multiple paths). If so a final check is made that all the vertices were non-spaces too.

Ø1©ȧn⁶µŒṪạ®SỊƊƇḢ©Wḟ@ƲƬṖṪ<3Ȧȧm2m€4Ȧ - Link: list of lines, M
Ø1                                 - literal [1,1]
  ©                                - (copy this to the register and yield it)
   ȧ                               - logical AND (with M) -> M 
     ⁶                             - literal space character
    n                              - not equal? (vectorises)
      µ                            - new monadic chain, call that N
       ŒṪ                          - truthy multidimensional indices
                     Ƭ             - collect up while distinct, applying:
                    Ʋ              -   last four links as a monad:
              Ƈ                    -     filter keep if (find neighbours):
             Ɗ                     -       last three links as a monad:
         ạ                         -         absolute difference (vectorises):
          ®                        -           current register value
           S                       -         sum
            Ị                      -         insignificant? (abs(z)<=1)
               Ḣ                   -     head (a neighbour [x,y] or 0 if none)
                ©                  -     (copy this to the register and yield it)
                 W                 -     wrap in a list
                   @               -     with swapped arguments:
                  ḟ                -       filter discard
                      Ṗ            - remove rightmost
                       Ṫ           - get rightmost (or 0 if none)
                        <3         - less than three? (vectorises)
                          Ȧ        - all non-zero when flattened?
                           ȧ       - logical AND (with N) -> 
                                   - (i.e. N if the entire path looped from [1,1]
                                   -  back to [2,1] leaving nothing unconsumed
                                   -  else 0)
                            m2     - every 2nd value
                              m€4  - every 4th value of each
                                 Ȧ - all non-zero when flattened?
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES7),  126 124  122 bytes

Takes input as (n)(matrix). Returns a Boolean value.

n=>g=(m,X=k=0,Y=0,d=0)=>m.map((r,y)=>r.map((c,x)=>++c|(x-X)**2+(y-Y)**2-1||g(m,x,r[++d,x%4|y%2||k++,x]=y)))|d>1?k=g:k==n*n

Try it online!

How?

Starting at \$(0,0)\$, we flood-fill the path and increment a counter \$k\$ each time we go through a cell \$(x,y)\$ such that \$x\equiv 0\pmod 4\$ and \$y\equiv 0\pmod 2\$.

At the end of the process, we must have \$k=n^2\$.

We additionally make sure that no cell has more than 2 neighbors. If it does happen, we set \$k\$ to a non-numeric value to force the final test to fail.

\$\endgroup\$
  • \$\begingroup\$ You can use alternatve ASCII representation. \$\endgroup\$ – Galen Ivanov Oct 26 at 13:49
  • 1
    \$\begingroup\$ @GalenIvanov Thanks for the notification. That would not help much in my case, because I'm just testing space vs not-space. \$\endgroup\$ – Arnauld Oct 26 at 17:42
  • \$\begingroup\$ Can we take the input as a matrix of zeros and ones? \$\endgroup\$ – Jonah Oct 29 at 1:47
3
\$\begingroup\$

Jelly, 54 bytes

n⁶,Z$µØ0jm2N,¹ƇɗƝ)m2)Z×LƊ€2¦Ẏ€;"/µØ-ḟN}Ḣɗ,+¥ƭƒịṪ¥¥ƬL=L

Try it online!

A monadic link which takes a list of strings as input and returns a boolean. The strings use the format of the question but omitting every other character (so half the width). Full explanation to follow.

\$\endgroup\$
1
\$\begingroup\$

J, 125 bytes

p=.((,-)#:1 2)|.!.0]
f=.([:(''-:2 0~.@-.~[:,]*+/@p)' '~:])*1-1 e.[:([:,@(,]+1=(2|#\)*/4|#\@|:)([:>./]*"2 p)^:_)_(<0 0)}' '~:]

Try it online!

Just a first draft, but all test cases are passing. Will attempt to golf and add explanation this week.

\$\endgroup\$

Your Answer

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

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