Growing Manhattan Ameobas

Question

An ***ameoba graph**** is a type of tree whose nodes all have values from 0 to some non-negative integer N, and any particular node with value x < N connects to x+1 distinct nodes with values x+1.

Ameoba graph for N = 3: (Denoted A₃)

Note that the 2's are not allowed to share any of the 3's; exactly three 3's must "belong" to each 2.

Challenge

Your task is to inductively "grow" these ameoba graphs in a 2-dimensional grid by greedily minimizing the Manhattan distance between nodes:

• Base case: A₀ is simply the graph 0.
• Inductive step: A_N+1 is generated by iteratively placing the new N+1 valued nodes as close as possible to the N values nodes in the existing A_N structure. (It can only be as close as possible since the closest spots may already be filled.)

For the inductive step the general procedure you must follow is:

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

(A different procedure with indistinguishable output is fine.)

Growth example for 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

The program you write must take in a number from 0 to 8 (inclusive) and output a valid ameoba graph of it, using the inductive growth pattern explained above.

What happens beyond 8 does not matter.

(A₈ contains 46234 nodes which is pushing it. Anything beyond A₈ would be too far. Thanks to Martin Büttner for noticing this.)

The input should come from stdin or the command line and output should go to stdout or a file.

Examples (taken directly from above)

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

* These type of graphs might already have a name. I admit I just made them up. ;)

Answer 1

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

Here is an example output for n = 5:

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

Input 8 takes about 4.5 minutes.

For a quick breakdown of my algorithm:

I'm using two look-up tables, f and g. The first one is just a sparse map containing the non-empty cells. The latter is a list containing all coordinate pairs for each cell-value (I think I don't even need to keep track of old ones here). I'm iterating through the coordinates in g to extend every cell from the last iteration. To do that I iterate over Manhattan distances, creating all possible vectors for each distance, and checking if the resulting cell is still empty (in which case I fill it). Repeat until enough new cells have been created.

When I'm done, I find the minimum and maximum coordinate in g and I create an appropriate grid, which is filled by looking up the cells in f. The rest is just joining everything into a single string with line breaks.

Answer 2

C - 309 305 301 275 bytes

Meh, too long...if only one could type #D or something instead of #define, then C would be really great. Of course -D compiler flags are possible but that seems like cheating to me, to have characters other than the ones in the source file.

Running instructions:

Be careful! The first key you press after the program starts constitutes the input. Upon a character entry other than '0' through '8', who knows what undefined things will happen.

#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 (but already thinking about future golfing) 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');
}

Edit: I realized that since I moved the declarations outside of main(), the arrays can no longer be allocated on the stack, so I am free to use memory in a profligate manner without risk of overflow.

Answer 3

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

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

Answer 4

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

Performance characteristics: it's O(n!). On my system, up to n=5 it's instantaneous; n=6 takes a second, n=7 takes a minute and n=8 takes an hour.

Non-golfed version

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              

Explanation:

• {...}⎕: read a line from the keyboard, evaluate it, and pass the result to the function.
• 0::0: if the other code raises an error, return a single 0. This is because the math fails when trying to calculate the size for a graph with 0 nodes, which happens to be the case when the output should be 0. (The previous version had ⍵=0:0, (if the input is 0 return 0 otherwise make the graph), but 0::0 (just try it and return 0 if it fails) is shorter.)
• M←⌈4×.5*⍨3÷⍨+/!⍳⍵: assuming the output is a rough circle (this works), sum the factorials from 1 to ⍵ (= area of output), divide by 3 (close enough to pi), take the square root (giving radius of output), multiply by 4, and take the ceiling. This gives twice the diameter of the circle, so the output fits with room to spare. Store this in M.
• V←,⍳⍴Z←' '⍴⍨2/M: make an M-by-M matrix of spaces and store it in Z. This will hold the output. Store a list of the coordinates of all elements in V.
• Z[G;G←⌈M÷2]←'0': set the middle element of Z to 0.
• Z⊢{...}¨⍳⍵: return Z, after applying the following function to the numbers 1 to ⍵:
  • ⍵∘{...}V/,Z=⍕⍵-1: for each element in Z with the value of the previous node:
    • ⍵∘{...}⍺/⍺: for the current node, N times,
      • ⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺]: get the free space closest to the current node,
      • (...⌷Z)←⍕⍵: and set that space in Z to the value of the current node.