Pomocy, jestem uwięziony w nieskończonej fabryce!

26

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.

Martin Ender
źródło
10
Dopasowanie muzyki
Fatalize
4
@Fatalize Dostaję retrospekcje Pokemona Twitcha ...
undergroundmonorail
„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.” - czy to oznacza, że ​​możemy wziąć siatkę przenośnika jako tablicę? Oznacza to, że siatka 2x2 [^^/v<]staje się [[0,1] [0,1];[0,-1] [-1,0]]? Czy masz na myśli, czy to od nas zależy, czy będzie to STDIN, ciąg znaków, tablica znaków itp., Ale nadal musi mieć postać ^, v,> i <?
Glen O
@GlenO Możesz pobrać nowy znak (lub inny znak) oddzielony ciąg, tablicę ciągów lub tablicę tablic znaków, ale każda komórka powinna być nadal reprezentowana przez znaki ><^vlub spację. Wyjaśnię to.
Martin Ender,
Co się stanie, jeśli ładunek przejdzie w konflikt, w którym kontynuacja kierunku nie jest jedną z opcji? To znaczy, jeśli poruszał się w prawo, a teraz musi wybierać między górą a lewą.
Joshua

Odpowiedzi:

7

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.

Cristian Lupascu
źródło
Ponieważ nie ma znaczenia, czy rzawiera dodatkowe wpisy poza czterema kierunkami, r[y>=0&&x>=0&&g[y]&&g[y][x]]+=1należy zapisać kilka bajtów.
Ventero,
@Ventero Wow, zrobiłeś niesamowite rzeczy w kodzie. Nigdy bym nie pomyślał o przekształceniu skrótu w lambda. Próbowałem niektóre z moich pomysłów na skrócenie programu, ale nie byłem bliski tego, co zrobiłeś. Wielkie dzięki!
Cristian Lupascu,
2
Zmniejszono go do 200 poprzez nieco krótszą obsługę ujemnych indeksów, chyba na razie to zostawię: ideone.com/k69BmH
Ventero
2
Właściwie 198: ideone.com/ptKrzf :)
Ventero,
8

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
                  )
            )
Sp3000
źródło
Nie możesz go skrócić, przypisując cmpdo zmiennej?
Niebieski
Czy wystarczy wykryć cykle, sprawdzając pozycje już odwiedzone? W oparciu o zasadę 4 na następny krok może również wpływać poprzedni kierunek. Wydaje się więc możliwe, że możesz dwukrotnie dojść do tej samej pozycji, ale nie mieć cyklu, ponieważ poruszasz się w różnych kierunkach w oparciu o różne poprzednie kierunki.
Reto Koradi,
@muddyfish That just break even
Sp3000
@RetoKoradi Mam nadzieję, że naprawione
Sp3000,
Tak, dodanie Ddo klawisza pozycji powinno to zrobić.
Reto Koradi,
8

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
Glen O
źródło
f(A,x,y)=jest krótszy niż f=(A,x,y)->.
Alex A.
@AlexA. - prawda, ale prawdopodobnie usunę ją f=i uczynię z niej anonimową funkcję, kiedy skończę grać w golfa.
Glen O
1
Będzie miała tę samą długość, jeśli jest to funkcja nazwana w porównaniu z funkcją anonimową, gdy istnieje wiele parametrów. f()=kontra ()->.
Alex A.