Gatunki gęsi znane jako Alex A znane są z przebywania w trójkątnych siatkach składających się z 64 komórek:

^{(Zdjęcie pochodzi z tego niezwiązanego problemu Euler projektu .)}

Będziemy oznaczyć każdą komórkę z numerami 0, aby 63począwszy od górnego rzędu, a następnie porusza się od lewej do prawej w każdym wierszu poniżej tego. Tak więc górna komórka jest, 0a dolna prawa komórka jest 63.

Każda komórka ma trzy granice. Możemy oznaczyć każdą ramkę w formie, a,bgdzie ai gdzie bsą numery komórek, które dzielą tę granicę. Na przykład zostanie wywołana granica między komórką 0a lub (nie ma znaczenia, w jakiej kolejności je umieścisz).20,22,0

System etykietowania granic na samej krawędzi siatki jest inny, ponieważ komórki na krawędzi siatki mają granicę, której nie dzielą z innymi komórkami. Jeśli ramka jest tylko częścią jednej komórki, użyjemy litery X. Na przykład, trzy granice komórki 0są 0,2, 0,X, i 0,X.

Niektóre komórki zawierają gęsi . Jednak te gęsi zostaną zabite przez złe lisy (które pochodzą spoza granic sieci), jeśli ich nie ochronicie. A jeśli wszystkie gęsi zginą, BrainSteel będzie smutny. Dlatego napiszemy program, który buduje ogrodzenia wokół gęsi, aby chronić je przed lisami. Gęsi powinny istnieć w jednym całkowicie zamkniętym wielokącie ogrodzenia. Nasz budżet na ogrodzenie jest dość niski, więc używaj możliwie najmniejszej liczby ogrodzeń.

Opis wejścia

Lista liczb, oddzielonych przecinkami, od 0do 63, reprezentujących komórki zawierające gęsi. Przykład:

6,12

Opis wyjścia

Lista granic, na których trzeba zbudować ogrodzenia, aby skutecznie chronić gęsi. Powinna to być jak najmniejsza liczba ogrodzeń. Przykład:

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

C #, 530 bajtów

Kompletny program w języku C #, pobiera dane wejściowe jako jeden wiersz ze STDIN i wysyła pojedynczy wiersz do STDOUT, z końcowym „”.

To jest dość długie ... i ma zbyt wiele powtórzeń x / y / z, ale do tej pory nie byłem w stanie zredukować go do niczego sensownego, a egzamin za 2 godziny może wrócić do jutra.

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

Ten schemat wyjaśnia większość tego, co się dzieje.

Zauważ, że ponieważ nie możemy mieć sekcji o szerokości 0, „sześciokąt” zawsze będzie najtańszym kształtem (i ma tę zaletę, że daje gęsi maksymalną przestrzeń do poruszania się).

Program działa najpierw poprzez przetłumaczenie wszystkich indeksów komórek wejściowych na współrzędne x / y / z i znalezienie min / max każdego z 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

Następnie przechodzi przez indeks każdej komórki i sprawdza, czy pasuje do opisanego powyżej sześciokąta. Jeśli tak, to sprawdza, czy znajduje się na którejś z ekstremalnych krawędzi granic (tj. X = xmin lub y = ymax) i dodaje odpowiednie krawędzie, jeśli tak jest. Musi obliczyć indeks krawędzi obok. W przypadku xiz zwiększamy / zmniejszamy je w dowolny sposób, a następnie stosujemy następującą formułę:

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

Zauważ, że „parzystość” zawsze się zmienia i że y nie jest zaangażowany. Dla y, nie musimy nic zmieniać, ale kod jest trochę bałaganu, ponieważ musi wykonać granice „trójkąta”, aby sprawdzić, czy komórka obok powinna być „X”, czy nie.

Przykładowe rozwiązanie (Komórki z gęsiami tylko z trzech rogów):

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 

Kod Tidier z komentarzami:

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