[Problem 182] Frodo and Black Riders
Back to General discussions forum
In my initial implementation, my logic was to estimate an area of the polar curve by counting the number of complete squares within it. To get a closer and closer approximation, stretch the polar curve horizontally and vertically by a large factor (say 10^3) and count again until the approximation is good enough.
My code went like this:
Iterate from theta = 0, 0.01 (or a suitably small step) ... 2pi to generate a list of coordinates of the polar curve (the "outline" of the polar curve if you will). Multiply these coordinates by a large factor and then round them to integers.
Using this list of coordinates, generate a set of coordinates of the points bounded within the polar curve. The approximate area (number of complete squares counted) should be be (sqrt(len(set)) - 1)^2, where len(set) is the number of points counted within the polar curve.
Repeat for other riders. Because we have a set of coordinates of inner points for every polar curve, we can also detect any overlaps of area using some set method like .intersection().
This implementation does not work and I cannot find the reason why. What is the flaw in my logic? Do I absolutely have to use some library to plot out the riders' coordinates on a graph?
Just iterate over a large sample (all?) of the possible hobbit coordinates and count the riders that can see each of those. An ambiguity for this problem comes from the fact that the problem does not specify what are valid coordinates. All examples in the text use integer coordinates but that is often not granular enough to get the expected answer. For the given example, checking all integer coordinates gives me 30% of them being visible by exactly one rider rather than the expected 31%. Thus going in steps of 0.5 or even 0.1 might be required.
Thanks, you're a lifesaver. I have no idea how I overlooked this method.