21
\$\begingroup\$

Take a look at this image. Specifically, at how the holes on the ends are arranged.

enter image description here

(Image source)

Notice how the pipes in this image are packed in a hexagonal pattern. It is known that in 2D, a hexagonal lattice is the densest packing of circles. In this challenge, we will be focusing on minimizing the perimeter of a packing of circles. One useful way to visualize the perimeter is to imagine putting a rubber band around the collection of circles.

The Task

Given a positive integer n as input, show a collection of n circles packed as tightly as possible.

Rules and Clarifications

  • Assume circles have a diameter of 1 unit.
  • The variable to be minimized is the length of the perimeter, which is defined to be the convex hull of the centers of the circles in the group. Take a look at this image:

enter image description here

The three circles in a straight line have a perimeter of 4 (the convex hull is a 2x0 rectangle, and the 2 is counted twice), those arranged in a 120-degree angle have a perimeter of about 3.85, and the triangle has a perimeter of only 3 units. Note that I am ignoring the additional pi units that the actual perimeter would be because I'm only looking at the circles' centers, not their edges.

  • There may (and almost certainly will be) multiple solutions for any given n. You may output any of these at your discretion. Orientation does not matter.
  • The circles must be on a hexagonal lattice.
  • The circles must be at least 10 pixels in diameter, and may be filled or not.
  • You may write either a program or a function.
  • Input may be taken through STDIN, as a function argument, or closest equivalent.
  • The output may be displayed or output to a file.

Examples

Below I have example valid and invalid outputs for n from 1 to 10 (valid examples only for the first five). The valid examples are on the left; every example on the right has a greater perimeter than the corresponding valid example.

enter image description here

Much thanks to steveverrill for help with writing this challenge. Happy packing!

\$\endgroup\$
  • 3
    \$\begingroup\$ Waiting on Hexagony, I'm betting. ;D \$\endgroup\$ – Addison Crump Nov 22 '15 at 22:12
  • \$\begingroup\$ @VoteToClose: I don't think Hexagony has graphical output, but MAN, that'd be awesome! \$\endgroup\$ – El'endia Starman Nov 22 '15 at 23:09
  • \$\begingroup\$ @El'endiaStarman Well, you could write an SVG to stdout, but I don't think I'm going to... :P \$\endgroup\$ – Martin Ender Nov 23 '15 at 9:57
  • 1
    \$\begingroup\$ Wow, no-one has thanked me in bold for my comments in the sandbox before. I'm blushing :-D Of course I commented because I liked the challenge, though I'm not sure if i'm going to have time to answer it. \$\endgroup\$ – Level River St Nov 23 '15 at 20:19
  • \$\begingroup\$ Per my discussion with Reto Koradi on user81655's answer, I think the largest hexagon we will see with sharp corners is sidelength 7d (8 circles.) That's N=169 circles total. You could consider restricting the problem to that number, which would give more chance of getting a correct answer (currently there aren't any) and of being able to check. On the other hand it may be more interesting to leave the problem open up to arbitrary N. \$\endgroup\$ – Level River St Nov 24 '15 at 8:34
4
\$\begingroup\$

Mathematica 295 950 bytes

Note: This still-to-be-golfed version addresses issues raised by Steve Merrill regarding my earlier attempts.

Although it is an improvement over the first version, it will not find the densest handle configuration where one would seek a circular, rather than hexagonal, overall shape.

It finds solutions by building a complete inner hexagon (for n>=6, and then examines all of the configurations for completing the outer shell with the remaining circles.

Interestingly, as Steve Merrill noted in the comments, the solution for n+1 circles does not always consist of the solution for n circles with another circle added on. Compare the given solution for 30 circles to the given solution for 31 circles. (Note: there is a unique solution for 30 circles.)

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

Some of the checks entailed comparisons of over one hundred thousand cases for a single value of n (including symmetries). It took approximately 5 minutes to run the total 34 test cases. Needless to say, with larger n's this brute-force approach would soon prove impractical. More efficient approaches are certain to exist.

The numbers to the right of each packing are the perimeters of the respective blue convex hulls. Below is the output for 3 < n < 35. The red circles are those added around a regular hexagon.

disks


\$\endgroup\$
  • 1
    \$\begingroup\$ As I mentioned on user 81655's answer, the protruding single circle on 22 (and 17, 25, 28, 31, 34) would be better placed at the middle of the row of circles on which it sits. \$\endgroup\$ – Level River St Nov 23 '15 at 23:01
  • \$\begingroup\$ I thought so also, but then I noted that 9, which also has a protruding circle was considered correct. When I have some time, I'll compare the measurements of the convex hulls (of the centers). \$\endgroup\$ – DavidC Nov 24 '15 at 1:05
  • \$\begingroup\$ in 9 the protruding circle is either 1/4 or 3/4 along the flat row, so it makes no difference. in 17, 22, 25, 28, 31 the protruding circle is 1/6, 3/6 or 5/6 along, so the middle position is better (think about pulling a string sideways: it's easier to pull from the middle because that way the string has less extension to do. In 34 (and 35) we have 1/8, 3/8, 5/8 and 7/8 along the flat side. So for these we should choose 3/8 and 5/8 before 1/8 and 7/8. \$\endgroup\$ – Level River St Nov 24 '15 at 1:19
  • \$\begingroup\$ You're absolutely right and this is confirmed by measurements. \$\endgroup\$ – DavidC Nov 24 '15 at 2:07
  • \$\begingroup\$ This is awesome! The transition 30->31 shows that we can't just take the previous shape and add a circle to the outside (that would have given a perimeter of 16.464.) There's also at least one case where you could have just added one circle to the outside, but chose a different arrangement: 12->13 \$\endgroup\$ – Level River St Nov 24 '15 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.