Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
June 17th, 2003, 05:41 PM
 infamous41md
not a fan of fascism (n00b)

Join Date: Feb 2003
Location: ct
Posts: 2,756
Time spent in forums: 2 Days 11 h 4 m 29 sec
Reputation Power: 94
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
June 18th, 2003, 09:55 AM
 epl
Contributing User

Join Date: Mar 2001
Location: Dublin
Posts: 413
Time spent in forums: 2 h 18 m 18 sec
Reputation Power: 13
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
June 18th, 2003, 12:19 PM
 infamous41md
not a fan of fascism (n00b)

Join Date: Feb 2003
Location: ct
Posts: 2,756
Time spent in forums: 2 Days 11 h 4 m 29 sec
Reputation Power: 94
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
June 18th, 2003, 03:56 PM
 infamous41md
not a fan of fascism (n00b)

Join Date: Feb 2003
Location: ct
Posts: 2,756
Time spent in forums: 2 Days 11 h 4 m 29 sec
Reputation Power: 94
here's my solution.
Attached Files
 solution.tar (10.0 KB, 610 views)

Last edited by infamous41md : July 25th, 2003 at 02:33 AM.

#5
July 19th, 2003, 05:10 PM
 aries21
Junior Member

Join Date: Feb 2003
Posts: 1
Time spent in forums: < 1 sec
Reputation 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
July 21st, 2003, 08:19 PM
 MarkSigEp
Junior Member

Join Date: Jul 2003
Posts: 1
Time spent in forums: < 1 sec
Reputation Power: 0
I'd use Dijkstra's algorithm to compute the shortest path - here's an example: URL

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > challenging math/programming question