Es bien sabido que una persona en una grilla bajo la influencia del alcohol tiene las mismas posibilidades de ir en cualquier dirección disponible. Sin embargo, esta declaración de sentido común no se aplica en el ámbito de los borrachos muy pequeños , cuyo comportamiento es muy similar al de tomar todos los caminos disponibles a la vez, y los posibles caminos que toman pueden interferir entre sí. Su tarea es mostrar las posibles posiciones de un borracho cuántico después de los npasos.

Especificación

El borracho en cuestión ocupa una cuadrícula cuadrada y puede considerarse como un autómata celular de 3 estados que utiliza un vecindario Von Neumann (en forma de más) que sigue estas simples reglas:

• Emptyva a Awakesi es adyacente a exactamente uno Awake, y de lo contrario va aEmpty
• Awake va a Sleeping
• Sleeping va a Sleeping

El estado inicial del tablero es un único Awakerodeado por un campo infinito de Emptys.

Desafío

Dado un número entero no negativo n, cree una representación ASCII del borracho después de los npasos. Cada estado debe estar representado por un carácter diferente, y las soluciones deben indicar qué carácter significa qué estado. Si usa espacios para Empty, no necesita incluir una serie de ellos al final de una línea.

Este es el código de golf , por lo que gana la respuesta más corta. Se aplican las lagunas estándar , se permiten espacios en blanco iniciales y finales, se permite la salida de matriz de cadenas / matriz de caracteres 2D, etc.

Ejemplos

Estos ejemplos usan for Empty, @for Awakey #for Sleeping.

n=0
@

n = 1
 @
@#@
 @

n = 2
  @
  #
@###@
  #
  @

n = 3
   @
  @#@
 @ # @
@#####@
 @ # @
  @#@
   @

n=6

      @
      # 
    @###@
     @#@  
  @  ###  @
  #@# # #@#
@###########@
  #@# # #@#
  @  ###  @
     @#@
    @###@
      #
      @

n=10
          @
          #
        @###@
         @#@
         ###
        # # #
       #######
      #  ###  #
  @  ##  ###  ##  @
  #@# ### # ### #@#
@###################@
  #@# ### # ### #@#
  @  ##  ###  ##  @
      #  ###  #
       #######
        # # #
         ###
         @#@
        @###@
          #
          @

Nota interesante

Al buscar la secuencia del número de células ocupadas en el OEIS, descubrí que el borracho cuántico es isomorfo a la secuencia de palillos de dientes mucho mejor estudiada . Si puede incorporar ese conocimiento en un mejor golf, quedaré adecuadamente impresionado.

Wolfram Language (Mathematica) , 92 91 bytes

Print@@@CellularAutomaton[{7049487784884,{3,{a={0,3,0},3-2a/3,a}},{1,1}},{j={{1}},0},{j#}]&

¡Un desafío perfecto para usar el generador incorporado de Mathematica CellularAutomaton!

Pruébalo en línea!

Vacío = 0, Despierto = 1, Durmiendo = 2

Animación de las primeras 256 iteraciones (blanco = vacío, gris = despierto, negro = dormido):

Explicación

CellularAutomaton[ ... ]

Ejecutar CellularAutomatoncon especificaciones ...

{7049487784884,{3,{a={0,3,0},3-2a/3,a}},{1,1}}

Aplique la regla totalista de 3 colores 7049487784884, con el vecindario de Von Neumann ...

{j={{1}},0}

En un tablero con un solo 1 en el medio, con un fondo de 0s ...

{j#}

Repetir <input>veces (se {j#}evalúa como {{{#}}}). La matriz se expande automáticamente si una celda fuera del borde no es lo mismo que el fondo

7049487784884

Esta regla proviene del número base-3 220221220221220221220221220, que significa "cambiar todo 1o 2a 2, y cambiar 0a 1si y solo si hay un número impar de 1s alrededor".

Print@@@

Imprime la matriz.

La semiprueba de "' 1s impar ' es equivalente a 'exactamente uno 1'":

Considere esta cuadrícula de píxeles de 5x5. El blanco es una 0o una 2celda (píxeles no despiertos), y el gris es una 1celda.

Si 1se generó una celda alrededor de tres 0celdas, entonces la cuadrícula debe verse así: tiene tres 1s dispuestos en forma de U (o una versión rotada) de la siguiente manera:

Debido a la autosimilitud de este autómata celular, cualquier patrón que aparezca en el autómata celular debe aparecer en diagonal (por inducción). Sin embargo, este patrón no es diagonalmente simétrico. es decir, no puede ocurrir en diagonal y no puede aparecer en ningún lugar del autómata celular.

Despertar / Dormir son equivalentes

Tenga en cuenta que una 0celda no puede estar rodeada exactamente por una o tres 2celdas y celdas en reposo 0, ya que eso implicaría que algunos pasos anteriores, la celda tenía un vecino de una o tres 1celdas, y debe haberse convertido en un 1ya (contradicción). Por lo tanto, está bien ignorar la distinción entre 1y 2y el estado 'cambiar todo 1a 1, y 0a a 1si y solo si tiene un número impar de vecinos distintos de cero'.

El autómata celular resultante es de hecho idéntico al original, la única diferencia es que no hay distinción entre borrachos "despiertos" y "dormidos". Este patrón se describe en OEIS A169707 .

Print@@@CellularAutomaton[{750,{2,{a={0,2,0},2-a/2,a}},{1,1}},{j={{1}},0},{j#}]&

Pruébalo en línea!

Comparación lado a lado de las primeras 16 iteraciones:

Agregar dos iteraciones consecutivas da un resultado que sigue las especificaciones de desafío (94 bytes):

Print@@@Plus@@CellularAutomaton[{750,{2,{a={0,2,0},2-a/2,a}},{1,1}},{{{1}},0},{Ramp@{#-1,#}}]&

Pruébalo en línea!

Python 2 , 192 bytes

x=input()
o=c={x+x*1j}
R=range(x-~x)
exec"n=[C+k for k in-1j,1j,-1,1for C in c];n={k for k in n if(k in o)<2-n.count(k)};o|=c;c=n;"*x
print[[`(X+Y*1jin c)+(X+Y*1jin o|c)`for Y in R]for X in R]

Pruébalo en línea!

-17 bytes gracias al Sr. Xcoder
-9 bytes usando el formato de salida de Jonathan
-11 bytes gracias a Lynn
-3 bytes gracias a ovs

C, 360 354 343 319

#define A(i,b,e)for(int i=b;i<e;++i)
#define B(b,e)A(r,b,e){A(c,b,e)
#define W(n)(n<0?-(n):n)
#define C(r,c)b[W(r)*s+W(c)]
#define D C(r,c)

q(n){char N,s=n+2,(*b)[2]=calloc(s,2*s);C(0,0)
[1]=1;A(g,0,n+1){B(0,s)*D=D[1];}B(0,g+2){N=(*C
(r-1,c)+*C(r+1,c)+*C(r,c-1)+*C(r,c+1))&1;D[1]=
*D?2:N;}}}B(2-s,s-1)putchar(*D+32);puts("");}}

Las nuevas #definelíneas después de no líneas son solo para presentación aquí, por lo que no se cuentan. Incluí una función de contenedor, por lo que es −6 (313) si la función no se cuenta y supones que nproviene de otro lugar. q(10)salidas:

          !          
          "          
        !"""!        
         !"!         
         """         
        " " "        
       """""""       
      "  """  "      
  !  ""  """  ""  !  
  "!" """ " """ "!"  
!"""""""""""""""""""!
  "!" """ " """ "!"  
  !  ""  """  ""  !  
      "  """  "      
       """""""       
        " " "        
         """         
         !"!         
        !"""!        
          "          
          !          

Utilizando para vacío, "para dormir y !para despierto.

Esto funciona así:

• A(i,b,e)es "∀i∈ [b, e)", B(b,e)es "∀r∈ [b, e) .∀c∈ [b, e)".

• Observe que después de n generaciones, el tablero es 2 n + 1 cuadrado.

• Debido a la simetría del tablero, esto solo necesita simular el cuadrante inferior derecho, por lo que asignamos una matriz cuadrada n + 1 con 1 fila y columna de relleno para la búsqueda de vecino posterior (entonces n + 2).

• Asignar con callocnos permite multiplicar simultáneamente el ancho por la altura y despejar el tablero a 0(vacío).

• Al buscar una celda por sus coordenadas ( Cy D), utiliza el valor absoluto de la fila y la columna ( W) para reflejar automáticamente las coordenadas.

• El tablero se almacena como un conjunto de pares de enteros que representan las generaciones actuales y anteriores. Los enteros en cuestión son charpara que podamos evitar sizeof.

• La generación que se busca con mayor frecuencia (según la prueba vecina) es la generación pasada, por lo que se coloca en el índice 0 en el par para que se pueda acceder a ella *.

• En cada generación ( g), la generación actual se copia sobre la generación anterior utilizando un Bbucle, luego la nueva generación se genera a partir de la anterior.

• Cada celda se representa usando 0para vacío, 1para despierto y 2para dormir. Contar vecinos era originalmente un cálculo del número de bits establecidos en los 4 bits bajos de la celda cuando los 4 vecinos se desplazan y OR juntos como banderas ( N), 16para dormir. Pero con la observación de que un número impar de vecinos es equivalente a exactamente 1 vecino, podemos guardar varios caracteres simplemente usando una máscara con 1.

• Al final, el tablero se imprime por completo iterando sobre el cuadrante inferior derecho usando el mismo truco de coordenadas de valor absoluto, menos el relleno, por lo que no imprimimos el relleno exterior en el tablero. Esta es también la razón por la cual el Bbucle incluye un corchete de apertura, porque tenemos la instrucción de nueva línea adicional en el bucle externo.

• Los códigos ASCII asignan convenientemente 0 + 32 (vacío) a un espacio, 2 + 32 (durmiendo) "y 1 + 32 (despierto) a !.

En general, creo que este es un golf sorprendentemente legible debido a la buena estructura del problema.

MATL , 39 bytes

QtE:=&*G:"tt0=w1Y6Z+Xj1=*w|gJ*+]Q|U31+c

Esto muestra

• Emptycomo (espacio)
• Awake como #
• Sleepingcomo !.

Pruébalo en línea! También puede ver crecer el patrónen el arte ASCII, o gráficamente (código modificado).

Explicación

El código utiliza números complejos 0, 1, jpara representar los tres estados: vacío, estela, dormir, respectivamente.

Q         % Implicitly input n. Add 1
tE        % Duplicate and multiply by 2
:         % Range [1 2 ... 2*n]
=         % Test for equalty. Gives [0 ... 0 1 0... 0], with 1 at position n
&*        % Matrix of all pairwise products. Gives square matrix of size 2*n
          % filled with 0, except a 1 at position (n,n). This is the grid
          % where the walk will take place, initiallized with an awake cell
          % (value 1). The grid is 1 column and row too large (which saves a
          % byte)
G:"       % Do n times
  tt      %   Duplicate current grid state twice
  0=      %   Compare each entry with 0. Gives true for empty cells, false
          %   for the rest
  w       %   Swap: moves copy of current grid state to top
  1Y6     %   Push 3×3 matrix with Von Neumann's neighbourhood
  Z+      %   2D convolution, maintaining size
  Xj      %   Real part
  1=      %   Compare each entry with 1. This gives true for cells that
          %   have exactly 1 awake neighbour
  *       %   Multiply, element-wise. This corresponds to logical "and": 
          %   cells that are currently empty and have exactly one awake
          %   neighbour. These become 1, that is, awake
  w       %   Swap: moves copy of current grid state to top
  |g      %   Absolute value, convert to logical: gives true for awake or
          %   sleeping cells, false for empty cells
  J*+     %   Mulltiply by j and add, element-wise. This sets awake and 
          %   sleeping cells to sleeping. The grid is now in its new state
]         % End
Q         % Add 1, element-wise. Transforms empty, awake, sleeping 
          % respectively from 0, 1, j into 1, 2, 1+j
|U        % Abolute value and square, element-wose. Empty, awake, sleeping 
          % respectively give 1, 4, 2
31+c      % Add 31 element-wise and convert to char. Empty, awake, sleeping 
          % respectively give characters ' ' (codepoint 32), '#' (codepoint 
          % 35) and '!' (codepoint 33). Implicitly display

Befunge, 384 304 bytes

&:00p->55+,000g->>00g30p:40p\:50p\5>>40g!50g!*vv0g05g04p03-<
@,+55_^#`g00:+1$_^>p:4+4g5%2-50g+5#^0#+p#1<v03_>30g:!#v_:1>^
#v_>$99g,1+:00g`^ ^04+g04-2%5g4:\g05\g04\p<>g!45*9+*3+v>p:5-
 >\50p\40p\30p:#v_>>0\99g48*`!>v >30g:1-30^>>**\!>#v_>v^9 9<
$0\\\\0$        >\99g88*-!+\:4->#^_\>1-!48>^       >$3>48*+^

Pruébalo en línea!

El problema al intentar implementar este tipo de cosas en Befunge es el tamaño limitado de la memoria (2000 bytes para datos y código). Así que tuve que usar un algoritmo que calcula el carácter correcto para cualquier coordenada dada sin referencia a cálculos anteriores. Lo logra al mirar recursivamente en el tiempo a través de todos los caminos posibles que el borracho podría haber seguido para llegar a ese punto.

Lamentablemente, esta no es una solución eficiente en particular. Funciona, pero es increíblemente lento, y se vuelve exponencialmente más lento cuanto mayor es el valor de n . Entonces, si bien podría funcionar para cualquier n hasta aproximadamente 127 (límite de celda de memoria de 7 bits de Befunge), en la práctica inevitablemente perderá interés esperando el resultado. En TIO, alcanzará el tiempo de espera de 60 segundos en algo más alto que alrededor de 6 (en el mejor de los casos). Un compilador funcionará mucho mejor, pero incluso entonces probablemente no quieras subir mucho más de 10.

Aún así, pensé que valía la pena enviarlo porque en realidad es una buena demostración de una "función" recursiva en Befunge.

Python 2 , 214 bytes

def f(n):k=n-~n;N=k*k;A=[0]*N;A[N/2]=2;exec"A=[[2*([j%k>0and A[j-1],j%k<k-1and A[j+1],j/k>0and A[j-k],j/k<k-1and A[j+k]].count(2)==1),1,1][v]for j,v in enumerate(A)];"*n;print[map(str,A)[k*x:][:k]for x in range(k)]

Pruébalo en línea!

Explicación

Usos 0para empty, 1para sleepingy 2para awake. Imprime una lista de caracteres bidimensionales (cadenas de una longitud).
Define una función que toma un número entero no negativo n. Avanza sucesivamente el autómata celular hasta alcanzar el estado deseado. Finalmente, se aplica una conversión entre los valores enteros internos y los caracteres reales.

Lua , 251 242 239 238 bytes

-8 bytes al simplificar el inicializador de matriz a costa de algunos espacios en blanco iniciales adicionales.
-1 byte cambiando c=i==2+...and print(s)a c=i~=2+...or print(s).
-3 bytes construyendo una cadena completa primero e imprimiendo una vez al final.
-1 byte gracias a Jonathan Frech reescribiendo or(g(...)==1 andcomo or(1==g(...)and.

function g(x,y)return(a[x]or{})[y]or 0 end a={{1}}for i=2,2+...do n={}s=""for x=-i,i do n[x]=n[x]or{}q=a[x]or{}for y=-i,i do n[x][y]=q[y]and 0or(1==g(x+1,y)+g(x,y+1)+g(x-1,y)+g(x,y-1)and 1)s=s..(q[y]or" ")end s=s.."\n"end a=n end print(s)

Pruébalo en línea!

Vacío =
Despertar del espacio = 1
Dormir =0

Toma datos de la línea de comando e imprime en stdout.

Al representar los estados como false/ nil, 1e 0internamente, la detección de "vacío" no necesita ningún código y la verificación "exactamente uno despierto" se puede hacer con solo una adición.

APL (Dyalog) , 38 bytes

((2∘∧⌈1={2⊃+/1=⍵,⍉⍵}⌺3 3)(⌽0,⍉)⍣4)⍣⎕⍪1

Pruébalo en línea!

-4 gracias a Adám .
-8 gracias a ngn .

Jalea , 39 29 bytes

-,1ṙ@€Sµ+Z
‘ṬŒḄ×þ`µÇ׬Ḃ+Ḃ+µ³¡

Pruébalo en línea!

Usos 0, 1y 2para vaciar despierto y dormido. El pie de página en el enlace convierte esto a , @y #.

• -1 byte usando en ṬŒḄlugar de ḤḶ=¹.
• -2 bytes usando en -lugar de 1N. También hace ¤innecesario.
• -1 byte usando en Slugar de +/.
• -6 bytes usando en Ḃ+Ḃ+lugar de %3=1+=1Ḥ$+. Ahora se usa 2para dormir en lugar de 3.

Explicación que viene ...

APL (Dyalog Classic) , 38 bytes

((2∘∧⌈2|⍉∘g∘⍉+g←3+/0,,∘0)(⌽0,⍉)⍣4)⍣⎕⍪1

Pruébalo en línea!

basado en la solución de Erik the Outgolfer

⍪1 es una matriz 1x1 que contiene 1

⎕ entrada evaluada

( )⍣⎕ aplicar eso muchas veces

• (⌽0,⍉)⍣4rodear con 0s, es decir 4 veces hacer: transponer ( ⍉), agregar 0s a la izquierda ( 0,), invertir horizontalmente ( ⌽)

• g←3+/0,,∘0 una función que suma triples horizontales, llámalo g

• ⍉∘g∘⍉una función que suma triples verticales - eso está gbajo transposición

• 2 | ⍉∘g∘⍉ + g←3+/0,,∘0 suma de las dos sumas módulo 2

• ⌈ cuanto mayor entre eso y ...

• 2∘∧ el MCM de 2 y la matriz original: esto convierte 1s en 2s, mientras conserva 0s y 2s

Perl 5 , 192 + 1 ( -n) = 193 bytes

for$i(1..2*$_+1){push@a,[()x$_]}$a[$_][$_]=1;map{@b=();for$i(0..$#a){map$b[$i][$_]=$a[$i][$_]?2:$a[$i-1][$_]+($_&&$a[$i][$_-1])+$a[$i+1][$_]+$a[$i][$_+1]==1?1:0,0..$#a}@a=@b}1..$_;say@$_ for@a

Pruébalo en línea!

Utiliza 0 para vacío, 1 para despierto y 2 para dormido.

Ruby , ₁₆₄₁₅₃ bytes

->n{(r=([e=' ']*(l=2*n+1)<<"
")*l)[n+n*l+=1]=a=?@
n.times{r=r.map.with_index{|c,i|c==a ??#:c==e ?r.values_at(i-1,i+1,i-l,i+l).one?{|v|v==a}?a:e:c}}
r*""}

Pruébalo en línea!

Utiliza "" para Vacío, "@" para Despertar y "#" para Dormir (como en el ejemplo). Supongo que podría ahorrar 6 bytes usando números, pero se ve mejor así.

Pip , 69 61 bytes

60 bytes de código, +1 para -lbandera.

YZG2*a+1y@a@a:1LaY{y@a@b?2oN(y@(a+_)@(b+B)MP[0o0v0])=1}MC#yy

Toma ncomo argumento de línea de comandos. Usos 0para vacío, 1para despertar y 2para dormir. (Para obtener un mejor arte ASCII como en los ejemplos del desafío, reemplace el final ycon " @#"@y).

Pruébalo en línea!

Explicación

Preparar:

YZG2*a+1y@a@a:1

                 Implicit: a is 1st cmdline arg; o is 1; v is -1
 ZG2*a+1         Square grid (i.e. nested list) of 0's, with side length 2*a+1
Y                Yank into y variable
        y@a@a:1  Set the element at coordinates (a,a) to 1

Bucle principal:

LaY{...}MC#y

La            Loop (a) times:
          #y  Len(y) (i.e. 2*a+1)
   {   }MC    Map this function to the coordinate pairs in a 2*a+1 by 2*a+1 grid
  Y           and yank the resulting nested list back into y

donde el cuerpo de la función es:

y@a@b?2oN(y@(a+_)@(b+B)MP[0o0v0])=1

                                     The function args, representing the coords of the
                                     current cell, are a and b
y@a@b?                               Is the cell at these coords 0 or nonzero?
      2                              If nonzero (1 or 2), make it 2
                                     Else, if zero, we need to check the neighbors
                         [0o0v0]     List of [0; 1; 0; -1; 0]
                       MP            Map this function to each adjacent pair of values--
                                     i.e. call it four times with args (0; 1), (1; 0),
                                     (0; -1), and (-1; 0)
          y                           Index into the grid using
           @(a+_)                     a + the 1st item in the pair as the row and
                 @(b+B)               b + the 2nd item in the pair as the column
                                     The result of MP is a list of the values of the cells
                                     in the Von Neumann neighborhood
       oN(                      )    Get the number of 1's in that list
                                 =1  and test if it equals 1
                                     If so, the new value of this cell is 1; if not, it's 0

Después del ciclo, simplemente imprimimos automáticamente y. La -lbandera significa que la lista anidada se imprime concatenando los contenidos de cada fila y separando las filas con nuevas líneas.

Java (OpenJDK 8) , 220 bytes

n->{int s=n*2+3,i=0,x,y;char[][]a=new char[s][s],b;for(a[s/2][s--/2]=61;i++<n;a=b)for(b=new char[s+1][s+1],x=0;++x<s;)for(y=0;++y<s;)b[x][y]=a[x][y]>32?'0':(a[x][y-1]+a[x][y+1]+a[x-1][y]+a[x+1][y])%8==5?61:' ';return a;}

Pruébalo en línea!

Nota: la matriz devuelta contiene un borde o '\0'caracteres. Como se supone que el plano es infinito, solo se utiliza el no borde.

Mapeo de personajes:

• Vacío: (espacio)
• Despierto: =
• Dormido: 0

Ahorra

• 29 bytes guardados gracias a Jonathan S.
• 9 bytes adicionales gracias a Jonathan S. intercambiando personajes con otros y "haciendo magia con números primos y aritmética modular"

Python, 199 192 bytes

Este código se ejecuta tanto en Python 2 como en Python 3, pero utiliza la popular biblioteca Numpy de terceros para hacer el manejo de la matriz.

from numpy import*
def f(n):
 m=2*n+1;g=zeros((m+2,)*2,'i');g[n+1,n+1]=1
 while n:a=g[1:-1,1:-1];a[:]=(a<1)*(sum(g[r:r+m,c:c+m]&1for r,c in((0,1),(1,0),(1,2),(2,1)))==1)+(a>0)*2;n-=1
 return g

Vacío = 0
Despierto = 1
Durmiendo = 2

print(f(6)) salidas

[[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 2 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 2 2 2 1 0 0 0 0 0]
 [0 0 0 0 0 0 1 2 1 0 0 0 0 0 0]
 [0 0 0 1 0 0 2 2 2 0 0 1 0 0 0]
 [0 0 0 2 1 2 0 2 0 2 1 2 0 0 0]
 [0 1 2 2 2 2 2 2 2 2 2 2 2 1 0]
 [0 0 0 2 1 2 0 2 0 2 1 2 0 0 0]
 [0 0 0 1 0 0 2 2 2 0 0 1 0 0 0]
 [0 0 0 0 0 0 1 2 1 0 0 0 0 0 0]
 [0 0 0 0 0 1 2 2 2 1 0 0 0 0 0]
 [0 0 0 0 0 0 0 2 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

Si desea una impresión más bonita, puede llamarlo de esta manera:

n=6;print('\n'.join(''.join(' @#'[v]for v in u)for u in f(n)))

que imprime con los mismos caracteres que figuran en la pregunta.