21
\$\begingroup\$

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

enter image description here

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.

enter image description here

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#
#^<<<<<<<<<<<<<#
################
\$\endgroup\$
  • \$\begingroup\$ In the GIF example, when it enters the pattern why would it not turn back to fill in the other parts of the empty spaces? It was definitely possible to turn left then up then left then down then back around, but the snake chose straight down instead. Is the goal to fill as many spaces as possible with the snake or follow only the "turn right when encountering a wall and end if turn right twice" strategy? \$\endgroup\$ – Magic Octopus Urn Jun 14 at 15:27
  • 2
    \$\begingroup\$ @MagicOctopusUrn I'm not sure I understand at what point you see the ambiguity. But, to answer your question, the goal is not to fill as much space as possible. However, the algorithm ("wall follower") is not just "turn right once or, if not possible, twice": if the snake finds itself without a wall on its left, it will have to turn left instead (keeping the "left hand" on the wall/on itself) \$\endgroup\$ – Nicola Sap Jun 14 at 15:32
  • \$\begingroup\$ (sorry I misread your algorithm rundown) \$\endgroup\$ – Nicola Sap Jun 14 at 15:41
  • 2
    \$\begingroup\$ @ jonah: correct. There is a single deterministic path and it's not optimal. @ value ink: yes. @ jonathanallan I struggle to see the ambiguity but it may be just me. My version of the wall-following algorithm is: keep your direction unless you don't have an obstacle to your left anymore [evaluated first], in which case turn left, or you hit a wall [evaluated second] in which case turn right if possible, or game over. \$\endgroup\$ – Nicola Sap Jun 14 at 18:43
  • 1
    \$\begingroup\$ I had to dissect the gif to figure out why the end state was the way it was. It isn't apparent from the final displayed frame, but rather from the state just before: i.stack.imgur.com/kj67V.png I hope that helps people. \$\endgroup\$ – Draco18s Jun 19 at 20:47
7
\$\begingroup\$

Charcoal, 94 68 bytes

F²⊞υSW¬⁼§υ⁰§υ±¹⊞υS≔⪫υ¶θPθ…θ⌕θo≔⁰θW№KV «≧⁺⊖⌕E³§KV⁺θκ θ✳§rdluθ§>v<^θ»o

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

F²⊞υSW¬⁼§υ⁰§υ±¹⊞υS≔⪫υ¶θ

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

Pθ…θ⌕θ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.

W№KV «

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

≧⁺⊖⌕E³§KV⁺θκ θ

Calculate whether the snake can turn left, or whether it is forced to turn right. The code ≦⊖θW¬⁼§KVθ ≦⊕θ 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 Po 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).

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ I have no flipping idea how this works, but I can verify that it does. Amazing job! \$\endgroup\$ – BradC Jun 17 at 15:58
  • \$\begingroup\$ @BradC thanks for confirming and the compliment. Sql solutions doesn't get much love these days. \$\endgroup\$ – t-clausen.dk Jun 18 at 9:13
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You can golf the initialisation of X, Y and F to X=0,1,0,-1;F,*Y=*X,0 if I'm not mistaken. Also, the import* costs you more bytes than it saves. \$\endgroup\$ – ArBo Jun 14 at 17:07
  • \$\begingroup\$ @ArBo Oh, I thought it was saving some lol. Also that's pretty clever, thanks! \$\endgroup\$ – HyperNeutrino Jun 14 at 17:16
  • \$\begingroup\$ I think you can save a byte with *g,=map(...). And does sys.stdin.readlines() work perhaps? \$\endgroup\$ – Andras Deak Jun 14 at 20:07
  • 1
    \$\begingroup\$ Alternatively, you can probably save a few of bytes by assuming a single-line input and using input(). \$\endgroup\$ – Andras Deak Jun 14 at 20:13
  • 1
    \$\begingroup\$ if C=="o" ~> if"o"==C, if g[r+X[L]][c+Y[L]]==" ", elif g[r+X[F]][c+Y[F]]>" ", if g[r-X[L]][c-Y[L]]>" " accordingly. \$\endgroup\$ – Jonathan Frech Jun 14 at 23:31
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.