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:
a(11) != 1
porque entonces3
y1
sería adyacente en dos lugares.a(11) != 2
porque entonces3
y2
sería adyacente en dos lugares.a(11) != 3
porque entonces3
sería adyacente a sí mismo.a(11) != 4
porque entonces3
y4
serí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 código de golf , por lo que gana el código más corto.
code-golf
sequence
hexagonal-grid
Peter Kagey
fuente
fuente
Respuestas:
JavaScript (ES6),
267 .. 206199 bytesDevuelve una matriz que contiene losnorte primeros términos de la secuencia.
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).
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:
Una celda tiene 3 vecinos entre las celdas anteriores si:
Implementación de vecinos celulares
En el código anterior:
map()
Encontrar el siguiente término de la secuencia
fuente
Limpias ,
284279272262 bytesPrué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í:
A partir de ahí, determinar la adyacencia es trivial y ocurre cuando uno de:
x1 == x2
yabs(y1-y2) == 1
y1 == y2
yabs(x1-x2) == 1
y1 == y2 - 1
yx2 == x1 - 1
y1 == y2 + 1
yx2 == x1 + 1
x1 == x2
yy1 == y2
Generación de puntos
Observe que al atravesar el hexágono en espiral las diferencias se repiten para cada capa
n
:n
pasos de(1,0)
n-1
pasos de(1,-1)
n
pasos de(0,-1)
n
pasos de(-1,0)
n
pasos de(-1,1)
n
pasos de(0,1)
Esto genera los puntos en el orden correcto tomando sumas de prefijos de esta secuencia:
Reuniéndolo
El código que realmente encuentra la secuencia de la pregunta es simplemente:
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:j
(i,j)
lugari
adyacente ap
(p,q)
donde el valorq
es igual av
(u,v)
lugaru
adyacente al punto actualfuente