Thread: how do i solve this problem?

Well, I came up with a pretty dumb solution that goes through the Cartesian coordinates and finds the coordinates and their distance in a rather brain-dead way. At least it seems to give the correct output:

Code:

//hive.cpp

#include <iostream>
#include <cmath>

struct Coord
{
    int x, y;
};

Coord coord_from_num(unsigned n)
{
    const unsigned turn_count = 6;
    Coord turns[turn_count] = {{-1, 0}, {0, -1}, {1, -1}, {1, 0}, {0, 1}, {-1, 1}};
    unsigned level = 0;
    unsigned level_start = 1;
    unsigned level_end = 1;
    //determine level on the spiral
    while (n > level_end) {
        level_start = level_end;
        ++level;
        level_end += level * 6;
    }

    //find coordinates by moving along the spiral
    Coord result = {0, level};
    for (unsigned i = 0; i != turn_count; ++i) {
        for (unsigned j = 0; j != level; ++j) {
            if (level_start == n)
                return result;
            result.x += turns[i].x;
            result.y += turns[i].y;
            ++level_start;
        }
    }
    return result; // 1

}

int get_move(int a, int b)
{
    //what should be added to a, to advance the value towards b
    if (a < b) return 1;
    else if (a > b) return -1;
    return 0;
}

int get_distance(Coord start, const Coord& target)
{
    //start advancing towards the target and count steps
    //move both in x and y direction, unless increments are (1, 1) or (-1, -1)
    int distance = 0;
    while (!(start.x == target.x && start.y == target.y)) {
        ++distance;
        int xInc = get_move(start.x, target.x);
        int yInc = get_move(start.y, target.y);
        start.x += xInc;
        if (abs(xInc + yInc) != 2)
            start.y += yInc;
    }
    return distance;
}

int main()
{
    int a = 0, b = 0;
    while (std::cin >> a >> b && a && b) {
        Coord ac = coord_from_num(a);
        Coord bc = coord_from_num(b);
        std::cout << "The distance between cells " << a << " and " << b << " is "
            << get_distance(ac, bc) << '\n';
    }
}

Originally Posted by mike_g

the side the outer/inner rings are on depends on the locations rotation on the ring which make it kind of tricky to deal with.

Not sure what you mean, but if I'm following you, it has no relevance sicne you can draw the hexagons on a piece of paper, rotate that piece of paper and the result is obviously the same.

All you need is a formula that tells you how much is 30 minus 19 on that coordinate system (as an example). Any attempt at using a cartesian system really would not going to be accepted by the judges

What you have in there is essentially an arithmetic progression. A slightly more complex one at that. But still an arithmetic progression, of which you need to find d.

edit: or geometric progression? I told you, i math challenged

I agree; I don't think the rotations matter. It seems clear (maybe I'm giving the game away) that the shortest path will get to/stay in the smaller ring, go around on the small ring, and then if necessary go out to get to the target. So you need to know how to get in and out. See if you can find a pattern for which outer cells you can get to from an inner.

Edit: And now looking again, that seems to work only if the cells are on the same half (or close enough to the center so it doesn't matter which way you go). Otherwise, you'll want to go through. Hmm....

28 and 37 are in the same ring, too, but if you don't go through the center, you'll never get the shortest path.

Another solution that I thought about is that it is easy to find the distance from the centre. So, the problem might be how to calculate the number of the end position if the centre is shifted to the start position.

Think of polar coordinates. And think of the Archimedean Spiral equation. The proposed coordinate system is nothing more, nothing less, than an archimedean spiral in a polar coordinate system.

I keep telling you, it's not that hard.

Ok I think I cracked it, although I took the mentally challenged route (I know, its sad)

Edit: oh whoops, it will give a compile error. To fix it remove the 'else' from the 'else if' at the start of the line and it will work.

mike_g, wasn't one requirement that it should handle positions up to 10000?