| Bytes | Lang | Time | Link |
|---|---|---|---|
| 126 | JavaScript ES7 | 250526T053802Z | Arnauld |
| 030 | Jelly | 250526T221903Z | Jonathan |
| 271 | Python3 | 250526T135329Z | Ajax1234 |
| 073 | Charcoal | 250526T110510Z | Neil |
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
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
Jelly, 30 bytes
ŒṪḢ,ṪW€ƲjⱮœ!JẎƊƊạƝ§ỊẠƲƇœị⁸ṂÞṪ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ẎƊƊạƝ§ỊẠƲƇœị⁸ṂÞṪ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
œị⁸ - 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
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))
Charcoal, 73 bytes
WS⊞υι≔⟦⟦υ⊖Lυ⊖Lθ¹⟧⟧υFυF⁴«§ι⁰J§ι²§ι¹✳⊗κ#F¬№#KK⊞υ⟦⪪⪫KAωLθⅉⅈ⊕§ι³⟧⎚»I⊟⊟Φυ⁼²№ι⁰
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θ¹⟧⟧υFυ
Input the maze and start a breath first search back from the exit, considering this to be your first step.
F⁴«
Try taking a step in all four orthogonal directions.
§ι⁰J§ι²§ι¹✳⊗κ#
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¬№#KK⊞υ⟦⪪⪫KAωLθⅉⅈ⊕§ι³⟧
If this doesn't run into a wall then save the new position to the search list.
⎚»I⊟⊟Φυ⁼²№ι⁰
Find the last (and therefore longest) entry that reached the start and output its length.