Wybiral

March 29th, 2008, 06:22 PM

This weeks challenge is to find the cheapest path from point A to point B.

Rules:

Your program must read the grid from file

Each cell can cost anywhere between 0 and 9

The starting point of the path must be (0, 0) (left, top)

The ending point of the path must be (N-1, N-1) (right, bottom)

The path can NOT make diagonal moves, ONLY left/right/down/up

You can NOT use a pre-written pathfinding library/module/etc

The first line of the file that must be parsed contains N, which is the width & height of the grid (they are the same, it's a square). Each line after that will contain the actual cost of each cell (each line is one row, each cell will be a value between 0 and 9).

Here is an example of a 3x3 grid file:

3

112

291

191

The goal is to find the cheapest path from (0, 0) to (N-1, N-1). That is, the sum of each cell visited along the path must be the lowest sum of all possible paths!

The resulting path can be presented in any way you choose. Some ideas could be:

Realtime animation of something moving along the path

Render the entire grid with the path being a separate color/character/object/etc

Output a sequence of R/L/D/U describing the motions used to solve it

Output the coordinates of each move

Feel free to get creative with this part, provided it's clear what the solution is.

For example, the 3x3 grid above could be presented as:

(0,0) (1,0) (2,0) (2,1) (2,2)

RRDD

111

001

001

Clues: ... (http://en.wikipedia.org/wiki/A*_search_algorithm) ... (http://en.wikipedia.org/wiki/Dijkstra's_algorithm) ... (http://en.wikipedia.org/wiki/Breadth-first_search) (to point you in the right wikipedia directions)

Be careful, the test file could be relatively large. I will favor fast solutions (not fast in terms of optimized code or language, but in terms of algorithm), so I won't be very impressed by purely brute-force search :)

Good luck, I'll pick the next challenge maker next Saturday (April 5).

Rules:

Your program must read the grid from file

Each cell can cost anywhere between 0 and 9

The starting point of the path must be (0, 0) (left, top)

The ending point of the path must be (N-1, N-1) (right, bottom)

The path can NOT make diagonal moves, ONLY left/right/down/up

You can NOT use a pre-written pathfinding library/module/etc

The first line of the file that must be parsed contains N, which is the width & height of the grid (they are the same, it's a square). Each line after that will contain the actual cost of each cell (each line is one row, each cell will be a value between 0 and 9).

Here is an example of a 3x3 grid file:

3

112

291

191

The goal is to find the cheapest path from (0, 0) to (N-1, N-1). That is, the sum of each cell visited along the path must be the lowest sum of all possible paths!

The resulting path can be presented in any way you choose. Some ideas could be:

Realtime animation of something moving along the path

Render the entire grid with the path being a separate color/character/object/etc

Output a sequence of R/L/D/U describing the motions used to solve it

Output the coordinates of each move

Feel free to get creative with this part, provided it's clear what the solution is.

For example, the 3x3 grid above could be presented as:

(0,0) (1,0) (2,0) (2,1) (2,2)

RRDD

111

001

001

Clues: ... (http://en.wikipedia.org/wiki/A*_search_algorithm) ... (http://en.wikipedia.org/wiki/Dijkstra's_algorithm) ... (http://en.wikipedia.org/wiki/Breadth-first_search) (to point you in the right wikipedia directions)

Be careful, the test file could be relatively large. I will favor fast solutions (not fast in terms of optimized code or language, but in terms of algorithm), so I won't be very impressed by purely brute-force search :)

Good luck, I'll pick the next challenge maker next Saturday (April 5).