Uma sequência espiral

29

fundo

A sequência OEIS A272573 descreve uma espiral em uma grade hexagonal da seguinte maneira:

Inicie uma espiral de números em um mosaico hexagonal, com o hexágono inicial como a (1) = 1. a (n) é o menor número inteiro positivo que não é igual a ou anteriormente adjacente a seus vizinhos.

A sequência começa

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

Aqui está uma ilustração do padrão espiral: insira a descrição da imagem aqui

  • a(11) != 1porque então 3e 1seria adjacente em dois lugares.
  • a(11) != 2porque então 3e 2seria adjacente em dois lugares.
  • a(11) != 3porque então 3seria adjacente a si mesmo.
  • a(11) != 4porque então 3e 4seria adjacente em dois lugares.
  • Portanto a(11) = 5.

Desafio

O desafio é escrever um programa que calcule A272573 . Isso é , então o código mais curto vence.

Peter Kagey
fonte
Não consigo ver a imagem como ela está bloqueada aqui, talvez esteja faltando alguma coisa, mas seu exemplo mostra a (11) = 4, mas na sua lista de sequências a (11) é 5.
Geobits
Apenas um erro - obrigado por pegá-lo.
Peter Kagey
7
Aparentemente, essa sequência de OEIS foi enviada por você mesmo. Agradável. :)
Arnauld 12/12
qual é o limite para n? Existe limite de tempo ?
Setop
5
Aguardando resposta Hexagony ...
Jonathan Allan

Respostas:

23

JavaScript (ES6),  267 .. 206  199 bytes

N

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]])

Experimente online!

Quão?

Definições

Por convenção, chamaremos célula de canto de uma célula que possui apenas uma aresta em comum com a camada anterior da espiral e a célula lateral de célula que possui duas arestas em comum com a camada anterior. Conforme sugerido por Ourous, também podemos pensar nelas como células da ordem 1 e 2, respectivamente.

As células de canto são mostradas em amarelo abaixo. Todas as outras células são células laterais (exceto a célula central, que é um caso especial).

tipos de células

Sobre vizinhos de célula

Nós realmente não precisamos acompanhar as coordenadas das células na grade. A única coisa que precisamos saber é a lista de células vizinhas para cada célula na espiral a qualquer momento.

Nos diagramas a seguir, os vizinhos na camada anterior são mostrados em tom claro e os vizinhos adicionais na camada atual em tom mais escuro.

Uma célula possui 2 vizinhos entre as células anteriores se:

  • é a primeira célula lateral de uma nova camada (como 8 )
  • ou é uma célula de canto, mas não a última da camada (como 9 )

2 vizinhos

Uma célula possui 3 vizinhos entre as células anteriores se:

  • é uma célula lateral, mas não a primeira da camada (como 10 )
  • ou é a última célula de canto da camada atual (como 19 )

3 vizinhos

Implementação de vizinhos de célula

1inUMA[n]

1 1-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
]                    //

No código acima:

  • eu1 1
  • j1 16×eu
  • d

map()kEu-k

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

Encontrando o próximo termo da sequência

k

nv[n]

( 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
fonte
Ótima explicação. Uma possível melhoria: tornar as explicações nos blocos de código totalmente visíveis sem a necessidade de rolagem horizontal (não importa para o código de golfe). Visualizando no Firefox, existem 5 colunas ocultas no primeiro bloco de códigos de explicação e 6 colunas ocultas no segundo.
trichoplax em 21/02
@trichoplax Obrigado pelo seu comentário e sugestão. Você poderia especificar qual versão do Firefox está usando e em qual plataforma? Eu sempre tento formatar blocos de explicação para que nenhuma rolagem horizontal seja necessária. Estou no Firefox 65 / Win10 agora e não tenho nenhuma coluna oculta.
Arnauld
Verificarei a versão do Firefox quando chegar em casa, mas pode ser porque estou no Fedora. Irá verificar em outro sistema operacional e que você saiba
trichoplax
11
Parece variar de acordo com o sistema operacional. Irá aumentar isso no MSE quando eu tiver a chance de reunir algumas evidências (se ainda não o foram)
trichoplax
11
Eu levantei isso no MSE . Sinta-se livre para editar se alguém vir outras combinações de SO / navegador que mostrem barras de rolagem horizontais.
trichoplax 27/02
7

Limpo , 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]])[]

Experimente online!

Gera a sequência para sempre.

Mapeamento hexagonal

A maior parte do código destina-se ao mapeamento de hexágonos exclusivamente para (x,y)coordenadas, para que haja uma função única e simples para determinar a adjacência que é válida para todos os mapeamentos de pontos.

Os pontos mapeados são assim:

              ---
        --- < 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 daí, determinar a adjacência é trivial e ocorre quando um dos seguintes:

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

Geração de pontos

Observe que, ao atravessar o hexágono em espiral, as diferenças se repetem para cada camada n:

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

Isso gera os pontos na ordem correta, somando prefixos dessa sequência:

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

Reunindo

O código que realmente encontra a sequência da pergunta é apenas:

$[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, por sua vez, é principalmente filtrado por and[r<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]

Esse filtro obtém pontos de m(a lista de pontos já mapeados) por:

  • Ignorando números naturais iguais a qualquer j
  • Para todos os (i,j)lugares iadjacentes ap
  • Para cada (p,q)onde o valor qé igual av
  • Para todos os (u,v)locais uadjacentes ao ponto atual
Furioso
fonte