Una secuencia en espiral

29

Fondo

La secuencia OEIS A272573 describe una espiral en una cuadrícula hexagonal de la siguiente manera:

Comience una espiral de números en un mosaico hexagonal, con el hexágono inicial como a (1) = 1. a (n) es el entero positivo más pequeño que no es igual o previamente adyacente a sus vecinos.

La secuencia comienza

1, 2, 3, 4, 5, 6, 7, 4, 6, 8, 5, 9, 8, 10, 2, 11, ...

Aquí hay una ilustración del patrón en espiral: ingrese la descripción de la imagen aquí

  • a(11) != 1porque entonces 3y 1sería adyacente en dos lugares.
  • a(11) != 2porque entonces 3y 2sería adyacente en dos lugares.
  • a(11) != 3porque entonces 3sería adyacente a sí mismo.
  • a(11) != 4porque entonces 3y 4sería adyacente en dos lugares.
  • Por lo tanto a(11) = 5.

Reto

El desafío es escribir un programa que calcule A272573 . Este es el , por lo que gana el código más corto.

Peter Kagey
fuente
No puedo ver la imagen ya que está bloqueada aquí, así que tal vez me falta algo, pero su ejemplo muestra a (11) = 4, pero en su lista de secuencias a (11) es 5.
Geobits
Solo un error, gracias por atraparlo.
Peter Kagey
77
Esta secuencia OEIS fue presentada por usted, aparentemente. Agradable. :)
Arnauld
¿Cuál es el límite para n? ¿hay un límite de tiempo?
Setop
55
Esperando respuesta de Hexagony ...
Jonathan Allan

Respuestas:

23

JavaScript (ES6),  267 .. 206  199 bytes

Devuelve una matriz que contiene los norte primeros términos de la secuencia.

n=>(F=v=>++i<n?F([...v,(A=N[i]=[1,!j++||d+1,j%L?d:(j%=L*6)?++d:L++&&d++].map(k=>N[k=i-k].push(i)&&k),g=k=>v[E='every']((V,x)=>V-k|N[x][E](y=>A[E](z=>v[y]-v[z])))?k:g(-~k))()]):v)([L=1],N=[[i=j=d=0]])

Pruébalo en línea!

¿Cómo?

Definiciones

Por convención, llamaremos a la celda de esquina una celda que solo tiene un borde en común con la capa anterior de la espiral y a la celda lateral una celda que tiene dos bordes en común con la capa anterior. Como sugirió Ourous, también podemos pensar en ellas como células de orden 1 y células de orden 2, respectivamente.

Las celdas de las esquinas se muestran en amarillo a continuación. Todas las demás celdas son celdas laterales (excepto la celda central, que es un caso especial).

tipos de células

Sobre vecinos celulares

Realmente no necesitamos hacer un seguimiento de las coordenadas de las celdas en la cuadrícula. Lo único que necesitamos saber es la lista de celdas vecinas para cada celda en la espiral en un momento dado.

En los siguientes diagramas, los vecinos de la capa anterior se muestran en tonos claros y los vecinos adicionales en la capa actual en tonos más oscuros.

Una celda tiene 2 vecinos entre las celdas anteriores si:

  • Es la primera celda lateral de una nueva capa (como 8 )
  • o es una celda de esquina, pero no la última de la capa (como 9 )

2 vecinos

Una celda tiene 3 vecinos entre las celdas anteriores si:

  • es una celda lateral, pero no la primera de la capa (como 10 )
  • o es la última celda de la esquina de la capa actual (como 19 )

3 vecinos

Implementación de vecinos celulares

1yonorteUNA[norte]

1-1

[                    //
  1,                 // the previous cell is always a neighbor of the current cell
  !j++ || d + 1,     // if this is not the first cell of the layer, the cell at -(d + 1)
                     // is a neighbor (otherwise, we insert 1 twice; doing it that way
                     // saves bytes and having duplicate neighbors is not a problem)
  j % L ?            // if this is a side-cell:
    d                //   the cell at -d is a neighbor
  :                  // else (corner-cell):
    (j %= L * 6) ?   //   if this is not the last cell:
      ++d            //     insert the dummy duplicate neighbor at -(d + 1); increment d
    :                //   else (last cell):
      L++ && d++     //     the cell at -d is a neighbor; increment L; increment d
]                    //

En el código anterior:

  • L1
  • j16 6×L
  • re

map()kyo-k

.map(k =>
  N[k = i - k].push(i) && k
)

Encontrar el siguiente término de la secuencia

k

nortev[norte]

( g =                 // g = recursive function taking
  k =>                // the candidate value k
    v.every((V, x) => // for each previous cell of value V at position x, make sure that:
      V - k           //   V is not equal to k
      |               //   OR
      N[x].every(y => //   for each neighbor y of x:
        A.every(z =>  //     for each neighbor z of the current cell:
          v[y] - v[z] //       the value of y is not equal to the value of z
        )             //     end
      )               //   end
    )                 // end
    ?                 // if the above conditions are fulfilled:
      k               //   stop recursion and return k
    :                 // else:
      g(-~k)          //   try again with k + 1
)()                   // initial call to g with k undefined (this will cause V - k to be
                      // evaluated as NaN and force the 1st iteration to fail)
Arnauld
fuente
Gran explicación Una posible mejora: hacer que las explicaciones en los bloques de código sean totalmente visibles sin la necesidad de desplazamiento horizontal (no importa el código de golf). Al ver en Firefox, hay 5 columnas ocultas en el primer bloque de código de explicación y 6 columnas ocultas en el segundo.
Trichoplax
@trichoplax Gracias por tu comentario y sugerencia. ¿Podría especificar qué versión de Firefox está utilizando y en qué plataforma? Siempre trato de formatear bloques de explicación para que no se necesite desplazamiento horizontal. Estoy en Firefox 65 / Win10 en este momento y no tengo ninguna columna oculta.
Arnauld
Verificará la versión de Firefox cuando llegue a casa, pero podría ser porque estoy en Fedora. Verificará en otro sistema operativo y te lo
haré
1
Parece variar según el sistema operativo. Planteará esto en MSE cuando haya tenido la oportunidad de reunir alguna evidencia (si aún no lo ha hecho)
trichoplax
1
He planteado esto en MSE . Siéntase libre de editar si alguien ve otras combinaciones de SO / navegador que muestran barras de desplazamiento horizontales.
Trichoplax
7

Limpias , 284 279 272 262 bytes

import StdEnv
l=[0,-1,-1,0,1,1]
c(u,v)(p,q)=(u-p)^2+(v-q)^2<2||(u-p)*(q-v)==1
$[h:t]m=hd[[e: $t[(h,e):m]]\\e<-[1..]|and[e<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]]

$(scan(\(a,b)(u,v)=(a-u,b-v))(0,0)[(i,j)\\n<-[1..],i<-[1,1:l]&j<-l,_<-[max(~j<<i)1..n]])[]

Pruébalo en línea!

Genera la secuencia para siempre.

Mapeo Hexagonal

La mayor parte del código va a mapear hexágonos únicamente para las (x,y)coordenadas, de modo que haya una función única y simple para determinar la adyacencia que se aplica a todas las asignaciones de puntos.

Los puntos asignados se ven así:

              ---
        --- < 2,-2> ---       x-axis ___.X'
  --- < 1,-2> === < 2,-1> ---  /__.X'
< 0,-2> === < 1,-1> === < 2, 0>'
  === < 0,-1> === < 1, 0> ===
<-1,-1> === < 0, 0> === < 1, 1>
  === <-1, 0> === < 0, 1> ===
<-2, 0> === <-1, 1> === < 0, 2>.__
  --- <-2, 1> === <-1, 2> ---  \  'Y.___
        --- <-2, 2> ---       y-axis    'Y.
              ---

A partir de ahí, determinar la adyacencia es trivial y ocurre cuando uno de:

  • x1 == x2 y abs(y1-y2) == 1
  • y1 == y2 y abs(x1-x2) == 1
  • y1 == y2 - 1 y x2 == x1 - 1
  • y1 == y2 + 1 y x2 == x1 + 1
  • x1 == x2 y y1 == y2

Generación de puntos

Observe que al atravesar el hexágono en espiral las diferencias se repiten para cada capa n:

  1. n pasos de (1,0)
  2. n-1 pasos de (1,-1)
  3. n pasos de (0,-1)
  4. n pasos de (-1,0)
  5. n pasos de (-1,1)
  6. n pasos de (0,1)

Esto genera los puntos en el orden correcto tomando sumas de prefijos de esta secuencia:

scan(\(a,b)(u,v)=(a-u,b-v))(0,0)[(i,j)\\n<-[1..],i<-[1,1:l]&j<-l,_<-[max(~j<<i)1..n]]

Reuniéndolo

El código que realmente encuentra la secuencia de la pregunta es simplemente:

$[h:t]m=hd[[e: $t[(h,e):m]]\\e<-[1..]|and[e<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]]

Que a su vez se filtra principalmente por and[r<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]

Este filtro toma puntos de m(la lista de puntos ya asignados) por:

  • Ignorando los números naturales que son iguales a cualquier j
  • Por cada (i,j)lugar iadyacente ap
  • Para cada lugar (p,q)donde el valor qes igual av
  • Para cada (u,v)lugar uadyacente al punto actual
Οurous
fuente