21
\$\begingroup\$

Background

A snake is a path over the cells of a square grid, such that it doesn't touch itself on a side of a unit square. Touching at a corner is allowed.

An example snake:

##.#.
.#.##
##..#
#.###
###..

Some example non-snakes:

###.#
#.#.#
#####
.#...
.####

###
.#.

##
##

Challenge

Given an empty grid with the two endpoints of a snake marked on it, find the longest possible snake that fits on the grid. If there are multiple answers having the same length, you may choose to output one or all of them.

The input can be given as a character matrix (or equivalent) with two endpoints marked on it, or the dimensions (width, height) and the coordinates of the endpoints. You may choose to output the grid containing the snake or a list of coordinates of cells occupied by the snake (or equivalent).

Standard rules apply. The shortest code in bytes wins.

Example I/O

Each I/O example is given as a character matrix, # being the part of the snake.

Input:
..#...#...
Output:
..#####...

Input: (corner case)
......
......
..##..
......
......
......
Output: same as input (no way to get longer without violating no-touch condition)

Input:
..#.#
.....
.....
.....
Output:
###.#
#...#
#...#
#####

Input:
#....
.....
.....
.....
....#
Output:
#####
....#
#####
#....
#####
\$\endgroup\$
4
  • 2
    \$\begingroup\$ I feel like shortest code here would be to generate all the possible solutions and then just pick one with longest snake \$\endgroup\$ – NoOorZ24 Jun 3 '20 at 12:26
  • \$\begingroup\$ Can we input the endpoint positions as x+w*y (that is, their positions in row-major order)? \$\endgroup\$ – the default. Jun 3 '20 at 16:26
  • \$\begingroup\$ @mypronounismonicareinstate No. \$\endgroup\$ – Bubbler Jun 4 '20 at 6:55
  • \$\begingroup\$ Can the input endpoints be marked in different characters? \$\endgroup\$ – Neil Jun 5 '20 at 21:09
5
\$\begingroup\$

Python 3.8 (pre-release), 207 194 181 bytes

-7 bytes thanks to @ovs

Input

The width \$ w \$, the height \$ h \$, the starting point \$ s \$, and the ending point \$ e \$. \$ s \$ and \$ e \$ are complex numbers which represent the coordinates of the endpoints.

Output

A list of points, in the form of complex numbers.


C={1,-1,1j,-1j}
def f(w,h,s,e):P=[[s]];exec("P=[j+[t+(t==e==(A:=j+[t]))]for j in P for k in C if w>(t:=j[-1]+k).real>-1<t.imag<h>0<all({t+l}-{*j}for l in{0}|C-{-k})];"*w*h);return A

Try it online!

Explanation

We use a breadth-first search to search for all possible snakes, starting at \$ s \$, making sure that the next tile is not adjacent to any previous tile, and that we do not go past the boundary. After each iteration, we check for all paths whose last element is \$ e \$, meaning that we have found a complete path from \$ s \$ to \$ e \$. Instead of storing all complete paths and returning the one with maximum length, we can simply return the last path found, since breadth-first search already searches for paths by length.

\$\endgroup\$
2
  • \$\begingroup\$ -7 by replacing the inner for-loop with [j[-1]==e!=(A:=j)for j in P]. \$\endgroup\$ – ovs Jun 4 '20 at 6:39
  • \$\begingroup\$ @ovs Thanks for the improvement :) \$\endgroup\$ – dingledooper Jun 4 '20 at 17:17
4
\$\begingroup\$

R, 275 272 251 229 206 197 bytes

f=function(p,m){a=p+cbind(-1:0,1:0,0:-1,0:1)
v=m[a<-t(a[,!colSums(!a|a>dim(m))])]
t=sum(!!v)
m[t(p)]=2
`if`(t<3&any(v==1),m,if(t<2)(s<-lapply(split(a,seq(v))[!v],f,m))[[which.max(sapply(s,sum))]])}

Try it online!

Edits 1-4: -69 bytes by using increasingly-arcane golfing obfuscations

Edit 5: -9 more bytes by removing useless explicit return of NULL for 'touching' cases, and instead just falling-off the end of the function

Recursive function:

  • find adjacent squares
  • count touching squares
  • mark position (differently to finish point)
  • if touching < 3 and we're touching the finish: return the matrix
  • else if touching > 1 (it's either a loop or an illegal position): return NULL
  • otherwise (there should always be at least one adjacent empty square left)
    • call self recursively with each adjacent empty square to get snakes from this position
    • return the longest snake

Code before golfing:

longest_snake=function(pos,matrix){

    # find adjacent squares
    d=dim(matrix)
    adjacent_squares=lapply(list(-1:0,1:0,0:-1,0:1),function(p){n=pos+p;if(all(n>0 & n<=d)){n}})
    adjacent_squares=do.call(rbind,adjacent_squares)

    # count touching squares
    adjacent_vals=matrix[adjacent_squares]
    touching=sum(!!adjacent_vals)

    # mark current position (differently to end, which is 1)
    matrix[pos]=2

    # if touching<3 & pos is touching finish => return matrix
    if((touching<3)&&any(adjacent_vals==1)){ return( matrix ) }

    # else if touching>1 then its either an illegal position or a loop  
    else if(touching>1){ return( NULL ) }

    else { # there should always be at least one adjacent empty square

        # now consider each of the adjacent empty squares
        new_pos=lapply(which(adjacent_vals==0),function(i) adjacent_squares[i,,drop=F])

        # get the longest snake from each of them
        snakes_from_here=lapply(new_pos,longest_snake,matrix)

        # and return the longest of these
        longest=which.max(sapply(snakes_from_here,sum))
        return(snakes_from_here[[longest]])
    }
}
\$\endgroup\$
2
\$\begingroup\$

R, 178 169 164 161 bytes

f=function(s,e,w,h,l=length,`/`=c,`*`=`%in%`,k=s[1]-1/-1i/-1/1i)if(!any(s[-2]*k))`if`(e*k,s/e,{for(j in k[Re(k)*1:w&Im(k)*1:h])if(l(F)<l(n<-f(j/s,e,w,h)))F=n;F})

Try it online!

This works with complex numbers, similarly to @dingledooper's answer. Inputs are 1-indexed coordinates of start and end points, as well as width and height of the grid. Output is a vector of points which form the snake.

Explanation

f = function(s, e, w, h) # start, end, width, height
{ # Select points to try at next iteration as neighbors of the snake head cell:
  k = s[1] + c(-1,1i,1,-1i) 
  # To avoid touches, only proceed if none of k points are already in snake:
  if(!any(s[-2] %in% k)) #s[2] is an exception - this is where we came from
    `if`(e %in% k, # If the neighbors include the endpoint, then...
      c(s,e)       # The loop is closed, add the endpoint to snake and return
      {# Loop through k, filtered so that all points fit in 1:w by 1:h grid:
        for(j in k[Re(k) %in% 1:w & Im(k) %in% 1:h])
        { # Prepend j to snake, and construct it further by recursive call:
          n <- f(c(j, s), e, w, h)
          if(length(F) < length(n))
            F = n # Select the longest snake that we encountered        
        }
        F # Return the longest snake
      }
    )
}  
\$\endgroup\$
5
  • \$\begingroup\$ You need to check for touches before checking you've reached the endpoint: otherwise, if they both happen at once, you'll accidentally register an 'illegal' snake like this \$\endgroup\$ – Dominic van Essen Jun 5 '20 at 19:25
  • \$\begingroup\$ ...but, otherwise, the complex number-based indexing is very nice and I'm jealous I didn't think of it myself! \$\endgroup\$ – Dominic van Essen Jun 5 '20 at 19:26
  • \$\begingroup\$ Well, technically the Python answer posted the same technique before me! Anyway, thanks for pointing the mistake, it looks like a direct swap of the order of conditions fixes it. \$\endgroup\$ – Kirill L. Jun 5 '20 at 19:58
  • \$\begingroup\$ Wow - /=c is a super sneaky-trick! \$\endgroup\$ – Dominic van Essen Jun 6 '20 at 9:57
  • \$\begingroup\$ (I tried to write that in a formatted way, but finding a valid combination of triple-backticks, escaped-backtick and escaped / character together got the better of me...) \$\endgroup\$ – Dominic van Essen Jun 6 '20 at 10:00
1
\$\begingroup\$

Python 3.8 (pre-release), 214 bytes

Takes a 1D boolean array g where the endpoints are marked True, and returns a 1D boolean array where snake tiles are marked True.

Try it online!

lambda w,h,g:max((list(map(v,range(w*h)))for x in range(2<<(w*h))if all((v:=lambda i:0<=i<w*h and(g[i]or x>>i&1))(i)==0 or(i%w>0 and v(i-1))+(i%w<w-1 and v(i+1))+v(i-w)+v(i+w)+g[i]==2 for i in range(w*h))),key=sum)

Explanation:

def f(w, h, g):
    return max(
        (
            # Brute force all possible grid configurations by counting in binary.
            # For each iteration, let the ith binary digit of x signify
            # whether the ith tile is considered part of the snake.
            [v(i) for i in range(w*h)] # <- Return a boolean array.
            for x in range(2<<(w*h))

            # Check if there is a valid snake path.
            if all(
                # The ith tile is part of the path if it's a given endpoint (g[i])
                # or the ith binary digit of x is 1 (x>>i&1).
                ( v:=lambda i:0<=i<w*h and (g[i] or x>>i&1) )(i) == 0
                # For a grid to have a valid snake path,
                # every tile must either not be part of the snake (v(i) == 0)...
                or
                # ...or the tile must have exactly 2 neighbors in the snake path.
                # (If the tile is an endpoint (g[i]), count itself as a neighbor.)
                (i%w>0 and v(i-1)) + (i%w<w-1 and v(i+1)) + v(i-w) + v(i+w) + g[i]
                == 2

                # Repeat this check for every tile.
                for i in range(w*h)
            )
        ),

        # Use max() to find the grid configuration with the most snake tiles;
        # that is, the most times that v(i) == True.
        key=sum
    )
\$\endgroup\$
1
  • 8
    \$\begingroup\$ Your conditions aren't sufficient. Certain illegal combination still satisfy the condition that each square is either 1) an endpoint, 2) isn't occupied or 3) has exactly two neighours. Disconnected loops for instance. A tiny modification of your test input shows that. I don't think you can solve this by looking locally, you need at least one global condition. \$\endgroup\$ – Abigail Jun 3 '20 at 13:43
1
\$\begingroup\$

JavaScript (Node.js), 199 bytes

s=>(o=g=(t,k,h=c=>t.replace(/2/,c),a=h(0),b=h(1),m=2*~s[0].length)=>a==b?[...a].some((_,i)=>_&1&~1<<B[i]>>a[i-m]>>a[i+m]>>a[i-2]>>a[i+2]|k<o)||(o=k,r=a):g(a,k)|g(b,-~k))(B=JSON.stringify(s))&&eval(r)

Try it online!

Seems this way is not that good one

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 76 bytes

WS⊞υι≔⪫υ¶θ≔⟦ω⟧ηFηFE⁴⁺ικ«J⁰¦⁰Pθ…θ⌕θ@Fκ✳⊗λ#¿∧›KK#‹№KV#²¿⁼KK@«#≔KAζ»⊞ηκ»UMKA§ζκ

Try it online! Link is to verbose version of code. Takes input as two @ endpoints in a field of ASCII characters greater than # (e.g. .). Explanation:

WS⊞υι≔⪫υ¶θ

Input the field.

≔⟦ω⟧ηFη

Start a breadth-first search with an empty path, and for each path...

FE⁴⁺ικ«

... search over the four possible paths formed by concatenating each direction.

J⁰¦⁰Pθ…θ⌕θ@

Print the field and move to the position of the first endpoint.

Fκ✳⊗λ#

Print the path.

¿∧›KK#‹№KV#²

Test whether the current position is legal (not off the edge, doubled back, or touching itself).

¿⁼KK@«

If we reached the other endpoint,

#≔KAζ

then overwrite it with a # and save the canvas.

»⊞ηκ

Otherwise add this path to the search candidates.

»UMKA§ζκ

Restore the canvas from the saved last (i.e. longest) path that reached the other endpoint.

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