Wachsende Manhattan Ameobas

11

*** Ein Ameoba Graph **** eine Art ist Baum , dessen Knoten alle Werte von 0 bis einigen nicht-negative ganze Zahl N, und jeder bestimmten Knoten mit dem Wert x <N verbindet sich mit x + 1 unterschiedliche Knoten mit Werten x + 1.

Ameoba-Graph für N = 3: (mit A 3 bezeichnet )

Ameoba 3

Beachten Sie, dass die 2er keine der 3er teilen dürfen. genau drei 3er müssen zu jeder 2 "gehören".

Herausforderung

Ihre Aufgabe ist es, diese Ameoba-Graphen in einem zweidimensionalen Raster induktiv zu "wachsen", indem Sie den Abstand zwischen den Knoten in Manhattan gierig minimieren :

  • Basisfall: Eine 0 ist einfach der Graph 0.
  • Induktiver Schritt: Ein N + 1 wird erzeugt, indem die neuen N + 1-Wertknoten iterativ so nahe wie möglich an den N-Wertknoten in der vorhandenen A N -Struktur platziert werden. (Es kann nur so nah wie möglich sein, da die nächstgelegenen Stellen möglicherweise bereits besetzt sind.)

Für den induktiven Schritt müssen Sie im Allgemeinen folgende Schritte ausführen:

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

(Ein anderes Verfahren mit nicht unterscheidbarer Ausgabe ist in Ordnung.)

Wachstumsbeispiel für A 4 :

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".

Programm

Das Programm, das Sie schreiben, muss eine Zahl von 0 bis einschließlich 8 aufnehmen und ein gültiges Ameoba-Diagramm davon unter Verwendung des oben erläuterten induktiven Wachstumsmusters ausgeben.

Was nach 8 passiert, spielt keine Rolle.

(Eine 8 enthält 46234 Knoten, die sie drücken. Alles, was über A 8 hinausgeht, wäre zu weit. Vielen Dank an Martin Büttner, der dies bemerkt hat.)

Die Eingabe sollte von stdin oder der Befehlszeile kommen und die Ausgabe sollte an stdout oder eine Datei gehen.

Beispiele (direkt von oben genommen)

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

* Diese Art von Grafiken hat möglicherweise bereits einen Namen. Ich gebe zu, ich habe sie gerade erfunden. ;)

code-golf graph-theory
quelle
Könnte angesichts der faktoriellen Wachstumsrate die Frage von einem Stopp bei A35 zu einem Stopp bei einer 1-Megabyte-Datei oder ähnlichem geändert werden? A10 ist die erste Amöbe mit über einer Million Zeichen.
isaacg
@ MartinBüttner Ich habe das Limit 8 erreicht, das bei 50.000 Knoten liegt. Immer noch viel, aber hoffentlich überschaubar.

Antworten:

6

Mathematica, 353 288 285 275 Bytes

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

Ungolfed:

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

Hier ist eine Beispielausgabe für n = 5:

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

Die Eingabe 8dauert ca. 4,5 Minuten.

Für eine schnelle Aufschlüsselung meines Algorithmus:

Ich verwende zwei Nachschlagetabellen fund g. Die erste ist nur eine spärliche Karte, die die nicht leeren Zellen enthält. Letzteres ist eine Liste, die alle Koordinatenpaare für jeden Zellenwert enthält (ich glaube, ich muss hier nicht einmal die alten verfolgen). Ich iteriere durch die Koordinaten g, um jede Zelle von der letzten Iteration zu erweitern. Dazu iteriere ich über Manhattan-Entfernungen, erstelle alle möglichen Vektoren für jede Entfernung und überprüfe, ob die resultierende Zelle noch leer ist (in diesem Fall fülle ich sie aus). Wiederholen, bis genügend neue Zellen erstellt wurden.

Wenn ich fertig bin, finde ich die minimale und maximale Koordinate in gund erstelle ein geeignetes Gitter, das durch Nachschlagen der Zellen gefüllt wird f. Der Rest fügt einfach alles zu einer einzigen Zeichenfolge mit Zeilenumbrüchen zusammen.

Martin Ender
quelle
5

C - 309 305 301 275 Bytes

Meh, zu lange ... wenn nur einer tippen könnte #Doder so #define, dann wäre C wirklich großartig. Natürlich sind -DCompiler-Flags möglich, aber das scheint mir ein Betrug zu sein, andere Zeichen als die in der Quelldatei zu haben.

Laufanleitung:

Achtung! Die erste Taste, die Sie nach dem Start des Programms drücken, bildet die Eingabe. Bei einer anderen Zeicheneingabe als '0' bis '8' weiß wer, welche undefinierten Dinge passieren werden.

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

Ungolfed (denkt aber schon an zukünftiges Golfen) Version:

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

Bearbeiten: Ich habe festgestellt, dass die Arrays nicht mehr auf dem Stapel zugeordnet werden können, da ich die Deklarationen außerhalb von main () verschoben habe. Daher kann ich den Speicher ohne Risiko eines Überlaufs auf verschwenderische Weise verwenden.

Feersum
quelle
2

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

Leicht ungolfed. 

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)}
Vektorisiert
quelle
2

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

Leistungsmerkmale: Es ist O (n!). Auf meinem System ist es bis zu n = 5 augenblicklich; n = 6 dauert eine Sekunde, n = 7 dauert eine Minute und n = 8 dauert eine Stunde.

Version ohne Golf

Prüfung:

      {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

Erläuterung:

  • {... }⎕: Lesen Sie eine Zeile von der Tastatur, werten Sie sie aus und übergeben Sie das Ergebnis an die Funktion.
  • 0::0: Wenn der andere Code einen Fehler auslöst, geben Sie einen einzelnen zurück 0. Dies liegt daran, dass die Mathematik fehlschlägt, wenn versucht wird, die Größe für ein Diagramm mit 0 Knoten zu berechnen. Dies ist zufällig der Fall, wenn die Ausgabe erfolgen soll 0. (Die vorherige Version hatte ⍵=0:0, (wenn die Eingabe zurückgegeben wird 0, 0sonst machen Sie das Diagramm), aber 0::0(versuchen Sie 0es einfach und geben Sie zurück, wenn es fehlschlägt) ist kürzer.)
  • M←⌈4×.5*⍨3÷⍨+/!⍳⍵: Angenommen, die Ausgabe ist ein grober Kreis (dies funktioniert), summieren Sie die Fakultäten von 1bis ⍵(= Fläche der Ausgabe), dividieren Sie durch 3 (nahe genug an pi), ziehen Sie die Quadratwurzel (geben Sie den Radius der Ausgabe an), multiplizieren Sie mit 4, und nimm die Decke. Dies ergibt den doppelten Durchmesser des Kreises, sodass die Ausgabe Platz bietet. Speichern Sie diese in M.
  • V←,⍳⍴Z←' '⍴⍨2/M: Erstellen Sie eine M-für-M-Matrix aus Leerzeichen und speichern Sie sie in Z. Dies hält die Ausgabe. Speichern Sie eine Liste der Koordinaten aller Elemente in V.
  • Z[G;G←⌈M÷2]←'0': setze das mittlere Element von Zauf 0.
  • Z⊢{... }¨⍳⍵: kehren Sie zurück Z, nachdem Sie die folgende Funktion auf die Zahlen 1angewendet haben ⍵:
    • ⍵∘{... }V/,Z=⍕⍵-1: für jedes Element Zmit dem Wert des vorherigen Knotens:
      • ⍵∘{... }⍺/⍺: für den aktuellen Knoten N-mal,
        • ⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺]: Holen Sie sich den freien Speicherplatz, der dem aktuellen Knoten am nächsten liegt.
        • (... ⌷Z)←⍕⍵: und setzen Sie diesen Platz Zauf den Wert des aktuellen Knotens.
Marinus
quelle