#1
  1. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95

    Lightbulb challenging math/programming question


    here is a challenge, i'd like to see what methods people can come up with to solve this other than the way i did it

    The problem is to write a program that computes the distance, defined as the number of cells in a shortest path, between any pair of cells. For example, two maggots in cells 19 and 30 are 5 cells apart. One of the shortest paths connecting the two cells via the cells 19 ? 7 ? 6 ? 5 ? 15 ? 30, so you must move five times to adjacent cells to get from 19 to 30.



    You will receive points (query a and query b). Then you have to calculate the distance between the two points. After, send the distance back to the server. Repeat this procedure 3 times. When you successfully complete this task and all 3 answers are correct, then you will get the password for the next level. (The input consists of several lines, each containing two integers a and b (a,b 10000), denoting numbers of cells )
    Last edited by infamous41md; July 25th, 2003 at 02:33 AM.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    I reckon mapping the 2 numbers to a coordinate system - either angle and distance from the origin or a cartesian x, y pairing - will get you a long way there. I'm going to have a go at

    It's a nice puzzle, by the way. mapping to an angle, distance pair and see what comes out.

    What language will you use? It's easy enoughto draw a grid like yours iteratively, btw - starting with the cell 1, then the six around it, then the twelve around it and so on...
  4. #3
  5. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    i did it in C. similar to what you were thinking, altho you run into some difficulties when it comes to calculating the distance. let me know when u finish it and i'll show u my solution and vice versa. and yea, i thought it was a very cool puzzle - even tho it drove me nuts for a few hours trying to work out the initial gameplan
  6. #4
  7. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    here's my solution.
    Attached Files
    Last edited by infamous41md; July 25th, 2003 at 02:33 AM.
  8. #5
  9. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Posts
    1
    Rep Power
    0
    This one is interesting, but heres how you can do it. Set up a coordinate system like you said, except make it a tricoord system (i.e. x,y,z) where they are like this.

    _ /
    \

    You can then determine the distance by adding the coords and dividing by 2...I think. I have some code that is similar to this on my other machine that I can show you if you'd like
  10. #6
  11. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2003
    Posts
    1
    Rep Power
    0
    I'd use Dijkstra's algorithm to compute the shortest path - here's an example: http://www-b2.is.tokushima-u.ac.jp/~...Dijkstra.shtml

IMN logo majestic logo threadwatch logo seochat tools logo