hi,
i want to develop a lisp pure recursive program (no iteration and no
assignment) to find the shortest path in a labyrinth! someone as same idea?
Thanks
Andrea
* "CheTeFreGa" <·······@tiscali.it>
| i want to develop a lisp pure recursive program (no iteration and no
| assignment) to find the shortest path in a labyrinth!
Why this irrelevant restriction on yourself? Homework assignment?
--
Erik Naggum, Oslo, Norway
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
Yes is a restriction of my Software Engineering prof.!
can you help me, Erik?
"Erik Naggum" <····@naggum.no> ha scritto nel messaggio
·····················@naggum.no...
> * "CheTeFreGa" <·······@tiscali.it>
> | i want to develop a lisp pure recursive program (no iteration and no
> | assignment) to find the shortest path in a labyrinth!
>
> Why this irrelevant restriction on yourself? Homework assignment?
>
> --
> Erik Naggum, Oslo, Norway
>
> Act from reason, and failure makes you rethink and study harder.
> Act from faith, and failure makes you blame someone and push harder.
* "CheTeFreGa" <·······@tiscali.it>
| Yes is a restriction of my Software Engineering prof.!
| can you help me, Erik?
Please do not quote the entire previous article when you respond. Place
your text below the short relevant extractions of the quoted article, like
other people whose news articles you read do. Thank you.
Na�ve labyrinth traversal is very simple. At every juncture, try every
direction (except the one you came from) in order as long as each attempt
fails, but if you have only one choice, just keep going, return failure if
none of your directions yield success. Success is defined as finding an
exit. This is a nice, clean, recursive function with no assignment. An
alternative approach, which is not naturally recursive, is to keep left and
remember where you were so you backtrack when you walk back along the same
path you came. An interesting problem is how you deal with circular paths
in both approaches. I assume you know whether you have them or not.
--
Erik Naggum, Oslo, Norway
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
In article <············@lacerta.tiscalinet.it>, CheTeFreGa wrote:
> hi,
> i want to develop a lisp pure recursive program (no iteration and no
> assignment) to find the shortest path in a labyrinth! someone as same idea?
Pour water into the maze at the starting point, and remove water at the
termination point. When the flow stabilizes, start adding dye to the incoming
water. The paths will become obvious, since they are the only ones with live
flow; all the dead ends become stillwater, into which the dye can only
travel by slow diffusion. The shortest paths will be the ones that are dyed
first; when the first trace of dye hits the termination point, be sure to snap
a photograph.
In an attempt to throw the authorities off his trail, Kaz Kylheku <···@ashi.footprints.net> transmitted:
> In article <············@lacerta.tiscalinet.it>, CheTeFreGa wrote:
>> i want to develop a lisp pure recursive program (no iteration and
>> no assignment) to find the shortest path in a labyrinth! someone as
>> same idea?
>
> Pour water into the maze at the starting point, and remove water at
> the termination point. When the flow stabilizes, start adding dye to
> the incoming water. The paths will become obvious, since they are
> the only ones with live flow; all the dead ends become stillwater,
> into which the dye can only travel by slow diffusion. The shortest
> paths will be the ones that are dyed first; when the first trace of
> dye hits the termination point, be sure to snap a photograph.
You could probably program that using a computational array, with a
cell for each location in the maze, each having a directional pressure
metric.
You add a unit of water at the start point, and then go through a
number of generations of evolution of the system, letting the pressure
propagate from cell to cell, and watch the water flow. Once the
system stabilizes, so that for every unit of water introduced, one
flows out, you can then introduce one more unit of water, and follow
it to wherever it goes, which will be the shortest path.
Coding it as a simulation of an analog computer would _surely_ be
worth extra credit...
--
(reverse (concatenate 'string ·············@" "sirhc"))
http://www.ntlug.org/~cbbrowne/sgml.html
"I have stopped reading Stephen King novels. Now I just read C code
instead." -- Richard A. O'Keefe
In article <···············@ID-125932.news.dfncis.de>, Christopher Browne wrote:
> In an attempt to throw the authorities off his trail, Kaz Kylheku <···@ashi.footprints.net> transmitted:
>> In article <············@lacerta.tiscalinet.it>, CheTeFreGa wrote:
>>> i want to develop a lisp pure recursive program (no iteration and
>>> no assignment) to find the shortest path in a labyrinth! someone as
>>> same idea?
>>
>> Pour water into the maze at the starting point, and remove water at
>> the termination point.
[snip]
> You could probably program that using a computational array, with a
> cell for each location in the maze, each having a directional pressure
> metric.
But of course in this problem, the little cell housing the undergraduate has
the maximal pressure metric. ;)
Kaz Kylheku <···@ashi.footprints.net> writes:
> The shortest paths will be the ones that are dyed first
Don't the widths of the corridors have any effect?
>>>>> "Kaz" == Kaz Kylheku <···@ashi.footprints.net> writes:
Kaz> In article <············@lacerta.tiscalinet.it>, CheTeFreGa
Kaz> wrote:
Kaz> Pour water into the maze at the starting point, and remove
Kaz> water at the termination point. When the flow stabilizes,
Kaz> start adding dye to the incoming water. The paths will become
Kaz> obvious, since they are the only ones with live flow; all the
Kaz> dead ends become stillwater, into which the dye can only
Kaz> travel by slow diffusion. The shortest paths will be the
Kaz> ones that are dyed first; when the first trace of dye hits
Kaz> the termination point, be sure to snap a photograph.
I do not agree.
A******
*
* *
* *
B****** **********exit
at the moment the dye hits the exit are A-exit and B-exit equally short
paths?
Immanuel
* Immanuel Litzroth wrote:
> I do not agree.
> A******
> *
> * *
> * *
> B****** **********exit
> at the moment the dye hits the exit are A-exit and B-exit equally short
> paths?
This maze has more than two portals. If you want to use Kaz's trick
for such a maze then you need to (1) pick the entrance and exit you
care about and then (2) block off all other portals by riveting steel
plates to them.
--tim
In an attempt to throw the authorities off his trail, Immanuel Litzroth <·········@enfocus.be> transmitted:
>>>>>> "Kaz" == Kaz Kylheku <···@ashi.footprints.net> writes:
>
> Kaz> In article <············@lacerta.tiscalinet.it>, CheTeFreGa
> Kaz> wrote:
> Kaz> Pour water into the maze at the starting point, and remove
> Kaz> water at the termination point. When the flow stabilizes,
> Kaz> start adding dye to the incoming water. The paths will become
> Kaz> obvious, since they are the only ones with live flow; all the
> Kaz> dead ends become stillwater, into which the dye can only
> Kaz> travel by slow diffusion. The shortest paths will be the
> Kaz> ones that are dyed first; when the first trace of dye hits
> Kaz> the termination point, be sure to snap a photograph.
>
> I do not agree.
>
>
> A******
> *
> * *
> * *
> B****** **********exit
>
> at the moment the dye hits the exit are A-exit and B-exit equally short
> paths?
Did you add dye at _both_ A and B?
You may be describing a true problem, but it needs to be characterized
differently...
*****A*****
* *
C***** * *
* * *
*B****** **********exit
What actually happens is that you introduce dye at point C. That dye
will flow, perhaps down multiple simultaneous paths, towards the exit.
If the paths involving A and B are both "dyed," that _is_ an
indication that those paths are both equally short. The dye doesn't
start at either A or B; it starts at the entrance.
--
(reverse (concatenate 'string ·············@" "enworbbc"))
http://www.ntlug.org/~cbbrowne/finances.html
Rules of the Evil Overlord #167. "If I am recruiting to find someone
to run my computer systems, and my choice is between the brilliant
programmer who's head of the world's largest international technology
conglomerate and an obnoxious 15-year-old dork who's trying to impress
his dream girl, I'll take the brat and let the hero get stuck with the
genius." <http://www.eviloverlord.com/>
Immanuel Litzroth <·········@enfocus.be> wrote in message news:<··············@enfocus.be>...
> >>>>> "Kaz" == Kaz Kylheku <···@ashi.footprints.net> writes:
>
> Kaz> In article <············@lacerta.tiscalinet.it>, CheTeFreGa
> Kaz> wrote:
> Kaz> Pour water into the maze at the starting point, and remove
> Kaz> water at the termination point. When the flow stabilizes,
> Kaz> start adding dye to the incoming water. The paths will become
> Kaz> obvious, since they are the only ones with live flow; all the
> Kaz> dead ends become stillwater, into which the dye can only
> Kaz> travel by slow diffusion. The shortest paths will be the
> Kaz> ones that are dyed first; when the first trace of dye hits
> Kaz> the termination point, be sure to snap a photograph.
>
> I do not agree.
>
>
> A******
> *
> * *
> * *
> B****** **********exit
>
> at the moment the dye hits the exit are A-exit and B-exit equally short
> paths?
> Immanuel
The water is being added at one point, so it would flow right to left
in this picture, emanating from the point marked exit, to the points
marked A and B. Adding dye at 'exit' would cause it to reach A before B.
>>>>> "Kaz" == Kaz Kylheku <···@ashi.footprints.net> writes:
Kaz> The water is being added at one point, so it would flow right
Kaz> to left in this picture, emanating from the point marked
Kaz> exit, to the points marked A and B. Adding dye at 'exit'
Kaz> would cause it to reach A before B.
If two paths from input to output share a common subpath at the end
there is no way for know which path "colored" the common
subpath.
In the drawing the ink flows from left to right. I only drew a part
of the maze. Hook up A and B to a common input. Assume input-A and
input-B are equally long. According to your algorithm the ink will
reach A and B at the same time. Let's call the beginning of the
common subpath C. If A-exit > B-C and and A-exit < B-exit then
input-B-C-exit will be completely colored at the time input-A-C-exit
is although that first path is longer than the second.
Immanuel
Immanuel Litzroth <·········@enfocus.be> wrote in message news:<··············@enfocus.be>...
> >>>>> "Kaz" == Kaz Kylheku <···@ashi.footprints.net> writes:
>
> Kaz> The water is being added at one point, so it would flow right
> Kaz> to left in this picture, emanating from the point marked
> Kaz> exit, to the points marked A and B. Adding dye at 'exit'
> Kaz> would cause it to reach A before B.
>
>
> If two paths from input to output share a common subpath at the end
> there is no way for know which path "colored" the common
> subpath.
Ah yes; because the solution for the subproblem disappears by
the time the overall problem is solved; so you would have to
take a whole lot more photographs. There can be some longer
subpath which merges with the shorter one way before the dye
reaches the exit, and so by then the longer and shorter path
are colored.
In article <···························@posting.google.com>, Kaz Kylheku wrote:
> Immanuel Litzroth <·········@enfocus.be> wrote in message news:<··············@enfocus.be>...
>> >>>>> "Kaz" == Kaz Kylheku <···@ashi.footprints.net> writes:
>>
>> Kaz> The water is being added at one point, so it would flow right
>> Kaz> to left in this picture, emanating from the point marked
>> Kaz> exit, to the points marked A and B. Adding dye at 'exit'
>> Kaz> would cause it to reach A before B.
>>
>>
>> If two paths from input to output share a common subpath at the end
>> there is no way for know which path "colored" the common
>> subpath.
>
> Ah yes; because the solution for the subproblem disappears by
> the time the overall problem is solved; so you would have to
> take a whole lot more photographs. There can be some longer
> subpath which merges with the shorter one way before the dye
> reaches the exit, and so by then the longer and shorter path
> are colored.
Well if your metric is distance then just measure the colored
paths through the maze and the smallest number wins.
marc
If you are going to discuss advanced path finding methods, why not use
Autonomous Agents/ Ant Colony Optimization / Swarm Intelligence/
whatever-else-you-may-call-it?
Its on a similar theme to flooding, where you send semi-smart agents
along several paths, and they co-operate to find the exit. It'll be a
pretty interesting multi-threaded simulation, easily done in Java. If
you go for Ant Colony Optimization, each "ant" agent will leave a
pheromone trail to show where it has been, and other ants will have to
deduce from the concentration of the pheromone trail what it implies.
This problem wil have the same connotations as the flood+die problem
kundi
In an attempt to throw the authorities off his trail, "CheTeFreGa" <·······@tiscali.it> transmitted:
> i want to develop a lisp pure recursive program (no iteration and no
> assignment) to find the shortest path in a labyrinth! someone as
> same idea?
If this is homework, and you're stumped, you should probably see about
meeting with one of the teaching assistants or with the professor to
see if you can get some extra help.
comp.lang.lisp isn't a "free homework consulting service."
--
(concatenate 'string "cbbrowne" ·@acm.org")
http://cbbrowne.com/info/rdbms.html#COURSEWORK
Signs of a Klingon Programmer - 15. "Python? That is for children. A
Klingon Warrior uses only machine code, keyed in on the front panel
switches in raw binary."
On Sat, 24 Aug 2002 10:44:40 +0200, CheTeFreGa <·······@tiscali.it> wrote:
>hi,
> i want to develop a lisp pure recursive program (no iteration and no
>assignment) to find the shortest path in a labyrinth! someone as same idea?
you should hope that posting your assignment here isn't a violation of your
schools' cheating policy, and further hope that your professor is not reading
this ng.
one way to solve this problem, but i don't recall if this guarantees shortest
path, is A* search with manhatten distance as your distance heuristic. i've
seen this approach to the 15-puzzle w/ no iteration, no assignment and fully
recursive.
--
===============================================================================
Christopher Jon Miller Drink and dance and laugh and lie
Parallel Systems Engineer Love, the reeling midnight through
For tomorrow we shall die!
(But, alas, we never do.)
-- Dorothy Parker, "The Flaw in Paganism"
===============================================================================
In article <·················@bird.hoax.qwest.net>, ··@bird.hoax.qwest.net
() wrote:
> On Sat, 24 Aug 2002 10:44:40 +0200, CheTeFreGa <·······@tiscali.it> wrote:
>>hi,
>> i want to develop a lisp pure recursive program (no iteration and no
>>assignment) to find the shortest path in a labyrinth! someone as same idea?
>
> you should hope that posting your assignment here isn't a violation of your
> schools' cheating policy, and further hope that your professor is not reading
> this ng.
He could find solutions without leaving a trace of his activity by doing quiet
research at a library.
I think that the obsession some American schools have with finding cheaters is
way over the top. Heaven forbid someone should actually use some existing
resources to learn.
No wonder the schools are cranking out wheel-reinventors.
In the real world, there is no excuse for inventing an algorithm if you can
copy it from somewhere. It's called wasting your employer's dollars.
The real skill is crafting it into a quality implementation; that skill
is something you can't fake.
Software development is not an academic activity. Programs are not
academic papers, which have to demonstrate original research.
I would give the students this type of homework: ``Try to find some computer
science literature about maze solving algorithms. Provide a citation to the
work, and try to adapt its approach to the programming language we are using.
In other words, show that you can do the actual job that you are probably
going to do when you get out of here. If instead you have academic
aspirations, substitute the programming part of the homework by citing at least
one improvement to that algorithm from later literature, and then suggest your
own improvement over that one.''