The five clowns

Computer Science Level 5

Five clowns are planning for a trip to Los Angeles .They have to pack their things,including their collection of circles. Each clown uses a rectangular box and packs his/her circles linearly so that each circle touches the bottom of the box.

The clowns wants to spend as little as they can on the boxes so they buy ones with the smallest possible size. Given below is the radii of the circles each clown needs to pack.

$80,50,31,19,56,38,87,21$ $85,69,22,28,2,84,82,83$ $31,77,40,75,48,99,45$ $5,55,22,33,07$ $12,23,97,42,9,15,50,21$

Find the width of the smallest rectangular box each clown needs to buy and input the sum of the widths of the five rectangles as the answer. (rounded DOWN to the nearest integer).

Details/Assumptions

Circles are arranged linearly and no circle is stacked on top of another.
Size refers to the width or horizontal length of the smallest possible rectangle.
Below is an example of an acceptable way of packing four circles,though it might not be the optimal way ;) .

Explicit examples

For three circles of radii $2,2,2$ the smallest possible size is $12$
For $1,2,3$ it is $11.293$
For $5,6$ it is $21.954$

The answer is 2914.

1 solution

Thaddeus Abiy
Jun 13, 2014

This problem is a bit tricky. Because there are cases that are not easily seen at a first glance.

For two circles with raddi $R$ and $r$ it is easy to find that the horizontal distance between their centers is $2 \sqrt{Rr}$ . So it is tempting to conclude that the minimum width of the box required to fit both of them in is $2\sqrt{Rr} + R + r$ . But this doesn't hold when the difference between the circles is large and the smaller circle is completely tucked under the larger one. In that case The minimum width would be the diameter of the larger circle.

Note also that order matters and we will have to compute the width for all permutations of the circles and find the minimum. This is not too bad as the most we would have to search is $8!=40320$ arrangements for a single list of circles.

To solve we just keep track of the center coordinates of the circles by placing the first one at $r$ . and recursively find the width. Then use pythons itertools module to find the permutation with the least size.

Python:

from math import *
from itertools import *
def Get_Distance( R , r): #HRzntl dist bn the centers of 2 circles
   return 2 * sqrt( R * r)

def Get_Width(Circles):
   C = [None]*len(Circles)
   Max=0
   if len(Circles)==1:
      return 2*Circles[0];
   C[0] = Circles[0]
   for i in range(0,len(Circles)):
      Max = 0
      for j in range(0,i):
         Max = max(Max,C[j]+Get_Distance(Circles[i],Circles[j]))
      C[i] = max(Circles[i],Max)
   Max = 0
   for i in range(0,len(Circles)):
      Max = max(Max,C[i]+Circles[i])
   return Max



def Get_Minimum_Width( Circles ):
   Minimum = 'infinity'
   for permutation in permutations(Circles):
      Width = Get_Width(permutation)
      if Width < Minimum:
         Minimum = Width
   return round(Minimum,3)

Packings = [
   [80,50,31,19,56,38,87,21],
[85,69,22,28,2,84,82,83],
[31,77,40,75,48,99,45],
[5,55,22,33,07],
[12,23,97,42,9,15,50,21] ]

Sum = 0
for clown in Packings:
   Sum += Get_Minimum_Width(clown)
print Sum

Thanks! I've updated the answer.

Calvin Lin Staff - 7 years ago

The five clowns

The answer is 2914.

1 solution

0 pending reports