Un graphe *** ameoba **** est un type d' arbre dont les nœuds ont tous des valeurs de 0 à un entier non négatif N, et tout nœud particulier avec la valeur x <N se connecte à x + 1 nœuds distincts avec les valeurs x + 1.

Graphique Ameoba pour N = 3: (noté A ₃ )

Notez que les 2 ne sont autorisés à partager aucun des 3; exactement trois 3 doivent "appartenir" à chacun des 2.

Défi

Votre tâche est de "développer" par induction ces graphiques ameoba dans une grille à 2 dimensions en minimisant goulûment la distance de Manhattan entre les nœuds:

• Cas de base: Un ₀ est simplement le graphique 0.
• Étape inductive: un _{N + 1} est généré en plaçant de manière itérative les nouveaux nœuds à valeur N + 1 aussi près que possible des nœuds à valeurs N dans la structure A _N existante . (Il ne peut être aussi proche que possible car les emplacements les plus proches peuvent déjà être remplis.)

Pour l'étape inductive, la procédure générale que vous devez suivre est la suivante:

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

(Une procédure différente avec une sortie impossible à distinguer est très bien.)

Exemple de croissance pour 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".

Programme

Le programme que vous écrivez doit prendre un nombre compris entre 0 et 8 (inclus) et en produire un graphique ameoba valide, en utilisant le schéma de croissance inductif expliqué ci-dessus.

Ce qui se passe au-delà de 8 n'a pas d'importance.

(A ₈ contient 46234 nœuds qui le poussent. Tout ce qui dépasse A ₈ serait trop loin. Merci à Martin Büttner de l'avoir remarqué.)

L'entrée doit provenir de stdin ou de la ligne de commande et la sortie doit aller vers stdout ou un fichier.

Exemples (pris directement d'en haut)

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

* Ces types de graphiques peuvent déjà avoir un nom. J'avoue que je viens de les inventer. ;)

Mathematica, 353 288 285 275 octets

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],"
"]<>""

Non golfé:

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
    ], "
  "] <> ""

Voici un exemple de sortie pour n = 5:

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

L'entrée 8prend environ 4,5 minutes.

Pour une ventilation rapide de mon algorithme:

J'utilise deux tables de recherche, fet g. La première est juste une carte clairsemée contenant les cellules non vides. Ce dernier est une liste contenant toutes les paires de coordonnées pour chaque valeur de cellule (je pense que je n'ai même pas besoin de garder une trace des anciennes ici). J'itère à travers les coordonnées gpour étendre chaque cellule de la dernière itération. Pour ce faire, j'itère sur les distances de Manhattan, créant tous les vecteurs possibles pour chaque distance et vérifiant si la cellule résultante est toujours vide (auquel cas je la remplis). Répétez jusqu'à ce que suffisamment de nouvelles cellules aient été créées.

Lorsque j'ai terminé, je trouve les coordonnées minimale et maximale dans get je crée une grille appropriée, qui est remplie en recherchant les cellules f. Le reste consiste simplement à tout joindre en une seule chaîne avec des sauts de ligne.

C - 309 305 301 275 octets

Meh, trop longtemps ... si un seul pouvait taper #Dou quelque chose à la place #define, alors C serait vraiment super. Bien sûr, -Dles drapeaux du compilateur sont possibles, mais cela me semble tricher, d'avoir des caractères autres que ceux du fichier source.

Instructions de course:

Faites attention! La première touche sur laquelle vous appuyez après le démarrage du programme constitue l'entrée. Lors d'une entrée de caractère autre que «0» à «8», qui sait quelles choses non définies se produiront.

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

Version non golfée (mais qui pense déjà au futur golf):

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

Edit: J'ai réalisé que depuis que j'ai déplacé les déclarations en dehors de main (), les tableaux ne peuvent plus être alloués sur la pile, donc je suis libre d'utiliser la mémoire de manière profligée sans risque de débordement.

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

Légèrement non golfé.

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}¨⍳⍵}⎕

Caractéristiques de performance: c'est O (n!). Sur mon système, jusqu'à n = 5, c'est instantané; n = 6 prend une seconde, n = 7 prend une minute et n = 8 prend une heure.

Version non golfée

Tester:

      {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              

Explication:

• {... }⎕: lire une ligne du clavier, l'évaluer et transmettre le résultat à la fonction.
• 0::0: si l'autre code génère une erreur, renvoyez-en un simple 0. Cela est dû au fait que les calculs échouent lors de la tentative de calcul de la taille d'un graphique à 0 nœuds, ce qui se produit lorsque la sortie doit l'être 0. (La version précédente avait ⍵=0:0, (si l'entrée est 0retournée, 0sinon, faites le graphique), mais 0::0(essayez-la et retournez-la 0si elle échoue) est plus courte.)
• M←⌈4×.5*⍨3÷⍨+/!⍳⍵: en supposant que la sortie est un cercle approximatif (cela fonctionne), additionnez les factorielles de 1à ⍵(= zone de sortie), divisez par 3 (assez proche de pi), prenez la racine carrée (donnant le rayon de sortie), multipliez par 4, et prenez le plafond. Cela donne deux fois le diamètre du cercle, de sorte que la sortie s'adapte à l'espace disponible. Conservez-le dans M.
• V←,⍳⍴Z←' '⍴⍨2/M: créer une matrice d'espaces M-par-M et la stocker Z. Cela conservera la sortie. Stockez une liste des coordonnées de tous les éléments dans V.
• Z[G;G←⌈M÷2]←'0': définir l'élément central de Zà 0.
• Z⊢{... }¨⍳⍵: retour Z, après avoir appliqué la fonction suivante aux nombres 1à ⍵:
  • ⍵∘{... }V/,Z=⍕⍵-1: pour chaque élément Zavec la valeur du nœud précédent:
    • ⍵∘{... }⍺/⍺: pour le nœud courant, N fois,
      • ⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺]: obtenir l'espace libre le plus proche du nœud actuel,
      • (... ⌷Z)←⍕⍵: et définissez cet espace Zsur la valeur du nœud actuel.