13
\$\begingroup\$

The species of geese known as Alex A are known for residing in triangular grids consisting of 64 cells:

Cells
(Picture taken from this unrelated Project Euler problem.)

We'll label each cell with the numbers 0 to 63 starting from the top row and then moving from left to right on each row below that. So the top cell is 0 and the bottom-right cell is 63.

Each cell has three borders. We can label each border in the form a,b where a and b are the numbers of the cells that share that border. For instance, the border between cell 0 and 2 would be called 0,2 or 2,0 (it doesn't matter what order you put them in).

The labeling system for borders on the very edge of the grid are different, since the cells on the edge of the grid have a border that they don't share with other cells. If a border is only part of one cell, we will use the letter X. For instance, the three borders of cell 0 are 0,2, 0,X, and 0,X.

Some of the cells contain geese. However, these geese will be killed by evil foxes (that come from outside the borders of the grid) if you don't protect them. And if all the geese die then BrainSteel will be sad. Therefore we will write a program that builds fences around the geese to protect them from the foxes. The geese should exist in a single fully enclosed polygon of fences. Our fence budget is quite low so use the least number of fences possible.

Input Description

A list of numbers, comma separated, from 0 to 63, representing the cells that contain geese. Example:

6,12

Output Description

A list of borders that need to have fences built on them to protect the geese successfully. This should be the smallest number of fences possible. Example:

5,6 6,7 11,12 12,13 
\$\endgroup\$
  • \$\begingroup\$ "The geese should exist in a fully enclosed polygon of fences." Must all the geese live in the same polygon, or may there be multiple (or 0) polygons? \$\endgroup\$ – feersum May 27 '15 at 3:56
  • \$\begingroup\$ @feersum All the geese should live in the same polygon. I've edited the question to make it clear. \$\endgroup\$ – absinthe May 27 '15 at 4:00
  • \$\begingroup\$ @Katya May the polygon have self-intersections or zero-width sections? Think like an hourglass shape. \$\endgroup\$ – orlp May 27 '15 at 6:04
  • \$\begingroup\$ @orlp What is a zero-width section? \$\endgroup\$ – absinthe May 27 '15 at 6:08
  • 2
    \$\begingroup\$ @orlp The polygon should not contain zero width sections. \$\endgroup\$ – absinthe May 27 '15 at 6:19
10
\$\begingroup\$

C#, 530 bytes

Complete C# program, takes input as a single line from STDIN, and outputs a single line to STDOUT, with a trailing " ".

This is rather long... and has way too much x/y/z repetition, but I've not been able to reduce it to anything sensible thus far, and have an exam in 2 hours, might come back to this tomorrow.

using Q=System.Console;class P{static void Main(){int q=9,w=0,e=9,r=0,t=9,u=0,i=0,x=0,y=0,z=0,p=0;System.Action V=()=>{z=(int)System.Math.Sqrt(i);p=(x=i-z*z)%2;x/=2;y=(++z*z--+~i)/2;},W=()=>{Q.Write(i+","+(x<0|y++<0|z>7?"X":""+(z*z+2*x+1-p))+" ");};foreach(var g in Q.ReadLine().Split(',')){i=int.Parse(g);V();q=q>x?x:q;w=w<x?x:w;e=e>y?y:e;r=r<y?y:r;t=t>z?z:t;u=u<z?z:u;}for(i=64;i-->0;){V();if(!(x<q|x>w|y<e|y>r|z<t|z>u))if(p>0){if(y==r)W();if(x++==w)W();x--;if(z--==t)W();}else{if(y--==e)W();if(x--==q)W();x++;if(z++==u)W();}}}}

This diagram explains most of what is going on.

Grid described as x/y/z/(p), showing example solution

Recognize that because we can't have 0-width sections, a "hexagon" is always going to be the cheapest shape (and has the benefit of giving the geese the maximum of space to move in).

The program works by first translating all the input cell indices into x/y/z coords, and finding the min/max of each of x/y/z.

z = floor(root(i))
x = floor((i - z^2) / 2)
y = floor((z+1)^2 - i - 1) / 2)
p = (i - z^2) % 2

Next, it goes through each cell index, and checking if it fits in the 'hexagon' bound we have described. If it is then it checks if it's on any of the extreme edges of the bounds (i.e. x = xmin, or y = ymax) and adds corresponding edges if it is. It has to work out the index of the edge it's next to. For x and z, we just increment/decrement them however we want, and then use the following formula:

i = z^2 + 2*x + (1-p)

Notice that the "parity" always changes, and that y is not involved. For y, we don't have to change anything, but the code is a bit of a mess because it has to perform "triangle" bounds checking to detect whether the cell next door should be an "X" or not.

Example solution (Cells with geese just in from the three corners):

Input
2,50,62

Output
62,63 61,X 59,X 57,X 55,X 53,X 51,X 50,49 48,X 36,X 35,X 25,X 24,X 16,X 15,X 9,X 8,X 4,X 3,X 2,0 1,X 

Tidier code with comments:

using Q=System.Console;

class P
{
    static void Main()
    {
        int q=9,w=0,e=9,r=0,t=9,u=0, // min/max x/y/z/ (init min high, and max low)
        i=0, // index of cell we are looking at
        x=0,y=0,z=0,p=0; // x,y,z dimension

        System.Action V=()=>
            { // translates the index into x/y/z/p
                z=(int)System.Math.Sqrt(i);
                p=(x=i-z*z)%2; // 'parity'
                x/=2; // see p assignment
                y=(++z*z--+~i)/2; // ~i == -i - 1
            },
            W=()=>
            { // writes out the edge of i, and the cell described by x/z/inverse of p   (the inversion of p handles y +/-)
                Q.Write(i+","+ // write out the edge
                        (x<0|y++<0|z>7?"X":""+(z*z+2*x+1-p)) // either X (if we go out of 'trianlge' bounds), or we translate x/z/inverse of p into an index
                        +" "); // leaves a trailing space (as shown in example output)
            };

        foreach(var g in Q.ReadLine().Split(',')) // for each cell with geese
        {
            i=int.Parse(g); // grab index of cell
            V(); // compute x/y/z/p
            q=q>x?x:q; // sort out mins/maxes
            w=w<x?x:w;
            e=e>y?y:e;
            r=r<y?y:r;
            t=t>z?z:t;
            u=u<z?z:u;

            // code like the above suggests a solution with a couple of arrays would be better...
            // I've not had success with that yet, but maybe in a couple of days I will try again
        }

        for(i=64;i-->0;) // for each cell
        {
            V(); // compute x/y/z/p
            if(!(x<q|x>w|y<e|y>r|z<t|z>u)) // if we are inside the 'hex' bounds
                if(p>0)
                { // x max, y max, z min
                    // these checks check that we are on the extremes of the 'hex' bounds,
                    // and set up the appropriate vars for W calls to put the edges in
                    // must do y first, because W modifies it for us (saves 2 bytes in the next block)
                    if(y==r) // don't need the ++ (can't go out of 'trianlge' bounds)
                        W();
                    if(x++==w)
                        W();
                    x--;
                    if(z--==t)
                        W();
                    //z++; not used again
                }
                else
                { // x min, y min, z max
                    if(y--==e) // do need the -- (used for 'trianlge' bounds checking)
                        W();
                    // y is reset in W, as such
                    if(x--==q)
                        W();
                    x++;
                    if(z++==u)
                        W();
                    //z--; not used again
                }
        }
    }
}
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ You can save a byte with using System;. \$\endgroup\$ – LegionMammal978 May 27 '15 at 13:00
  • \$\begingroup\$ @LegionMammal978 infact he gains two doing that.. He only uses it for Q.Write and Q.ReadLine. those, plus the using statement he has now is using Q=System.Console;Q.Write();Q.ReadLine() (45 Bytes) versus your suggestion using System;Console.Write();Console.ReadLine() (47 Bytes). \$\endgroup\$ – Kade May 27 '15 at 13:39
  • \$\begingroup\$ Also, you can drop 10 bytes by not needlessly initializing i, x, y, z, and p to 0. \$\endgroup\$ – LegionMammal978 May 27 '15 at 14:41
  • \$\begingroup\$ @LegionMammal978 you sure? I tried that and it's giving errors for using a un-assigned vairable. \$\endgroup\$ – Kade May 27 '15 at 14:49
  • \$\begingroup\$ @Vioz- Which variables? Which lines on the annotated version? \$\endgroup\$ – LegionMammal978 May 27 '15 at 15:40

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.