Talk:Problem of Apollonius: Difference between revisions
(→Meta error propagation: some comments to remind the brave ones who may want to fix the bug) |
|||
Line 14: | Line 14: | ||
Besides the above, there are other special cases: <code>[(0, 0), 1], [(0, 0), 2], [(0, 0), 3]</code> has no solution; <code>[(0, 1), 1], [(0, 2), 2], [(0, 3), 3]</code> has infinitely many solutions, to name just two. Someone once said, "programming is all about special cases." Unfortunately, for Problem of Apollonius, there seem to be nothing ''but'' special cases. --[[User:Ledrug|Ledrug]] |
Besides the above, there are other special cases: <code>[(0, 0), 1], [(0, 0), 2], [(0, 0), 3]</code> has no solution; <code>[(0, 1), 1], [(0, 2), 2], [(0, 3), 3]</code> has infinitely many solutions, to name just two. Someone once said, "programming is all about special cases." Unfortunately, for Problem of Apollonius, there seem to be nothing ''but'' special cases. --[[User:Ledrug|Ledrug]] |
||
:For what it's worth: the J implementation treats all these degenerate cases as having no solutions. --[[User:Rdm|Rdm]] 20:11, 15 September 2011 (UTC) |
Revision as of 20:11, 15 September 2011
Suggest inline/block quoting the problem and algebraic solutions. (With citations, of course) --Michael Mol 17:34, 13 August 2010 (UTC)
Meta error propagation
Here's the danger of everyone copying everyone else's code: how many of the examples can handle the following three circles? x=0, y=2, r=1; x=0, y=-2, r=1; x=4, y=0, r=1
--Ledrug 23:38, 14 September 2011 (UTC)
- OK great. What do we do to fix it? --Mwn3d 01:46, 15 September 2011 (UTC)
- Problems which are simple translations are usually indications that the translator is unfamiliar with the algorithm and/or the target language. Perhaps rewrites (or audits) should be preferred. Perhaps translations should show up on the unimpl pages as ENAs? --Michael Mol 02:20, 15 September 2011 (UTC)
- The problem is a division by zero, specifically when v11 is 0. AFAIK it's in all the examples. There may be other problems, for instance I wouldn't be surprised if all the solutions fail to handle some degenerate cases.
- On a not quite related note, I do think line-by-line translations should be discouraged. Even if you have to pick up the algorithm from some existing examples, it's probably better to rewrite the code from semi-scratch, if only to make sure it's more idiomatic to your language. As to a solution -- I have no idea. --Ledrug 02:34, 15 September 2011 (UTC)
- Problems which are simple translations are usually indications that the translator is unfamiliar with the algorithm and/or the target language. Perhaps rewrites (or audits) should be preferred. Perhaps translations should show up on the unimpl pages as ENAs? --Michael Mol 02:20, 15 September 2011 (UTC)
In searching of a proper fix, I scribbled many circles on a piece of paper, and reached the conclusion: I don't want any part of it. First off, the current problem of dividing by zero is just a minor annoyance. There are two fundamental problems:
- Circles can't always be represented by
[(x, y), r]
. Even if we ignore degenerate input circles, one still has to deal with degenerate solution circles, e.g.[(0, -2), 1], [(0, 0), 1], [(0, 2), 1]
has two solutions that are straight lines. - Touching each circle internally or externally isn't enough to identify a unique solution.
[(0, -3), 2], [(0, 0), 1], [(0, 3), 2]
has no solution that contains all circles inside, but has two solutions that's outside every circle. Essentially this involves whether solution is allowed to have negative radius: if it is, there's the risk of double counting; if not, there's the risk of missing solutions.
Besides the above, there are other special cases: [(0, 0), 1], [(0, 0), 2], [(0, 0), 3]
has no solution; [(0, 1), 1], [(0, 2), 2], [(0, 3), 3]
has infinitely many solutions, to name just two. Someone once said, "programming is all about special cases." Unfortunately, for Problem of Apollonius, there seem to be nothing but special cases. --Ledrug
- For what it's worth: the J implementation treats all these degenerate cases as having no solutions. --Rdm 20:11, 15 September 2011 (UTC)