*** Wykres ameoba **** jest rodzajem drzewa, którego wszystkie węzły mają wartości od 0 do niektórych nieujemnych liczb całkowitych N, a każdy konkretny węzeł o wartości x <N łączy się z x + 1 odrębnymi węzłami o wartościach x + 1.

Wykres Ameoba dla N = 3: (oznaczono A ₃ )

Zauważ, że 2 nie mogą współdzielić żadnego z 3; dokładnie trzy 3 muszą „należeć” do każdej 2.

Wyzwanie

Twoim zadaniem jest indukcyjne „powiększenie” tych wykresów ameoba w dwuwymiarowej siatce poprzez chciwe minimalizowanie odległości Manhattanu między węzłami:

• Sprawa podstawowa: ₀ to po prostu wykres 0.
• Indukcyjny krok: _{n + 1} jest wytwarzany przez iteracyjne umieszczenie nowej N + 1 o wartości węzłów, tak blisko jak to możliwe, N wartości węzłów w Istniejące _N struktury. (Może być tak blisko, jak to możliwe, ponieważ najbliższe miejsca mogą już być wypełnione).

W przypadku etapu indukcyjnego ogólna procedura, którą należy wykonać, to:

for each existing node P with value N:
    for each new N+1 valued node Q you need to connect to P: //this loops N+1 times
        find the set of vacant spots that are minimally distant from P //by Manhattan distance
        place Q in any of these vacant spots

(Inna procedura z nierozróżnialnym wyjściem jest w porządku.)

Przykład wzrostu dla A ₄ :

A0 is always the same:

0

For A1 I happen to put the 1 to the right of the 0 (it has to go on one of the 4 open sides):

01

For A2 I happen to put the two 2's above and to the right of the 1:

 2
012


For A3 I find that one of the six 3's I must place cannot be directly next to a 2, so I put in one of the next closest places:

 3
323
0123
  33 <-- this 3 is distance two away from its 2

The process continues in A4. Note that I'm iterating over each 3 and placing four 4's next to it or as close as possible, then moving to the next 3 (the order of 3's does not matter):

 444
443444
4323444
4012344
 44334
  4444
   44

Always keep in mind that nodes cannot be "shared".

Program

Program, który piszesz, musi przyjmować liczbę od 0 do 8 (włącznie) i generować prawidłowy wykres ameoba, używając opisanego powyżej wzorca wzrostu indukcyjnego.

To, co dzieje się po 8, nie ma znaczenia.

(A ₈ zawiera 46234 węzły, które go popychają. Wszystko poza A ₈ byłoby za daleko. Podziękowania dla Martina Büttnera za zauważenie tego.)

Dane wejściowe powinny pochodzić ze stdin lub wiersza poleceń, a dane wyjściowe powinny przejść do stdout lub pliku.

Przykłady (wzięte bezpośrednio z góry)

Input: 0
Output:

0

Input: 1
Output:

01

Input: 2
Output:

 2
012

Input: 3
Output:

 3
323
0123
  33

Input: 4
Output:

 444
443444
4323444
4012344
 44334
  4444
   44

* Ten typ wykresów może już mieć nazwę. Przyznaję, że właśnie je wymyśliłem. ;)

Mathematica, 353 288 285 275 bajtów

n=Input[];f@_=" ";g={z={0,0}};i=f@z=0;For[r=Range,i++<n,g=Reap[(j=i;o={};For[d=0,j>0,o=Rest@o,If[o=={},o=Join@@({e={#,d-#},-e,e={d-#,-#},-e}&/@r@++d)];If[f[c=#&@@o+#]==" ",f@c=i;Sow@c;--j]])&/@g][[2,1]]];Riffle[(x=#;ToString@f@{x,#}&/@m~r~M)&/@r[m=Min@{g,0},M=Max@g],"
"]<>""

Nie golfowany:

n = Input[];
f@_ = " ";
g = {z = {0, 0}};
i = f@z = 0;
For[r = Range, i++ < n,
  g = Reap[(
        j = i;
        o = {}; 
        For[d = 0, j > 0, o = Rest@o,
         If[o == {}, 

          o = Join @@ ({e = {#, d - #}, -e, e = {d - #, -#}, -e} & /@  
              r@++d)
          ];  
         If[f[c = # & @@ o + #] == " ",
          f@c = i;
          Sow@c;
          --j 
          ]   
         ]   
        ) & /@ g
     ][[2, 1]] 
  ];  
Riffle[(
     x = #;
     ToString@f@{x, #} & /@ m~r~M
     ) & /@ r[m = Min@{g, 0}, 
    M = Max@g
    ], "
  "] <> ""

Oto przykładowy wynik dla n = 5:

      5
     5555     
    555555    
   5555555    
  555555555   
 55555555555  
5555554445555 
5555544444555 
 5555443305555
 55554432144555
 55555443234555
  5555544344555
   555554445555
    5555555555
      5555555 
       55555  
       55     

Wejście 8zajmuje około 4,5 minuty.

Aby szybko rozbić mój algorytm:

Używam dwóch tabel przeglądowych fi g. Pierwszy to tylko rzadka mapa zawierająca niepuste komórki. Ta ostatnia jest listą zawierającą wszystkie pary współrzędnych dla każdej wartości komórki (myślę, że nawet nie muszę tutaj śledzić starych). Iteruję przez współrzędne, gaby rozszerzyć każdą komórkę od ostatniej iteracji. Aby to zrobić, iteruję po odległościach Manhattanu, tworząc wszystkie możliwe wektory dla każdej odległości i sprawdzając, czy wynikowa komórka jest nadal pusta (w którym to przypadku ją wypełniam). Powtarzaj aż do utworzenia wystarczającej liczby nowych komórek.

Kiedy skończę, znajduję współrzędną minimalną i maksymalną gi tworzę odpowiednią siatkę, która jest wypełniana przez wyszukiwanie komórek f. Reszta to po prostu łączenie wszystkiego w jeden ciąg znaków z podziałem linii.

C - 309 305 301 275 bajtów

Meh, za długo ... gdyby tylko ktoś mógł wpisać #Dlub coś zamiast #define, wtedy C byłby naprawdę świetny. Oczywiście -Dflagi kompilatora są możliwe, ale wydaje mi się, że to oszustwo, aby mieć znaki inne niż te w pliku źródłowym.

Instrukcje biegowe:

Bądź ostrożny! Pierwszy klawisz, który naciśniesz po uruchomieniu programu, stanowi wejście. Po wprowadzeniu znaku innego niż „0” do „8”, kto wie, co się stanie.

#define F(D,O)x=*r+O d;for(c=d;h*c--;x+=D)!g[x]?g[*w++=x]=l,--h:5;
L=400;g[1<<18];n;s;*r;*w;*m;h;l;d;x;main(c){n=getch()-32;r=w=g+L*L;for(l=g[*w++=80200]=16;l++<n;)for(m=w;r<m;r++)for(d=1,h=l-16;h;d++){F(L+1,-)F(L-1,-L*)F(-L+1,L*)F(~L,)}for(n=L*L;--n;)putch(n%L?g[n]+32:10);}

Wersja bez golfa (ale już myśli o przyszłości golfa):

void exit(int);

#define L 400

#define FIND(D, X0)   x = *pread X0 d; \
                for(c = d; c--; x+=D) { \
                    if(x%L == 0 || x%L == L-1 || x/L == 0 || x/L == L-1) \
                        exit(5); \
                    if(!g[x]) { \
                        g[*pwrite++ = x] = '0' + l; \
                        if(!--children) \
                            goto pnext; \
                    } \
                }

main()
{
    int n = getch() - '0';
    //char g[3] = {};
    char g[L*L] = {};
    int plist[46324];

    int *pwrite = plist, *pread = plist;
    *pwrite++ = L/2*L + L/2;
    g[*plist] = '0';
    int factorial = 1;
    int l,  c, parents, children, d, x;
    for(l = 1; l <= n; l++) {
        for(parents = factorial; parents--; pread++) {
            children = l;
            for(d = 1; ; d++) {
                FIND(L + 1, - )
                FIND(L - 1, -L* )
                FIND(-L + 1, +L* )
                FIND(-L - 1, + )
            }
            pnext:;
        }
        factorial *= l;
    }
    int i;
    for(i = L*L; i--; )
        putch(i%L ? (g[i] ? g[i] : ' ') : '\n');
}

Edycja: Zdałem sobie sprawę, że ponieważ przeniosłem deklaracje poza main (), tablic nie można już przypisywać do stosu, więc mogę swobodnie korzystać z pamięci w rozrzutny sposób, bez ryzyka przepełnienia.

Rubin - 296

g=[s=' ']*d=10**6
$*[g[50500]=0].to_i.times{|c|d.times{|x|g[x]==c&&(r=1;a=c;(4.times{|v|r.times{|w|g[q=x+r*(1e3*(v-1-v/2)+v%2-v/2)+w*(1e3*~0**(v/2)+~0**v)]==s&&a>~0?(g[q]=c+1;a-=1):0}};r+=1)while~0<a)}}
g=g.join.scan(/.{1000}/)
g.map{|s|s[/\d/]&&(puts s[g.map{|s|s[/\A */].size}.min..-1].rstrip)}

Nieco golfa.

g=[s=' ']*d=10**6 # Initialize a big 1d array as a 2d grid
$*[g[50500]=0].to_i.times{|c| # For n times
    d.times{|x| # For each index in the grid
        g[x]==c&&( # If the element at x is equal to the current growth stage, c
            r=1;   # Initial manhattan radius = 1
            a=c;   # a is number of times the ameoba must replicate
            (4.times{|v| # For each of the 4 sides of the manhattan diamond
                r.times{|w| # For each node in each side
                    # Spawn the 'c+1' ameoba's from the c ameobas... 
                    # The messy formula gives the index of the space in the grid to try spawning
                    g[q=x+r*(1e3*(v-1-v/2)+v%2-v/2)+w*(1e3*~0**(v/2)+~0**v)]==s&&a>~0?(g[q]=c+1;a-=1):0 
                }
            };
            r+=1 # Increase the raidus of the manhattan diamond by one
            ) while~0<a # while not enough ameoba's have been spawned
        )
    }
}
g=g.join.scan(/.{1000}/) # Join the 1d array into a huge string and slice it into rows
# Strip away the empty spaces all around the graph and print it
g.map{|s|s[/\d/]&&(puts s[g.map{|s|s[/\A */].size}.min..-1].rstrip)} 

APL (Dyalog) (121)

{0::0⋄V←,⍳⍴Z←' '⍴⍨2/M←⌈4×.5*⍨3÷⍨+/!⍳⍵⋄Z[G;G←⌈M÷2]←'0'⋄Z⊣{⍵∘{⍵∘{+((⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺])⌷Z)←⍕⍵}¨⍺/⍺}¨V/⍨,Z=⍕⍵-1}¨⍳⍵}⎕

Charakterystyka wydajności: to O (n!). W moim systemie do n = 5 jest natychmiastowe; n = 6 zajmuje sekundę, n = 7 zajmuje minutę, a n = 8 zajmuje godzinę.

Wersja bez golfa

Test:

      {0::0⋄V←,⍳⍴Z←' '⍴⍨2/M←⌈4×.5*⍨3÷⍨+/!⍳⍵⋄Z[G;G←⌈M÷2]←'0'⋄Z⊣{⍵∘{⍵∘{+((⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺])⌷Z)←⍕⍵}¨⍺/⍺}¨V/⍨,Z=⍕⍵-1}¨⍳⍵}⎕
⎕:
      5





           5555             
          555555            
         55555555           
        5555445555          
       555544445555         
      55554433445555        
     5555444323445555       
    5555544321455555        
     555554430455555        
     555555444555555        
       555555555555         
        5555555555          
         55555555           
          55555             
           555              

Wyjaśnienie:

• {... }⎕: przeczytaj wiersz z klawiatury, oceń go i przekaż wynik funkcji.
• 0::0: jeśli inny kod zgłosi błąd, zwróć pojedynczy 0. Wynika to z faktu, że matematyka kończy się niepowodzeniem podczas próby obliczenia rozmiaru wykresu z 0 węzłami, co zdarza się, gdy dane wyjściowe powinny być 0. (Poprzednia wersja miała ⍵=0:0(jeśli dane wejściowe są 0zwracane, w 0przeciwnym razie wykonaj wykres), ale 0::0(po prostu spróbuj i zwróć, 0jeśli się nie powiedzie) jest krótsza.)
• M←⌈4×.5*⍨3÷⍨+/!⍳⍵: zakładając, że wyjście jest grubym okręgiem (działa), zsumuj silnię od 1do ⍵(= obszar wyjścia), podziel przez 3 (wystarczająco blisko do pi), weź pierwiastek kwadratowy (dając promień wyjścia), pomnóż przez 4, i weź sufit. Daje to podwójną średnicę koła, więc wyjście pasuje do wolnego miejsca. Przechowuj to w M.
• V←,⍳⍴Z←' '⍴⍨2/M: utwórz macierz M-M-M spacji i zapisz ją Z. To zatrzyma wynik. Przechowuj listę współrzędnych wszystkich elementów w V.
• Z[G;G←⌈M÷2]←'0': ustaw środkowy element Zna 0.
• Z⊢{... }¨⍳⍵: powrót Zpo zastosowaniu następującej funkcji do liczb 1do ⍵:
  • ⍵∘{... }V/,Z=⍕⍵-1: dla każdego elementu Zo wartości poprzedniego węzła:
    • ⍵∘{... }⍺/⍺: dla bieżącego węzła, N razy,
      • ⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺]: uzyskaj wolną przestrzeń najbliżej bieżącego węzła,
      • (... ⌷Z)←⍕⍵: i ustaw tę przestrzeń Zna wartość bieżącego węzła.