Creciente Manhattan Ameobas

11

Un *** ameoba graph **** es un tipo de árbol cuyos nodos tienen valores de 0 a algún número entero no negativo N, y cualquier nodo particular con valor x <N se conecta a x + 1 nodos distintos con valores x + 1)

Gráfico de Ameoba para N = 3: (Denotado A 3 )

ameoba 3

Tenga en cuenta que los 2 no pueden compartir ninguno de los 3; exactamente tres 3 deben "pertenecer" a cada 2.

Desafío

Su tarea es "hacer crecer" inductivamente estos gráficos de ameoba en una cuadrícula bidimensional minimizando con avidez la distancia de Manhattan entre nodos:

  • Caso base: Un 0 es simplemente el gráfico 0.
  • Paso inductivo: se genera un N + 1 colocando iterativamente los nuevos nodos valorados N + 1 lo más cerca posible de los nodos de los valores N en la estructura A N existente. (Solo puede estar lo más cerca posible ya que los lugares más cercanos pueden estar llenos).

Para el paso inductivo, el procedimiento general que debe seguir es:

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

(Un procedimiento diferente con salida indistinguible está bien).

Ejemplo de crecimiento para 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".

Programa

El programa que escriba debe incluir un número del 0 al 8 (inclusive) y generar un gráfico de ameoba válido, utilizando el patrón de crecimiento inductivo explicado anteriormente.

Lo que sucede más allá de 8 no importa.

(A 8 contiene 46234 nodos que lo están empujando. Cualquier cosa más allá de A 8 estaría demasiado lejos. Gracias a Martin Büttner por notar esto).

La entrada debe provenir de stdin o la línea de comando y la salida debe ir a stdout o un archivo.

Ejemplos (tomados directamente de arriba)

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

* Es posible que este tipo de gráficos ya tenga un nombre. Admito que acabo de inventarlos. ;)

code-golf graph-theory
fuente
A la luz de la tasa de crecimiento factorial, ¿podría cambiarse la pregunta de detenerse en A35 a detenerse en un archivo de 1 Megabyte, o algo similar? A10 es la primera ameba con más de un millón de personajes.
isaacg
@ MartinBüttner He establecido el límite 8, que es de alrededor de 50k nodos. Todavía mucho, pero con suerte manejable.

Respuestas:

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

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

Aquí hay un ejemplo de salida para n = 5:

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

La entrada 8toma aproximadamente 4.5 minutos.

Para un desglose rápido de mi algoritmo:

Estoy usando dos tablas de búsqueda, fy g. El primero es solo un mapa disperso que contiene las celdas no vacías. La última es una lista que contiene todos los pares de coordenadas para cada valor de celda (creo que ni siquiera necesito hacer un seguimiento de los antiguos aquí). Estoy iterando a través de las coordenadas gpara extender cada celda desde la última iteración. Para hacer eso, itero sobre las distancias de Manhattan, creando todos los vectores posibles para cada distancia, y verificando si la celda resultante todavía está vacía (en cuyo caso la lleno). Repita hasta que se hayan creado suficientes celdas nuevas.

Cuando termino, encuentro la coordenada mínima y máxima gy creo una cuadrícula apropiada, que se completa al buscar las celdas f. El resto es solo unir todo en una sola cadena con saltos de línea.

Martin Ender
fuente
5

C - 309305301 275 bytes

Meh, demasiado tiempo ... si solo uno pudiera escribir #Do algo así #define, entonces C sería realmente genial. Por supuesto, -Dlos indicadores del compilador son posibles, pero eso me parece una trampa, tener caracteres distintos a los del archivo fuente.

Instrucciones de funcionamiento:

¡Ten cuidado! La primera tecla que presione después de que comience el programa constituye la entrada. En una entrada de personaje que no sea '0' a '8', quién sabe qué cosas indefinidas sucederán.

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

Versión sin golf (pero ya pensando en el futuro 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');
}

Editar: me di cuenta de que desde que moví las declaraciones fuera de main (), las matrices ya no se pueden asignar en la pila, por lo que tengo la libertad de usar la memoria de manera desproporcionada sin riesgo de desbordamiento.

Feersum
fuente
2

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

Ligeramente no golfista. 

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

Características de rendimiento: es O (n!). En mi sistema, hasta n = 5 es instantáneo; n = 6 toma un segundo, n = 7 toma un minuto yn = 8 toma una hora.

Versión sin golf

Prueba:

      {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

Explicación:

  • {... }⎕: lee una línea desde el teclado, la evalúa y pasa el resultado a la función.
  • 0::0: si el otro código genera un error, devuelve uno solo 0. Esto se debe a que las matemáticas fallan al intentar calcular el tamaño de un gráfico con 0 nodos, que es el caso cuando la salida debería ser 0. (La versión anterior tenía ⍵=0:0, (si la entrada es 0devuelta, de lo 0contrario, haga el gráfico), pero 0::0(solo inténtelo y devuelva 0si falla) es más corto).
  • M←⌈4×.5*⍨3÷⍨+/!⍳⍵: suponiendo que la salida es un círculo aproximado (esto funciona), sume los factoriales de 1a ⍵(= área de salida), divida por 3 (lo suficientemente cerca de pi), tome la raíz cuadrada (dando el radio de salida), multiplique por 4, y tomar el techo Esto da el doble del diámetro del círculo, por lo que la salida se ajusta con espacio de sobra. Almacene esto en M.
  • V←,⍳⍴Z←' '⍴⍨2/M: crea una matriz de espacios M-por-M y guárdala Z. Esto mantendrá la salida. Almacene una lista de las coordenadas de todos los elementos en V.
  • Z[G;G←⌈M÷2]←'0': establece el elemento medio de Zto 0.
  • Z⊢{... }¨⍳⍵: volver Z, después de aplicar la siguiente función a los números 1para ⍵:
    • ⍵∘{... }V/,Z=⍕⍵-1: para cada elemento Zcon el valor del nodo anterior:
      • ⍵∘{... }⍺/⍺: para el nodo actual, N veces,
        • ⊃F[⍋+/¨|(F←V/⍨,Z=' ')-⊂⍺]: obtener el espacio libre más cercano al nodo actual,
        • (... ⌷Z)←⍕⍵: y establece ese espacio en Zel valor del nodo actual.
marinus
fuente