Find the longest snake on a grid

Question

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 code-golf 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:
#####
....#
#####
#....
#####

Answer 1

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.

Answer 2

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]])
    }
}

Answer 3

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
      }
    )
}  

Answer 4

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
    )

Answer 5

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

Answer 6

Charcoal, 76 bytes

ＷＳ⊞υι≔⪫υ¶θ≔⟦ω⟧ηＦηＦＥ⁴⁺ικ«Ｊ⁰¦⁰Ｐθ…θ⌕θ@Ｆκ✳⊗λ#¿∧›ＫＫ#‹№ＫＶ#²¿⁼ＫＫ@«#≔ＫＡζ»⊞ηκ»ＵＭＫＡ§ζκ

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:

ＷＳ⊞υι≔⪫υ¶θ

Input the field.

≔⟦ω⟧ηＦη

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

ＦＥ⁴⁺ικ«

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

Ｊ⁰¦⁰Ｐθ…θ⌕θ@

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

Ｆκ✳⊗λ#

Print the path.

¿∧›ＫＫ#‹№ＫＶ#²

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

¿⁼ＫＫ@«

If we reached the other endpoint,

#≔ＫＡζ

then overwrite it with a # and save the canvas.

»⊞ηκ

Otherwise add this path to the search candidates.

»ＵＭＫＡ§ζκ

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