find_rings_2.cc

#include <cstdio>
#include <cstdlib>
#include <deque>
#include <cmath>

struct Component
{   int num;
    double scale;
};

std::deque<Component> solution;

template<class T> inline T abs (T a)
{   return (a > 0) ? a : -a;
}

inline bool isZero (double a)
{   return abs<double> (a) < 0.0001;
}

inline bool isInteger (double a)
{   return isZero (a - (int) a);
}

// =============================================================================
// ringFinder
//
// This is the main algorithm of the ring finder. It tries to use math to find
// the one ring between r0 and r1. If it fails (the ring number is non-integral),
// it finds an intermediate radius (ceil of the ring number times scale) and
// splits the radius at this point, calling this function again to try find the
// rings between r0 - r and r - r1.
//
// This does not always yield into usable results. If at some point r == r0 or
// r == r1, there is no hope of finding the rings, at least with this algorithm,
// as it would fall into an infinite recursion.
// -----------------------------------------------------------------------------
bool ringFinder (double r0, double r1)
{   // Find the scale and number of a ring between r1 and r0.
    double scale = r1 - r0;
    double num = r0 / scale;

    // If the ring number is integral, we have found a fitting ring to r0 -> r1!
    if (isInteger (num))
    {   Component cmp;
        cmp.scale = scale;
        cmp.num = (int) ceil (num);
        solution.push_back (cmp);
    }
    else
    {   // If not, find an intermediate <r> between the radii
        double r = ceil (num) * scale;

        // If r is the same as r0 or r1, we simply cannot find any rings between
        // r0 and r1. Stop and return failure.
        if (isZero (r0 - r) || isZero (r1 - r))
            return false;

        // Split this ring into r0 -> r and r -> r1. Recurse to possibly find
        // the rings for these. If either recurse fails, the entire algorithm
        // fails as well.
        if (!ringFinder (r0, r) || !ringFinder (r, r1))
            return false;
    }

    // The algorithm did not fail, thus we succeeded!
    return true;
}

int main (int argc, char* argv[])
{   char* endptr0, *endptr1;
    double r0, r1;

    if (argc != 3)
    {   fprintf (stderr, "usage: %s <r0> <r1>\n", argv[0]);
        return 1;
    }

    r0 = strtod (argv[1], &endptr0);
    r1 = strtod (argv[2], &endptr1);

    if (*endptr0 != '\0' || *endptr1 != '\0')
    {   fprintf (stderr, "error: arguments are not numbers\n");
        return 1;
    }

    if (r0 > r1)
        std::swap (r0, r1);

    if (!ringFinder (r0, r1))
    {   printf ("Failed to find rings for %g - %g\n", r0, r1);
        exit (EXIT_FAILURE);
    }

    for (std::deque<Component>::iterator it = solution.begin(); it != solution.end(); ++it)
        printf ("Ring %d, scale by %g (%g -> %g)\n", it->num, it->scale,
            it->num * it->scale, (it->num + 1) * it->scale);
}