1. #### 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 01:33 AM.
2. No Profile Picture
epl
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2001
Location
Dublin
Posts
413
Rep Power
15
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...
3. 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
4. here's my solution.
Last edited by infamous41md; July 25th, 2003 at 01:33 AM.
5. 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
6. 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