[Guest]

There doesn't appear to be many algorithm puzzles on this forum, so I thought I would start some and see how they are received.

You are given an n x m matrix/array of 1s and 0s. You are given starting co-ordinates (A,B) and destination co-ordinates (X,Y). Your goal is to find the quickest path to get from start to finish moving 1 square at a time (no diagonals). However, you cannot move onto a square with a 1 in it. Effectively you have to solve a maze. The output should give directions and be something of the form:

UUDDLRLUUD

You can use this as a test case:

m=10

n=10

A=0

B=0

X=9

Y=9


Maze {

0,1,0,0,0,1,0,0,0,0,

0,0,0,1,0,0,0,1,1,0,

0,1,1,1,1,1,1,1,0,0,

0,1,0,0,0,0,0,1,0,1,

0,1,0,1,1,1,0,1,0,1,

0,1,0,0,0,1,0,1,0,0,

0,1,1,1,0,1,0,1,1,0,

0,1,0,0,0,1,0,1,0,0,

0,1,0,1,1,1,0,1,0,1,

0,0,0,0,0,0,0,1,0,0

}

The most time efficient algorithm will be the winner (credit may also be given to the most memory efficient solution). Good Luck.

Edited August 15, 2010 by psychic_mind

[Guest]

It's not time efficient, but it'll make things easier if you go by all the cells and everywhere there's a 0 with 3 or 4 1's surrounding it that should be converted into a 1 (as in it's a dead end so close it) then go though the matrix again and again until all dead ends are closed, also to save a bit time after you close a cell with 3 1's surrounding it check the 0 that is connected to it...

[Guest]

sorry double post.

Edited August 15, 2010 by krityx

[Guest]

I'd use Lee's algorithm (I think that was it) You pick a starting point and give it a value, i'll say 2 to avoid confusion. Then to every available neighbor (marked 0) you give the value 3. and then you take those with the value 3 and do the same thing so their neighbors will have the value 4 and so on until you arrive at your destination. Then you take the way back and there's your way.

[Guest]

I'd use Lee's algorithm (I think that was it) You pick a starting point and give it a value, i'll say 2 to avoid confusion. Then to every available neighbor (marked 0) you give the value 3. and then you take those with the value 3 and do the same thing so their neighbors will have the value 4 and so on until you arrive at your destination. Then you take the way back and there's your way.

Ingenious, I like that idea...

[Guest]

So I haven't done any Java all summer so I just wanted to code something, so I gave krityx's solution a shot.

Credit goes to him/her, this is how I coded it, it's probably pretty nasty looking. But it works!

The only situation I see that it might get confused is if there are two paths of exactly the same length, but I would hope it just picks one and goes with it since it won't matter because they would both be just as efficient. And of course if the solution takes more than 1000 steps (I threw that in there because something is probably going wrong if num reaches 1000)

public class Main {


	public static void main(String[] args) {


		int[][] maze = {{0,0,0,0,0,0,0,0,0,0},{1,0,1,1,1,1,1,1,1,0},{0,0,1,0,0,0,1,0,0,0},

				{0,1,1,0,1,0,1,0,1,0},{0,0,1,0,1,0,0,0,1,0},{1,0,1,0,1,1,1,1,1,0},

				{0,0,1,0,0,0,0,0,0,0},{0,1,1,1,1,1,1,1,1,1},{0,1,0,0,0,0,1,0,0,0},

				{0,0,0,1,1,0,0,0,1,0},};


		Maze m = new Maze(maze);

		System.out.println(m.solve(0, 0, 9, 9));


	}


}

public class Maze {


	private int maze[][];

	private int num = 2;


	public Maze (int[][] maze) {

		setMaze(maze);

	}


	public String solve(int a, int b, int x, int y) {


		maze[a][b] = num;

		num++;


		while (maze[x][y] == 0 && num < 1000) {

			check();

			num++;

		}


		String s = "";

		String d = "";


		for (int step = num - 1, i = x, j = y; step > 2; step--) {

			d = next(i, j);

			s = d + s;


			if (d == "U")

				j++;

			else if (d == "D")

				j--;

			else if (d == "L")

				i++;

			else if (d == "R")

				i--;

		}


		return s;

	}


	private String next (int x, int y) {

		String s = "";


		try {

			if (maze[x][y+1] == maze[x][y] - 1  && s == "")

				s = "U";

		} catch (Exception e) {}

		try {

			if (maze[x][y-1] == maze[x][y] - 1  && s == "")

				s = "D";

		} catch (Exception e) {}

		try {			

			if (maze[x+1][y] == maze[x][y] - 1  && s == "")

				s = "L";

		} catch (Exception e) {}

		try {

			if (maze[x-1][y] == maze[x][y] - 1  && s == "")

				s = "R";

		} catch (Exception e) {}


		return s;

	}


	private void check() {

		for (int i = 0; i < maze[0].length; i++) {

			for (int j = 0; j < maze.length; j++) {

				if (maze[j][i] == num - 1)

					replace(j, i);

			}

		}

	}


	private void replace(int a, int b) {

		try {

			if (maze[a-1][b] == 0)

				maze[a-1][b] = num;

		} catch (Exception e) {}

		try {

			if (maze[a+1][b] == 0)

				maze[a+1][b] = num;

		} catch (Exception e) {}

		try {	

			if (maze[a][b-1] == 0)

				maze[a][b-1] = num;

		} catch (Exception e) {}

		try {

			if (maze[a][b+1] == 0)

				maze[a][b+1] = num;

		} catch (Exception e) {}


	}


	public void setMaze(int[][] maze) {

		this.maze = maze;

	}

}

[Guest]

I'd use Lee's algorithm (I think that was it) You pick a starting point and give it a value, i'll say 2 to avoid confusion. Then to every available neighbor (marked 0) you give the value 3. and then you take those with the value 3 and do the same thing so their neighbors will have the value 4 and so on until you arrive at your destination. Then you take the way back and there's your way.

I was thinking that a little variation of this algorithm should work better. We could apply the algo. with two start points : the starting point(with every successive no. on the +ve scale i.e. 2,3,4,...) and the destination point(with every successive path unit getting a no. on the negative scale -2,-3,-4,...). This will first of all ensure that there exists an entry into the destination. The algo. will then stop as soon as a positive no. (obviously >1) is found besides a negative one. Also in case of multiple such paths, it is highly likely that we always get the shortest path.

[Guest]

I am not a programmer, but I think the most efficient way would be to backtrack from end-point to the starting point rather than from going from start to end. If you find more than 1 way to go, the program should then give the shortest route as the output.

Following the previous post I made, I reliased that my suggestion would make more sense for this matrix and these set of points only, because the end point is on a rather "restricted path".

For a more general solution, the first step then should be to look for "degrees of freedom" for both starting point and end point to see whether the algorithm should follow from start pt to end point or from end pt to start point.

Edited August 16, 2010 by DeeGee

[Guest]

I think the correct solution has been found by krityx and implemented K4D. The algorithm should only have linear time complexity for a maze with N squares. Now I need to see if I something else for Algorithm 2!

[Guest]

I think the correct solution has been found by krityx and implemented K4D. The algorithm should only have linear time complexity for a maze with N squares. Now I need to see if I something else for Algorithm 2!

In case you didn't get the VM I sent you, go check out the "Other Mind Boggling Stuff on the Web" forum...

[Guest]

@k4d. Even if there are 2 or more paths of the same length it wouldn't get confused because it would take whatever it finds first (depends on how you code it, if it first checks the northern neighbor or the southern one etc) then the number to check for decreases and it will stick to that path. In the end it doesn't matter which path because for all the length will be the same.

[EventHorizon]

Assuming you cannot edit the map variable (that would be a lot of free space), the algorithm that would take the least amount of space (and still be guaranteed to find the shortest path) would be iterative deepening depth-first search. The space to find it would be simply the space to store the path, whereas the space to store the distances in Lee's algorithm would take another copy of the map.

If you would accept probably finding the shortest path, iterative deepening random wouldn't even need to store the path (try a path while printing it out, print out 'failed' and try again until a solution is found). Depending on how long you run it at each depth, you could be almost certain (to any required probability) that you've checked all paths, but it will be monumentally slow.

As for the quickest, that would depend on the map. I think A* would be best for large worlds with few obstacles and lots of possible paths. For highly constrained worlds that still have a lot of long dead ends and branches, bidirectional breadth-first search would be my choice. For small constrained worlds with few paths, bidirectional (or just unidirectional if small and only small branches) Lee's is fine (unless you add in variable edge costs, then you'd need to add a priority queue).

A contest would be interesting, but I'm not sure how much I'd participate (have other stuff I need to code).