• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

July Newsletter Puzzle (Maze Solver)

 
Sheriff
Posts: 6450
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

This month's puzzle is courtesy of Jim Yingst.


Maze Solver


Given an input ascii representation of a maze, write a program to find and
display a path from the start point of the maze to the end point of the maze.
The output should be a textual representation of the path through the maze from
start to finish. It is suggested to use a series of '.' (period) symbols to
indicate the path through the maze.


Notes:
  • No diagonal moves are allowed.
  • For an extra challenge, if there are multiple paths from start to finish,

  • find the path leading to the shortest solution.

    Legend
    OStart
    XFinish
    +Wall


    Maze #1

    <pre>+++++++++++++++
    + + + + +
    + + + + + +
    + +++ +++++ + +
    O + +++ X
    +++ +++++ +++
    + + +++ + +
    + + + +
    +++++++++++++++</pre>

    Maze #2

    <pre>+++++++++++++++++++++++++
    + + +
    + +++++++ + + +++++++++ +
    + + + + + +
    + +++++ +++ + +++ +++ + +
    + + + + + + + + +
    +++ + + + + +++ +++ + + +
    + +O + + + +X + +
    + +++++ + + +++++ +++++++
    + + + + + +
    +++++ + +++ + + + + +++ +
    + + + + + + + +
    + +++ + +++++ + +++++ +++
    + + + +
    +++++++++++++++++++++++++</pre>

     
 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This is serious brute force:

Here is the file I ran it against:

For results
 
Ranch Hand
Posts: 4632
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Not really sure this is the way you want an answer, but here goes anyway (actually this is a bit similar to the word & knights tour puzzles)
 
Ranch Hand
Posts: 83
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My solution is non-recursive and breadth-first. It could use some polish, but it's getting REALLY late :-)
MazeSolver.java

Maze.java

Graph.java

MyPoint.java

Vertex.java

Edge.java

Path.java
 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi, this is my first ever message.. here is my version.. its pretty vanila...

[ July 11, 2003: Message edited by: Chandaka Fernando ]
[edited to add CODE tags and disable smilies --JM]
[ July 11, 2003: Message edited by: Jason Menard ]
 
Ranch Hand
Posts: 195
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is mine:
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's a solution that should return the shortest path every time unless I messed up my implementation of Djisktra's algorithm:
Class MazeBuilder (contains main method):

Cell.java:

MazeSolver.java

[edited to turn off Dave's smilies ;-) -- JM]
[ July 11, 2003: Message edited by: Jason Menard ]
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yup. I messed it up -- not the shortest path (I was doing my own interpretation of the textbook version designed in a more human-friendly manner, but apparently I implemented David's algorithm and not Djikstras). I think I forgot to sort some stuff. Time to debug...
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I seem to have fixed the problem, but I took a shortcut at some cost. Java doesn't come with a built-in priority heap implementation, so I just use a list and keep sorting it every time I add a few elements. Hackish, but at least it works and I know where to look if it ever needs to be faster.
MazeSolver.java (version 2):
 
Stan James
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Cool. I borrowed the optimization to keep track of the shortest path to each cell and continue recursion only if we're doing better than before. Added 4 lines of code.
This is refactored into better objects than before, no longer compiles as a single file. The solver is now an interface for a strategey; if you want to just work on a new solver for a char[][] representation of the maze, feel free to grab the rest.
 
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What a wonderful thread. You guys are really !
I think one may try concurrency here for the improvement of performence - suppose we implemented a universal maze loader so that can load different mazes, including very huge ones . Let tow objects start off concurrently from the entry and exit of the maze, and see if they can meet somewhere in the maze. And, if breath-first searching is implemented, every branch point can also has its several threads.
For David's solution, the idea is excellent. However I have question whether Djiskra's algorithm is the very suitable here. I guess a maze would have no more than 100 possible solutions - keep the different length value of every possible solution path in a list, then find out the shortest one - so that a naiver/simpler algorithm is not necessarily slower for a maze.
Maybe the maze puzzle can be also implemented via some kind of adjacency matrix other than adjacency list. I hope I could have time for it after all my homework of theoretical proofs there....

Regards,
Ellen
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Consider this maze:

(Note -- this doesn't look right because spaces aren't as wide as other characters ) Imagine that the right wall is actually at the right.
In order to find the best solution with the naive solution, you need to try every possible path. .
You might try to be clever to not looking at paths longer than one's you've already found, but look at the maze above. Suppose you tried to solve it by first looking up, then left, then down, then right. The first solution you find will be the absolute worst one, zig-zagging up and down until it finally hits the X. The next one will be only slightly better, since the beginning of the path will be largely unchanged. It will continually only find new solutions that are just a little bit better than the current optimum, thus severely limiting the power of the heuristic.
Now there could be heuristics to avoid this kind of problem. You could, for example, try each direction in random order. A less reliable technique would be to try looking first in directions that lead closer to the solution (although that would also allow evil worst-case scenarios to be constructed).
I'm about to make a small modification to my Djikstra implementation so it runs in O(V^2 + E) time and constant memory. Reliable, effective, scalable, and predictable.
[ July 12, 2003: Message edited by: David Weitzman ]
[Attempted to fix appearance in Mozilla - Jim]
[ July 13, 2003: Message edited by: Jim Yingst ]
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Okay, I don't expect to change my solution anymore:
MazeSolver.java
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ellen, if you want to do some concurrent computation testing then a good tool to use would probably be Doug Lea's Fork-Join tasks (available as part of util.concurrent.
 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
" Multi-threaded programs will be easier to write with the new concurrency utilities in JSR 166." from here
Seems Doug Lea's concurrency utility package is being added to the J2SE library.

regards,
Ellen
 
Stan James
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the "worst case" type test. With my optimizations in place (also added stop when there is a shorter solution than current length) I handle that one ok, but without them there is either a bug in my solver or it takes hundreds of millions of tries to find all the dead end paths. (Guess which. I gave up waiting to find out.)
I really like the non-recursive approach David is showing. I was a music major, not CS, so I pick up these fancy schmancy Djikstra algorithms slowly.
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Ellen Zhao:
" Multi-threaded programs will be easier to write with the new concurrency utilities in JSR 166." from here
Seems Doug Lea's concurrency utility package is


JSR 166 is a bit more expansive in scope than Lea's package, since Lea and Bloch et al. have permission to modify core classes like Thread. Another cool plus is that it will add a Queue interface to the collection framework and use that instead of Channel.
However it won't contain Fork-Join tasks for the humble computer scientist trying to exploit multiple processors. In Lea's words (from the concurency interest mailing list): "This
was just a decision about generality -- FJTasks are too nichy to put
into JDK. I'll continue to make them available separately though"
 
Brace yourself while corporate america tries to sell us its things. Some day they will chill and use tiny ads.
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic