- **Ruby**
(*http://www.velocityreviews.com/forums/f66-ruby.html*)

- - **[QUIZ] The Smallest Circle (#157)**
(*http://www.velocityreviews.com/forums/t848149-quiz-the-smallest-circle-157-a.html*)

[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. |

Re: [QUIZ] The Smallest Circle (#157)[Note: parts of this message were removed to make it a legal post.]
If one of the points is on the enclosing circle, is that a valid solution ? |

Re: [QUIZ] The Smallest Circle (#157)Horea Raducan wrote:
> If one of the points is on the enclosing circle, is that a valid solution ? > > I wouldn't care about such details : the points are defined by floating point coordinates : I'd say that defining a circle with a center and a radius in floating point which passes exactly through such points is most often impossible. There are obvious exceptions like circles with zero radius and some values where there's no approximation in the computations but these cases aren't likely to matter here. Lionel |

Re: The Smallest Circle (#157)On Feb 15, 1:06 pm, "Horea Raducan" <hradu...@gmail.com> wrote:
> If one of the points is on the enclosing circle, is that a valid solution ? Yes, points on the circle are considered enclosed. Which also means that for an input set of one point, your function should return a circle with that point as its center and a zero radius. |

Re: The Smallest Circle (#157)On Feb 15, 3:19 pm, Matthew D Moss <matthew.m...@gmail.com> wrote:
> > 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 May I propose a bit refined random method? class Point < Struct.new(:x, :y) def self.random Point.new(0.5 - rand, 0.5 - rand) end This should give us negative coordinates as well. :-) -- Cheers and welcome new quizmasters! Alex |

[Quiz] The Smallest Circle (#157)Interesting, the numbering is continuing from Ruby Quiz ?
Not starting at 1??? SUGGESTION: I don't have time to do this quiz, but it looks like fun. I for one would encourage anybody to do it with some visual representation! (suggested libs: RMagick, Gosu, Rubygame, Ruby/SDL, etc...) An audio representation could be interesting as well (perhaps a sort of sonar?) |

Re: [Quiz] The Smallest Circle (#157)On Feb 16, 2008 3:21 PM, John Joyce <dangerwillrobinsondanger@gmail.com> wrote:
> Interesting, the numbering is continuing from Ruby Quiz ? > Not starting at 1??? > > SUGGESTION: I don't have time to do this quiz, but it looks like fun. I also would love to do this one, but am on vacation :) I hope there's someone out there that supplies a multidimensional solution (something that gives the user a choice of the dimensional space; 3-D, 4-D, etc). > I for one would encourage anybody to do it with some visual > representation! (suggested libs: RMagick, Gosu, Rubygame, Ruby/SDL, > etc...) > An audio representation could be interesting as well (perhaps a sort > of sonar?) Those would be pretty interesting. Todd |

Re: The Smallest Circle (#157)> May I propose a bit refined random method?
> > =A0 =A0 =A0class Point < Struct.new(:x, :y) > =A0 =A0 =A0 =A0 =A0def self.random > =A0 =A0 =A0 =A0 =A0 =A0 =A0Point.new(0.5 - rand, 0.5 - rand) > =A0 =A0 =A0 =A0 =A0end > > This should give us negative coordinates as well. :-) Sure, but your algorithm should work with any set of random points, whether they fit in the unit square from 0 to 1, -0.5 to 0.5, or coordinates outside the unit square. |

Re: [Quiz] The Smallest Circle (#157)From: "John Joyce" <dangerwillrobinsondanger@gmail.com> > > SUGGESTION: I don't have time to do this quiz, but it looks like fun. > I for one would encourage anybody to do it with some visual > representation! (suggested libs: RMagick, Gosu, Rubygame, Ruby/SDL, > etc...) Here's an OpenGL/GLUT-based visualizer for the quiz: http://tastyspleen.net/~billk/ruby/q...sualization.rb The visualizer is designed to run with any quiz solution that provides the encircle() and generate_samples(n) methods at outer scope. A screenshot for those curious, but not curious enough to actually try installing ruby OpenGL bindings ... <grin> http://tastyspleen.net/~billk/ruby/q...le/157_vis.png NOTE: I've only tried this program on ruby 1.8.4 so far... I have no idea if it might run on 1.9 ... Also... I believe I'm using yoshi's opengl-0.32f bindings. I haven't tried it with the very latest ruby/OpenGL bindings on rubyforge. Regards, Bill |

Re: The Smallest Circle (#157)On Feb 17, 8:59 am, Bill Kelly <bi...@cts.com> wrote:
> From: "John Joyce" <dangerwillrobinsondan...@gmail.com> > > > > > SUGGESTION: I don't have time to do this quiz, but it looks like fun. > > I for one would encourage anybody to do it with some visual > > representation! (suggested libs: RMagick, Gosu, Rubygame, Ruby/SDL, > > etc...) > > Here's an OpenGL/GLUT-based visualizer for the quiz: > > http://tastyspleen.net/~billk/ruby/q...rcle/157_small... I'm trying to utilize gnuplot for visualization. With any luck I can post the visual part without spoiling the quiz. ;) Anyone interested? -- Alex |

All times are GMT. The time now is 03:56 AM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.