Упаковочные круги

21

Посмотрите на это изображение. В частности, как расположены отверстия на концах.

введите описание изображения здесь

( Источник изображения )

Обратите внимание, как трубы на этом изображении упакованы в шестиугольную форму. Известно, что в 2D гексагональная решетка является самой плотной упаковкой окружностей. В этой задаче мы сосредоточимся на минимизации периметра упаковки кругов. Один из полезных способов визуализации периметра состоит в том, чтобы наложить круг вокруг круглой резинки.

Задание

Учитывая положительное целое число в nкачестве входных данных, покажите коллекцию nокружностей, упакованных как можно плотнее.

Правила и разъяснения

  • Предположим, что круги имеют диаметр 1 единицу.
  • Переменная быть сведена к минимуму длина периметра, который определен , чтобы быть выпуклой оболочкой из центров окружностей в группе. Посмотрите на это изображение:

введите описание изображения здесь

Три круга по прямой линии имеют периметр 4 (выпуклый корпус представляет собой прямоугольник 2x0, а число 2 считается дважды), те, которые расположены под углом 120 градусов, имеют периметр около 3,85, а треугольник имеет периметр всего 3 единицы. Обратите внимание, что я игнорирую дополнительные единицы пи, которыми будет фактический периметр, потому что я смотрю только на центры окружностей, а не на их края.

  • Там может (и почти наверняка будет) несколько решений для любого данного n. Вы можете вывести любой из них по своему усмотрению. Ориентация не имеет значения.
  • Круги должны быть на гексагональной решетке.
  • Круги должны быть не менее 10 пикселей в диаметре и могут быть заполнены или нет.
  • Вы можете написать либо программу, либо функцию.
  • Ввод может быть взят через STDIN, в качестве аргумента функции или ближайшего аналога.
  • Вывод может отображаться или выводиться в файл.

Примеры

Ниже приведен пример допустимых и недействительных выходов для n от 1 до 10 (допустимые примеры только для первых пяти). Действительные примеры слева; каждый пример справа имеет больший периметр, чем соответствующий действительный пример.

введите описание изображения здесь

Большое спасибо Steveverrill за помощь в написании этой задачи. Удачной упаковки!

Эльендия Старман
источник
3
Жду на гексагонии, держу пари. ; D
Эддисон Крамп
@VoteToClose: я не думаю, что у Hexagony есть графический вывод, но MAN, это было бы здорово!
El'endia Starman
@ El'endiaStarman Ну, вы могли бы написать SVG для stdout, но я не думаю, что я собираюсь ...: P
Мартин Эндер
1
Ничего себе, никто не поблагодарил меня жирным шрифтом за мои комментарии в песочнице. Я краснею :-D Конечно, я прокомментировал, потому что мне понравился вызов, хотя я не уверен, что у меня будет время, чтобы ответить на него.
Уровень Река St
В моем разговоре с Рето Коради об ответе пользователя 81655 я думаю, что самый большой шестиугольник, который мы увидим с острыми углами, - это длина стороны 7d (8 кругов). Это всего N = 169 кругов. Вы можете рассмотреть возможность ограничения проблемы до этого числа, что даст больше шансов получить правильный ответ (в настоящее время его нет) и возможность проверить. С другой стороны, может быть интереснее оставить проблему открытой для произвольного N.
Уровень River St

Ответы:

4

Mathematica 295 950 байт

Примечание. В этой версии, которая еще только для игры в гольф, рассматриваются проблемы, поднятые Стивом Мерриллом в связи с моими более ранними попытками.

Хотя это и является улучшением по сравнению с первой версией, он не найдет наиболее плотную конфигурацию рукоятки, где можно было бы искать круглую, а не шестиугольную общую форму.

Он находит решения путем построения полного внутреннего шестиугольника (для n> = 6, а затем проверяет все конфигурации для завершения внешней оболочки с оставшимися кругами.

Интересно, что, как отметил Стив Меррилл в комментариях, решение для n+1кругов не всегда состоит из решения для n кругов с добавлением еще одного круга. Сравните данное решение для 30 кругов с данным решением для 31 кругов. (Примечание: существует уникальное решение для 30 кругов.)

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

Некоторые проверки повлекли за собой сравнение более ста тысяч случаев для одного значения n (включая симметрии). Потребовалось приблизительно 5 минут, чтобы выполнить всего 34 тестовых случая. Само собой разумеется, что при более широком n'sподходе этот метод грубой силы вскоре окажется непрактичным. Существуют более эффективные подходы.

Цифры справа от каждой упаковки являются периметрами соответствующих синих выпуклых корпусов. Ниже вывод для 3 < n < 35. Красные круги - это те, которые добавляются вокруг правильного шестиугольника.

диски


DavidC
источник
1
Как я упоминал в ответе пользователя 81655, выступающий одиночный круг 22 (и 17, 25, 28, 31, 34) был бы лучше размещен в середине ряда кругов, на которых он сидит.
Уровень Река St
Я тоже так думал, но потом я заметил, что 9, который также имеет выступающий круг, считался правильным. Когда у меня будет время, я сравню размеры выпуклых оболочек (центров).
DavidC
в 9 выступающий круг равен 1/4 или 3/4 вдоль плоского ряда, так что это не имеет значения. в 17, 22, 25, 28, 31 выступающий круг составляет 1/6, 3/6 или 5/6 вдоль, поэтому среднее положение лучше (подумайте о том, чтобы натянуть струну вбок: легче потянуть за середину, потому что это таким образом, строка имеет меньшее расширение. В 34 (и 35) у нас есть 1/8, 3/8, 5/8 и 7/8 вдоль плоской стороны. Поэтому для них мы должны выбрать 3/8 и 5/8 до 1/8 и 7/8.
Уровень Река St
Вы абсолютно правы, и это подтверждается измерениями.
DavidC
Это круто! Переход 30-> 31 показывает, что мы не можем просто взять предыдущую фигуру и добавить окружность снаружи (это дало бы периметр 16.464). Есть также по крайней мере один случай, когда вы могли бы просто добавить один кружок к снаружи, но выбрал другое расположение: 12-> 13
Level River St