Koła do pakowania

21

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

wprowadź opis zdjęcia tutaj

( Ź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:

wprowadź opis zdjęcia tutaj

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.

wprowadź opis zdjęcia tutaj

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

El'endia Starman
źródło
3
Czekam na Hexagony, stawiam. ; D
Addison Crump
@VoteToClose: Nie sądzę, że Hexagony ma wyjście graficzne, ale MAN, to byłoby niesamowite!
El'endia Starman
@ El'endiaStarman dobrze, mógłby napisać SVG do stdout, ale nie sądzę, mam zamiar ...: P
Martin Ender
1
Wow, nikt wcześniej nie podziękował mi śmiało za moje komentarze w piaskownicy. Rumienię się :-D Oczywiście skomentowałem, ponieważ spodobało mi się to wyzwanie, choć nie jestem pewien, czy będę miał czas, aby na nie odpowiedzieć.
Level River St,
Według mojej dyskusji z Reto Koradi na temat odpowiedzi user81655, myślę, że największy sześciokąt, który zobaczymy z ostrymi narożnikami, ma długość boczną 7d (8 kół). To łącznie N = 169 kół. Możesz rozważyć ograniczenie problemu do tej liczby, co dałoby większe szanse na uzyskanie poprawnej odpowiedzi (obecnie nie ma żadnych) i możliwości sprawdzenia. Z drugiej strony bardziej interesujące może być pozostawienie problemu otwartemu dla arbitralnego N.
Level River St

Odpowiedzi:

4

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.

dyski


DavidC
źródło
1
Jak wspomniałem w odpowiedzi użytkownika 81655, wystający pojedynczy okrąg na 22 (i 17, 25, 28, 31, 34) byłby lepiej umieszczony na środku rzędu kół, na którym siedzi.
Level River St
Tak też myślałem, ale zauważyłem, że 9, która również ma wystający okrąg, zostało uznane za prawidłowe. Kiedy będę miał trochę czasu, porównam wymiary wypukłych kadłubów (centrów).
DavidC
na 9 wystający okrąg ma albo 1/4, albo 3/4 wzdłuż płaskiego rzędu, więc nie ma znaczenia. w 17, 22, 25, 28, 31 wystający okrąg ma 1/6, 3/6 lub 5/6 wzdłuż, więc środkowa pozycja jest lepsza (pomyśl o pociągnięciu sznurka na bok: łatwiej jest ciągnąć od środka, ponieważ to sposób, w jaki struna ma mniejszą długość do zrobienia. W 34 (i 35) mamy 1/8, 3/8, 5/8 i 7/8 wzdłuż płaskiej strony. Więc dla tych powinniśmy wybrać 3/8 i 5/8 przed 1/8 i 7/8
Level River St
Masz absolutną rację, co potwierdzają pomiary.
DavidC
To jest niesamowite! Przejście 30-> 31 pokazuje, że nie możemy po prostu przyjąć poprzedniego kształtu i dodać koła na zewnątrz (dałoby to obwód 16.464). Jest też co najmniej jeden przypadek, w którym można dodać jeden okrąg do na zewnątrz, ale wybrał inny układ: 12-> 13
Level River St