# Find the longest snake on a grid

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

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

# Python 3.8 (pre-release), 207194 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.

• -7 by replacing the inner for-loop with [j[-1]==e!=(A:=j)for j in P].
– ovs
Jun 4, 2020 at 6:39
• @ovs Thanks for the improvement :) Jun 4, 2020 at 17:17

# R, 275272251229206 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:

• 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){

d=dim(matrix)

# count touching squares

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

# if touching<3 & pos is touching finish => 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

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


# R, 178169164 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
}
)
}

• 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 Jun 5, 2020 at 19:25
• ...but, otherwise, the complex number-based indexing is very nice and I'm jealous I didn't think of it myself! Jun 5, 2020 at 19:26
• 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. Jun 5, 2020 at 19:58
• Wow - /=c is a super sneaky-trick! Jun 6, 2020 at 9:57
• (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...) Jun 6, 2020 at 10:00

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

• 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. Jun 3, 2020 at 13:43

# 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

# 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.