Fill the maze with a wall-following Snake until it gets stuck

Question

Make a snake fill any maze (until it gets stuck).

The snake

The snake starts at a given starting point, pointing EAST. It moves by always having a wall or a part of its body immediately to the LEFT of its head ("left-hand rule wall follower"), until it gets stuck because all four directions around its head are occupied. (Note: a stuck snake can possibly not fill all the reachable space, but that is not the goal!)

The challenge

Write a program or function that accepts a maze as input in the form of a 2D text:

• The input can be in any reasonable format: e.g. a list of strings, a single string with newlines, a file.

• The maze has walls ("#"), empty spaces (" ") and exactly one starting point ("o").

• You can choose to

  • either assume that the first and last row and column are entirely walls;
  • or assume that every input is considered to have an implicit outer layer of walls

• You can assume that the starting point has a wall (or an implicit wall) directly above it (NORTH) and that the snake can make a valid starting move in the EAST or SOUTH direction.

• You can assume that no other characters are present in the text (except newlines if your input needs them).

• You can assume that all lines are the same length.

and prints / returns a "filled maze" as output, with a snapshot of the snake at the moment it got stuck:

• The body of the snake is represented by the characters >v<^ pointing to where its next segment is
• The starting point of the snake is either its direction at the start (">" unless it had to turn immediately) or an o character (no need to be consistent)
• The end point of the snake is an o character

Scoring

Usual code golf: the shortest code wins

Example

in:
#################################
#                    o          #
#                               #
#     ##       ###       ##     #
#    ##     ##     ##     ##    #
#    ##     ##     ##     ##    #
#    ##      ##   ##      ##    #
#   ##       ##   ##       ##   #
#   ##         ###         ##   #
#    ##       #####       ##    #
#    ##       #####       ##    #
#    ##        ###        ##    #
#     ##                 ##     #
#                               #
#                               #
#################################

out:
#################################
#>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>v#
#^>>>>>>>>>>>>>>>>>v>>>>>>>>>>vv#
#^^   ##>>>>>>v###o>>>>>v##   vv#
#^^  ##>^   ##>>>>^##   >v##  vv#
#^^  ##^    ##     ##    v##  vv#
#^^  ##^     ##   ##     v##  vv#
#^^ ##>^     ##   ##     >v## vv#
#^^ ##^<       ###       v<## vv#
#^^  ##^      #####      v##  vv#
#^^  ##^      #####      v##  vv#
#^^  ##^<      ###      v<##  vv#
#^^   ##^<<<<<<<<<<<<<<<<##   vv#
#^^<<<<<<<<<<<<<<<<<<<<<<<<<<<<v#
#^<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<#
#################################

Animated (for illustration purposes):

Edit: note that, when in doubt, the snake should "keep its left hand" on the wall it is already on, following corners, not jumping to a wall 1-block away.

Thanks Jonathan Allan for bringing it up, and Draco18s for the explanatory snapshot above.

Other examples

in:
####################
#               o# #  
#                ###
#                  #
#      ##          #
#                ###
####################

out:
####################
#>>>>>>>>>>>>>>vv# #
#^>>>>>>>>>>>>vvv###
#^^   v<<<o<<<<v>>v#
#^^<<<<##^<<<<<<v<<#
#^<<<<<<<<<<<<<<<###
####################

in:
####################
#         o    #####  
#              #####
#                  #
#                 ##
####################

out:
####################
#         >>>>v#####
#             v#####
#             >>>>o#
#                 ##
####################

in:
################
#o             #
#   ########## #
# #          # #
# #          # #
# #          # #
# #  #       # #
# #          # #
# #          # #
# #          # #
# ############ #
#              #
################

out:
################
#>>>>>>>>>>>>>v#
#>>v##########v#
#^#>>>>>>>>>v#v#
#^#>>>>>>>>vv#v#
#^#^>>>>>>vvv#v#
#^#^^#    vvv#v#
#^#^^o<<<<<vv#v#
#^#^^<<<<<<<v#v#
#^#^<<<<<<<<<#v#
#^############v#
#^<<<<<<<<<<<<<#
################

Answer 1

Charcoal, 94 68 bytes

Ｆ²⊞υＳＷ¬⁼§υ⁰§υ±¹⊞υＳ≔⪫υ¶θＰθ…θ⌕θo≔⁰θＷ№ＫＶ «≧⁺⊖⌕Ｅ³§ＫＶ⁺θκ θ✳§rdluθ§>v<^θ»o

Try it online! Link is to verbose version of code. Explanation:

Ｆ²⊞υＳＷ¬⁼§υ⁰§υ±¹⊞υＳ≔⪫υ¶θ

Slurp the input into a string. This could be avoided by using a less convenient input format.

Ｐθ…θ⌕θo

Print the input without moving the cursor, and then print up to the o again, so that the cursor ends up under it.

≔⁰θ

Initialise the current direction.

Ｗ№ＫＶ «

Repeat while there's still a free space in some direction.

≧⁺⊖⌕Ｅ³§ＫＶ⁺θκ θ

Calculate whether the snake can turn left, or whether it is forced to turn right. The code ≦⊖θＷ¬⁼§ＫＶθ ≦⊕θ also works for this for the same byte count although it considers 0 as up instead of right so the rest of the code needs to be adapted.

✳§rdluθ§>v<^θ

Output the appropriate body character in the appropriate direction.

»o

Restore the head. This can also be written as Ｐo which prints the head without moving the cursor each pass through the loop instead (but this allows the loop to be implicitly closed for the same byte count).

Answer 2

Python 2, 273 253 242 bytes

^{-11 bytes thanks to ArBo}

g=input()
d=0
t=lambda g,k=1:'\n'.join(map(''.join,zip(*g.split('\n')[::k])[::-k]))
h='o '
while 1:
 l,r=t(g,-1),t(g)
 if h in l:g=l;d-=1
 elif h in g:g=g.replace(h,'>v<^'[d%4]+'o')
 elif h in r:g=r;d+=1
 else:break
exec-d%4*'g=t(g);'
print g

Try it online!

This working by searching the string 'o ', and replacing it by '[>v<^]o', if it is in the maze.

The same check will also be made on the rotated maze, printing the filled maze when the string isn't there anymore.

The function t=lambda g,k=1:'\n'.join(map(j,zip(*g.split('\n')[::k])[::-k])) is used to rotate the grid

Answer 3

Jelly, 72 56 bytes

œṣ€⁾o j€ṛị“v<^>”;”oʋ,
UZ$ṛ¡+ƭ€Ɱ3r5¤ç/€ḟ$Ḣß$ṛ¹?
,0ÇZU$ṛ¡/

Try it online!

A full program that takes the input as a list of strings and returns a list of strings with the final snake. Note the footer on TIO converts a single newline separated string into the desired input and restores the newlines at the end; this is merely for convenience.

Solution somewhat inspired by the method used by @Rod’s Python 2 answer, though implementation is very different.

Answer 4

Ruby, 126 118 bytes

-8 bytes saved by abusing += instead of manually searching for o again after repositioning it.

->s{d=[q=1,1+l=s=~/$/,-1,~l];i=s=~/o/;(s[i]=">v<^"[q];s[i+=d[q]]=?o)while q=[~-q%4,q,-~q%4].find{|e|s[i+d[e]]==' '};s}

Try it online!

Answer 5

T-SQL 2008 query, 373 371 366 bytes

I had a priority list, always slither left, straight, right. I changed that priority to always slither back, left, straight, right. Slithering back will always be blocked, so the priority is still the same except the first slither. By turning the snake down initially (C=4), it attempts to slithering up when backslithering. This little stunt saved me 2 bytes. Because I didn't need to add 1 to ~-~-c%4.

I inserted 2 line breaks to make it readable

DECLARE @ varchar(8000)=
'################
#o             #
#   ########## #
# #          # #
# #          # #
# #          # #
# #  #       # #
# #          # #
# #          # #
# #          # #
# ############ #
#              #
################';

WITH s as(SELECT 0i,4c,@ m 
UNION ALL
SELECT~-i,x,stuff(stuff(m,~-a+x/3*2+(x-3)%2*s,1,'o')
,a,1,char(59+x+~x%2*11*~x))FROM(SELECT
charindex(' ',replicate(stuff(substring(m,~-a,3),2,1,substring(m,a+~s,1))+
substring(m,a-~s,1)+'~',2),-~-~c%4)%5x,*FROM(SELECT*,charindex('o',m)a,charindex('
',M)S FROM S)Q)L
WHERE x>0)SELECT top 1m FROM s
ORDER BY i
OPTION(MAXRECURSION 0)

I had to make some minor adjustments to execute this online, the posted version runs in MS-SQL server management studio.

Push Ctrl-T before execute in MS-SQL server management studio, this will show result as text.

Try it online

Answer 6

Python 3, 343 bytes

import sys
X=0,1,0,-1
F,*Y=*X,0
L=3
g=[*map(list,sys.stdin.read().split("\n"))]
e=enumerate
r,c=[[r,c]for r,R in e(g)for c,C in e(R)if"o"==C][0]
while 1:
	if" "==g[r+X[L]][c+Y[L]]:F,L=L,~-L%4
	elif" "<g[r+X[F]][c+Y[F]]:
		if" "<g[r-X[L]][c-Y[L]]:g[r][c]="o";break
		L,F=F,-~F%4
	g[r][c]=">v<^"[F];r,c=r+X[F],c+Y[F]
for r in g:print("".join(r))

Try it online!

-11 bytes thanks to ArBo
-4 bytes thanks to Jonathan Frech

Answer 7

05AB1E, 54 52 bytes

[S¶¡øí3FDíø})J€»¼D¾èU¼.Δ.¼„o ©å}DÄiXqë®">^<v"¾è'o«.;

I/O both as a single multi-line string.

Try it online or verify all test cases.

Explanation:

[                      # Start an infinite loop:
 S                     #  Split the multi-line string into a list of characters
                       #  (which will use the implicit input in the first iteration)
  ¶¡                   #  Then split by newlines
    øí                 #  Rotate the matrix once clockwise
      3F               #  Loop 3 times:
        D              #   Create a copy of the matrix
         íø            #   And rotate this copy once counterclockwise
       })              #  After the loop: wrap all four matrices into a list
 J                     #  Join each inner-most character-list to string-lines again
  €»                   #  And join each inner list of lines by newlines again
    ¼                  #  Increase variable `c` by 1 (variable `c` is 0 by default)
     D¾<è              #  Index the updated variable `c` in a copy of the list of matrices
                       #  (note that indexing wraps around in 05AB1E)
         U             #  Pop and store it in variable `X`
    ¼                  #  Then increase variable `c` again
    .Δ                 #  Find the first multi-line string in the list which is truthy for:
      .¼               #   Decrease variable `c` by 1 first
        „o             #   Push string "o "
           ©           #   Store this string in variable `®` (without popping)
            å          #   Check if the current multi-line string contains this "o "
    }D                 #  Duplicate the result (results in -1 if none were truthy/found)
      Äi               #  If no result was found:
        X              #   Push variable `X`
         q             #   And stop the program, after which this multi-line string of
                       #   variable `X` is output implicitly as result
       ë               #  Else:
         ">^<v"¾è      #   Get the `c`'th character in string ">^<v"
                       #   (note that indexing wraps around in 05AB1E)
                 'o«  '#   Append a trailing "o" to this character
        ®           .; #   And replace the first variable `®` ("o ") in the 
                       #   multi-line string with this
            

Answer 8

Pyth, 161 bytes

J.zK[Z1Z_1)=Y+tKZVlJFTl@JNIq@@JNT\oA[NT;=N3=TZ#Iq@@J+G@KN+H@YNd=TN=N%tN4.?In@@J+G@KT+H@YTdIn@@J-G@KN-H@YNd XJGX@JGH\oB=NT=T%hT4)) XJGX@JGH@">v<^"TA(+G@KT+H@YT;jJ

Try it online!

Port of HyperNeutrino's Python 3 solution. Now that I'm done with it, I'm thinking maybe I should have ported Rod's Python 2 solution instead, but I already spent way too much time on this.