Most Recent Blog

King's View of the Battle

 Open GL model of a chess board.

February 3, 2020

Fly Swatter Problem Google Code Jam 2008 Qualifying Round Problem 3

The Fly Swatter problem was quite challenging.
This solution uses an "Exact" closed form solution.

Basic problem summary: calculate the probability of hitting a fly with a tennis racket.
CodeJam's Detailed statement:  Code Jam 2008 Qualifying Round P3

The basic idea is the following:

  • Divided the Tennis racket into 4 symmetric quadrants
  • Calculate the area where the fly would be able to safely fly through
  • Calculate the total Area
  • Solution 1-safeArea/totalArea is the solution.  format and maintain 6 sig figs.
Prior to really diving into this problem there is a bit of Trigonometry that must be programmed. Specifically, we will be required to calculate the area of a "chord" of a circle.  For the most part equations of this assume that $Area = f(\theta,r) \stackrel{\bullet}{\equiv} \theta  $.  However, we will need this in the form $Area = f(x_{1},x_{2},r) \space where \space x_{1} ,  x_{2}  $ are the x-coordinates of the 2 points of the chord.  So the Area of the chord in a usable format for this problem becomes: $$ { 1 \over {2}} r^2 ( 2 \arcsin{{l}\over{2r}}) - \sin{(2 \arcsin{l\over{2r}})}$$ where $ l $ is the length of the chord.
Or In Code Calculate the Area of a Chord:

The North-East Case:
$$Area = gap^{2}  -  {1 \over 2} (xTwo -  X_{RIM \space yTwo} ) * (yTwo - X_{RIM \space xTwo}) + ChordArea (X_{RIM \space yTwo},X_{RIM \space xTwo})$$,




West East Case:
$$ Area = gap*(yOne - RIM_{y \space xTwo}) + {{1 \over 2} (RIM_{y \space xOne} - RIM_{y \space xTwo})} + ChordArea (X_{RIM \space xTwo},X_{RIM \space xOne})$$
OR IN CODE In Code Area Calc for West-East Case:


For The North South And West South Cases: the code with picture is self explanatory, see the code at the bottom of the blog or on Git HUB








No comments:

Post a Comment

All comments are greatly appreciated! Comments will be moderated, and usually appear within 1 day. If you like a post, instead of saying you like it, vote for it or digg it (links provided). If there is any ERROR, PLEASE Comment I strive for good quality complete content.