how do i solve this problem?

This is a discussion on how do i solve this problem? within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Well, I came up with a pretty dumb solution that goes through the Cartesian coordinates and finds the coordinates and ...

  1. #16
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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';
        }
    }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  2. #17
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    anon: Yeah, nice. My distances are a bit short because I'm getting the distance from point to target in a direct line, however it should be accurate enough to set the path in the right direction each move.

    mario: Although moving between squares will pretty much have to be done using the original co-ord system its not as easy as it may look. 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. All the solutions I can think of are so complicated I can't even be bothered to attempt them. If theres a simple equation for dealing with this I would still be interested to know. I can't see one.

  3. #18
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,468
    Quote Originally Posted by mike_g View Post
    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
    Last edited by Mario F.; 04-13-2008 at 05:08 PM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  4. #19
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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....
    Last edited by tabstop; 04-13-2008 at 10:30 PM.

  5. #20
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,707
    Quote Originally Posted by tabstop View Post
    It seems clear [...] that the shortest path will get to/stay in the smaller ring
    Were you to build an algorithm dependent on the smallest ring, would it still work if you didn't have to cross over to the opposite side of the honey comb to get from A to B? For instance, in the example, going from 58 to 54 is an easy four-step path, but if you don't build carefully you'll probably get a really silly answer.

  6. #21
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    54 and 58 are in the same ring, so you wouldn't change rings at all. (I don't mean the smallest ring down in the center, I mean the smaller of the two rings -- start and finish.)

  7. #22
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #23
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #24
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Yeah, thats basically how my version woks. The ring is the distance from the center. The sector is the step on the ring and the x/y co-ords are got by doint sin/cos on the sector multiplied by the distance.

    If I can get the adjacent tile numbers, then it should be possible to step towards the the target each iteration until its reached. I might get back to this later on.

  10. #25
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    map the coordinates of the center of each cell, then draw a line from cell A to cell B, the shortest path is defined by the cells the line passes through, if the line passes alogn the line between 2 cells, randomly pick on of the two, as either route will be the same distance.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  11. #26
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Well, as I said in the post above I already have that part. I just need to find a way to move using the radial co-ordinate system. It should be possible to step in and out of rings by adding /subtracting a ring size with a modifier to take into account the spiral effect. Some sectors will have more paths to the outer ring than others as the image shows, and whether moving up, is: in, out or along the ring depends at which angle the current position is on the ring.
    http://i92.photobucket.com/albums/l1...ndel/pic_a.png
    Seems like a bloody nightmare :/

  12. #27
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,468
    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.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  13. #28
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by PING View Post
    I assume that is a joke. Comparing ACM ICPC world final's problems to 'elementary school world problems' is something i cannot fathom.
    I didn't say they were easy like elementary problems. I said they contain deceptive information, like elementary problems.

  14. #29
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.
    Attached Files Attached Files
    Last edited by mike_g; 04-14-2008 at 01:32 PM.

  15. #30
    The larch
    Join Date
    May 2006
    Posts
    3,573
    mike_g, wasn't one requirement that it should handle positions up to 10000?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Solve This Problem Within 3 Hr Urgent Need
    By annum in forum C Programming
    Replies: 12
    Last Post: 10-04-2009, 09:56 AM
  2. problem solve
    By coolnarugodas in forum C Programming
    Replies: 7
    Last Post: 04-26-2005, 12:31 PM
  3. Replies: 2
    Last Post: 04-25-2005, 11:59 AM
  4. Bubble Sort / selection problem
    By Drew in forum C++ Programming
    Replies: 7
    Last Post: 08-26-2003, 03:23 PM
  5. problem cant solve please help.
    By sarah in forum C Programming
    Replies: 6
    Last Post: 09-03-2001, 01:32 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21