24
\$\begingroup\$

The goal of this challenge is to find the direction and area enclosed by a loop.

Input:

A rectangular grid consisting entirely of these characters: ^v<>

(Optionally, you may also be given the dimensions of the grid before the grid itself in decimal with a prefix, suffix, and separator character of your choice.)

A loop in the grid is a set of the aforementioned characters such that one points to the next, pointing to the next, eventually pointing back at the first character. For example:

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

The left grid is the sample input; the right grid is the loop isolated.

The input grid will contain either no loops at all or one loop; you do not have to worry about any cases in which the grid contains more than one loop.

Output:

If the grid contains no loop, output X.

If the grid contains two arrows pointing at each other, output 0.

If the grid contains a counterclockwise loop, count the characters enclosed by the loop, including the border. Output that number.

If the grid contains a clockwise loop, follow the same process for the counterclockwise loop, but output the negative of that number. For instance, the above input grid would have an output of -11: 10 come from the loop itself, and 1 from the character enclosed by the loop.

This is . Shortest code wins.

Test cases:

<<^
^>v
^v<

Output X.

<<<<
><<<
>>^>

Output 0.

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

Output -15.

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

Output 20.

\$\endgroup\$
  • 4
    \$\begingroup\$ Why the downvotes? The question looks fine to me. \$\endgroup\$ – xnor Nov 25 '15 at 8:51
  • \$\begingroup\$ How do you determine if a loop is clockwise or not? For example, search "double spiral maze" on Google Images. How do you determine which way the path is running? Here's an example. \$\endgroup\$ – ghosts_in_the_code Nov 25 '15 at 12:45
  • \$\begingroup\$ @ghosts_in_the_code That does not form a closed loop. \$\endgroup\$ – Martin Ender Nov 25 '15 at 12:53
  • \$\begingroup\$ @MartinBüttner Imagine the outer two ends to connect to each other. \$\endgroup\$ – ghosts_in_the_code Nov 25 '15 at 13:04
  • 4
    \$\begingroup\$ @ghosts_in_the_code Then one of the ends would have to turn around to meet the other. In that case you get an intersection free loop which can be unfolded into a circle to show whether it's going clockwise or counterclockwise. A simple test is to look at the bottom-most point of the loop and check if it's going left or right (in the case of the grid, that point is not unique, but you could look at the bottom-right-most cell of the loop and check if it's going left or up). \$\endgroup\$ – Martin Ender Nov 25 '15 at 13:07
4
\$\begingroup\$

C#, 604 bytes

Complete program, accepts input (line-delimitated layout, no dimensions) from STDIN, outputs to STDOUT.

using C=System.Console;class P{static void Main(){int w=0,W,i,j,t,k,l,c;string D="",L;for(;(L=C.ReadLine())!=null;D+=L)w=L.Length;var R=new[]{-1,0,1,w,-w};L="X";for(W=i=D.Length;i-->0;){var M=new int[W];for(k=j=i;i>0;){M[j]=++k;t=j+R[c=D[j]%5];if(t<0|t>=W|c<3&t/w!=j/w|c>2&t%w!=j%w)break;j=t;if((l=M[j])>0){var J=new int[W+1];System.Func<int,int>B=null,A=s=>J[s]<0?0:J[k=B(s)]=k==W?k:i;B=x=>J[x]==x?x:B(J[x]);for(i=J[W]=W;i>0;)J[--i]=M[i]<l?i%w<1|i%w>w-2|i<w|i>W-w?W:i:-1;for(;i<W;)if(J[++i]<0)l=D[i]%5/2-1;else{A(i-1);if(i>w)A(i-w);}for(c=W;i-->0;L=""+(c>2?c:0)*l)c-=J[i]<0?0:B(i)/W;}}}C.WriteLine(L);}}

The program works by first reading in the layout, needless to say, and then iterating over every cell. We then run a 'snake' from each cell, which follows the arrows until it runs off the edge, or runs into itself. If it runs into itself, then we know we have found a loop (or one of those "><" things), and it also knows how much of the snake is in the loop.

Once we know we have a loop, we know which cells are on the loop, and we create a map from each cell (+1, for reasons) to either itself, -1 (means it's on the loop), or W (the whole width) if it's on the edge (or the +1 (which is at index W) to simplify things further one).

While we do this, we also find the direction that the 'last' element of the loop has (that is, the last element of the loop on the last row that has elements from the loop on it). This element must be a "<" or an "^", and this tells us the clockness (CW/CCW) of the loop (translated to -1/+1).

We then perform a disjoin set pass, which assigns all the elements that are outside the loop to the W set. We then subtract how many of these there are from W to get the number contained on and in the loop. If this number is less than 3, we replace it with 0. We multiply this by the clockness, set it as the result, and somehow escape from the for loops, where the result is output.

If, however, most of the above never happens (because no snake ever finds itself), then the result remains as "X", and that is outputted.

using C=System.Console;

class P
{
    static void Main()
    {
        int w=0, // width
        W, // full length
        i, // used for iterating over all the cells
        j, // keeps track of where the snake as got to
        t, // t is next j
        k, // how far along the snake we are, kind of
        // later on, k is used as temp for A
        l, // stores a threshold for how far along the snake the loop starts
        // later on, l stores the last seen pointer - this tells us the clockness
        c; // the translated direction
        // later on, c is a backwards-count

        string D="", // D is the map
        L; // used for reading lines, and then storing the result

        // might not be the best yay of doing this
        for(;(L=C.ReadLine())!=null; // read a line, while we can
            D+=L) // add the line to the map
            w=L.Length; // record the width

        var R=new[]{-1,0,1,w,-w}; // direction table (char%5) - might be able to replace this array with some bit bashing/ternary

        L="X"; // can't seem to fit this in anywhere... (don't strictly need to re-use L)
        for(W=i=D.Length;i-->0;) // for each cell, we send a 'snake' to try to find the loop from that cell
        {
            var M=new int[W]; // stores how far along the snake this point is

            for(k=j=i; // k's value doesn't really matter, as long as it's not stupidly big
                i>0;) // the i>0 check is just for when we return (see comment at the end of the code)
            {
                M[j]=++k; // store snake point and advance distance

                t=j+R[c=D[j]%5]; // t is position after move (translate <>v^ to 0234 (c is direction))
                //c=D[j]%5; // translate <>v^ to 0234 (c is direction)
                //t=j+R[c]; // t is position after move
                if(t<0|t>=W|c<3&t/w!=j/w|c>2&t%w!=j%w)
                    break; // hit an edge - will always happen if we don't find a loop - give up on this snake
                j=t; // move to new position

                if((l=M[j])>0) // we've been here before...
                {
                    // disjoint sets (assign all the edges to one set, assign all the ones on the line to another set, do adjacent disjoint, return size-outteredge (minus if necessary)
                    var J=new int[W+1]; // looks like we can reuse M for this

                    System.Func<int,int>B=null,
                    // whatever s points at should point to i, unless s points to W, in which case it should keep point to W
                    A=s=>J[s]<0?0:J[k=B(s)]=k==W?k:i;
                    // read the value this points to
                    B=x=>J[x]==x?x:B(J[x]);

                    for(i=J[W]=W;i>0;)
                        J[--i]=M[i]<l? // if we are not part of the loop
                            i%w<1|i%w>w-2|i<w|i>W-w? // if we are on the edge
                                W: // on the edge
                                i: // not on the edge
                             -1; // this is on the loop

                    // now fill in
                    // we don't have to worry about wrapping, the important bit being an un-wrapping closed loop
                    // i = 0
                    for(;i<W;)
                        if(J[++i]<0) // we are on the loop
                            l=D[i]%5/2-1; // last one must be ^(4) or <(0)
                        else{ // can probably crush this into an l returning l assigning term (with if above)
                            A(i-1);
                            if(i>w)
                                A(i-w);
                        }

                    // now count the number of non-edges
                    for(c=W; // assume everything is a non-edge
                        i-->0;
                        L=""+(c>2?c:0)*l) // set output to be number of non-edges * clockness (or 0 if too few)
                        c-=J[i]<0?0:B(i)/W; // subtract 1 if an edge (B(i) is W), othewise 0

                    // at this point, i is 0, so we will fall out of all the loops
                }
            }
        }

        C.WriteLine(L); // output result
    }
}
\$\endgroup\$

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.