Verpackungskreise

21

Schauen Sie sich dieses Bild an. Insbesondere, wie die Löcher an den Enden angeordnet sind.

Bildbeschreibung hier eingeben

( Bildquelle )

Beachten Sie, wie die Rohre in diesem Bild in einem sechseckigen Muster gepackt sind. Es ist bekannt, dass in 2D ein hexagonales Gitter die dichteste Packung von Kreisen ist. Bei dieser Herausforderung werden wir uns darauf konzentrieren, den Umfang einer Packung von Kreisen zu minimieren. Ein nützlicher Weg, um den Umfang zu visualisieren, besteht darin, sich vorzustellen, ein Gummiband um die Sammlung von Kreisen zu legen.

Die Aufgabe

nZeigen Sie bei einer positiven Ganzzahl als Eingabe eine Sammlung von nKreisen, die so eng wie möglich gepackt sind.

Regeln und Erläuterungen

  • Angenommen, Kreise haben einen Durchmesser von 1 Einheit.
  • Die zu minimierende Variable ist die Länge des Umfangs, die als konvexe Hülle der Zentren der Kreise in der Gruppe definiert ist. Schauen Sie sich dieses Bild an:

Bildbeschreibung hier eingeben

Die drei Kreise in einer geraden Linie haben einen Umfang von 4 (die konvexe Hülle ist ein 2x0-Rechteck und die 2 wird zweimal gezählt), die in einem Winkel von 120 Grad angeordneten Kreise haben einen Umfang von etwa 3,85 und das Dreieck hat einen Umfang von nur 3 Einheiten. Beachten Sie, dass ich die zusätzlichen pi-Einheiten ignoriere, die der tatsächliche Umfang darstellen würde, da ich nur die Zentren der Kreise und nicht deren Kanten betrachte.

  • Es kann (und wird mit ziemlicher Sicherheit) mehrere Lösungen für jede gegebene geben n. Sie können diese nach eigenem Ermessen ausgeben. Orientierung spielt keine Rolle.
  • Die Kreise müssen sich auf einem sechseckigen Gitter befinden.
  • Die Kreise müssen mindestens 10 Pixel im Durchmesser haben und dürfen gefüllt sein oder nicht.
  • Sie können entweder ein Programm oder eine Funktion schreiben.
  • Die Eingabe kann über STDIN als Funktionsargument oder über das nächste Äquivalent erfolgen.
  • Die Ausgabe kann angezeigt oder in eine Datei ausgegeben werden.

Beispiele

Unten habe ich Beispiele für gültige und ungültige Ausgaben für n von 1 bis 10 (gültige Beispiele nur für die ersten fünf). Die gültigen Beispiele finden Sie links. Jedes Beispiel auf der rechten Seite hat einen größeren Umfang als das entsprechende gültige Beispiel.

Bildbeschreibung hier eingeben

Vielen Dank an steveverrill für die Hilfe beim Schreiben dieser Herausforderung. Viel Spaß beim Packen!

El'endia Starman
quelle
3
Ich warte auf Hexagony und wette. ; D
Addison Crump
@VoteToClose: Ich denke nicht, dass Hexagony eine grafische Ausgabe hat, aber MAN, das wäre großartig!
El'endia Starman
@ El'endiaStarman Nun, man könnte ein SVG stdout schreiben, aber ich glaube nicht , ich werde ...: P
Martin Ender
1
Wow, niemand hat mir in Fettdruck für meine Kommentare im Sandkasten gedankt. Ich erröte :-D Natürlich habe ich kommentiert, weil mir die Herausforderung gefallen hat, obwohl ich nicht sicher bin, ob ich Zeit habe, sie zu beantworten.
Level River St
Laut meiner Diskussion mit Reto Koradi über die Antwort von user81655 ist das größte Sechseck, das wir mit scharfen Ecken sehen werden, die Seitenlänge 7d (8 Kreise). Das sind N = 169 Kreise insgesamt. Sie könnten erwägen, das Problem auf diese Nummer zu beschränken, um eine korrekte Antwort zu erhalten (derzeit gibt es keine) und zu überprüfen. Auf der anderen Seite ist es vielleicht interessanter, das Problem willkürlich N.
Level River St

Antworten:

4

Mathematica 295 950 Bytes

Hinweis: Diese noch zu spielende Version befasst sich mit Problemen, die Steve Merrill in Bezug auf meine früheren Versuche angesprochen hat.

Obwohl es eine Verbesserung gegenüber der ersten Version ist, wird es nicht die dichteste Griffkonfiguration finden, bei der man eher eine kreisförmige als eine sechseckige Gesamtform anstreben würde.

Es wird eine Lösung gefunden, indem ein vollständiges inneres Sechseck (für n> = 6) erstellt und anschließend alle Konfigurationen zur Vervollständigung der äußeren Hülle mit den verbleibenden Kreisen untersucht werden.

Interessanterweise besteht, wie Steve Merrill in den Kommentaren feststellte, die Lösung für n+1Kreise nicht immer aus der Lösung für n Kreise mit einem weiteren Kreis. Vergleichen Sie die angegebene Lösung für 30 Kreise mit der angegebenen Lösung für 31 Kreise. (Hinweis: Es gibt eine eindeutige Lösung für 30 Kreise.)

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

Einige der Überprüfungen umfassten Vergleiche von über einhunderttausend Fällen für einen einzelnen Wert von n (einschließlich Symmetrien). Es dauerte ungefähr 5 Minuten, um die insgesamt 34 Testfälle auszuführen. Es erübrigt sich zu erwähnen, dass sich n'sdieser Brute-Force-Ansatz bei größerem Umfang bald als unpraktisch erweisen würde. Effizientere Ansätze sind mit Sicherheit vorhanden.

Die Zahlen rechts von jeder Packung sind die Umfänge der jeweiligen blauen konvexen Rümpfe. Unten ist die Ausgabe für 3 < n < 35. Die roten Kreise sind die, die um ein reguläres Sechseck hinzugefügt werden.

Festplatten


DavidC
quelle
1
Wie ich in der Antwort von Benutzer 81655 erwähnt habe, ist der hervorstehende Einzelkreis auf 22 (und 17, 25, 28, 31, 34) besser in der Mitte der Kreisreihe platziert, auf der er sitzt.
Level River St
Das habe ich auch gedacht, aber dann habe ich festgestellt, dass 9, die ebenfalls einen hervorstehenden Kreis hat, als richtig angesehen wurde. Wenn ich etwas Zeit habe, vergleiche ich die Maße der konvexen Hüllen (der Mitten).
DavidC
in 9 ist der hervorstehende Kreis entweder 1/4 oder 3/4 entlang der flachen Reihe, so dass es keinen Unterschied macht. in 17, 22, 25, 28, 31 ist der hervorstehende Kreis 1/6, 3/6 oder 5/6 entlang, daher ist die mittlere Position besser (denken Sie daran, eine Schnur seitwärts zu ziehen: es ist einfacher, aus der Mitte heraus zu ziehen, weil das so ist In 34 (und 35) haben wir 1/8, 3/8, 5/8 und 7/8 entlang der flachen Seite, also sollten wir für diese 3/8 und 5/8 wählen vor dem 08.01. und dem 08.07.
Level River St
Sie haben vollkommen recht und dies wird durch Messungen bestätigt.
DavidC
Das ist fantastisch! Der Übergang 30-> 31 zeigt, dass wir nicht einfach die vorherige Form annehmen und einen Kreis nach außen hinzufügen können (das hätte einen Umfang von 16,464 ergeben.) Es gibt auch mindestens einen Fall, in dem Sie nur einen Kreis hinzufügen hätten können die Außenseite, aber wählte eine andere Anordnung: 12-> 13
Level River St