Take a look at this image. Specifically, at how the holes on the ends are arranged.
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.
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:
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.
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.
Much thanks to steveverrill for help with writing this challenge. Happy packing!