MakaroF wrote:
> Hi! If you can, please, help me. I need write some aplication on LISP.
> "MAZE". We need enter maze, and find exit amd parhs to exit.
Have you tried (apropos "mouse") ?
Will
In article
<····································@1g2000hsl.googlegroups.com>,
William D Clinger <········@yahoo.com> wrote:
> MakaroF wrote:
> > Hi! If you can, please, help me. I need write some aplication on LISP.
> > "MAZE". We need enter maze, and find exit amd parhs to exit.
>
> Have you tried (apropos "mouse") ?
>
> Will
LOOKS LIKE mAKAROf IS TRAPPED IN SOME MAZE, BUT HAS INTERNET ACCESS.
I'M NOT SURE IF LISP CAN HELP HIM. MAYBE ARIADNE'S THREAD
WILL HELP? IF YOU HAVE ACCESS TO AN OLD LISP MACHINE, TRY THE
COMMAND: FIND SYMBOL ARIADNE .
--
http://lispm.dyndns.org/
On Jan 2, 12:44 pm, MakaroF <·········@gmail.com> wrote:
[snip]
> We need enter maze, and find exit amd parhs to exit.
Whenever I get trapped in a maze, I simply place my right hand on the
wall and walk until I find the cheese/exit. And, yes, there's an
algorithm in the preceding statement.
On Jan 2, 4:38 pm, vanekl <·····@acd.net> wrote:
> On Jan 2, 12:44 pm, MakaroF <·········@gmail.com> wrote:
> [snip]
>
> > We need enter maze, and find exit amd parhs to exit.
>
> Whenever I get trapped in a maze, I simply place my right hand on the
> wall and walk until I find the cheese/exit. And, yes, there's an
> algorithm in the preceding statement.
And here's the Lisp code. [This compiles in SBCL, albeit with a few
warnings.]
(defun right-hand-search (maze state goal-f)
(if (funcall goal-f (funcall state))
t ;; solution state found
(if (see-cat (funcall state))
(throw 'err "GAME OVER")
(if (eql (funcall state) (entrance maze))
nil ;; did not find solution; came full circle
;; continue search
(right-hand-search maze (funcall state 'walk-some-more) goal-
f)))))
(defun right-hand-search-init (maze)
(let ((location (entrance maze)))
(place-right-hand-on-wall maze location)
(lambda(&optional do-walk)
(when do-walk
(setf location (walk maze location)))
location)))
(defun search-maze (maze)
;; search maze for cheese using the right-hand-search algorithm
(right-hand-search
maze
(right-hand-search-init maze)
(lambda(location)(contains location 'cheese))))
On Wed, 2 Jan 2008 08:38:20 -0800 (PST), vanekl <·····@acd.net> wrote:
>On Jan 2, 12:44�pm, MakaroF <·········@gmail.com> wrote:
>[snip]
>> We need enter maze, and find exit amd parhs to exit.
>
>Whenever I get trapped in a maze, I simply place my right hand on the
>wall and walk until I find the cheese/exit. And, yes, there's an
>algorithm in the preceding statement.
It's not much help if you wake up somewhere in the middle and the maze
is constructed with loops.
George
--
for email reply remove "/" from address
On Jan 3, 5:05 am, George Neuner <·········@/comcast.net> wrote:
> On Wed, 2 Jan 2008 08:38:20 -0800 (PST), vanekl <·····@acd.net> wrote:
> >On Jan 2, 12:44 pm, MakaroF <·········@gmail.com> wrote:
> >[snip]
> >> We need enter maze, and find exit amd parhs to exit.
>
> >Whenever I get trapped in a maze, I simply place my right hand on the
> >wall and walk until I find the cheese/exit. And, yes, there's an
> >algorithm in the preceding statement.
>
> It's not much help if you wake up somewhere in the middle and the maze
> is constructed with loops.
>
> George
> --
> for email reply remove "/" from address
You're right George, this algo doesn't work in all circumstances. I
guess a conventional BFS or DFS would be more practical.
On Jan 3, 2:05 am, vanekl <·····@acd.net> wrote:
> On Jan 3, 5:05 am, George Neuner <·········@/comcast.net> wrote:
>
> > On Wed, 2 Jan 2008 08:38:20 -0800 (PST), vanekl <·····@acd.net> wrote:
> > >On Jan 2, 12:44 pm, MakaroF <·········@gmail.com> wrote:
> > >[snip]
> > >> We need enter maze, and find exit amd parhs to exit.
>
> > >Whenever I get trapped in a maze, I simply place my right hand on the
> > >wall and walk until I find the cheese/exit. And, yes, there's an
> > >algorithm in the preceding statement.
>
> > It's not much help if you wake up somewhere in the middle and the maze
> > is constructed with loops.
>
> > George
> > --
> > for email reply remove "/" from address
>
> You're right George, this algo doesn't work in all circumstances. I
> guess a conventional BFS or DFS would be more practical.
I was under the impression that conventional DFS and the right-hand-on-
the-wall traversal were essentially the same thing. DFS will have the
same problem with loops if there isn't a mechanism to prevent
expanding the same state twice. BFS could use lots of memory if states
are expanded multiple times, but would eventually find a path. I'd
probably end up using one of the conventional searches, but there's an
interesting writeup of Zippers applied to mazes (so as to use the
[left|right]-hand-rule) at http://en.wikibooks.org/wiki/Haskell/Zippers
. It uses Haskell, but, of course, you can use the same technique in
Lisp.
//J
On Jan 3, 1:18 pm, Joshua Taylor <···········@gmail.com> wrote:
> On Jan 3, 2:05 am, vanekl <·····@acd.net> wrote:
>
>
>
> > On Jan 3, 5:05 am, George Neuner <·········@/comcast.net> wrote:
>
> > > On Wed, 2 Jan 2008 08:38:20 -0800 (PST), vanekl <·····@acd.net> wrote:
> > > >On Jan 2, 12:44 pm, MakaroF <·········@gmail.com> wrote:
> > > >[snip]
> > > >> We need enter maze, and find exit amd parhs to exit.
>
> > > >Whenever I get trapped in a maze, I simply place my right hand on the
> > > >wall and walk until I find the cheese/exit. And, yes, there's an
> > > >algorithm in the preceding statement.
>
> > > It's not much help if you wake up somewhere in the middle and the maze
> > > is constructed with loops.
>
> > > George
> > > --
> > > for email reply remove "/" from address
>
> > You're right George, this algo doesn't work in all circumstances. I
> > guess a conventional BFS or DFS would be more practical.
>
> I was under the impression that conventional DFS and the right-hand-on-
> the-wall traversal were essentially the same thing. DFS will have the
> same problem with loops if there isn't a mechanism to prevent
> expanding the same state twice. BFS could use lots of memory if states
> are expanded multiple times, but would eventually find a path. I'd
> probably end up using one of the conventional searches, but there's an
> interesting writeup of Zippers applied to mazes (so as to use the
> [left|right]-hand-rule) athttp://en.wikibooks.org/wiki/Haskell/Zippers
> . It uses Haskell, but, of course, you can use the same technique in
> Lisp.
>
> //J
Ah, rereading that page more carefully, they've started by modeling
the maze as a tree so as to avoid repeating states, which means that
they don't really address the issue of loops in the maze. It's still
an interesting read though.
On Jan 3, 6:18 pm, Joshua Taylor <···········@gmail.com> wrote:
> On Jan 3, 2:05 am, vanekl <·····@acd.net> wrote:
>
>
>
> > On Jan 3, 5:05 am, George Neuner <·········@/comcast.net> wrote:
>
> > > On Wed, 2 Jan 2008 08:38:20 -0800 (PST), vanekl <·····@acd.net> wrote:
> > > >On Jan 2, 12:44 pm, MakaroF <·········@gmail.com> wrote:
> > > >[snip]
> > > >> We need enter maze, and find exit amd parhs to exit.
>
> > > >Whenever I get trapped in a maze, I simply place my right hand on the
> > > >wall and walk until I find the cheese/exit. And, yes, there's an
> > > >algorithm in the preceding statement.
>
> > > It's not much help if you wake up somewhere in the middle and the maze
> > > is constructed with loops.
>
> > > George
> > > --
> > > for email reply remove "/" from address
>
> > You're right George, this algo doesn't work in all circumstances. I
> > guess a conventional BFS or DFS would be more practical.
>
> I was under the impression that conventional DFS and the right-hand-on-
> the-wall traversal were essentially the same thing. DFS will have the
> same problem with loops if there isn't a mechanism to prevent
> expanding the same state twice. BFS could use lots of memory if states
> are expanded multiple times, but would eventually find a path. I'd
> probably end up using one of the conventional searches, but there's an
> interesting writeup of Zippers applied to mazes (so as to use the
> [left|right]-hand-rule) athttp://en.wikibooks.org/wiki/Haskell/Zippers
> . It uses Haskell, but, of course, you can use the same technique in
> Lisp.
>
> //J
It's all in the implementation details. If you code the algo in a
literal (naive) stick-right-hand-on-wall-and-continue-walking-until-
either-you-find-the-cheese-or-you-end-up-in-a-previous-state-such-as-
the-maze-entrance manner, you can get stuck in a cycle.
If, on the other hand, you use an implementation that doesn't follow
old paths (e.g. DFS, as defined by Cormen et al), you will eventually
be guaranteed to search the entire maze.
An example of how the former implementation would fail is if the maze
was constructed of just two boxes, each with one hole, where one of
the boxes is placed inside the other. Let's say the goal state is the
center of the maze. Literally putting your hand on the outside wall
will have you going in circles, never finding the goal. My smart-ass
implementation that I posted to this thread Jan 2, 4:38 would at times
fail to find the cheese.
vaneki wrote:
> If, on the other hand, you use an implementation that doesn't follow
> old paths (e.g. DFS, as defined by Cormen et al), you will eventually
> be guaranteed to search the entire maze.
Another approach is depth-first search to bounded depth.
When iterated over increasing bounds on the search depth,
that will eventually find the goal if it can be found at
all.
Will
On Jan 3, 7:34 pm, William D Clinger <········@yahoo.com> wrote:
> vaneki wrote:
> > If, on the other hand, you use an implementation that doesn't follow
> > old paths (e.g. DFS, as defined by Cormen et al), you will eventually
> > be guaranteed to search the entire maze.
>
> Another approach is depth-first search to bounded depth.
> When iterated over increasing bounds on the search depth,
> that will eventually find the goal if it can be found at
> all.
>
> Will
Yeah, I think the term that is applied to this technique is "iterative
deepening," and is more commonly used where the search space is
extremely large, such as in some game trees.
vanekl <·····@acd.net> writes:
> On Jan 3, 7:34��pm, William D Clinger <········@yahoo.com> wrote:
> > vaneki wrote:
> > > If, on the other hand, you use an implementation that doesn't follow
> > > old paths (e.g. DFS, as defined by Cormen et al), you will eventually
> > > be guaranteed to search the entire maze.
> >
> > Another approach is depth-first search to bounded depth.
> > When iterated over increasing bounds on the search depth,
> > that will eventually find the goal if it can be found at
> > all.
> >
> > Will
>
> Yeah, I think the term that is applied to this technique is "iterative
> deepening," and is more commonly used where the search space is
> extremely large, such as in some game trees.
It's also used as a technique to give you the same effect as
breadth-first search, but without the memory requirements of BFS, since
it uses sequential depth-first searches to explore the space. The cost
of the memory savings is that run-time increases, but if the branching
factor is reasonably high, the actual run-time increase is not all that
great.
--
Thomas A. Russ, USC/Information Sciences Institute
From: Patrick May
Subject: Re: Please, help me! Need some aplication on LISP
Date:
Message-ID: <m2ejcy9wud.fsf@spe.com>
George Neuner <·········@/comcast.net> writes:
> On Wed, 2 Jan 2008 08:38:20 -0800 (PST), vanekl <·····@acd.net> wrote:
>>On Jan 2, 12:44�pm, MakaroF <·········@gmail.com> wrote:
>>[snip]
>>> We need enter maze, and find exit amd parhs to exit.
>>
>>Whenever I get trapped in a maze, I simply place my right hand on
>>the wall and walk until I find the cheese/exit. And, yes, there's an
>>algorithm in the preceding statement.
>
> It's not much help if you wake up somewhere in the middle and the
> maze is constructed with loops.
Wow, your friends are mean. Were you naked and tattooed with
permanent magic marker, too?
Sympathetically,
Patrick
------------------------------------------------------------------------
S P Engineering, Inc. | Large scale, mission-critical, distributed OO
| systems design and implementation.
···@spe.com | (C++, Java, Common Lisp, Jini, middleware, SOA)
On Jan 2, 1:44 pm, MakaroF <·········@gmail.com> wrote:
> Hi! If you can, please, help me. I need write some aplication on LISP.
> "MAZE". We need enter maze, and find exit amd parhs to exit.
The right way to ask for help in this newsgroup is showing your
current effort and asking for tip in a right direction not a complete
solution. If you want someone to solve your homework without doing
any yourself work hire a consultant.
Slobodan