Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <cstring>
- #include <vector>
- int g_stack = 0;
- // One ring component within a solution
- struct Component
- { int num;
- double scale;
- };
- // =============================================================================
- // Solution class
- // -----------------------------------------------------------------------------
- class Solution
- { public:
- // Components of this solution
- inline const std::vector<Component>& components() const
- { return m_components;
- }
- // Add a component to this solution
- void addComponent (const Component& a)
- { m_components.push_back (a);
- }
- // Compare solutions
- bool operator> (const Solution& other) const
- { // If this solution has less components than the other one, this one
- // is definitely better.
- if (components().size() < other.components().size())
- return true;
- // vice versa
- if (other.components().size() < components().size())
- return false;
- // Calculate the maximum ring number. Since the solutions have equal
- // ring counts, the solutions with lesser maximum rings should result
- // in cleaner code and less new primitives, right?
- int maxA = 0,
- maxB = 0;
- for (size_t i = 0; i < components().size(); ++i)
- { if (components()[i].num > maxA)
- maxA = components()[i].num;
- if (other.components()[i].num > maxB)
- maxB = other.components()[i].num;
- }
- if (maxA < maxB)
- return true;
- if (maxB < maxA)
- return false;
- // Solutions have equal rings and equal maximum ring numbers. Let's
- // just say this one is better, at this point it does not matter which
- // one is chosen.
- return true;
- }
- private:
- std::vector<Component> m_components;
- };
- std::vector<Solution> solutions;
- Solution bestSolution;
- 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 - floor (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 ringFinderRecursor (double r0, double r1, Solution& currentSolution)
- { char tabs[64];
- memset (tabs, '\t', g_stack);
- tabs[g_stack] = '\0';
- // Don't recurse too deep.
- if (g_stack >= 5)
- return false;
- // 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) round (num);
- currentSolution.addComponent (cmp);
- // If we're still at the first recursion, this is the only
- // ring and there's nothing left to do. Guess we found the winner.
- if (g_stack == 0)
- { solutions.push_back (currentSolution);
- return true;
- }
- }
- else
- { // Try find solutions by splitting the ring in various positions.
- if (isZero (r1 - r0))
- return false;
- double interval;
- // Determine interval. The smaller delta between radii, the more precise
- // interval should be used. We can't really use a 0.5 increment when
- // calculating rings to 10 -> 105... that would take ages to process!
- if (r1 - r0 < 0.5)
- interval = 0.1;
- else if (r1 - r0 < 10)
- interval = 0.5;
- else if (r1 - r0 < 50)
- interval = 1;
- else
- interval = 5;
- // Now go through possible splits and try find rings for both segments.
- std::vector<double> radii;
- // r1 / 2 is a particularly good split point, as r1 / 2 - r1 can be
- // filled with just one ring, possibly covering a lot of space.s
- if (r1 / 2 > r0)
- radii.push_back (r1 / 2);
- for (double r = r0 + interval; r < r1; r += interval)
- radii.push_back (r);
- for (std::vector<double>::iterator it = radii.begin(); it != radii.end(); ++it)
- { double r = *it;
- Solution sol = currentSolution;
- g_stack++;
- bool res = ringFinderRecursor (r0, r, sol) && ringFinderRecursor (r, r1, sol);
- g_stack--;
- if (res)
- { // We succeeded in finding radii for this segment. If the stack is 0, this
- // is the first recursion to this function. Thus there are no more ring segments
- // to process and we can add the solution.
- //
- // If not, when this function ends, it will be called again with more arguments.
- // Accept the solution to this segment by setting currentSolution to sol, and
- // return true to continue processing.
- if (g_stack == 0)
- solutions.push_back (sol);
- else
- { currentSolution = sol;
- return true;
- }
- }
- }
- return false;
- }
- return true;
- }
- // =============================================================================
- // Main function. Call this with r0 and r1. If this returns true, use bestSolution
- // for the solution that was presented.
- // -----------------------------------------------------------------------------
- bool findRings (double r0, double r1)
- { Solution sol;
- // Recurse in and try find solutions.
- ringFinderRecursor (r0, r1, sol);
- // Compare the solutions and find the best one. The solution class has an operator>
- // overload to compare two solutions.
- const Solution* best = NULL;
- for (std::vector<Solution>::iterator solp = solutions.begin(); solp != solutions.end(); ++solp)
- { const Solution& sol = *solp;
- if (best == NULL || sol > *best)
- best = /
- }
- // If we found one best solution, return it now.
- if (best)
- { bestSolution = *best;
- return true;
- }
- // This should only happen if no solutions were found in the first place.
- return false;
- }
- int main (int argc, char* argv[])
- { char* endptr0, *endptr1;
- double r0, r1;
- // Validate input
- 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);
- // Use the algorithm to find a solution
- if (!findRings (r0, r1))
- { printf ("can't find rings between %g and %g\n", r0, r1);
- return 1;
- }
- // Iterate through the solution and print the rings involved.
- for (std::vector<Component>::const_iterator it = bestSolution.components().begin(); it != bestSolution.components().end(); ++it)
- printf ("Ring %d, scale by %g (%g -> %g)\n", it->num, it->scale, it->num * it->scale, (it->num + 1) * it->scale);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement