Jetez un oeil à cette image. Plus précisément, comment les trous sur les extrémités sont disposés.

^{( Source de l'image )}

Remarquez comment les tuyaux de cette image sont placés dans un motif hexagonal. On sait qu'en 2D, un réseau hexagonal est le plus dense des cercles. Dans ce défi, nous nous concentrerons sur la minimisation du périmètre d'un emballage de cercles. Une façon utile de visualiser le périmètre est d'imaginer mettre un élastique autour de la collection de cercles.

La tâche

Étant donné un entier positif nen entrée, montrez une collection de ncercles aussi serrés que possible.

Règles et clarifications

• Supposons que les cercles ont un diamètre de 1 unité.
• La variable à minimiser est la longueur du périmètre, qui est définie comme étant la coque convexe des centres des cercles du groupe. Jetez un oeil à cette image:

Les trois cercles en ligne droite ont un périmètre de 4 (la coque convexe est un rectangle 2x0 et les 2 sont comptés deux fois), ceux disposés selon un angle de 120 degrés ont un périmètre d'environ 3,85 et le triangle a un périmètre de seulement 3 unités. Notez que j'ignore les unités pi supplémentaires que serait le périmètre réel parce que je ne regarde que les centres des cercles, pas leurs bords.

• Il peut y avoir (et il y en aura presque certainement) de multiples solutions pour tout n. Vous pouvez produire n'importe lequel de ces éléments à votre discrétion. L'orientation n'a pas d'importance.
• Les cercles doivent être sur un réseau hexagonal.
• Les cercles doivent avoir au moins 10 pixels de diamètre et peuvent être remplis ou non.
• Vous pouvez écrire soit un programme soit une fonction.
• L'entrée peut être prise via STDIN, comme argument de fonction ou équivalent le plus proche.
• La sortie peut être affichée ou sortie dans un fichier.

Exemples

Ci-dessous, j'ai des exemples de sorties valides et invalides pour n de 1 à 10 (exemples valides uniquement pour les cinq premiers). Les exemples valides sont à gauche; chaque exemple à droite a un périmètre plus grand que l'exemple valide correspondant.

Un grand merci à steveverrill pour son aide à la rédaction de ce défi. Bon emballage!

Mathematica 295 950 octets

Remarque: Cette version encore à jouer résout les problèmes soulevés par Steve Merrill concernant mes tentatives précédentes.

Bien qu'il s'agisse d'une amélioration par rapport à la première version, il ne trouvera pas la configuration de poignée la plus dense où l'on chercherait une forme globale circulaire plutôt qu'hexagonale.

Il trouve des solutions en construisant un hexagone intérieur complet (pour n> = 6, puis examine toutes les configurations pour compléter la coque extérieure avec les cercles restants.

Fait intéressant, comme Steve Merrill l'a noté dans les commentaires, la solution pour les n+1cercles ne consiste pas toujours en la solution pour n cercles avec un autre cercle ajouté. Comparez la solution donnée pour 30 cercles à la solution donnée pour 31 cercles. (Remarque: il existe une solution unique pour 30 cercles.)

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

Certaines vérifications ont entraîné des comparaisons de plus de cent mille cas pour une seule valeur de n (y compris les symétries). Il a fallu environ 5 minutes pour exécuter les 34 cas de test au total. Inutile de dire qu'avec une n'sapproche plus large, cette approche par force brute se révélerait bientôt impossible. Il est certain que des approches plus efficaces existent.

Les nombres à droite de chaque emballage sont les périmètres des coques convexes bleues respectives. Ci-dessous la sortie pour 3 < n < 35. Les cercles rouges sont ceux ajoutés autour d'un hexagone régulier.