26
\$\begingroup\$

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.

\$\endgroup\$
  • 10
    \$\begingroup\$ Fitting music \$\endgroup\$ – Fatalize Aug 16 '15 at 11:22
  • 4
    \$\begingroup\$ @Fatalize I'm getting Twitch Plays Pokemon flashbacks... \$\endgroup\$ – undergroundmonorail Aug 16 '15 at 11:34
  • \$\begingroup\$ "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." - does this mean we can have the conveyor grid taken in as an array of arrays? That is, a 2x2 grid with [^^/v<] becomes [[0,1] [0,1];[0,-1] [-1,0]]? Or do you mean it's up to us whether it's STDIN, a string input, a char array input, etc, but it still has to be in the form of ^, v, >, and <? \$\endgroup\$ – Glen O Aug 16 '15 at 11:39
  • \$\begingroup\$ @GlenO You can take a newline (or other character) separated string, an array of strings, or an array of arrays of characters, but each cell should still be represented by the characters ><^v or a space. I'll clarify that. \$\endgroup\$ – Martin Ender Aug 16 '15 at 11:41
  • \$\begingroup\$ So what happens if the cargo moves onto a conflict where the continued direction is not one of the choices? That is, if it was moving right, and now must choose between up and left. \$\endgroup\$ – Joshua Aug 16 '15 at 20:47
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Since it doesn't matter whether r contains additional entries besides the four directions, r[y>=0&&x>=0&&g[y]&&g[y][x]]+=1 should save a few bytes. \$\endgroup\$ – Ventero Aug 16 '15 at 14:49
  • \$\begingroup\$ I took the liberty of golfing things a little further, hope you don't mind: ideone.com/k69BmH \$\endgroup\$ – Ventero Aug 16 '15 at 16:11
  • \$\begingroup\$ @Ventero Wow, you've done amazing things to the code. I would never have thought about transforming the hash into a lambda. I was trying out some of my ideas to shorten the program, but was nowhere near what you did. Thanks a lot! \$\endgroup\$ – Cristian Lupascu Aug 16 '15 at 17:04
  • 2
    \$\begingroup\$ Got it down to 200 through slightly shorter handling of negative indices, guess I'll leave it at that for now: ideone.com/k69BmH \$\endgroup\$ – Ventero Aug 16 '15 at 19:16
  • 2
    \$\begingroup\$ Actually, 198: ideone.com/ptKrzf :) \$\endgroup\$ – Ventero Aug 17 '15 at 0:21
8
\$\begingroup\$

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
                  )
            )
\$\endgroup\$
  • \$\begingroup\$ Can't you shorten it by assigning cmp to a variable? \$\endgroup\$ – Blue Aug 16 '15 at 16:21
  • \$\begingroup\$ Is it sufficient to detect cycles by checking for already visited positions? Based on rule 4, the next step can also be influenced by the previous direction. So it seems possible that you could arrive at the same position twice, but not have a cycle because you move in different directions based on different previous directions. \$\endgroup\$ – Reto Koradi Aug 16 '15 at 16:26
  • \$\begingroup\$ @muddyfish That'd just break even \$\endgroup\$ – Sp3000 Aug 16 '15 at 16:33
  • \$\begingroup\$ @RetoKoradi Hopefully fixed \$\endgroup\$ – Sp3000 Aug 17 '15 at 9:41
  • \$\begingroup\$ Yes, adding D to the position key should do it. \$\endgroup\$ – Reto Koradi Aug 17 '15 at 15:19
8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ f(A,x,y)= is shorter than f=(A,x,y)->. \$\endgroup\$ – Alex A. Aug 16 '15 at 19:26
  • \$\begingroup\$ @AlexA. - true, but then, I'll probably remove the f= and make it an anonymous function when I finish golfing it. \$\endgroup\$ – Glen O Aug 16 '15 at 19:32
  • 1
    \$\begingroup\$ It'll be the same length if it's a named function versus an anonymous function when there are multiple parameters. f()= versus ()->. \$\endgroup\$ – Alex A. Aug 16 '15 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.