Spraw, by wąż wypełnił dowolny labirynt (aż utknie).

Wąż

Wąż zaczyna się w danym punkcie początkowym, wskazując WSCHÓD . Porusza się, zawsze mając ścianę lub część ciała bezpośrednio po LEWEJ stronie swojej głowy („ zwolennik reguły ściany lewej ”), dopóki nie utknie, ponieważ wszystkie cztery kierunki wokół jego głowy są zajęte. (Uwaga: utknięty wąż może nie wypełnić całej dostępnej przestrzeni, ale to nie jest cel!)

Wyzwanie

Napisz program lub funkcję, która akceptuje labirynt jako dane wejściowe w postaci tekstu 2D:

• Dane wejściowe mogą być w dowolnym rozsądnym formacie: np. Lista ciągów, pojedynczy ciąg znaków z nowymi liniami, plik.
• Labirynt ma ściany („ #”), puste przestrzenie („ ”) i dokładnie jeden punkt początkowy („ o”).

• Możesz to zrobić

  • albo przyjąć, że pierwszy i ostatni rząd i kolumna są całkowicie ścianami;
  • lub załóżmy, że każdy wkład ma domyślną zewnętrzną warstwę ścian

• Możesz założyć, że punkt początkowy ma ścianę (lub ukrytą ścianę) bezpośrednio nad nią (PÓŁNOC) i że wąż może wykonać prawidłowy ruch początkowy w kierunku WSCHODNIM lub POŁUDNIOWYM.

• Możesz założyć, że w tekście nie ma żadnych innych znaków (oprócz znaków nowej linii, jeśli ich potrzebujesz).
• Możesz założyć, że wszystkie linie mają tę samą długość.

i drukuje / zwraca „wypełniony labirynt” jako dane wyjściowe, wraz z migawką węża w momencie, gdy utknął :

• Ciało węża jest reprezentowane przez postacie >v<^wskazujące, gdzie jest jego następny segment
• Punktem początkowym węża jest albo jego kierunek na początku („ >”, chyba że musiał natychmiast skręcić), albo opostać (nie trzeba być konsekwentnym)
• Punktem końcowym węża jest opostać

Punktacja

Zwykły kod golfowy: wygrywa najkrótszy kod

Przykład

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

Animowane (w celach ilustracyjnych):

Edycja: Należy zauważyć, że w razie wątpliwości, wąż powinien „trzymać swoją lewą rękę” na ścianie już jest, w następstwie kątach, nie skacze do ściany 1 przecznicę od hotelu.

Dziękuję Jonathanowi Allanowi za jego poruszenie, a Draco'owi za powyższą migawkę wyjaśniającą.

Inne przykłady

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

Węgiel drzewny , 94 68 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

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

Slurpuj dane wejściowe w ciągu. Można tego uniknąć, stosując mniej dogodny format wejściowy.

Ｐθ…θ⌕θo

Wydrukuj dane wejściowe bez przesuwania kursora, a następnie wydrukuj do góry o, aby kursor znalazł się pod nim.

≔⁰θ

Zainicjuj bieżący kierunek.

Ｗ№ＫＶ «

Powtarzaj, dopóki w pewnym kierunku jest jeszcze wolne miejsce.

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

Oblicz, czy wąż może skręcić w lewo, czy jest zmuszony skręcić w prawo. Kod ≦⊖θＷ¬⁼§ＫＶθ ≦⊕θdziała również w tym przypadku dla tej samej liczby bajtów, chociaż uważa się 0za up zamiast zamiast prawo, więc reszta kodu musi zostać dostosowana.

✳§rdluθ§>v<^θ

Wypisz odpowiedni charakter ciała we właściwym kierunku.

»o

Przywróć głowę. Można to również zapisać jako Ｐowypisujące głowę bez przesuwania kursora za każdym razem, gdy przechodzi ona przez pętlę (ale umożliwia to niejawne zamknięcie pętli dla tej samej liczby bajtów).

Python 2 , 273 253 242 bajtów

^{-11 bajtów dzięki 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

Wypróbuj online!

Działa to poprzez przeszukanie łańcucha 'o 'i zastąpienie go '[>v<^]o', jeśli jest w labiryncie.

Ta sama kontrola zostanie również wykonana w obróconym labiryncie, drukując wypełniony labirynt, gdy struny już nie ma.

Funkcja t=lambda g,k=1:'\n'.join(map(j,zip(*g.split('\n')[::k])[::-k]))służy do obracania siatki

Galaretka , 72 56 bajtów

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

Wypróbuj online!

Pełny program, który przyjmuje dane wejściowe jako listę ciągów i zwraca listę ciągów wraz z końcowym wężem. Zauważ, że stopka na TIO konwertuje pojedynczy ciąg oddzielony nową linią na pożądane dane wejściowe i przywraca nowe linie na końcu; jest to wyłącznie dla wygody.

Rozwiązanie nieco zainspirowane metodą zastosowaną w odpowiedzi na pytanie Pytona 2 @ Rod , choć implementacja jest zupełnie inna.

Rubin , 126 118 bajtów

-8 bajtów zapisanych przez nadużywanie +=zamiast ręcznego wyszukiwania opo zmianie położenia.

->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}

Wypróbuj online!

Zapytanie T-SQL 2008, 373 371 366 bajtów

Miałem listę priorytetów, zawsze ślizgającą się w lewo, prosto, w prawo. Zmieniłem ten priorytet na zawsze ślizgający się do tyłu, w lewo, prosto, w prawo. Cofanie zawsze będzie blokowane, więc priorytet pozostaje taki sam, z wyjątkiem pierwszego slitheru. Obracając węża początkowo w dół (C = 4), próbuje się ślizgać w górę podczas cofania. Ten mały wyczyn zaoszczędził mi 2 bajty. Ponieważ nie musiałem dodawać 1 do ~ - ~ -c% 4.

Wstawiłem 2 podziałki linii, aby było czytelne

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)

Musiałem wprowadzić drobne poprawki, aby wykonać to online, opublikowana wersja działa w studiu zarządzania serwerem MS-SQL.

Naciśnij Ctrl-T przed uruchomieniem w studiu zarządzania serwerem MS-SQL, to pokaże wynik jako tekst.

Wypróbuj online

Python 3 , 343 bajty

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

Wypróbuj online!

-11 bajtów dzięki ArBo
-4 bajtów dzięki Jonathanowi Frechowi

05AB1E , 54 52 bajty

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

I / O jako jeden ciąg wielu linii.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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

Pyth , 161 bajtów

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

Wypróbuj online!

Port rozwiązania Python 3 dla HyperNeutrino . Teraz, gdy już z tym skończyłem, myślę, że powinienem był przenieść port Pythona 2 na Rod, ale spędziłem już na tym zbyt dużo czasu.