diff options
Diffstat (limited to 'C_C++/FindSpiralNumber.cpp')
| -rw-r--r-- | C_C++/FindSpiralNumber.cpp | 179 |
1 files changed, 0 insertions, 179 deletions
diff --git a/C_C++/FindSpiralNumber.cpp b/C_C++/FindSpiralNumber.cpp deleted file mode 100644 index 78e1681..0000000 --- a/C_C++/FindSpiralNumber.cpp +++ /dev/null @@ -1,179 +0,0 @@ -#include <iostream> - -using namespace std; - -int main() -{ - int x, y; - cout << "x = "; - cin >> x; - cout << "y = "; - cin >> y; - - int n, v = max(abs(x), abs(y)), g = 8 * (v * (v + 1) / 2); - - if (y == v || x == v) { // Top row or right column - n = g - x + y - 6 * v; - } - else { // Left column or bottom row - n = g + x - y - 2 * v; - } - - printf("n = %d", n); - - return 0; -} - -/* -------------- - * Task condition - * -------------- - * You have a spiral of whole numbers, starting from 0, like this: - * - * 36 < 35 < 34 < 33 < 32 < 31 < 30 - * V ^ - * 37 16 < 15 < 14 < 13 < 12 29 - * V V ^ ^ - * 38 17 4 < 3 < 2 11 28 - * V V V ^ ^ ^ - * 39 18 5 0 > 1 10 27 ... - * V V V ^ ^ ^ - * 40 19 6 > 7 > 8 > 9 26 51 - * V V ^ ^ - * 41 20 > 21 > 22 > 23 > 24 > 25 50 - * V ^ - * 42 > 43 > 44 > 45 > 46 > 47 > 48 > 49 - * - * The distance between two neighbouring numbers is 1, meaning 0 is at (0;0), 1 is at (1;0), 38 is at (-3;1). - * You are given the coordinates of a number and you have to find the actual number. - * - * -------------------------- - * Explanation of my solution - * -------------------------- - * - * My solution is a very mathematical one. First, I divide the spiral into squares, - * depending on the offset of 0;0. - * Example: - * - Square 1 (because x and y are between -1 and 1 (one of them is always 1 or -1)): - * 4 < 3 < 2 - * V ^ - * 5 1 - * V - * 6 > 7 > 8 - * - * - Square 2 (because x and y are between -2 and 2 (one of them is always 2 or -2)): - * 16 < 15 < 14 < 13 < 12 - * V ^ - * 17 11 - * V ^ - * 18 10 - * V ^ - * 19 9 - * V - * 20 > 21 > 22 > 23 > 24 - * - * - Square 3 (because x and y are between -3 and 3 (one of them is always 3 or -3)): - * 36 < 35 < 34 < 33 < 32 < 31 < 30 - * V ^ - * 37 29 - * V ^ - * 38 28 - * V ^ - * 39 27 - * V ^ - * 40 26 - * V ^ - * 41 25 - * V - * 42 > 43 > 44 > 45 > 46 > 47 > 48 - * - * And so on. I call the number of the square "v". - * We can find it by getting the absolute value of both coordinates and get the biggest number. - * - * Then there is the biggest number in the square, the one in the bottom right corner, I call that "g". - * g for square 1 (v = 1) is 8, for v = 2: g = 24, for v = 3: g = 48 and so on. - * We can see that each g is divisble by 8, but the multiplier is slightly tricky to find. - * The multiplier is the sum of all whole number from 1 up until v. - * - * Example: - * v = 2 - * g = 8 * (Sum of numbers from 1 to v) = 8 * (1 + 2) = 8 * 3 = 24 - * - * v = 3 - * g = 8 * (Sum of numbers from 1 to v) = 8 * (1 + 2 + 3) = 8 * 6 = 48 - * - * Then, we divide the whole square into two corners. We take the diagonal from top left to bottom right, and check in which part the coordinates are. - * We do that because we have two formulas. In brief, what they do is tranform the coordinates into the number from which we'll subtract from g. - * - * Example: - * v = 3, g = 48 - * - * Lets take a look at the formula for the bottom of the square. We aren't interested in g, so the important part is "x - y - 2*v". - * What it does is make the coordinates for x and y correspond to a number from -12 to 0. - * So this: - * 36 - * V - * 37 - * V - * 38 - * V - * 39 - * V - * 40 - * V - * 41 - * V - * 42 > 43 > 44 > 45 > 46 > 47 > 48 - * Becomes: - * -12 - * V - * -11 - * V - * -10 - * V - * -9 - * V - * -8 - * V - * -7 - * V - * -6 > -5 > -4 > -3 > -2 > -1 > 0 - * - * "- 2 * v" is -6, the number in the bottom left corner. Then, if we increase Y (meaning we want to go up the left column), - * we want the number to also decrease (make it further away from 0). We also have to account for X, because there it's always -3. - * So, we need them to sum up to 0 when we're on the bottom left corner, so we can just subtract Y from X. As we said, - * X is always -3 on the left column, so by increasing Y, we also increase the negative number. - * - * Ok, here are some example numbers: - * X | Y | X - Y - * ---|----|------ - * -3 | -3 | 0 - * -3 | -2 | -1 - * -3 | 0 | -3 - * - * This actually works out for us just fine when we're traversing the bottom row. There, Y is always -3, and - * when increasing X we want to increase our number (make it close to 0). So, X - Y become a positive number, - * which summed up with the negative number ("-2*v") makes the result number closer to 0, which is what we want. - * - * Here are more example numbers: - * X | Y | X - Y - * ---|----|------ - * -3 | -3 | 0 - * -2 | -3 | 1 - * 0 | -3 | 3 - * - * The formula for the top of the square (top row and right column) works the same , but there our corner number isn't "-2*v" but "-6*v", - * and we want the reverse effect: increase number (make smaller) on increasing X and decerease number on incrasing Y, - * so we make "X - Y" to be "Y - X" - * - * -13 < -14 < -15 < -16 < -17 < -18 < -19 - * ^ - * -20 - * ^ - * -21 - * ^ - * -22 - * ^ - * -23 - * ^ - * -24 - */ |