Les espèces d'oies connues sous le nom d' Alex A sont connues pour résider dans des grilles triangulaires composées de 64 cellules:

^{(Photo prise à partir de ce problème non lié au projet Euler .)}

Nous allons étiqueter chaque cellule avec les numéros 0à 63partir de la ligne du haut, puis de gauche à droite sur chaque ligne en dessous. La cellule du haut est donc la cellule 0du bas à droite 63.

Chaque cellule a trois bordures. Nous pouvons étiqueter chaque bordure sous la forme a,boù aetb sont les numéros des cellules qui partagent cette bordure. Par exemple, la frontière entre la cellule 0et 2serait appelée 0,2ou 2,0(peu importe l'ordre dans lequel vous les mettez).

Le système d'étiquetage des bordures sur le bord même de la grille est différent, car les cellules sur le bord de la grille ont une bordure qu'elles ne partagent pas avec d'autres cellules. Si une bordure n'est qu'une partie d'une cellule, nous utiliserons la lettre X. Par exemple, les trois frontières de la cellule0 sont 0,2, 0,Xet 0,X.

Certaines cellules contiennent oies . Cependant, ces oies seront tuées par des renards maléfiques (qui viennent de l'extérieur des frontières de la grille) si vous ne les protégez pas. Et si toutes les oies meurent, BrainSteel sera triste. Par conséquent, nous allons écrire un programme qui construit des clôtures autour des oies pour les protéger des renards. Les oies doivent exister dans un seul polygone entièrement clos de clôtures. Notre budget de clôture est assez faible, utilisez donc le moins de clôtures possible.

Description de l'entrée

Une liste de nombres, séparés par des virgules, de 0à 63, représentant les cellules qui contiennent des oies. Exemple:

6,12

Description de sortie

Une liste des frontières sur lesquelles des clôtures doivent être construites pour protéger les oies avec succès. Ce devrait être le plus petit nombre de clôtures possible. Exemple:

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

C #, 530 octets

Programme C # complet, prend l'entrée en une seule ligne de STDIN et sort une seule ligne vers STDOUT, avec un "" de fin.

C'est assez long ... et a beaucoup trop de répétitions x / y / z, mais je n'ai pas été en mesure de le réduire à quelque chose de sensé jusqu'à présent, et passer un examen dans 2 heures, pourrait y revenir demain.

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

Ce diagramme explique la plupart de ce qui se passe.

Reconnaissez que parce que nous ne pouvons pas avoir de sections de largeur 0, un "hexagone" sera toujours la forme la moins chère (et a l'avantage de donner aux oies le maximum d'espace pour se déplacer).

Le programme fonctionne en traduisant d'abord tous les indices de cellule d'entrée en coordonnées x / y / z et en trouvant le min / max de chacun des 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

Ensuite, il passe par chaque index de cellule, et vérifie s'il s'inscrit dans la limite «hexagonale» que nous avons décrite. Si c'est le cas, il vérifie s'il se trouve sur l'un des bords extrêmes des limites (c'est-à-dire x = xmin ou y = ymax) et ajoute les bords correspondants si c'est le cas. Il doit déterminer l'indice du bord à côté duquel il se trouve. Pour x et z, nous les incrémentons / décrémentons comme nous le voulons, puis utilisons la formule suivante:

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

Notez que la "parité" change toujours et que y n'est pas impliqué. Pour y, nous n'avons rien à changer, mais le code est un peu désordonné car il doit effectuer des vérifications de limites "triangulaires" pour détecter si la cellule voisine doit être un "X" ou non.

Exemple de solution (cellules avec des oies venant des trois coins):

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 

Code plus ordonné avec commentaires:

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