Spójrz na to zdjęcie. W szczególności, w jaki sposób rozmieszczone są otwory na końcach.

^{( Źródło obrazu )}

Zauważ, jak rury na tym obrazie są upakowane w sześciokątny wzór. Wiadomo, że w 2D sieć sześciokątna jest najgęstszym upakowaniem kół. W tym wyzwaniu skupimy się na zminimalizowaniu obwodu wypełnienia kół. Jednym z przydatnych sposobów wizualizacji obwodu jest wyobrażenie sobie zakładania gumki wokół kolekcji kół.

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą njako dane wejściowe, pokaż kolekcję nkręgów spakowanych tak ciasno, jak to możliwe.

Zasady i wyjaśnienia

• Załóżmy, że koła mają średnicę 1 jednostki.
• Zmienna być zminimalizowane jest długość obwodu, który jest zdefiniowany jako kadłub wypukła z ośrodków z kręgów w grupie. Spójrz na ten obraz:

Trzy okręgi w linii prostej mają obwód 4 (wypukły kadłub to prostokąt 2x0, a 2 jest liczony dwukrotnie), te ustawione pod kątem 120 stopni mają obwód około 3,85, a trójkąt ma obwód tylko 3 jednostki. Zauważ, że ignoruję dodatkowe jednostki pi, którymi byłby rzeczywisty obwód, ponieważ patrzę tylko na środki okręgów, a nie na ich krawędzie.

• Może istnieć (i prawie na pewno będzie) wiele rozwiązań dla każdego n. Możesz wydać dowolne z nich według własnego uznania. Orientacja nie ma znaczenia.
• Kręgi muszą znajdować się na siatce sześciokątnej.
• Koła muszą mieć co najmniej 10 pikseli średnicy i mogą być wypełnione lub nie.
• Możesz napisać program lub funkcję.
• Dane wejściowe mogą być pobierane przez STDIN, jako argument funkcji lub najbliższy odpowiednik.
• Dane wyjściowe mogą być wyświetlane lub w postaci pliku.

Przykłady

Poniżej mam przykładowe prawidłowe i nieprawidłowe dane wyjściowe dla n od 1 do 10 (prawidłowe przykłady tylko dla pierwszych pięciu). Prawidłowe przykłady znajdują się po lewej stronie; każdy przykład po prawej stronie ma większy obwód niż odpowiadający mu prawidłowy przykład.

Ogromne podziękowania dla Steveverrill za pomoc w napisaniu tego wyzwania. Miłego pakowania!

Mathematica 295 950 bajtów

Uwaga: Ta wersja do gry w golfa rozwiązuje problemy poruszone przez Steve'a Merrilla dotyczące moich wcześniejszych prób.

Chociaż jest to ulepszenie w stosunku do pierwszej wersji, nie znajdzie najgęstszej konfiguracji uchwytu, w której można by poszukiwać okrągłego, a nie sześciokątnego, ogólnego kształtu.

Znajduje rozwiązania, budując pełny wewnętrzny sześciokąt (dla n> = 6, a następnie sprawdza wszystkie konfiguracje do ukończenia zewnętrznej powłoki z pozostałymi okręgami.

Co ciekawe, jak zauważył Steve Merrill w komentarzach, rozwiązanie dla n+1kręgów nie zawsze składa się z rozwiązania dla n kręgów z dodanym innym kręgiem. Porównaj podane rozwiązanie dla 30 kręgów z danym rozwiązaniem dla 31 kręgów. (Uwaga: istnieje unikalne rozwiązanie dla 30 kręgów).

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

Niektóre kontrole obejmowały porównania ponad stu tysięcy przypadków dla pojedynczej wartości n (w tym symetrii). Przeprowadzenie łącznie 34 przypadków testowych zajęło około 5 minut. Nie trzeba dodawać, że przy większym n'spodejściu brutalna siła wkrótce okaże się niepraktyczna. Z pewnością istnieją bardziej wydajne podejścia.

Liczby po prawej stronie każdego opakowania są obwodami odpowiednich niebieskich wypukłych kadłubów. Poniżej znajduje się wynik dla 3 < n < 35. Czerwone kółka to te dodane wokół zwykłego sześciokąta.