Adjacência hexagonal

28

Exemplo de espiral hexagonal

A imagem acima exibe uma grade hexagonal de hexágonos. Cada célula da grade recebe um índice, começando do centro e girando no sentido anti-horário, como mostrado. Observe que a grade continuará indefinidamente - a imagem acima é simplesmente a primeira seção. O próximo hexágono seria adjacente a 60 e 37.

Sua tarefa é determinar se duas células nessa grade são adjacentes.

Escreva um programa ou função que, dados dois índices de células, imprima / retorne um valor verdadeiro se as duas células forem adjacentes e um valor falsey se não.

Se não for limitado por razões práticas, seu código deve funcionar teoricamente para qualquer tamanho de entrada.

Casos de teste de verdade:

0, 1
7, 18
8, 22
24, 45
40, 64
64, 65

Casos de teste de Falsey:

6, 57
29, 90
21, 38
38, 60
40, 63
41, 39
40, 40

Isso é então a resposta mais curta em bytes vence. Explicações, mesmo para idiomas não esotéricos, são incentivadas.

John Michael Law
fonte

Respostas:

7

Elixir , 263 257 264 223 214 218 214 bytes

a=fn x,y->i=&(&1*(&1-1)*3+1)
[x,y]=Enum.sort [x,y]
if x<1,do: y in 1..6,else: (y-x==1||fn->a=y-trunc i.((r=(:math.sqrt(12*x-3)+3)/6)+1)
t=trunc r
a in [0,1,rem(b=x-i.(t)+1, t)<1&&b-t*6!=0&&2]||b<2&&a==-1 end.())end

Experimente online!

versão ungolfed

def get_ring(x) do
    1/6*(:math.sqrt(12*x-3)+3)
end

def inv_get_ring(x), do: x*(x-1)*3+1

def ring_base(x), do: inv_get_ring(trunc(x))

def is_corner(x) do
    ring = trunc(get_ring(x))
    inv_ring = ring_base(ring)
    stuff = (x-inv_ring+1)
    rem(stuff, ring) == 0
end

def is_last(x),do: ring_base(get_ring(x)+1)-1 == x
def is_first(x),do: ring_base(get_ring(x)) == x

def hex_adj(x, y) do
    {x, y} = {min(x,y), max(x,y)}
    cond do 
        x == 0 ->y in 1..6      
        y-x==1 -> true
        true ->
            adj = trunc(inv_get_ring(get_ring(x)+1))
            number = if is_corner(x)&&!is_last(x), do: 2, else: 1
            if y-adj in 0..number do
                true
            else
                is_first(x) && y == adj-1
            end
    end
end
  • trunc(number) Retorna a parte inteira do número
  • rem(a,b) Retorna o restante de a / b
  • cond do end Isso é equivalente a outras cláusulas if ou switch case em muitas linguagens imperativas

Explicação

get_ring (índice)

Calcula o "anel" do índice.

Exemplo: 1 para 1-6, 2 para 7-18, etc.

Isso só se aplica se o resultado for floored. Os dígitos finais representam a que distância esse bloco está ao redor do anel.

inv_get_ring (anel)

Calcula o inverso de get_ring(index).

ring_base (ring)

Calcula o índice do primeiro bloco no anel.

is_corner (índice)

Cantos são peças que possuem três peças adajentes no anel externo. O anel mais interno consiste inteiramente de cantos.

Exemplos: 21,24,27,30,33,36

is_last (índice)

É verdadeiro se este índice for o mais alto em seu anel.

is_first (índice)

É verdade se esse é o bloco base do anel.

Garuno
fonte
2
Eu editei a resposta para incluir uma correção para a beira-case :)
Garuno
Eu segui sua versão do golfe pela primeira vez nas iterações, mas então parecia que você mudou sua abordagem. Sua versão atual do golfe ainda é equivalente à versão não-golfada?
John Michael Lei
Sim! Acabei de aprender que você pode declarar variáveis ​​em linha no Elixir. Isso me deu a capacidade de me livrar das funções lambda no início do código. Eu apenas misturei as variáveis ​​um pouco, para torná-las mais eficientes.
Garuno
5

MATL , 47 45 44 43 41 bytes

s:"JH3/^6:^t5)w5:&)@qY"w@Y"]vYs0hG)d|Yo1=

Experimente online! Ou verifique todos os casos de teste .

Como bônus, o código gera uma espiral hexagonal que rastreia as posições dos centros celulares, que podem ser vistas graficamente no MATL Online , modificando a última parte do código.

Explicação

Ideia geral    O código primeiro constrói uma espiral hexagonal suficientemente grande com uma etapa unitária. A espiral é definida como um vetor de números complexos que representam as posições dos centros celulares. A indexação nesse vetor com os números de entrada e a diferença absoluta calculam a distância entre as duas células indicadas. As células são adjacentes se, e somente se, o resultado for 1. No entanto, devido às imprecisões do ponto flutuante, o arredondamento é necessário antes da comparação com 1.

Construindo a espiral    A espiral terá um número de "camadas" iguais à soma das duas entradas. Isso é (muito) maior que o necessário e garante que as células de entrada estejam presentes na espiral.

Para construir a espiral, o número complexo j 2/3 (onde j é a unidade imaginária) é primeiro calculado. Aumentar isso para os expoentes 1 a 6 fornece um conjunto básico de deslocamentos, de modo que seguir esses deslocamentos em ordem traçaria um hexágono. Esse hexágono formaria a camada mais interna da espiral, exceto que seria "fechada". Na verdade, queremos que o hexágono "cresça" no último passo e depois traçamos um hexágono maior, com o dobro de pontos (alinhados em grupos de dois), para formar a próxima camada da espiral; veja a ilustração aqui . A próxima camada terá três vezes mais pontos que o primeiro (em grupos de três); veja aqui .

Para fazer isso, o quinto deslocamento do conjunto básico (que aponta na direção sudeste) é escolhido como o passo "crescente". A camada k começa com esse passo, seguido pelos cinco primeiros passos básicos repetidos k vezes, seguidos pelo sexto passo (direção leste) repetido k -1 vezes. Esperamos que isso fique mais claro, observando os dois números acima.

O vetor resultante, incluindo todas as camadas, representa os deslocamentos complexos que rastreariam a espiral. A soma cumulativa fornece as coordenadas reais dos centros celulares.

Por fim, a célula inicial, localizada em 0, é anexada ao final desse vetor. Isso ocorre porque o MATL usa indexação modular com base em 1 e o índice 0 refere-se à última entrada de uma matriz.

Teste de adjacência    As duas células fornecidas pelos números de entrada são selecionadas, suas coordenadas são subtraídas e o valor absoluto é arredondado e comparado com 1.

Código comentado

s         % Implicitly input array of two numbers. Push their sum, say S
:         % Range [1 2 ... S]
"         % For each k in [1 2 ... S]
  J       %   Push 1j
  H3/     %   Push 2, then 3, then divide: gives 2/3
  ^       %   Power
  6:      %   Push [1 2 ... 6]
  ^       %   Element-wise power. This is the array of 6 basic displacements
  t5)     %   Duplicate. Get 5th entry
  w5:&)   %   Swap. Push subarray with entries 1st to 5th, then push 6th
  @qY"    %   Repeat the 6th displacement k-1 times
  w@Y"    %   Swap. Repeat 1st to 5th displacements k times
]         % End
v         % Concatenate everything into a column vector
Ys        % Cumulative sum. This gives the cell center coordinates
0h        % Append a 0
G)        % Index by the input vector
d|        % Absolute difference
Yo        % Round to nearest integer
1=        % Does it equal 1? Implicitly display
Luis Mendo
fonte
Você poderia adicionar uma explicação?
Shaggy
@ Shaygy eu adicionei uma explicação geral. Deixe-me saber se está claro (é difícil de explicar). I irá adicionar o código comentado mais tarde
Luis Mendo
2

05AB1E (herdado) , 30 29 27 bytes

α2‹i1q}1ݹ+v12y*3-tîÌy+}Ÿ²å

Experimente online!

Explicação do código:

α2‹i1q}                     : if the absolute diff of the two number is 1 or 0 return 1
                          ²å: return that the second number is in
                         Ÿ  : range of {
       1Ý                   :  create [0, 1]
         ¹+                 :  add the first number to the elements
           v            }   :  map that list
            12y*3-tîÌy+     :  calculate the corresponding value where it's an adjacency
                                }

Explicação da matemática:

Eu "desperdicei" cerca de 5 horas fazendo este golfe. Em resumo, comecei a fazer um gráfico 2D das entradas e desenhar Xonde elas estavam adjacentes umas às outras. Então eu encontrei um padrão. Eu procurei no OEIS e no bingo! Eu encontrei essa sequência e usei a fórmula dada no site.

krinistof
fonte
1

C (gcc) , 175 173 bytes

Agradecimentos a Peter Taylor por pegar um bug.

Obrigado ao ceilingcat por -2 bytes. Esse operador continua sendo meu principal ponto cego.

c,r,C,L;y(a){a=a<L*2?L-a:a<L*3?-L:a<5*L?a-L*4:L;}z(a){L=ceil(sqrt(a/3.+.25)-.5);C=y(a-=3*L*~-L);L?L=y((L+a)%(L*6)):0;}f(a,b){z(a);c=C,r=L;z(b);a=a-b&&(abs(c-C)|abs(r-L))<2;}

Experimente online!

Essa abordagem está focada em encontrar a linha e a coluna das duas células e compará-las; quaisquer vizinhos não podem ter suas coordenadas correspondentes diferindo em mais de 1. Movendo-se do centro para fora, observamos que cada camada tem mais 6 células que a anterior. Isso significa que o "índice" mais alto em cada camada L está no formato 6 * (L * (L - 1) * (L - 2) ...) ou C = 6 * (L 2 + L) / 2 , onde C é o número de célula "global". Ao embaralhar as coisas, obtemos L 2 + L - C / 3 = 0, o que fornece flashbacks de matemática do ensino médio. A partir disso, obtemos a fórmula ceil (sqrt (1/4 + C / 3) + 0,5). Ao conectar um índice global de células, recebemos em qual camada a célula está.

Como a primeira célula de cada camada é naturalmente uma mais alta que a mais alta da camada anterior, encontramos L start = (6 * (L - 1) 2 + (L - 1)) / 2, o que simplifica para 3 * (L 2 - L). A partir disso, obtemos o índice de camada L index = C - L start .

Em seguida, vemos que cada camada é composta por seis seções, cada uma com comprimento L. Começando no nordeste e indo no sentido anti-horário, vemos que nas duas primeiras seções (1 <= L index <= 2 * L) , obtemos a coluna de L - L índice . A próxima seção L * 2 <L index <= L * 3 possui todas as células que compartilham uma única coluna -L. As duas próximas seções são L * 3 <L índice <= L * 5 com suas colunas de acordo com o índice L - L * 4. E, por fim, a sexta seção tem todas as células na coluna L. Podemos mudar os limites superiores um passo adiante para salvar alguns bytes no código.

Então e as linhas? Para reutilizar o código, giramos a grade para que a célula 44 fique reta. Em seguida, executamos a mesma lógica das colunas, mas desta vez chamamos os resultados de "linhas". É claro que, em vez de realmente virar uma grade, apenas andamos 1/6 de volta em volta dela.

gastropner
fonte
@PeterTaylor Boa captura, obrigado!
Gastropner
1

Python 3, 150 bytes

def h(a,b):
 L=[];i=1
 while len(L)<a+b:r=sum((i*[1j**(k/3)]for k in range(4,16,2)),[]);r[0]+=1;L+=r;i+=1
 return.9<abs(sum(L[min(a,b):max(a,b)]))<1.1

Minha solução segue basicamente a mesma linha de pensamento que a de Luis Mendo acima. Se escrito mais legível, o código é bastante auto-explicativo:

def h(a,b):
    L=[]
    i=1
    while len(L)<a+b:
        l=sum((i*[1j**(k/3)]for k in range(4,16,2)),[])
        l[0]+=1
        L+=l
        i+=1
return .9<abs(sum(L[min(a,b):max(a,b)]))<1.1
  1. A função hfaz o seguinte:
  2. A lista L conterá as posições (complexas) de cada número.
  3. i é o número do toque.
  4. No loop while, um novo anel é adicionado a cada iteração. Em vez de descobrir quantos anéis precisamos, continuamos a construir a lista até que ela seja longa o suficiente para conter a + b, e certamente é longa o suficiente para conter qualquer um deles.
  5. a 'lista de anéis' lé uma concatenação de 6 listas de len (i) vezes o vetor escalonado, onde o vetor escalonado é de 1j ** (2/3) a alguma potência. O intervalo não começa em 0, mas em 4, o que causa uma rotação de toda a grade. Isso me permite fazer:
  6. l[0]+=1 na linha 6, que é a etapa de um toque para o próximo.
  7. L+=l concatena a lista completa e a lista de toques.
  8. A lista L contém apenas vetores de etapas, que ainda precisam ser somados (integrados) para obter uma posição. Uma característica interessante aqui é que podemos somar a fatia do número mais baixo para o mais alto para obter a distância! Devido a erros de arredondamento, o resultado não será exatamente 1, portanto, o .9 <... <1.1. Curiosamente, o caso zero h(0,0)ou h (0,1) é tratado implicitamente, porque a soma de uma lista vazia é zero. Se eu pudesse ter certeza de que a<b, ou seja, os argumentos viriam em ordem crescente, eu poderia cortar outros 14 bytes substituindo L[min(a,b):max(a,b)]por L[a:b], mas infelizmente!

PS: Eu não sabia que esse era um desafio tão antigo, apareceu no topo há alguns dias e continuou me incomodando desde :)

Hermen
fonte
Esta é uma ótima resposta! Não se preocupe com a resposta tardia, não temos realmente nenhum problema com isso aqui no PPCG.
Rɪᴋᴇʀ
0

Mathematica, 111 105 104 bytes

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&

Explicação:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&define uma função rque recebe entrada #e calcula a distância (em número de células) para a célula 0. Faz isso explorando o padrão nas últimas células de cada distância / anel: 0 = 3 (0 ^ 2 + 0), 6 = 3 (1 ^ 2 + 1), 18 = 3 (2 ^ 2 + 2), 36 = 3 (3 ^ 2 + 3), ... e invertendo a fórmula para esse padrão. Observe que para a célula 0, na verdade, é usado o piso de (1/2) + i * (sqrt (3) / 6), que calcula em componentes para obter 0 + 0 * i = 0.

Com rdefinido, r@#é o anel para célula #(dentro da definição de outra função). #+3r@#-3(r@#)^2&não aparece exatamente no código, mas pega o número de uma célula e subtrai o número mais alto de uma célula no próximo anel interno, para que ele responda à pergunta "qual célula do anel atual é essa?" Por exemplo, a célula 9 é a terceira célula do anel 2; portanto r[9], a saída 2 e a #+3r@#-3(r@#)^2&[9]saída 3.

O que podemos fazer com a função acima é usá-la para encontrar o ângulo polar , no sentido anti-horário, do raio "célula 0, célula 17, célula 58" para a célula em questão. A última célula de cada anel está sempre em um ângulo Pi / 6 e contornamos um anel em incrementos de Pi / (3 * número do anel). Portanto, em teoria, precisamos calcular algo como Pi / 6 + (qual_cell_of_the_current_ring) * Pi / (3 * ring_number). No entanto, a rotação da imagem não afeta nada, portanto podemos descartar a parte Pi / 6 (para economizar 6 bytes). Combinando isso com a fórmula anterior e simplificando, obtemosPi(#/(3r@#)+1-r@#)&

Infelizmente, isso não é definido para a célula 0, pois seu número de toque é 0, por isso precisamos contornar isso. Uma solução natural seria algo parecido t=If[#==0,0,Pi(#/(3r@#)+1-r@#)]&. Mas como não nos importamos com o ângulo da célula 0 e, como r@#é repetida, podemos salvar um byte aqui comt=Limit[Pi(#/(3x)+1-x),x->r@#]&

Agora que temos o número do anel e o ângulo, podemos encontrar a posição de uma célula (centro) para testar a adjacência. Encontrar a posição real é irritante porque os anéis são hexagonais, mas podemos simplesmente fingir que os anéis são círculos perfeitos, para que tratemos o número do anel como a distância do centro da célula 0. Isso não será um problema, pois a aproximação é bastante Fechar. Usando a forma polar de um número complexo , podemos representar esta posição aproximada no plano complexo com uma função simples:p = r@#*Exp[I*t@#] &;

A distância entre dois números complexos no plano complexo é dada pelo valor absoluto de sua diferença, e então podemos arredondar o resultado para resolver quaisquer erros da aproximação e verificar se isso é igual a 1. A função que finalmente este trabalho não tem nome, mas é Round@Abs[p@#-p@#2]==1&.


Você pode experimentá-lo on-line na caixa de proteção Wolfram Cloud colando código como o seguinte e clicando em Equipamento -> "Avaliar célula" ou pressionando Shift + Enter ou o teclado numérico Enter:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&[24,45]

Ou para todos os casos de teste:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&//MapThread[#,Transpose[{{0,1},{7,18},{8,22},{24,45},{40,64},{64,65},{6,57},{29,90},{21,38},{38,60},{40,63},{41,39},{40,40}}]]&
Mark S.
fonte