Help, I'm trapped in an infinite factory!

Question

This challenge is loosely inspired by the Zachtronics game Infinifactory.

You are given a top-down view of a rectangular grid of conveyors, represented by >v<^. There may be cells without conveyors, represented by spaces. Here is an example:

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

This setup is implicitly surrounded by an infinite number of spaces.

Furthermore, you are given the dimensions of a rectangular piece of cargo which is placed onto the conveyors in the top left corner of the grid. Your task is to figure out whether the cargo ever comes to rest or whether it will end up moving in a loop.

Of course, the cargo is likely to cover several conveyors at once, so here are the rules for figuring out the direction of the cargo in each step:

1. Opposite conveyors cancel each other. So if a 3x2 cargo covers any of the following patches (outlined with hyphens and pipes for clarity), the result would be the same:

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

   The same goes for these:

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

   Since the exact position of a conveyor underneath the cargo is irrelevant, it doesn't matter which pairs you cancel.

   This cancellation is applied before the other rules. Therefore, for the other rules there will only be conveyors in at most two directions.

2. If the cargo doesn't cover any conveyors at all (either because all conveyors cancel, because it covers only spaces or because it moved fully off the grid), it comes to rest.

3. If the cargo covers more conveyors of one direction than of the other, the cargo moves in that direction. E.g., if a 3x2 cargo covered the following patch

   >>
   ^>^
   

   it would move to the right, because there are more > than ^. On the other hand, if it covered

   >>^
     ^
   

   this rule would not apply, because there's a tie between > and ^.

4. This leaves only cases in which there is a tie between adjacent directions (a tie between opposite directions would have cancelled). In this case, the cargo keeps moving along the axis it is already moving in. E.g. if a right-moving or left-moving 3x2 cargo is now covering the patch

   >>^
   ^  
   

   it would move to the right. If it had arrived on this patch moving up or down, it would now move up instead. If this kind of conflict occurs on the very first step of the simulation, assume that the cargo had been moving to the right.

Detailed Examples

Consider the conveyor grid at the top and a 3x2 cargo. The following is a step-by-step visualisation of the process. Each step consists of the grid, with the cargo represented by #, a small box which shows the conveyors covered by the cargo, another box with the conveyors after cancellation, and the rule that determines where the cargo moves:

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

At this point, the cargo enters a loop between the last two frames.

Now consider a 2x3 cargo instead:

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

In the last step, rule 2 applies because the cargo has moved off the grid, so it comes to rest and there won't be a loop.

Rules and Assumptions

Your input will be the conveyor grid as described above along with the width and height of the cargo. You may take these three parameters in any convenient order and format. For the grid, this means that you can read a single string with lines separated by newlines or other characters, or an array of strings, or an array of arrays of characters, as long as the individual grid cells are still represented by the characters >v<^ and spaces.

You should output a truthy value if the setup results in a loop of at least two frames or a falsy value if the cargo will come to rest.

You may assume that the grid will be padded to a rectangle with spaces, and that the cargo will initially fit into the grid.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

This is code golf, so the shortest answer (in bytes) wins.

Test Cases

The test cases are grouped by grids.

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

As an additional set of test cases, consider that any input where the grid consists solely of spaces must yield a falsy result.

I've checked all the test cases manually, so let me know if you think I've made a mistake.

Answer 1

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: Thanks a lot to Ventero who shortened the code a lot by applying some amazing tricks!

Input and output

The code represents a ruby function that takes three parameters:

• the grid, represented as an array of strings (each row is a different string)
• the width of the cargo
• the height of the cargo

It returns 1 (truthy) in case there's a loop, or nil (falsy) in case the cargo rests.

Tests

Here it is passing all of Martin's tests: http://ideone.com/zPPZdR

Explanation

There are no clever tricks in the code; it's a pretty straightforward implementation of the rules.

In the code below, move is a recursive function that makes a move according to the rules, and:

• returns truthy in case of a loop
• returns falsy in case of a rest
• otherwise calls itself to execute the next move

A more readable version is available here.

Note: the golfed code has undergone several modifications and is no longer similar to the readable version.

Answer 2

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)

Returns 1 if the cargo loops, and 0 if it comes to a stop. It's not "strictly" truthy/falsy, in that Julia doesn't permit 0 and 1 in boolean contexts... but I consider values x for which bool(x)==true are truthy and bool(x)==false are falsy.

Input A should be of the form of a character array. If you're copy/pasting the conveyor grid, you'll need to get it into the appropriate form. To save you from having to manually handle it, use the following:

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

Where obviously, (PASTE GRID HERE) should be replaced with the grid itself. Double-check the spaces at the end of each line, to make sure it actually has all of the spaces (it doesn't check to make sure that all lines are equal length). Note that this line isn't part of the actual solution code, just a convenient piece of code to make using the solution code a bit easier.

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

Note: 1-[19 8]i%82%3 has been chosen to map the five possible characters to the appropriate coordinate pairs by the most efficient method I could find. This is also the reason for using 5 to fill the spaces when creating G - it's a single-digit character that maps to [0 0].

Example of usage:

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

Answer 3

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

Input the grid as a list of rows, e.g.

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

followed by the width and height. Returns 0 or True accordingly.

Explanation

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