Mira esta imagen. Específicamente, en cómo están dispuestos los agujeros en los extremos.

^{( Fuente de la imagen )}

Observe cómo las tuberías en esta imagen se empaquetan en un patrón hexagonal. Se sabe que en 2D, una red hexagonal es el paquete de círculos más denso. En este desafío, nos centraremos en minimizar el perímetro de un paquete de círculos. Una forma útil de visualizar el perímetro es imaginarse colocando una banda elástica alrededor de la colección de círculos.

La tarea

Dado un entero positivo ncomo entrada, muestre una colección de ncírculos empaquetados lo más ajustados posible.

Reglas y aclaraciones

• Suponga que los círculos tienen un diámetro de 1 unidad.
• La variable a minimizar es la longitud del perímetro, que se define como el casco convexo de los centros de los círculos en el grupo. Mira esta imagen:

Los tres círculos en línea recta tienen un perímetro de 4 (el casco convexo es un rectángulo de 2x0, y el 2 se cuenta dos veces), los dispuestos en un ángulo de 120 grados tienen un perímetro de aproximadamente 3,85 y el triángulo tiene un perímetro de solo 3 unidades. Tenga en cuenta que estoy ignorando las unidades pi adicionales que el perímetro real sería porque solo estoy mirando los centros de los círculos, no sus bordes.

• Puede haber (y casi con seguridad habrá) múltiples soluciones para cualquier cosa n. Puede enviar cualquiera de estos a su discreción. La orientación no importa.
• Los círculos deben estar en una red hexagonal.
• Los círculos deben tener al menos 10 píxeles de diámetro y pueden estar rellenos o no.
• Puede escribir un programa o una función.
• La entrada puede tomarse a través de STDIN, como un argumento de función, o su equivalente más cercano.
• La salida puede mostrarse o enviarse a un archivo.

Ejemplos

A continuación tengo ejemplos de salidas válidas e inválidas para n del 1 al 10 (ejemplos válidos solo para los primeros cinco). Los ejemplos válidos están a la izquierda; cada ejemplo a la derecha tiene un perímetro mayor que el correspondiente ejemplo válido.

Muchas gracias a steveverrill por ayudarme a escribir este desafío. Feliz embalaje!

Mathematica 295 950 bytes

Nota: Esta versión aún por jugar al golf aborda los problemas planteados por Steve Merrill con respecto a mis intentos anteriores.

Aunque es una mejora con respecto a la primera versión, no encontrará la configuración de manillar más densa donde uno buscaría una forma general circular, en lugar de hexagonal.

Encuentra soluciones construyendo un hexágono interno completo (para n> = 6, y luego examina todas las configuraciones para completar la capa externa con los círculos restantes.

Curiosamente, como señaló Steve Merrill en los comentarios, la solución para n+1círculos no siempre consiste en la solución para n círculos con otro círculo agregado. Compare la solución dada para 30 círculos con la solución dada para 31 círculos. (Nota: hay una solución única 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]]]

Algunas de las verificaciones implicaron comparaciones de más de cien mil casos para un solo valor de n (incluidas las simetrías). Tomó aproximadamente 5 minutos ejecutar el total de 34 casos de prueba. No hace falta decir que con un n'senfoque más amplio de fuerza bruta pronto resultaría poco práctico. Es seguro que existen enfoques más eficientes.

Los números a la derecha de cada embalaje son los perímetros de los respectivos cascos convexos azules. A continuación se muestra la salida para 3 < n < 35. Los círculos rojos son los que se agregan alrededor de un hexágono regular.