Wyzwanie to jest luźno zainspirowane grą Zachtronics Infinifactory .

Otrzymujesz widok z góry prostokątnej siatki przenośników, reprezentowanej przez >v<^. Mogą istnieć komórki bez przenośników, reprezentowane przez spacje. Oto przykład:

> <vv    <
 v ^ >v v 
  >v^^>vv^
    ^>^ v 
>  v<v  >>
  >v v<^  

Ta konfiguracja jest domyślnie otoczona nieskończoną liczbą spacji.

Ponadto podano wymiary prostokątnego kawałka ładunku, który umieszcza się na przenośnikach w lewym górnym rogu siatki. Twoim zadaniem jest ustalenie, czy ładunek kiedykolwiek się zatrzyma, czy też skończy się w pętli.

Oczywiście ładunek prawdopodobnie może obejmować kilka przenośników jednocześnie, więc oto zasady ustalania kierunku ładunku na każdym etapie:

1. Przeciwne przenośniki znoszą się nawzajem. Tak więc, jeśli ładunek 3x2 obejmuje dowolne z następujących łatek (dla zachowania przejrzystości opatrzonych łącznikami i rurkami), wynik byłby taki sam:

   +---+   +---+   +---+
   |>>^|   |  ^|   |v^^|
   |^<<|   |^  |   |^^v|
   +---+   +---+   +---+
   

   To samo dotyczy tych:

   +---+   +---+   +---+
   |v^<|   |   |   |><>|
   |>>>|   |>> |   |>><|
   +---+   +---+   +---+
   

   Ponieważ dokładne położenie przenośnika pod ładunkiem jest nieistotne, nie ma znaczenia, które pary anulujesz.

   To anulowanie jest stosowane przed innymi zasadami. Dlatego w przypadku pozostałych zasad przenośniki będą dostępne tylko w co najwyżej dwóch kierunkach.

2. Jeśli ładunek w ogóle nie obejmuje żadnych przenośników (ponieważ wszystkie przenośniki anulują się, ponieważ obejmują tylko przestrzenie lub ponieważ całkowicie zsunął się z rusztu), zatrzymuje się.

3. Jeżeli ładunek obejmuje więcej przenośników w jednym kierunku niż w drugim, ładunek przesuwa się w tym kierunku. Na przykład, jeśli ładunek 3x2 obejmuje następną łatkę

   >>
   ^>^
   

   przesunie się w prawo, ponieważ jest ich więcej >niż ^. Z drugiej strony, jeśli to obejmowało

   >>^
     ^
   

   ta zasada nie miałaby zastosowania, ponieważ istnieje powiązanie między >i ^.

4. Pozostawia to tylko przypadki, w których występuje remis między sąsiednimi kierunkami (remis między przeciwnymi kierunkami zostałby anulowany). W takim przypadku ładunek porusza się wzdłuż osi, w którą już się porusza. Np. Jeśli ładunek 3x2 poruszający się w prawo lub w lewo pokrywa teraz łatkę

   >>^
   ^  
   

   przesunie się w prawo. Gdyby ta łatka dotarła w górę lub w dół, przesunie się teraz w górę. Jeśli tego rodzaju konflikt występuje na pierwszym etapie symulacji, załóż, że ładunek przesuwał się w prawo.

Szczegółowe przykłady

Rozważ kratkę przenośnika u góry i ładunek 3x2. Poniżej przedstawiono krok po kroku wizualizację procesu. Każdy krok składa się z siatki, z ładunkiem reprezentowanym przez #, małe pudełko, które pokazuje przenośniki objęte ładunkiem, kolejne pudełko z przenośnikami po anulowaniu i regułą, która określa, gdzie przemieszcza się ładunek:

 ###vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <
 ###^ >v v     ###^ >v v      v ^ >v v      v ^ >v v      v ^ >v v      v ^ >v v 
   >v^^>vv^    ###v^^>vv^    ###v^^>vv^     ###^^>vv^      ###^>vv^      >###>vv^
     ^>^ v         ^>^ v     ### ^>^ v      ###^>^ v       ###>^ v        ###^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>    >  v<v  >>
   >v v<^        >v v<^        >v v<^        >v v<^        >v v<^        >v v<^  

+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+
|> <|  |   |  | v |  | v |  |  >|  |  >|  | >v|  | >v|  |>v^|  |> ^|  |v^^|  | ^^|
| v |  | v |  |  >|  |  >|  |   |  |   |  |   |  |   |  |  ^|  |   |  | ^>|  |  >|
+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+

   Rule 3        Rule 4        Rule 3        Rule 4        Rule 4        Rule 3

 ================================================================================

 > <vv    <    > <###   <    > <vv    <
  v ###v v      v ###v v      v ###v v 
   >###>vv^      >v^^>vv^      >###>vv^
     ^>^ v         ^>^ v         ^>^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>
   >v v<^        >v v<^        >v v<^  

+---+  +---+  +---+  +---+  +---+  +---+
|^ >|  |  >|  |vv |  | v |  |^ >|  |  >|
|v^^|  | ^^|  |^ >|  |  >|  |v^^|  | ^^|
+---+  +---+  +---+  +---+  +---+  +---+

   Rule 3        Rule 4        Rule 3

W tym momencie ładunek wchodzi w pętlę między dwiema ostatnimi ramami.

Teraz rozważ zamiast tego ładunek 2x3:

 ##<vv    <    >##vv    <    > <vv    <    > <vv    <    > <vv    <    > <vv    <
 ## ^ >v v      ##^ >v v      ##^ >v v      v ^ >v v      v ^ >v v      v ^ >v v 
 ##>v^^>vv^     ##v^^>vv^     ##v^^>vv^     ##v^^>vv^      ##^^>vv^      >v^^>vv^
     ^>^ v         ^>^ v      ## ^>^ v      ## ^>^ v       ##^>^ v       ##^>^ v 
 >  v<v  >>    >  v<v  >>    >  v<v  >>    >##v<v  >>    > ##<v  >>    > ##<v  >>
   >v v<^        >v v<^        >v v<^        >v v<^        >v v<^        ## v<^  

 +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+
 |> |  |> |    | <|  |  |    |v |  |v |    | >|  | >|    |>v|  |>v|    |  |  |  |
 | v|  | v|    |v |  |v |    | >|  | >|    |  |  |  |    |  |  |  |    | v|  | v|
 |  |  |  |    | >|  |  |    |  |  |  |    |  |  |  |    | v|  | v|    |>v|  |>v|
 +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+    +--+  +--+

   Rule 4        Rule 3        Rule 4        Rule 3        Rule 3        Rule 3

 ================================================================================

 > <vv    <    > <vv    <    > <vv    <
  v ^ >v v      v ^ >v v      v ^ >v v 
   >v^^>vv^      >v^^>vv^      >v^^>vv^
     ^>^ v         ^>^ v         ^>^ v 
 > ##<v  >>    >  v<v  >>    >  v<v  >>
   ## v<^        ## v<^        >v v<^  
   ##            ##            ##
                 ##            ##
                               ##

 +--+  +--+    +--+  +--+    +--+  +--+
 | v|  | v|    |>v|  |>v|    |  |  |  |
 |>v|  |>v|    |  |  |  |    |  |  |  |
 |  |  |  |    |  |  |  |    |  |  |  |
 +--+  +--+    +--+  +--+    +--+  +--+

   Rule 3        Rule 4        Rule 2

W ostatnim kroku obowiązuje zasada 2, ponieważ ładunek zsunął się z siatki, więc zatrzymuje się i nie ma pętli.

Zasady i założenia

Twoim wkładem będzie siatka przenośnika, jak opisano powyżej, wraz z szerokością i wysokością ładunku. Możesz wziąć te trzy parametry w dowolnej dogodnej kolejności i formacie. W przypadku siatki oznacza to, że można odczytać pojedynczy ciąg z liniami oddzielonymi znakami nowej linii lub innymi znakami, lub tablicę ciągów lub tablicę tablic znaków, o ile poszczególne komórki siatki są nadal reprezentowane przez znaki >v<^i spacje.

Powinieneś wypisać prawdziwą wartość, jeśli konfiguracja powoduje pętlę co najmniej dwóch ramek lub wartość fałszowania, jeśli ładunek zatrzyma się.

Możesz założyć, że siatka zostanie wypełniona prostokątem ze spacjami i że ładunek początkowo będzie pasował do siatki.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Przypadki testowe

Przypadki testowe są pogrupowane według siatek.

Grid (2x2):

>v
^<

Width  Height  Loop?
1      1       True
1      2       True
2      1       True
2      2       False

Grid (3x3):

> v

^ <

Width  Height  Loop?
1      1       False
1      2       False
1      3       False
2      1       False
2      2       True
2      3       True
3      1       False
3      2       True
3      3       False

Grid (4x3):

>^>v
v^v 
^ <<

Width  Height  Loop?
2      2       False

Grid (6x5):

>v>v>v
^v^v^v
^v^v^v
^>^>^v
^<<<<<

Width  Height  Loop?
1      1       True
1      2       False
2      1       True
2      2       True
2      4       True
2      5       False
3      1       False
3      2       True
3      3       True
3      5       True
6      2       False
6      3       True
6      5       False

Grid (10x6):

> <vv    <
 v ^ >v v 
  >v^^>vv^
    ^>^ v 
>  v<v  >>
  >v v<^  

Width  Height  Loop?
1      1       False
2      3       False
2      6       False
3      2       True
5      4       False
6      1       True
10     6       False

Jako dodatkowy zestaw przypadków testowych należy wziąć pod uwagę, że wszelkie dane wejściowe, w których siatka składa się wyłącznie ze spacji, muszą dawać wynik fałszowania.

Ręcznie sprawdziłem wszystkie przypadki testowe, więc daj mi znać, jeśli uważasz, że popełniłem błąd.

Ruby, 306 298 251 204 198

->g,w,h{m=->y,x,d,v=[]{q=y,x
r=->s{([""]*h+g)[y+h,h].map{|l|(?x*w+l)[x+w,w]}.join.count s}
z=k=r[?v]-r[?^],j=r[?>]-r[?<]
q[d=[d,1,0][j*j<=>k*k]]+=z[d]<=>0
v&[q<<d]!=[]?q!=v[-1]:m[*q,v<<q]}
m[0,0,1]}

Edycja: Bardzo dziękuję Ventero, który znacznie skrócił kod, stosując niesamowite sztuczki!

Wejście i wyjście

Kod reprezentuje funkcję ruby, która przyjmuje trzy parametry:

• siatka reprezentowana jako tablica ciągów (każdy wiersz jest innym ciągiem)
• szerokość ładunku
• wysokość ładunku

Zwraca 1(prawda) w przypadku pętli lub nil(fałsz), gdy ładunek odpoczywa.

Testy

Tutaj przechodzi wszystkie testy Martina: http://ideone.com/zPPZdR

Wyjaśnienie

W kodzie nie ma sprytnych sztuczek; jest to dość prosta implementacja zasad.

W poniższym kodzie movejest funkcja rekurencyjna, która wykonuje ruch zgodnie z regułami i:

• zwraca prawdę w przypadku pętli
• zwraca fałsz w przypadku odpoczynku
• w przeciwnym razie wywołuje się, aby wykonać następny ruch

Bardziej czytelna wersja jest dostępna tutaj .

Uwaga: kod do gry w golfa przeszedł kilka modyfikacji i nie jest już podobny do wersji do odczytu.

Python 2, 207 bajtów

def f(L,w,h,u=0,v=0,D=1,S=[]):a,b,c,d=map(`[r[u*(u>0):u+w]for r in L[v*(v>0):v+h]]`.count,"v^><");D=cmp(abs(a-b),abs(c-d))<D;T=u,v,D;return T in S or a-b|c-d and f(L,w,h,u+cmp(c,d)*D,v+cmp(a,b)*0**D,D,S+[T])

Wprowadź siatkę jako listę wierszy, np

['>v>v>v', '^v^v^v', '^v^v^v', '^>^>^v', '^<<<<<']

następnie szerokość i wysokość. Zwraca 0lub Trueodpowiednio.

Wyjaśnienie

def f(L,          # Grid
      w,h,        # Width, height of cargo
      u=0,v=0,    # Position of top-left of cargo, initially (0, 0)
      D=1,        # Moving left/right = 1, up/down = 0
      S=[]        # Seen (pos, axis) pairs, initially empty
     ):     

     # Arrows under cargo - no need for "".join since we only need to count v^<>
     A = `[r[u*(u>0):u+w]for r in L[v*(v>0):v+h]]`

     # Count for each arrow
     a,b,c,d=map(A.count,"v^><")

     # Golfed form of abs(a-b) < abs(c-d) or (abs(a-b) == abs(c-d) and D == 1)
     D=cmp(abs(a-b),abs(c-d))<D
     T=u,v,D

     return (T in S                # Return True if (pos, axis) previously seen
             or a-b|c-d               # Return 0 if all conveyors cancel
             and f(L,w,h,             # Otherwise, recurse
                   u+cmp(c,d)*D,      # Update u if moving left/right
                   v+cmp(a,b)*0**D,   # Update v if moving up/down
                   D,
                   S+[T]          # Add (pos, axis) to seen
                  )
            )

Julia - 394 300 246 214 bajtów

f(A,x,y)=(Z=sign;(S,T)=size(A);X=x+1;Y=y+1;G=fill(5,S+2y,T+2x);G[Y:S+y,X:T+x]=A;C=0G;D=1;while C[Y,X]!=D C[Y,X]=D;i,j=sum(i->1-[19 8]i%82%3,G[Y:Y+y-1,X:X+x-1]);D=Z(2i^2-2j^2+(i!=0)D);X+=Z(i+D*i);Y+=Z(j-D*j)end;D^2)

Zwraca 1, jeśli ładunek zapętla się, i 0, jeśli zatrzyma się. To nie jest „ściśle” prawda / fałsz, ponieważ Julia nie zezwala na 0 i 1 w kontekście boolowskim ... ale uważam wartości, xdla których bool(x)==truesą prawdziwe i bool(x)==falsesą fałszywe.

Dane wejściowe Apowinny mieć postać tablicy znaków. Jeśli kopiujesz / wklejasz siatkę przenośnika, musisz ustawić ją w odpowiedniej formie. Aby uniknąć konieczności ręcznego obsługiwania go, użyj następujących poleceń:

A=foldl(hcat,map(collect,split("""(PASTE GRID HERE)""","\n")))'

Gdzie oczywiście (PASTE GRID HERE)należy zastąpić samą siatką. Sprawdź dwukrotnie spacje na końcu każdej linii, aby upewnić się, że faktycznie ma wszystkie spacje (nie sprawdza, czy wszystkie linie mają równą długość). Zauważ, że ten wiersz nie jest częścią rzeczywistego kodu rozwiązania, a jedynie wygodnym fragmentem kodu, aby ułatwić korzystanie z kodu rozwiązania.

Nie golfowany:

function f(A,x,y)
  # Determine size of grid for use later
  (S,T)=size(A)
  # Initialise starting position (performed here to save characters)
  X=x+1
  Y=y+1
  # Create an expanded field that is functionally "spaces" (to provide
  # spaces at edges for the cargo to stop in)
  G=fill(5,S+2y,T+2x)
  # Put the conveyor grid into centre of the expanded field
  G[Y:S+y,X:T+x]=A
  # Create an array storing the most recent movement direction:
  # will use 1=horizontal, -1=vertical, 0=stopped
  C=0G
  # Initialise current direction (same system as C)
  D=1
  # Loop until it finds itself repeating a coordinate/direction pair
  while C[Y,X]!=D
    # Mark current coordinate/direction pair in array
    C[Y,X]=D
    # Determine the net coordinate pairing, stored in two variables
    # for golf purposes *SEE NOTE*
    i,j=sum(i->1-[19 8]i%82%3,G[Y:Y+y-1,X:X+x-1])
    # Determine new movement axis (if D=0, cargo stopped)
    D=sign(2i^2-2j^2+(i!=0)D)
    # Update X or Y depending on signs of D and the appropriate direction
    X+=sign(i+D*i)
    Y+=sign(j-D*j)
  end
  # if D=±1, return 1 (cargo is still moving), otherwise return 0
  return D^2
end

Uwaga: 1-[19 8]i%82%3wybrano mapowanie pięciu możliwych znaków na odpowiednie pary współrzędnych za pomocą najbardziej efektywnej metody, jaką mogłem znaleźć. Jest to również powód użycia 5 do wypełnienia spacji podczas tworzenia G- jest to jednocyfrowy znak, który odwzorowuje [0 0].

Przykład użycia:

julia> A=foldl(hcat,map(collect,split(""">v>v>v
       ^v^v^v
       ^v^v^v
       ^>^>^v
       ^<<<<<""","\n")))';

julia> f(A,2,1)
true

julia> f(A,3,3)
true

julia> f(A,5,2)
false