From: Matthew D Moss <matthew.moss@...>
Date: 2008-02-15T22:19:55+09:00
Subject: [QUIZ] The Smallest Circle (#157)

The three rules of Ruby Quiz 2:

1.  Please do not post any solutions or spoiler discussion for this  
quiz until 48 hours have passed from the time on this message.

2.  Support Ruby Quiz 2 by submitting ideas as often as you can! (A  
permanent, new website is in the works for Ruby Quiz 2. Until then,  
please visit the temporary website at <http:// 
matthew.moss.googlepages.com/home>.

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem  
helps everyone
on Ruby Talk follow the discussion.  Please reply to the original  
quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- 
=-=-=-

The Smallest Circle
by Matthew Moss

Your task this week sounds simple enough, but may be more difficult  
than it first appears. Given a set of points on a plane, your goal is  
to find the smallest circle that encloses those points.

You are to provide a function, *encircle*, that takes an array of  
points and returns the smallest circle surrounding those points.  
Start with the following base code and extend as needed to solve the  
problem:

     class Point < Struct.new(:x, :y)
         def self.random
             Point.new(rand, rand)
         end

         def to_s
             "(#{x}, #{y})"
         end
     end

     class Circle < Struct.new(:center, :radius)
         def to_s
             "{center:#{center}, radius:#{radius}}"
         end
     end

     def encircle(points)        # takes array of Point objects
         # returns a Circle object
     end


I will be running several tests on the submitted solutions, with  
various point sets, to see how well they perform at this task. I  
recommend you you test your algorithm with a variety of sample sets,  
from small sets consisting of just 1-5 points, up to medium and  
larger sets, containing a few thousand points.

To generate an array of random points, start with the above code and  
add:

     def generate_samples(n)
         (1..n).map { Point.random }
     end


And then you may test your implementation like this:

     # encircle 10 random points
     puts encircle( generate_samples(10) )


As mentioned, this one may be more difficult than it seems. Feel free  
to estimate the smallest circle, if you get stuck on getting the  
exact solution.