Las especies de gansos conocidos como Alex A son conocidos por residir en cuadrículas triangulares que consisten en 64 células:

^{(Imagen tomada de este problema no relacionado del Proyecto Euler ).}

Vamos a etiquetar cada celda con los números 0para 63comenzar desde la fila superior y luego movernos de izquierda a derecha en cada fila debajo de eso. Entonces la celda superior es 0y la celda inferior derecha es 63.

Cada celda tiene tres bordes. Podemos etiquetar cada borde en la forma a,bdonde ay bson los números de las celdas que comparten ese borde. Por ejemplo, el borde entre la celda 0y 2se llamaría 0,2o 2,0(no importa en qué orden los coloque).

El sistema de etiquetado para los bordes en el borde de la cuadrícula es diferente, ya que las celdas en el borde de la cuadrícula tienen un borde que no comparten con otras celdas. Si un borde es solo parte de una celda, utilizaremos la letra X. Por ejemplo, las tres fronteras de célula 0son 0,2, 0,X, y 0,X.

Algunas de las células contienen gansos . Sin embargo, estos gansos serán asesinados por zorros malvados (que vienen de fuera de los bordes de la cuadrícula) si no los proteges. Y si todos los gansos mueren, BrainSteel estará triste. Por lo tanto, escribiremos un programa que construya cercas alrededor de los gansos para protegerlos de los zorros. Los gansos deberían existir en un único polígono de cercos completamente cerrado. Nuestro presupuesto de cercas es bastante bajo, así que use la menor cantidad de cercas posible.

Descripción de entrada

Una lista de números, separados por comas, de 0a 63, que representan las celdas que contienen gansos. Ejemplo:

6,12

Descripción de salida

Una lista de fronteras que necesitan tener cercas construidas para proteger a los gansos con éxito. Este debería ser el menor número de cercas posible. Ejemplo:

5,6 6,7 11,12 12,13 

C #, 530 bytes

Complete el programa C #, toma la entrada como una sola línea desde STDIN y emite una sola línea hacia STDOUT, con un "" final.

Esto es bastante largo ... y tiene demasiada repetición x / y / z, pero hasta ahora no he podido reducirlo a nada sensato, y tener un examen en 2 horas, podría volver a esto mañana.

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();}}}}

Este diagrama explica la mayor parte de lo que está sucediendo.

Reconozca que debido a que no podemos tener secciones de ancho 0, un "hexágono" siempre será la forma más barata (y tiene la ventaja de dar a los gansos el máximo espacio para moverse).

El programa funciona traduciendo primero todos los índices de las celdas de entrada a las coordenadas x / y / z, y encontrando el mínimo / máximo de cada uno de 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

A continuación, revisa cada índice de celda y comprueba si encaja en el límite 'hexágono' que hemos descrito. Si es así, comprueba si está en cualquiera de los bordes extremos de los límites (es decir, x = xmin, o y = ymax) y agrega los bordes correspondientes si es así. Tiene que resolver el índice del borde al lado del cual está. Para x y z, simplemente los incrementamos / decrementamos como queramos, y luego usamos la siguiente fórmula:

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

Observe que la "paridad" siempre cambia, y que y no está involucrado. Para y, no tenemos que cambiar nada, pero el código es un poco desordenado porque tiene que realizar una comprobación de límites de "triángulo" para detectar si la celda de al lado debe ser una "X" o no.

Solución de ejemplo (Celdas con gansos justo desde las tres esquinas):

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 

Código ordenado con comentarios:

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