Este desafío está inspirado libremente en el juego de Zachtronics Infinifactory .

Se le da una vista de arriba hacia abajo de una cuadrícula rectangular de transportadores, representados por >v<^. Puede haber celdas sin transportadores, representadas por espacios. Aquí hay un ejemplo:

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

Esta configuración está implícitamente rodeada por un número infinito de espacios.

Además, se le dan las dimensiones de una pieza rectangular de carga que se coloca en los transportadores en la esquina superior izquierda de la cuadrícula. Su tarea es determinar si la carga se detiene o si terminará moviéndose en un bucle.

Por supuesto, es probable que la carga cubra varios transportadores a la vez, así que aquí están las reglas para determinar la dirección de la carga en cada paso:

1. Los transportadores opuestos se cancelan entre sí. Entonces, si una carga de 3x2 cubre alguno de los siguientes parches (delineados con guiones y tuberías para mayor claridad), el resultado sería el mismo:

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

   Lo mismo vale para estos:

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

   Dado que la posición exacta de un transportador debajo de la carga es irrelevante, no importa qué pares cancele.

   Esta cancelación se aplica antes que las otras reglas. Por lo tanto, para las otras reglas solo habrá transportadores en un máximo de dos direcciones.

2. Si la carga no cubre ningún transportador (ya sea porque todos los transportadores se cancelan, porque cubre solo espacios o porque se movió completamente fuera de la red), se detiene.

3. Si la carga cubre más transportadores de una dirección que de la otra, la carga se mueve en esa dirección. Por ejemplo, si una carga de 3x2 cubrió el siguiente parche

   >>
   ^>^
   

   se movería hacia la derecha, porque hay más >que ^. Por otro lado, si cubría

   >>^
     ^
   

   esta regla no se aplicaría, porque hay un vínculo entre >y ^.

4. Esto deja solo casos en los que hay un empate entre direcciones adyacentes (un empate entre direcciones opuestas se habría cancelado). En este caso, la carga sigue moviéndose a lo largo del eje en el que ya se está moviendo. Por ejemplo, si una carga 3x2 que se mueve hacia la derecha o hacia la izquierda ahora está cubriendo el parche

   >>^
   ^  
   

   se movería a la derecha. Si hubiera llegado a este parche moviéndose hacia arriba o hacia abajo, ahora se movería hacia arriba. Si este tipo de conflicto ocurre en el primer paso de la simulación, suponga que la carga se ha estado moviendo hacia la derecha.

Ejemplos detallados

Considere la rejilla del transportador en la parte superior y una carga de 3x2. La siguiente es una visualización paso a paso del proceso. Cada paso consiste en la cuadrícula, con la carga representada por #, una pequeña caja que muestra los transportadores cubiertos por la carga, otra caja con los transportadores después de la cancelación y la regla que determina dónde se mueve la carga:

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

En este punto, la carga entra en un bucle entre los dos últimos cuadros.

Ahora considere una carga 2x3 en su lugar:

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

En el último paso, la regla 2 se aplica porque la carga se ha salido de la red, por lo que se detiene y no habrá un bucle.

Reglas y suposiciones

Su entrada será la rejilla del transportador como se describió anteriormente junto con el ancho y la altura de la carga. Puede tomar estos tres parámetros en cualquier orden y formato convenientes. Para la cuadrícula, esto significa que puede leer una sola cadena con líneas separadas por líneas nuevas u otros caracteres, o una matriz de cadenas, o una matriz de matrices de caracteres, siempre que las celdas individuales de la cuadrícula sigan representadas por los caracteres >v<^y espacios

Debe generar un valor verdadero si la configuración da como resultado un bucle de al menos dos cuadros o un valor falso si la carga se detendrá.

Puede suponer que la cuadrícula se rellenará con un rectángulo con espacios y que la carga inicialmente se ajustará a la cuadrícula.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Casos de prueba

Los casos de prueba están agrupados por cuadrículas.

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

Como un conjunto adicional de casos de prueba, considere que cualquier entrada donde la cuadrícula consista únicamente en espacios debe producir un resultado falso.

Revisé todos los casos de prueba manualmente, así que avíseme si cree que he cometido un error.

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

Editar: ¡ Muchas gracias a Ventero que acortó mucho el código aplicando algunos trucos increíbles!

Entrada y salida

El código representa una función ruby ​​que toma tres parámetros:

• la cuadrícula, representada como una matriz de cadenas (cada fila es una cadena diferente)
• el ancho de la carga
• la altura de la carga

Regresa 1(verdad) en caso de que haya un bucle, o nil(falso) en caso de que la carga descanse.

Pruebas

Aquí está pasando todas las pruebas de Martin: http://ideone.com/zPPZdR

Explicación

No hay trucos ingeniosos en el código; Es una implementación bastante sencilla de las reglas.

En el siguiente código, movees una función recursiva que realiza un movimiento de acuerdo con las reglas y:

• devuelve verdadero en caso de un bucle
• devuelve falsedad en caso de descanso
• de lo contrario se llama a sí mismo para ejecutar el siguiente movimiento

Una versión más legible está disponible aquí .

Nota: el código de golf ha sufrido varias modificaciones y ya no es similar a la versión legible.

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

Ingrese la cuadrícula como una lista de filas, por ej.

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

seguido por el ancho y la altura. Devoluciones 0o en Trueconsecuencia.

Explicación

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

Devuelve 1 si la carga se repite y 0 si se detiene. No es "estrictamente" verdad / falsedad, ya que Julia no permite 0 y 1 en contextos booleanos ... pero considero valores xpara los que bool(x)==trueson verdaderos y bool(x)==falsefalsos.

La entrada Adebe tener la forma de una matriz de caracteres. Si está copiando / pegando la cuadrícula del transportador, deberá colocarlo en la forma adecuada. Para evitar que tenga que manejarlo manualmente, use lo siguiente:

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

Donde obviamente, (PASTE GRID HERE)debe reemplazarse con la propia cuadrícula. Verifique dos veces los espacios al final de cada línea, para asegurarse de que realmente tenga todos los espacios (no verifica para asegurarse de que todas las líneas tengan la misma longitud). Tenga en cuenta que esta línea no es parte del código de solución real, solo es un código conveniente para facilitar un poco el uso del código de solución.

Sin golf:

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

Nota: 1-[19 8]i%82%3ha sido elegido para asignar los cinco caracteres posibles a los pares de coordenadas apropiados por el método más eficiente que pude encontrar. Esta es también la razón para usar 5 para llenar los espacios al crear G: es un carácter de un solo dígito al que se asigna [0 0].

Ejemplo de uso:

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