----------------------------------- MysticVegeta Mon Jun 20, 2005 7:32 am Shortest Path in a Maze ----------------------------------- hi, I have been tring to code this problem in Dwite. It involves to find the shortest path in a maze from path A to B. 5 5 #A### #...# ###.# #...# #B### 10 8 ######## #....#.# ###....# A.#.##.# #....#.# ###..#.# #...##.B #..##..# ##.....# ######## Any Idea? ----------------------------------- Delos Mon Jun 20, 2005 10:22 am ----------------------------------- I could think of some sort of graphical solution to it. One could plot a line that connects A to B via the pathways (some nifty recurssion would be used to ensure that in the end, only the direct path is saved) and if multiple paths are found, one would simply determine the length of each resultant line. The details of this though, elude me. I know there are ways of doing it, having seen it been done before, but just how it is... ----------------------------------- zylum Mon Jun 20, 2005 2:45 pm ----------------------------------- the easiet but slowest method would be recursion... you would try all possible paths until you find one. you store a value for the length of the path and a variable that holds the shortest length. if you find a path, check if its length is smaller than the current shortest path. pseudo code: int findpath (int sx, int sy, int fx, int fy, d, boolean[][] map) if (sx and sy is not a valid point) return maxIntValue if (sx == fx and sy == fy) return d map[sx][sy] = false minValue = findpath (sx + 1, sy, fx, fy, d+1, map) minValue = min(minValue, findpath (sx - 1, sy, fx, fy, d+1, map)) minValue = min(findpath (sx, sy + 1, fx, fy, d+1, map)) minValue = min(findpath (sx, sy - 1, fx, fy, d+1, map)) map[sx][sy] = true return minValue + d end findpath another way i suppose you can do it is find the distance between all vertecise and create and adjacency matrix and use floyd's algorithm on it. or you could always impliment one of the standard pathfinding algorithms like the A* (which is pretty complex) ----------------------------------- MysticVegeta Mon Jun 20, 2005 6:31 pm ----------------------------------- I was thinking that maybe i can do this -> 1> Assign every point in a 2d array. 2> run the 2 loops (2d array) and when it finds an "A", 3> "counterstart" = true, position of "A" (x, y) = 1 4> continue the loop untill it finds the next dot. When it does -> 5> if dot(x, y) shares a direction with the previously postion of (x, y) being 1 then count += 1 end if 6> Repeat till "B", 7> Do the same thing for other directions except this time make the locations (x, y) = 2. 8> So on and so forth. Looks like its gunna take time, so i was just wondering if this will work, comments? Btw, I didnt get to any complex algorithms, matrices, etc (will be finishing grade 9 in 2 days) but i plan to read some books for prior learning. thanks, Tan ----------------------------------- zylum Wed Jun 22, 2005 11:25 am ----------------------------------- well the first example that i posted was simple recursion... im not sure how this would be done with loops but either way im sure recursion would be a lot easier. if youre not familiar with recursion i suggest you learn it if you want to do contest type programming. plus its really interesting. 1> Assign every point in a 2d array. this is what i mean when i use map in my pseudo code... map is a 2d array of boolean type. true means you can travel on that square and false means its a wall. so the basic recursive method would be to start at the starting position and go in all posible directions. ie up/down/left/right. thats if the direction is permisable ie its not a wall or out of bounds. everytime you go to a new square you mark the old one as false so you dont travel on it again. to go to the next square you just call your function again but with updated perameters such as new starting position and updated map array and distance traveled. once you reach the finish, you check your distance vs your shortest distance variable and update its value if the new distance is shorter... ----------------------------------- MysticVegeta Wed Jun 22, 2005 11:32 am ----------------------------------- ic ic, i never thought about a boolean array lol. Anyways, How can people code this in 45 mins??? or maybe i just underestimated grade 12's :shock: ----------------------------------- zylum Wed Jun 22, 2005 2:16 pm ----------------------------------- its not hard once you do a couple of similar problems... there are much harder problems on the CCC... dwite is sort of a joke if you ask me. if youre serious about this kind of thing check out www.topcoder.com/tc they hold weekly online contests. the next 2 even have cash prizes! if you go on this site regularly untill your in grade 12 you should be able to be in the top 3 in canada in CCC. ----------------------------------- Martin Wed Jun 22, 2005 2:53 pm ----------------------------------- This was a stupid dwite question. The shortest path is easy to calculate, but the solution is not always efficient. Think of it like this: in actuality, would you like the shortest path, or a path that is probably the shortest (and if not, very close to being the shortest) and takes significantly less memory to calculate? Google for the A-star algorithm. A much better solution. ----------------------------------- zylum Wed Jun 22, 2005 3:09 pm ----------------------------------- ya i suggested A* but this is a dwite question... with the time constraints and his skill level i think a simple recursive solution would be best for him especially if the problem constraints are small (dwite rarely has tight constraints) ----------------------------------- MysticVegeta Thu Jun 23, 2005 10:58 am ----------------------------------- Zylum : I registered the Top Coder thingy. heh. It doesnt have Turing as your default language so i put C++, lol. I can solve some of them in C++ that i can solve in Turing. Anyways, I will search for the A-star algorithm and maybe i will just use the 2d boolean array, code is in progress, lets see how many months it takes... :lol: ----------------------------------- zylum Thu Jun 23, 2005 1:46 pm ----------------------------------- good job! the next contest is this wednesday, unfortunately i wont be able to participate this week. :cry: ----------------------------------- MysticVegeta Thu Jun 23, 2005 1:56 pm ----------------------------------- you see i was in this practice arena and i was a doing a 250 question so in the code typing area i put somethinglike this -> #include int main() { cout >> "eh?"; } Why did that have problems compiling? Gave me the following errors: Your code did not compile: errors compiling: In file included from top level:3: StringContents.cc: In function `int main()': StringContents.cc:3: `cout' undeclared (first use this function) StringContents.cc:3: (Each undeclared identifier is reported only once for each function it appears in.) In file included from top level:10: Your class or method was improperly declared: In function `std::vector _wrapper::thunk(std::vector)': Your class or method was improperly declared:20003: invalid use of undefined type `struct StringContents' end of your submission:10030: forward declaration of `struct StringContents' ----------------------------------- zylum Thu Jun 23, 2005 2:06 pm ----------------------------------- //#defines go here using namespace std; struct ClassName { public: returnType methodName (varType parameters) { //your code goes here return whatEver; // must be of type returnType ie int or double or } }; your C code always has to have that structure. what they do to test your code is create an instance of your class and call the method in the class. therefore it is necessary to declare the class and method otherwise you will get errors. ----------------------------------- thegoose Thu Jun 23, 2005 4:23 pm ----------------------------------- This was a stupid dwite question. The shortest path is easy to calculate, but the solution is not always efficient. Think of it like this: in actuality, would you like the shortest path, or a path that is probably the shortest (and if not, very close to being the shortest) and takes significantly less memory to calculate? Google for the A-star algorithm. A much better solution. Actually in this case with a grid maze, the shortest path could be calculated in O(RC) time and O(RC) memory using BFS, where R is the number of rows and C is the number of columns. Since the reading the whole maze in takes is O(RC) time and the maze takes O(RC) storage, there is no point not doing the shortest path. (A* is also considerably harder to code compared to BFS from what I heard) ----------------------------------- MysticVegeta Fri Jul 29, 2005 9:08 pm ----------------------------------- Sorry i know its been over a month, but i coded the problem using recursions but runs really really really slow. No way any processor would be able to debug it in 2.5 seconds, and what is this algorithm you are talking about?? Where can i find info on this? I would do a google on this but i dont know what to search for... :oops: ----------------------------------- zylum Fri Jul 29, 2005 10:08 pm ----------------------------------- var file : int var fileName : string := "data1.txt" var rows, cols : int var currentPath, bestPath : int := 0 bestPath := 1000000 var sx, sy, fx, fy : int open : file, fileName, get get : file, rows get : file, cols var maze : array 0 .. cols + 1, 0 .. rows + 1 of boolean %initialize maze for i : 0 .. cols + 1 for j : 0 .. rows + 1 maze (i, j) := false end for end for %read file and fill maze array. also find start and finish point. var temp : string for y : 1 .. rows get : file, temp for x : 1 .. cols if temp (x) = '.' then maze (x, y) := true elsif temp (x) = 'A' then maze (x, y) := true sx := x sy := y elsif temp (x) = 'B' then maze (x, y) := true fx := x fy := y end if end for end for %recursive solution (Depth First Search) proc solve (x, y : int) if ~maze (x, y) or currentPath >= bestPath then return elsif x = fx and y = fy then if bestPath > currentPath + 1 then bestPath := currentPath + 1 end if return end if maze (x, y) := false currentPath += 1 solve (x + 1, y) solve (x - 1, y) solve (x, y + 1) solve (x, y - 1) maze (x, y) := true currentPath -= 1 end solve solve (sx, sy) put "Best Path: ", bestPath - 2, " Time: ", Time.Elapsed / 1000 happy? im not sure how large your test data will be but this should work fine... ----------------------------------- MysticVegeta Sat Jul 30, 2005 3:33 pm ----------------------------------- Input: 5 5 #A### #...# ###.# #...# #B### 10 8 ######## #....#.# ###....# A.#.##.# #....#.# ###..#.# #...##.B #..##..# ##.....# ######## Expected Output: 7 13 Output: 9 15 Sry, it doesnt work. ----------------------------------- zylum Sat Jul 30, 2005 3:39 pm ----------------------------------- common, both the answers are off by 2.. shouldnt it be obvious that my solution counts the first and last positions (A and B)... so to fix that all you have to do is subtract 2 from the final answer... :? ----------------------------------- MysticVegeta Sun Jul 31, 2005 8:26 am ----------------------------------- hehe lol i was trying to get you scared there. :) apparently you are too smart for that, :cry: