Hilfe, ich bin in einer unendlichen Fabrik gefangen!

26

Diese Herausforderung ist locker vom Zachtronics-Spiel Infinifactory inspiriert .

Sie erhalten eine Ansicht von oben auf ein rechteckiges Gitter von Förderbändern, dargestellt durch >v<^. Es kann Zellen ohne Förderer geben, die durch Leerzeichen dargestellt werden. Hier ist ein Beispiel:

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

Dieser Aufbau ist implizit von einer unendlichen Anzahl von Leerzeichen umgeben.

Darüber hinaus erhalten Sie die Abmessungen eines rechteckigen Stücks Fracht, das in der linken oberen Ecke des Gitters auf die Förderbänder gelegt wird. Sie müssen herausfinden, ob die Ladung jemals zur Ruhe kommt oder ob sie sich in einer Schleife bewegt.

Natürlich deckt die Ladung wahrscheinlich mehrere Förderer gleichzeitig ab. Daher gelten die folgenden Regeln, um die Richtung der Ladung in jedem Schritt zu bestimmen:

  1. Gegenüberliegende Förderer heben sich gegenseitig auf. Wenn also eine 3x2-Ladung eines der folgenden Patches abdeckt (aus Gründen der Klarheit mit Bindestrichen und Rohren versehen), ist das Ergebnis dasselbe:

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

    Gleiches gilt für diese:

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

    Da die genaue Position eines Förderers unter der Ladung unerheblich ist, spielt es keine Rolle, welche Paare Sie stornieren.

    Diese Stornierung wird vor den anderen Regeln angewendet. Daher gibt es für die anderen Regeln nur Förderer in höchstens zwei Richtungen.

  2. Wenn die Ladung überhaupt keine Förderer abdeckt (entweder weil alle Förderer ausfallen, weil sie nur Leerzeichen abdeckt oder weil sie sich vollständig vom Gitter entfernt hat), kommt sie zur Ruhe.
  3. Wenn die Ladung mehr Förderer einer Richtung als der anderen abdeckt, bewegt sich die Ladung in diese Richtung. ZB wenn eine 3x2 Ladung den folgenden Patch abdeckt

    >>
    ^>^
    

    es würde sich nach rechts bewegen, denn es gibt mehr >als ^. Auf der anderen Seite, wenn es bedeckt ist

    >>^
      ^
    

    Diese Regel würde nicht gelten, da zwischen >und ein Zusammenhang besteht ^.

  4. Dies lässt nur Fälle übrig, in denen es ein Unentschieden zwischen benachbarten Richtungen gibt (ein Unentschieden zwischen entgegengesetzten Richtungen hätte aufgehoben). In diesem Fall bewegt sich die Ladung weiter entlang der Achse, in der sie sich bereits bewegt. Bedeckt nun beispielsweise eine sich rechts oder links bewegende 3x2-Ladung das Feld

    >>^
    ^  
    

    es würde sich nach rechts bewegen. Wenn es auf diesem Patch angekommen wäre, der sich nach oben oder unten bewegt, würde es sich stattdessen nach oben bewegen. Wenn diese Art von Konflikt im ersten Schritt der Simulation auftritt, nehmen Sie an, dass sich die Fracht nach rechts bewegt hat.

Ausführliche Beispiele

Betrachten Sie das Fördergitter oben und eine 3x2-Ladung. Das Folgende ist eine schrittweise Visualisierung des Prozesses. Jeder Schritt besteht aus dem Raster, in dem die Ladung durch #ein Kästchen dargestellt wird , in dem die von der Ladung abgedeckten Förderer, ein weiteres Kästchen mit den Förderern nach der Stornierung und die Regel angegeben sind, die festlegt, wohin sich die Ladung bewegt:

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

Zu diesem Zeitpunkt tritt die Ladung in eine Schleife zwischen den letzten beiden Rahmen ein.

Betrachten Sie stattdessen eine 2x3-Ladung:

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

Im letzten Schritt gilt Regel 2, weil sich die Ladung vom Gitter entfernt hat, so dass sie zur Ruhe kommt und es keine Schleife gibt.

Regeln und Annahmen

Ihre Eingabe wird das oben beschriebene Fördergitter sein, zusammen mit der Breite und Höhe der Ladung. Sie können diese drei Parameter in beliebiger Reihenfolge und in beliebigem Format verwenden. Für das Raster bedeutet dies, dass Sie eine einzelne Zeichenfolge mit durch Zeilenumbrüche oder andere Zeichen getrennten Zeilen oder ein Array von Zeichenfolgen oder ein Array von Arrays von Zeichen lesen können, solange die einzelnen Rasterzellen noch durch die Zeichen >v<^und dargestellt werden Leerzeichen.

Sie sollten einen Wahrheitswert ausgeben , wenn das Setup eine Schleife von mindestens zwei Frames ergibt, oder einen falschen Wert, wenn die Ladung zur Ruhe kommt.

Sie können davon ausgehen, dass das Gitter zu einem Rechteck mit Leerzeichen aufgefüllt wird und die Ladung zunächst in das Gitter passt.

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Testfälle

Die Testfälle sind nach Rastern gruppiert.

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

Berücksichtigen Sie als zusätzlichen Satz von Testfällen, dass jede Eingabe, bei der das Raster nur aus Leerzeichen besteht, ein falsches Ergebnis liefern muss.

Ich habe alle Testfälle manuell überprüft. Lassen Sie mich wissen, wenn Sie glauben, dass ich einen Fehler gemacht habe.

Martin Ender
quelle
10
Passende
4
@Fatalize Ich bekomme Twitch Plays Pokemon Flashbacks ...
undergroundmonorail
"Ihre Eingabe wird das oben beschriebene Fördergitter sein, zusammen mit der Breite und Höhe der Ladung. Sie können diese drei Parameter in jeder geeigneten Reihenfolge und in jedem geeigneten Format verwenden." - Heißt das, wir können das Fördergitter als Array von Arrays aufnehmen lassen? Das heißt, ein 2x2 - Raster mit [^^/v<]wird [[0,1] [0,1];[0,-1] [-1,0]]? Oder liegt es an uns, ob es sich um STDIN, eine Zeichenfolgeeingabe, eine Zeichenfeldeingabe usw. handelt, aber es muss immer noch die Form ^, v,> und <haben?
Glen O
@GlenO Sie können eine durch Zeilenumbrüche (oder andere Zeichen) getrennte Zeichenfolge, ein Array von Zeichenfolgen oder ein Array von Arrays von Zeichen verwenden. Jede Zelle sollte jedoch weiterhin durch die Zeichen ><^voder ein Leerzeichen dargestellt werden. Ich werde das klären.
Martin Ender
Was passiert also, wenn die Fracht in einen Konflikt gerät, in dem die weitere Richtung nicht zur Wahl steht? Das heißt, wenn es sich nach rechts bewegte und nun zwischen oben und links wählen muss.
Joshua

Antworten:

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

Edit: Vielen Dank an Ventero, der den Code durch einige erstaunliche Tricks stark verkürzt hat!

Ein- und Ausgabe

Der Code stellt eine Ruby-Funktion dar, die drei Parameter akzeptiert:

  • das Gitter, dargestellt als ein Array von Zeichenfolgen (jede Zeile ist eine andere Zeichenfolge)
  • die Breite der Ladung
  • die Höhe der Ladung

Es gibt 1(wahr) zurück, falls es eine Schleife gibt, oder nil(falsch), falls die Ladung ruht.

Tests

Hier besteht es alle Martins Tests: http://ideone.com/zPPZdR

Erläuterung

Der Code enthält keine cleveren Tricks. Es ist eine ziemlich einfache Implementierung der Regeln.

Im folgenden Code movehandelt es sich um eine rekursive Funktion, die einen Zug gemäß den Regeln ausführt.

  • Gibt im Falle einer Schleife wahrheitsgemäß zurück
  • gibt im Ruhefall falsisch zurück
  • Andernfalls ruft er sich selbst auf, um den nächsten Zug auszuführen

Eine besser lesbare Version finden Sie hier .

Hinweis: Der Golf-Code wurde mehrfach geändert und ähnelt nicht mehr der lesbaren Version.

Cristian Lupascu
quelle
Da es egal ist, ob rneben den vier Richtungen weitere Einträge enthalten sind, r[y>=0&&x>=0&&g[y]&&g[y][x]]+=1sollten ein paar Bytes gespart werden.
Ventero
Ich habe mir erlaubt,
Ventero
@Ventero Wow, du hast erstaunliche Dinge mit dem Code gemacht. Ich hätte nie darüber nachgedacht, den Hash in einen Lambda umzuwandeln. Ich habe einige meiner Ideen ausprobiert, um das Programm zu verkürzen, war aber bei weitem nicht in der Nähe von dem, was Sie getan haben. Vielen Dank!
Cristian Lupascu
2
Durch etwas kürzeren Umgang mit negativen Indizes wurde der Wert auf
200
2
Eigentlich 198: ideone.com/ptKrzf :)
Ventero
8

Python 2, 207 Bytes

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

Geben Sie das Raster als Liste von Zeilen ein, z

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

gefolgt von der Breite und Höhe. Rückgabe 0oder Trueentsprechend.

Erläuterung

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
quelle
Können Sie es nicht verkürzen, indem Sie es cmpeiner Variablen zuweisen ?
Blue
Reicht es aus, Zyklen durch Überprüfen auf bereits besuchte Positionen zu erkennen? Basierend auf Regel 4 kann der nächste Schritt auch von der vorherigen Richtung beeinflusst werden. Es scheint also möglich, dass Sie zweimal an derselben Position ankommen, aber keinen Zyklus haben, weil Sie sich in verschiedene Richtungen bewegen, basierend auf verschiedenen vorherigen Richtungen.
Reto Koradi
@ Schlammfisch Das wäre gerade
ausgeglichen
@RetoKoradi Hoffentlich behoben
Sp3000
Ja, das Hinzufügen Dzur Positionstaste sollte dies tun.
Reto Koradi
8

Julia - 394 300 246 214 Bytes

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)

Gibt 1 zurück, wenn die Ladung eine Schleife durchläuft, und 0, wenn sie zum Stillstand kommt. Es ist nicht "streng" wahr / falsch, da Julia 0 und 1 in booleschen Kontexten nicht zulässt ... aber ich betrachte Werte, xfür die bool(x)==truewahr und bool(x)==falsefalsch sind.

Die Eingabe Asollte in Form eines Zeichenarrays erfolgen. Wenn Sie das Fördergitter kopieren / einfügen, müssen Sie es in die entsprechende Form bringen. Verwenden Sie Folgendes, um zu vermeiden, dass Sie manuell damit umgehen müssen:

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

Wo offensichtlich (PASTE GRID HERE) sollte mit dem Gitter selbst ersetzt werden. Überprüfen Sie die Leerzeichen am Ende jeder Zeile, um sicherzustellen, dass alle Leerzeichen vorhanden sind (stellen Sie nicht sicher, dass alle Zeilen gleich lang sind). Beachten Sie, dass diese Zeile nicht Teil des eigentlichen Lösungscodes ist, sondern lediglich ein praktischer Code, um die Verwendung des Lösungscodes zu vereinfachen.

Ungolfed:

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

Hinweis: 1-[19 8]i%82%3wurde ausgewählt, um die fünf möglichen Zeichen mit der effizientesten Methode, die ich finden konnte, den entsprechenden Koordinatenpaaren zuzuordnen. Dies ist auch der Grund, warum beim Erstellen 5 verwendet wird, um die Leerzeichen zu füllen. Dies ist Gein einstelliges Zeichen, das zugeordnet wird [0 0].

Anwendungsbeispiel:

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
quelle
f(A,x,y)=ist kürzer als f=(A,x,y)->.
Alex A.
@AlexA. - stimmt, aber dann werde ich wahrscheinlich die entfernen f=und sie zu einer anonymen Funktion machen, wenn ich mit dem Golfen fertig bin.
Glen O
1
Es ist gleich lang, wenn es sich um eine benannte Funktion handelt, während es sich bei mehreren Parametern um eine anonyme Funktion handelt. f()=versus ()->.
Alex A.