diff options
Diffstat (limited to 'C++/FindSpiralNumberCoord.cpp')
| -rw-r--r-- | C++/FindSpiralNumberCoord.cpp | 147 |
1 files changed, 0 insertions, 147 deletions
diff --git a/C++/FindSpiralNumberCoord.cpp b/C++/FindSpiralNumberCoord.cpp deleted file mode 100644 index 07b2071..0000000 --- a/C++/FindSpiralNumberCoord.cpp +++ /dev/null @@ -1,147 +0,0 @@ -#include <iostream> - -using namespace std; - -int main() -{ - int n, v, g, x, y; - cout << "n = "; - cin >> n; - - while (g < n) { - v++; - g = 8 * (v * (v + 1) / 2); - } - - if (n >= g - 2 * v) { // Bottom row - y = -v; - x = v - (g - n); - } - else if (n >= g - 4 * v) { // Left column - x = -v; - y = ((g - 2 * v) - n) - v; - } - else if (n >= g - 6 * v) { // Top row - y = v; - x = ((g - 4 * v) - n) - v; - } - else { // Right column - x = v; - y = v - ((g - 6 * v) - n); - } - - printf("(%d;%d)\n", x, y); - - 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 - * - * You are given a number n and your goal is to find the coordinates of the number. - * The distance between two neighbouring numbers is 1, meaning 0 is at (0;0), 1 is at (1;0), 38 is at (-3;1). - * - * -------------------------- - * 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". - * - * 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 - * - * After we've found g and v, we start looking at the numbers in the corners. - * The bottom right corner is g by definition, the bottom left corner is g - 2 * v, - * the top left is g - 4 * v and the top right is g - 6 * v. - * By comparing the values in the corners we can determine where the number is: - * top row, bottom row, left column or right column. - * - * Example: - * v = 2, g = 24, n = 11 - * - * if (n > bottom left corner) number is on bottom row (between 20 and 24) - * else if (n > top left corner) number is on left column (between 16 and 20) - * else if (n > top right corner) number is on top row (between 16 and 12) - * else number is on right column (between 12 and 9) - * - * After we find on which side the number is, we can immediately determine the x or y coordinate, - * as it will be +v or -v. - * The final step is to determine the other coordinate. The formula differs slightly depending on a side, - * but the gist of it is that we look at the difference between a corner number and our number, which gives - * us distance from the corner number and we offset the searched coordinate. - * - * Example: - * v = 2, g = 24, n = 11 - * We have determined that our number is in the right column. - * This means we know for sure that the X coordinate of n is 2. - * - * offset = corner number - n = (g - 6 * v) - 11 = 12 - 11 = 1 - * - * The Y coordinate of the corner number is 2 (12 is located at (2;2)). - * In our case, we want to subtract our offset from that coordinate, so - * - * Y coordinate of n = Y coordinate of corner number - offset = 2 - 1 = 1. - * - * And so we found that n is located at (2;1) - */ |