Longest path through maze

Question

Finding the shortest path through a maze is boring. The scenic route is more interesting.

Write a program or function to find the longest possible path through a maze, visiting each space 0 or 1 times only.

The maze is given by rows of text: # is wall, is empty space. You cannot move through walls, nor outside the bounds of the maze, nor visit a space you have already visited.

You always begin in the top left cell, and exit by reaching the bottom right cell.

For example:

______
_###__
___#__

The longest possible path would here would take 10 steps.

123456
_###87
___#90

(In these snippets, the space character has been replaced by _ for clarity. Your code needs to operate on mazes using the space character.)

Input

Rows of text (newline-separated string, arrays of arrays of characters, etc), of equal length, consisting only of # and . The maze is always at least 2x2. There is always at least one valid path from start to finish. There may be islands in the maze.

Output

A number representing the number of steps in the longest possible path from top left to bottom right, including the entrance and exit cell. (You may output N-1 if you prefer.)

Scoring

Code golf.

Sample data

_______
__##___
_______

17

______
__#_#_

9

_______
__#__#_

12

_#______
_#______
_####___
________
###_____

30

__#____________
_##########_#_#
__#_______#_#__
#_________#_#__
__#########_#__
_##_________#__
__###########_#
#______________

24

__________#______
 ######_###______
________###______
_##########_###__
_________________

55

__#____________
_##__#######_#_
__#_______#_#__
#_________#_#__
____#######_#__
_##____________
__##_########_#
#______________

72

• Lucenaposition: Is this NP-complete?
• Ainsley H.: @Lucenaposition yes, because Hamiltonian Path is NP-complete on subgraphs of grid graphs.

Answer 1

JavaScript (ES7), 126 bytes

Expects a matrix of characters.

f=(m,X,Y,n=o=1)=>m.map((r,y)=>r.map((c,x)=>c>" "|(X-x)**2+(Y-y)**2^x+y>0?0:m[y+!r[x+1]]?r[f(m,x,y,r[x]=n+1),x]=c:n<o?0:o=n))|o

Try it online!

Commented

f = ( // f is a recursive function taking:
 m, // m[] = input matrix
 X, Y, // (X, Y) = current position, initially undefined
 n = // n = number of visited cells, initialized to 1
 o = 1 // o = output
) => //
m.map((r, y) => // for each row r[] at index y in m[]:
 r.map((c, x) => // for each character c at index x in r[]:
 c > " " | // if c is not a space
 (X - x) ** 2 + // or the squared Euclidean distance
 (Y - y) ** 2 ^ // between (x,y) and (X,Y) is not equal to ...
 x + y > 0 ? // ... NaN at the top-left corner / 1 otherwise:
 0 // do nothing
 : // else:
 m[y + !r[x + 1]] ? // if we're not at the bottom-right corner:
 r[ //
 f( // do a recursive call:
 m, // pass m[]
 x, y, // pass the new position
 r[x] = n + 1 // mark r[x] as visited and increment n
 ), // end of recursive call
 x // then restore r[x] ...
 ] = c // ... to c
 : // else:
 n < o ? 0 // update o to max(n, o)
 : o = n //
 ) // end of inner map()
) | o // end of outer map(); return o

• Steve Bennett: Great job! Technically it needs to operate on ` ` not _ (eg tio.run/… )
• Steve Bennett: Apologies - there was meant to be a note about why the snippets use _ instead of space, it got lost somewhere.
• l4m2: 125
• Arnauld: @l4m2 Is Y-y+c really safe?
• l4m2: The idea is that shift all "nearby" to outside when c is positive, not sure if currently correct. Worst case is f(r[x]=m,x,y,n+1), which makes Y-y+c NaN when it has been reached, but that makes thing slower

Answer 2

Charcoal, 73 bytes

WS⊞υι≔⟦⟦υ⊖Lυ⊖Lθ1⟧⟧υFυF4«§ι0J§ι2§ι1✳⊗κ#F¬No#KK⊞υ⟦⪪⪫KAωLθji⊕§ι3⟧⎚»I⊟⊟Φυ=2Noι0

Try it online! Link is to verbose version of code. Should be 72 bytes but I wanted a version that I could paste the test cases in without converting the _s to spaces. Too slow for the last two test cases on TIO. Explanation:

WS⊞υι≔⟦⟦υ⊖Lυ⊖Lθ1⟧⟧υFυ

Input the maze and start a breath first search back from the exit, considering this to be your first step.

F4«

Try taking a step in all four orthogonal directions.

§ι0J§ι2§ι1✳⊗κ#

Print the maze so far, jump to the current position for this search entry, overwrite the current position with a wall and move one step in the desired direction.

F¬No#KK⊞υ⟦⪪⪫KAωLθji⊕§ι3⟧

If this doesn't run into a wall then save the new position to the search list.

⎚»I⊟⊟Φυ=2Noι0

Find the last (and therefore longest) entry that reached the start and output its length.

Answer 3

Python3, 271 bytes

E=enumerate
def f(b):
 d={(x,y):v for x,r in E(b)for y,v in E(r)}
 q,s=[(0,0,[(0,0)])],[]
 for x,y,p in q:
 if(x,y)==(len(b)-1,len(b[0])-1):s+=[p];continue
 q+=[(*j,p+[j])for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]if d.get(j:=(x+X,y+Y))and j not in p]
 return max(map(len,s))

Try it online!

• ceilingcat: 253 bytes

Answer 4

Jelly, 30 bytes

ŒṪḢ,ṪW€ƲjⱮœ!JẎƊƊạƝ§ỊẠƲƇœị8ṂÞṪL

A (brutally inefficient) monadic Link that accepts a list of lists of characters (lines) and yields the length of the longest orthogonal path through the maze.

Try it online! (Not all that useful since it will time out for more than ten _# characters!)

How?

ŒṪḢ,ṪW€ƲjⱮœ!JẎƊƊạƝ§ỊẠƲƇœị8ṂÞṪL - Link: list of lists of characters, Maze
ŒṪ - truthy multidimensional indices (includes walls)
 Ɗ - last three links as a monad - f(AllCoords):
 Ʋ - last four links as a monad - f(AllCoords):
 Ḣ - head -> [1,1]
 Ṫ - tail -> [#rows,#columns]
 , - pair -> [[1,1],[#rows,#columns]]
 W€ - wrap each -> [[[1,1]],[[#rows,#columns]]]
 Ɗ - last three links as a monad - f(AllCoords - first & last):
 œ! - permutations without replacement across:
 J - [1..#coords-2]
 Ẏ - tighten
 jⱮ - map with join -> all lists of distinct coords starting with
 [1,1] and ending with [#rows,#columns], length ascending
 Ƈ - keep those for which:
 Ʋ - last four links as a monad - f():
 ạƝ - absolute difference of neighbouring pairs
 § - sums -> Manhattan distances
 Ị - insignificant (effectively, for each: is one?)
 Ạ - all?
 -> All paths through the maze ignoring walls
 œị8 - get the paths' characters
 ṂÞ - sort by minimum -> placing those with only '_'s on the right
 Ṫ - tail -> (one of) the longest all '_' path(s)
 L - length