• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Devaka Cooray
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Junilu Lacar
  • Paul Clapham
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • salvin francis
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

Maze with more exits  RSS feed

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone, i have problem and i need some ideas. i have maze in java entered i and i have to find fastest route to exit.
R-starting point, #-Wall, E-exit .... Function should be recursive , right?

Example:

############E##
#R       ###           #
###      ###          E
###      ###      ###
###                  ###
###############
 
Marshal
Posts: 6494
441
BSD Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Nikola Mis wrote:Function should be recursive , right?


Why do you think so? I'm not saying Yes or No, I'm just asking you.
 
Nikola Mis
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:Why do you think so? I'm not saying Yes or No, I'm just asking you.


Well , i need to find all exits and then fastest route to every exit and then print fastest like RRLLDU(right,left,down....)
So i think it's better with it.
 
Marshal
Posts: 62819
203
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you will have to provide more explanation than that.
 
Nikola Mis
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I think you will have to provide more explanation than that.


Ok i will try, in this given maze, first and only step is to go R(right),
on the second right you can go right and left, if you go left there is end because you cant go up nor down nor left, you can only go back right and that's same route so 2nd step needs to be R again.
On a 3rd move you can go right and you can go down, now everytime you choose path, you need to call function to check for all moves(R,L,U,D). If you can go all 4 then you should and save route as a ex. string so for first exit you have something like this
( R,R,R,D,D,D,R,R,R,R,R,R,R,U,U,R,R,R) , but also you will have some different paths for same exit with extra steps. I hope you will understand me. And sorry if something is unclear, English is not my 1st language.  
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why does that have to be a recursive solution?
 
Nikola Mis
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well i'm asking. I'm not sure....
 
Campbell Ritchie
Marshal
Posts: 62819
203
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I couldn't see any reason that your solution must be recursive. But I can't remember any maze following algorithms; which algorithm are you using?
 
Nikola Mis
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Didn't decide yet, that's why i wanted to hear ideas.
 
Sheriff
Posts: 12964
217
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I remember correctly, solutions to problems like this tend to lend themselves naturally to recursion. Think of the Visitor Pattern: each point of the path you're on so far would be marked as "visited" so you avoid backtracking and going back over where you've already been before.
 
Junilu Lacar
Sheriff
Posts: 12964
217
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also look up shortest path algorithms -- you will need to figure out how you're going to handle walls and exit points. Walls so that you know where it's not possible to turn and exit points so you know when you've reached a terminal state. Again, these kinds of algorithms tend to be recursive as well.
 
Junilu Lacar
Sheriff
Posts: 12964
217
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you happen to stumble upon the Google Easter Egg challenge, there's at least a couple of problems in the series that involve these kinds of algorithms. The one I had to solve had one condition where you could choose to bust through a wall to take a "shortcut" but you could only this once while navigating through the maze. You had to find the optimal place to do that to get the shortest path. It was actually a fun challenge to solve. Tough but challenging, so it was quite fun in hindsight, after you get all Google's tests to pass. A non-recursive solution I think would give unacceptable performance; the solution that passed all the tests, which included checks for acceptable performance, was recursive.
 
Liutauras Vilda
Marshal
Posts: 6494
441
BSD Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Such problems are always interesting, and I think I've solved something similar (and very different at the same time) few years back.

Nikola Mis wrote:Ok i will try, in this given maze, first and only step is to go R(right),
on the second right you can go right and left, if you go left there is end because you cant go up nor down nor left, you can only go back right and that's same route so 2nd step needs to be R again.


I think you messed up something here in this explanation, but let's make it clear about the move instructions first.

L (left), R (right), U (up), D (down). That is irrespective which direction you are presumably heading at (really there is no heading direction), so you never look from the character eyes perspective, but rather from the top, similarly as looking to a map (i.e. world map). In which case instructions would be clearer W (west), E (east), N (north), S (south), but ok, you got them as you got. Now read the bold part, and you'll see that what you wrote doesn't make sense, at least to me.

In this map I'd mark the starting position (S in blue) to make it unambiguous. Was that your starting position so you marked first step as R?
############E##
SR       ###           #
###      ###          E
###      ###      ###
###                  ###
###############
 
Nikola Mis
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, that R was misspelled , that is starting point.. I said it can't go up because there is a wall, and when you go right you can go right again or left(up and down are walls)... Choosing the left path you will be back at starting point and again you only have option to go right so that's the wrong way. Problem is given as it is, from eye-bird perspective with left,right,up,down and with two exits.
 
Liutauras Vilda
Marshal
Posts: 6494
441
BSD Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok. Having such typos you could spend the rest of your life trying to figure out why your solution is wrong, while actually not the solution, but misinterpretation of initial requirements.

Neither Campbell, nor I said you should not use recursion, we just questioned why you think you want to go with recursive solution. Indeed, such problems usually are being crunched with recursive solutions.

Now that we said that... try to decompose the problem, forget about the shortest solution.

How about if you would find an exit first, no matter how long path you take? Sticking to that idea in general, you might get puzzled how to figure out where to go. Junilu gave a hint actually already - word "visited".

Now please tell you, whether you get an idea what we are talking about here?

Do you understand what is the recursive function and what kind of parts it consists of usually?

 
Liutauras Vilda
Marshal
Posts: 6494
441
BSD Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nikola, have you done any progress? I'm very keen to see your solution, at least an attempt
 
Master Rancher
Posts: 3080
108
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Be careful with marking cells as being visited. You might miss a shorter route, depending on your seach algorithm.

For those fond of this kind of puzzles, a nice variant can be found on Project Euler, 81-83.
 
Saloon Keeper
Posts: 2137
80
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just wanted to share, a few months ago I was trying to make a similar path finding algorithm and I had come across "A* search algorithm". Hope it helps.
 
Liutauras Vilda
Marshal
Posts: 6494
441
BSD Linux Mac OS X VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:Be careful with marking cells as being visited. You might miss a shorter route


I'd think it is useful for OP first to find an exit ignoring the need of a shortest path towards it. For that purpose blindly used "visited" concept indeed what is needed. Don't know about the shortest path yet, but have some of the ideas floating in my mind.

Piet Souris wrote:For those fond of this kind of puzzles, a nice variant can be found on Project Euler, 81-83.


Piet, thank you for reminding this project, I just had a look to my Project Euler account, unfortunately, I see I've solved only 9 problems back in early 2016. I'm keen on picking up where I left off.
 
Piet Souris
Master Rancher
Posts: 3080
108
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You do not need to follow the problems sequentially. Although the problems state otherwise, I found problem 82 more challenging (i.e. difficult) then problem 83. There I used A* like Salvin mentioned, although my h(n) was 0 (couldn't think of a suitable estimation function). Anyway, it were very nice problems indeed.

For this case, with more than one exit, I simply used BFS, non-recursively. Fast enough, and guaranteed to find the shortest solution (if any).
 
All of the world's problems can be solved in a garden - Geoff Lawton. Tiny ad:
RavenDB is an Open Source NoSQL Database that’s fully transactional (ACID) across your database
https://coderanch.com/t/704633/RavenDB-Open-Source-NoSQL-Database
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!