Save the Geese from Extinction

Question

The species of geese known as Alex A are known for residing in triangular grids consisting of 64 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 

Answer 1

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.

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