• API
• FAQ
• Tools
• Archive
SHARE
TWEET # find_rings_3.cc slatenails  Oct 16th, 2013 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <cstdio>
2. #include <cstdlib>
3. #include <cmath>
4. #include <cstring>
5. #include <vector>
6.
7. int g_stack = 0;
8.
9. // One ring component within a solution
10. struct Component
11. {       int num;
12.         double scale;
13. };
14.
15. // =============================================================================
16. // Solution class
17. // -----------------------------------------------------------------------------
18. class Solution
19. {       public:
20.                 // Components of this solution
21.                 inline const std::vector<Component>& components() const
22.                 {       return m_components;
23.                 }
24.
25.                 // Add a component to this solution
26.                 void addComponent (const Component& a)
27.                 {       m_components.push_back (a);
28.                 }
29.
30.                 // Compare solutions
31.                 bool operator> (const Solution& other) const
32.                 {       // If this solution has less components than the other one, this one
33.                         // is definitely better.
34.                         if (components().size() < other.components().size())
35.                                 return true;
36.
37.                         // vice versa
38.                         if (other.components().size() < components().size())
39.                                 return false;
40.
41.                         // Calculate the maximum ring number. Since the solutions have equal
42.                         // ring counts, the solutions with lesser maximum rings should result
43.                         // in cleaner code and less new primitives, right?
44.                         int maxA = 0,
45.                                 maxB = 0;
46.
47.                         for (size_t i = 0; i < components().size(); ++i)
48.                         {       if (components()[i].num > maxA)
49.                                         maxA = components()[i].num;
50.
51.                                 if (other.components()[i].num > maxB)
52.                                         maxB = other.components()[i].num;
53.                         }
54.
55.                         if (maxA < maxB)
56.                                 return true;
57.
58.                         if (maxB < maxA)
59.                                 return false;
60.
61.                         // Solutions have equal rings and equal maximum ring numbers. Let's
62.                         // just say this one is better, at this point it does not matter which
63.                         // one is chosen.
64.                         return true;
65.                 }
66.
67.         private:
68.                 std::vector<Component> m_components;
69. };
70.
71. std::vector<Solution> solutions;
72. Solution bestSolution;
73.
74. template<class T> inline T abs (T a)
75. {       return (a > 0) ? a : -a;
76. }
77.
78. inline bool isZero (double a)
79. {       return abs<double> (a) < 0.0001;
80. }
81.
82. inline bool isInteger (double a)
83. {       return isZero (a - floor (a));
84. }
85.
86. // =============================================================================
87. // ringFinder
88. //
89. // This is the main algorithm of the ring finder. It tries to use math to find
90. // the one ring between r0 and r1. If it fails (the ring number is non-integral),
91. // it finds an intermediate radius (ceil of the ring number times scale) and
92. // splits the radius at this point, calling this function again to try find the
93. // rings between r0 - r and r - r1.
94. //
95. // This does not always yield into usable results. If at some point r == r0 or
96. // r == r1, there is no hope of finding the rings, at least with this algorithm,
97. // as it would fall into an infinite recursion.
98. // -----------------------------------------------------------------------------
99. bool ringFinderRecursor (double r0, double r1, Solution& currentSolution)
100. {       char tabs;
101.         memset (tabs, '\t', g_stack);
102.         tabs[g_stack] = '\0';
103.
104.         // Don't recurse too deep.
105.         if (g_stack >= 5)
106.                 return false;
107.
108.         // Find the scale and number of a ring between r1 and r0.
109.         double scale = r1 - r0;
110.         double num = r0 / scale;
111.
112.         // If the ring number is integral, we have found a fitting ring to r0 -> r1!
113.         if (isInteger (num))
114.         {       Component cmp;
115.                 cmp.scale = scale;
116.                 cmp.num = (int) round (num);
118.
119.                 // If we're still at the first recursion, this is the only
120.                 // ring and there's nothing left to do. Guess we found the winner.
121.                 if (g_stack == 0)
122.                 {       solutions.push_back (currentSolution);
123.                         return true;
124.                 }
125.         }
126.         else
127.         {       // Try find solutions by splitting the ring in various positions.
128.                 if (isZero (r1 - r0))
129.                         return false;
130.
131.                 double interval;
132.
133.                 // Determine interval. The smaller delta between radii, the more precise
134.                 // interval should be used. We can't really use a 0.5 increment when
135.                 // calculating rings to 10 -> 105... that would take ages to process!
136.                 if (r1 - r0 < 0.5)
137.                         interval = 0.1;
138.                 else if (r1 - r0 < 10)
139.                         interval = 0.5;
140.                 else if (r1 - r0 < 50)
141.                         interval = 1;
142.                 else
143.                         interval = 5;
144.
145.                 // Now go through possible splits and try find rings for both segments.
147.
148.                 // r1 / 2 is a particularly good split point, as r1 / 2 - r1 can be
149.                 // filled with just one ring, possibly covering a lot of space.s
150.                 if (r1 / 2 > r0)
151.                         radii.push_back (r1 / 2);
152.
153.                 for (double r = r0 + interval; r < r1; r += interval)
155.
156.                 for (std::vector<double>::iterator it = radii.begin(); it != radii.end(); ++it)
157.                 {       double r = *it;
158.                         Solution sol = currentSolution;
159.
160.                         g_stack++;
161.                         bool res = ringFinderRecursor (r0, r, sol) && ringFinderRecursor (r, r1, sol);
162.                         g_stack--;
163.
164.                         if (res)
165.                         {       // We succeeded in finding radii for this segment. If the stack is 0, this
166.                                 // is the first recursion to this function. Thus there are no more ring segments
167.                                 // to process and we can add the solution.
168.                                 //
169.                                 // If not, when this function ends, it will be called again with more arguments.
170.                                 // Accept the solution to this segment by setting currentSolution to sol, and
171.                                 // return true to continue processing.
172.                                 if (g_stack == 0)
173.                                         solutions.push_back (sol);
174.                                 else
175.                                 {       currentSolution = sol;
176.                                         return true;
177.                                 }
178.                         }
179.                 }
180.
181.                 return false;
182.         }
183.
184.         return true;
185. }
186.
187. // =============================================================================
188. // Main function. Call this with r0 and r1. If this returns true, use bestSolution
189. // for the solution that was presented.
190. // -----------------------------------------------------------------------------
191. bool findRings (double r0, double r1)
192. {       Solution sol;
193.
194.         // Recurse in and try find solutions.
195.         ringFinderRecursor (r0, r1, sol);
196.
197.         // Compare the solutions and find the best one. The solution class has an operator>
198.         // overload to compare two solutions.
199.         const Solution* best = NULL;
200.         for (std::vector<Solution>::iterator solp = solutions.begin(); solp != solutions.end(); ++solp)
201.         {       const Solution& sol = *solp;
202.
203.                 if (best == NULL || sol > *best)
204.                         best = &sol;
205.         }
206.
207.         // If we found one best solution, return it now.
208.         if (best)
209.         {       bestSolution = *best;
210.                 return true;
211.         }
212.
213.         // This should only happen if no solutions were found in the first place.
214.         return false;
215. }
216.
217. int main (int argc, char* argv[])
218. {       char* endptr0, *endptr1;
219.         double r0, r1;
220.
221.         // Validate input
222.         if (argc != 3)
223.         {       fprintf (stderr, "usage: %s <r0> <r1>\n", argv);
224.                 return 1;
225.         }
226.
227.         r0 = strtod (argv, &endptr0);
228.         r1 = strtod (argv, &endptr1);
229.
230.         if (*endptr0 != '\0' || *endptr1 != '\0')
231.         {       fprintf (stderr, "error: arguments are not numbers\n");
232.                 return 1;
233.         }
234.
235.         if (r0 > r1)
236.                 std::swap (r0, r1);
237.
238.         // Use the algorithm to find a solution
239.         if (!findRings (r0, r1))
240.         {       printf ("can't find rings between %g and %g\n", r0, r1);
241.                 return 1;
242.         }
243.
244.         // Iterate through the solution and print the rings involved.
245.         for (std::vector<Component>::const_iterator it = bestSolution.components().begin(); it != bestSolution.components().end(); ++it)
246.                 printf ("Ring %d, scale by %g (%g -> %g)\n", it->num, it->scale, it->num * it->scale, (it->num + 1) * it->scale);
247. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top