Círculos de embalagem

21

Dê uma olhada nesta imagem. Especificamente, como os orifícios nas extremidades são organizados.

insira a descrição da imagem aqui

( Fonte da imagem )

Observe como os tubos nesta imagem são compactados em um padrão hexagonal. Sabe-se que em 2D, uma rede hexagonal é o empacotamento mais denso de círculos. Neste desafio, estaremos focados em minimizar o perímetro de uma embalagem de círculos. Uma maneira útil de visualizar o perímetro é imaginar colocar um elástico ao redor da coleção de círculos.

A tarefa

Dado um número inteiro positivo ncomo entrada, mostre uma coleção de ncírculos compactados o mais firmemente possível.

Regras e esclarecimentos

  • Suponha que os círculos tenham um diâmetro de 1 unidade.
  • A variável a ser minimizada é o comprimento do perímetro, definido como o casco convexo dos centros dos círculos no grupo. Veja esta imagem:

insira a descrição da imagem aqui

Os três círculos em uma linha reta têm um perímetro de 4 (o casco convexo é um retângulo 2x0 e o 2 é contado duas vezes), aqueles dispostos em um ângulo de 120 graus têm um perímetro de cerca de 3,85 e o triângulo tem um perímetro de apenas 3 unidades. Observe que estou ignorando as unidades pi adicionais que o perímetro real seria porque estou apenas olhando para os centros dos círculos, não para as bordas.

  • Pode (e quase certamente haverá) várias soluções para qualquer dado n. Você pode emitir qualquer uma dessas opções a seu critério. Orientação não importa.
  • Os círculos devem estar em uma estrutura hexagonal.
  • Os círculos devem ter pelo menos 10 pixels de diâmetro e podem ser preenchidos ou não.
  • Você pode escrever um programa ou uma função.
  • A entrada pode ser obtida através do STDIN, como argumento de função ou equivalente mais próximo.
  • A saída pode ser exibida ou em um arquivo.

Exemplos

Abaixo, tenho exemplos de saídas válidas e inválidas para n de 1 a 10 (exemplos válidos apenas para os cinco primeiros). Os exemplos válidos estão à esquerda; todo exemplo à direita tem um perímetro maior que o exemplo válido correspondente.

insira a descrição da imagem aqui

Muito obrigado a steveverrill pela ajuda na elaboração deste desafio. Embalagem feliz!

El'endia Starman
fonte
3
Esperando no Hexagony, estou apostando. ; D
Addison Crump
@VoteToClose: Eu não acho que o Hexagony tenha saída gráfica, mas MAN, isso seria incrível!
El'endia Starman 22/11/2015
@ El'endiaStarman Bem, você poderia escrever um SVG para stdout, mas eu não acho que eu vou ...: P
Martin Ender
11
Uau, ninguém me agradeceu em negrito pelos meus comentários na caixa de areia antes. Estou corando :-D É claro que comentei porque gostei do desafio, embora não tenha certeza se vou ter tempo para responder.
Level River St
De acordo com minha discussão com Reto Koradi sobre a resposta do usuário81655, acho que o maior hexágono que veremos com cantos afiados é o comprimento lateral 7d (8 círculos). Isso é N = 169 círculos no total. Você pode restringir o problema a esse número, o que daria mais chances de obter uma resposta correta (atualmente não há nenhuma) e de poder verificar. Por outro lado, pode ser mais interessante deixar o problema se aberto a N. arbitrária
Nível River St

Respostas:

4

Mathematica 295 950 bytes

Nota: Esta versão ainda por jogar aborda questões levantadas por Steve Merrill em relação às minhas tentativas anteriores.

Embora seja uma melhoria em relação à primeira versão, ela não encontrará a configuração de alça mais densa, na qual se procuraria uma forma geral circular, e não hexagonal.

Ele encontra soluções construindo um hexágono interno completo (para n> = 6 e, em seguida, examina todas as configurações para concluir o shell externo com os círculos restantes.

Curiosamente, como Steve Merrill observou nos comentários, a solução para n+1círculos nem sempre consiste na solução para n círculos com outro círculo adicionado. Compare a solução fornecida para 30 círculos com a solução fornecida para 31 círculos. (Nota: existe uma solução exclusiva para 30 círculos.)

m[pts_]:={Show[ConvexHullMesh[pts],Graphics[{Point/@pts,Circle[#,1/2]&/@ pts}], 
ImageSize->Tiny,PlotLabel->qRow[{Length[pts],"  circles"}]],
RegionMeasure[RegionBoundary[ConvexHullMesh[pts]]]};
nPoints = ((#+1)^3-#^3)&;pointsAtLevelJ[0] = {{0,0}};
pointsAtLevelJ[j_]:=RotateLeft@DeleteDuplicates@Flatten[Subdivide[#1, #2, j] &@@@
Partition[Append[(w=Table[j{Cos[k Pi/3],Sin[k Pi/3]},{k,0,5}]), 
w[[1]]], 2, 1], 1];nPointsAtLevelJ[j_] := Length[pointsAtLevelJ[j]]
getNPoints[n_] := Module[{level = 0, pts = {}},While[nPoints[level]<=n, 
pts=Join[pointsAtLevelJ[level],pts];level++];Join[Take[pointsAtLevelJ[level],n-Length[pts]],
pts]];ns={1,7,19,37,61,91};getLevel[n_]:=Position[Union@Append[ns,n],n][[1, 1]]-1;
getBaseN[n_] := ns[[getLevel[n]]];pack[1]=Graphics[{Point[{0,0}], Circle[{0, 0}, 1/2]}, 
ImageSize->Tiny];pack[n_]:=Quiet@Module[{base = getNPoints[getBaseN[n]], 
outerRing = pointsAtLevelJ[getLevel[n]], ss},ss=Subsets[outerRing,{n-getBaseN[n]}];
SortBy[m[Join[base,#]]&/@ss,Last][[1]]]

Algumas das verificações envolveram comparações de mais de cem mil casos para um valor único de n (incluindo simetrias). Demorou aproximadamente 5 minutos para executar o total de 34 casos de teste. Escusado será dizer que, com maior n'sessa abordagem de força bruta logo se mostraria impraticável. Certamente, existem abordagens mais eficientes.

Os números à direita de cada embalagem são os perímetros dos respectivos cascos azuis convexos. Abaixo está a saída para 3 < n < 35. Os círculos vermelhos são aqueles adicionados em torno de um hexágono regular.

discos


DavidC
fonte
11
Como mencionei na resposta do usuário 81655, o círculo único saliente em 22 (e 17, 25, 28, 31, 34) seria melhor colocado no meio da linha de círculos em que está assentado.
Level River St
Eu também pensava assim, mas depois notei que 9, que também tem um círculo saliente, era considerado correto. Quando tiver algum tempo, compararei as medidas dos cascos convexos (dos centros).
DavidC
em 9, o círculo saliente é 1/4 ou 3/4 ao longo da linha plana, portanto não faz diferença. em 17, 22, 25, 28, 31 o círculo saliente é 1/6, 3/6 ou 5/6, portanto a posição do meio é melhor (pense em puxar uma corda de lado: é mais fácil puxar do meio, porque isso A corda tem menos extensão. Em 34 (e 35) temos 1/8, 3/8, 5/8 e 7/8 no lado plano, portanto, para esses, devemos escolher 3/8 e 5/8 antes de 1/8 e 7/8
Level River St
Você está absolutamente certo e isso é confirmado por medidas.
DavidC
Isso é incrível! A transição 30-> 31 mostra que não podemos simplesmente pegar a forma anterior e adicionar um círculo para o exterior (isso daria um perímetro de 16.464.) Há também pelo menos um caso em que você poderia apenas adicionar um círculo ao do lado de fora, mas escolheu um arranjo diferente: 12-> 13
Level River St