Labyrinth can be represented in the list: L = ((i1, J1) (i2, J2), ...,
(In, JN)), where (ik, jk) is the existence a way from ik room in
jk.
Write function that checks if it can pass from ie room in jm. Show
that path if it exists.
(LABIRINT L ie im)
On Apr 12, 11:53 pm, Aliska <················@gmail.com> wrote:
> Labyrinth can be represented in the list: L = ((i1, J1) (i2, J2), ...,
> (In, JN)), where (ik, jk) is the existence a way from ik room in
> jk.
> Write function that checks if it can pass from ie room in jm. Show
> that path if it exists.
> (LABIRINT L ie im)
Hold your left hand against the "wall". Walk forward, never removing
your hand. If you reach the destination, then print the path. If you
end up back where you started, then no path. Simple enough.
-Jason
On 13 avr, 09:59, Jason <·······@gmail.com> wrote:
> On Apr 12, 11:53 pm, Aliska <················@gmail.com> wrote:
>
> > Labyrinth can be represented in the list: L = ((i1, J1) (i2, J2), ...,
> > (In, JN)), where (ik, jk) is the existence a way from ik room in
> > jk.
> > Write function that checks if it can pass from ie room in jm. Show
> > that path if it exists.
> > (LABIRINT L ie im)
>
> Hold your left hand against the "wall". Walk forward, never removing
> your hand. If you reach the destination, then print the path. If you
> end up back where you started, then no path. Simple enough.
>
> -Jason
Can I write in one function?
Aliska wrote:
> Can I write in one function?
Yes, the non-working version from Jason, and maybe a better solution with
backtracking, both could be written in one function, but usually it is
better for larger programs to structure it in more than one function.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On 13 avr, 10:50, Frank Buss <····@frank-buss.de> wrote:
> Aliska wrote:
> > Can I write in one function?
>
> Yes, the non-working version from Jason, and maybe a better solution with
> backtracking, both could be written in one function, but usually it is
> better for larger programs to structure it in more than one function.
>
> --
> Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
I find this exemple:
defun search_room (point labirint)
(cond ((null labirint) nil)
((eql (caar labirint) point) (second (car labirint)))
(t (search_room point (cdr labirint)))))
can it exemple change for my probleme?
Aliska wrote:
> I find this exemple:
>
> defun search_room (point labirint)
> (cond ((null labirint) nil)
> ((eql (caar labirint) point) (second (car labirint)))
> (t (search_room point (cdr labirint)))))
>
>
> can it exemple change for my probleme?
This looks like a good starting point. Of course, in Common Lisp you would
format it a little bit different:
(defun search-room (point labirint)
(cond ((null labirint) nil)
((eql (caar labirint) point)
(second (car labirint)))
(t (search-room point (cdr labirint)))))
But you are using Google Groups, so you have to switch to a fixed width
font, before you can see it.
If I didn't missed something, this is a solution for your problem, if each
room has exactly two doors. But this was not specified in your problem
description, so you can't assume it.
Is this a homework? Usually we don't do your homework in this newsgroup,
but we can help you, if you say it is a homework and if you show that
you've tried to solve it, but got stuck somewhere. Not saying that it is a
homework can result in funny answers :-)
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> If I didn't missed something, this is a solution for your problem, if each
> room has exactly two doors. But this was not specified in your problem
> description, so you can't assume it.
I just realized that this would be a very boring Labyrinth :-)
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On 13 avr, 11:37, Frank Buss <····@frank-buss.de> wrote:
> Frank Buss wrote:
> > If I didn't missed something, this is a solution for your problem, if each
> > room has exactly two doors. But this was not specified in your problem
> > description, so you can't assume it.
>
> I just realized that this would be a very boring Labyrinth :-)
>
> --
> Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
I'm started in Lisp, I made some functions to practical lessons for
the master, it is a other task, but I don't find a exactly idiea for
this problem where I can start, I need the logic of solving, I'm not
programming in LISP, I have to learn and know the principles of
programming in Lisp
Aliska wrote:
> I'm started in Lisp, I made some functions to practical lessons for
> the master, it is a other task, but I don't find a exactly idiea for
> this problem where I can start, I need the logic of solving, I'm not
> programming in LISP, I have to learn and know the principles of
> programming in Lisp
This doesn't make sense. If you are not programming in Lisp, why do you
have to program in Lisp? If you need an algorithm for solving, only, you
don't need to implement it in Lisp (but would be nice, because then you can
see, if it works).
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On 13 avr, 12:05, Frank Buss <····@frank-buss.de> wrote:
> Aliska wrote:
> > I'm started in Lisp, I made some functions to practical lessons for
> > the master, it is a other task, but I don't find a exactly idiea for
> > this problem where I can start, I need the logic of solving, I'm not
> > programming in LISP, I have to learn and know the principles of
> > programming in Lisp
>
> This doesn't make sense. If you are not programming in Lisp, why do you
> have to program in Lisp? If you need an algorithm for solving, only, you
> don't need to implement it in Lisp (but would be nice, because then you can
> see, if it works).
>
> --
> Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
I am obliged to solve this problem in Lisp :(
Aliska wrote:
> On 13 avr, 12:05, Frank Buss <····@frank-buss.de> wrote:
>> Aliska wrote:
>>> I'm started in Lisp, I made some functions to practical lessons for
>>> the master, it is a other task, but I don't find a exactly idiea for
>>> this problem where I can start, I need the logic of solving, I'm not
>>> programming in LISP, I have to learn and know the principles of
>>> programming in Lisp
>> This doesn't make sense. If you are not programming in Lisp, why do you
>> have to program in Lisp? If you need an algorithm for solving, only, you
>> don't need to implement it in Lisp (but would be nice, because then you can
>> see, if it works).
>>
>> --
>> Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
>
> I am obliged to solve this problem in Lisp :(
Can you solve it in another language?
kt
Aliska wrote:
> I am obliged to solve this problem in Lisp :(
You are lucky, because Lisp is one of the best available language (though
Pascal may be better for programming beginners). Which environment do you
use? The free versions of LispWorks or AllegroCL are nice, if you want an
easy to install and easy to use system (the LispWorks editor can be even
configured NOT to use Emacs keybindings).
But solving your problem is independant of the language you use. First you
have to think about an algorithm, then you can implement it. Do you have an
idea for an algorithm?
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On 13 avr, 12:35, Frank Buss <····@frank-buss.de> wrote:
> Aliska wrote:
> > I am obliged to solve this problem in Lisp :(
>
> You are lucky, because Lisp is one of the best available language (though
> Pascal may be better for programming beginners). Which environment do you
> use? The free versions of LispWorks or AllegroCL are nice, if you want an
> easy to install and easy to use system (the LispWorks editor can be even
> configured NOT to use Emacs keybindings).
>
> But solving your problem is independant of the language you use. First you
> have to think about an algorithm, then you can implement it. Do you have an
> idea for an algorithm?
>
> --
> Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
I'm use CLISP, I think find all couples of items which containing ie
and im, then to find if these couples have elemnts commons and build
the way
Aliska wrote:
> I'm use CLISP,
With SLIME or any other descent editor? You can't enjoy Lisp without an
IDE, where you can hit a compile button (or key stroke) to compile it in a
running Lisp system and a nice REPL with good editing capabilities.
> I think find all couples of items which containing ie
> and im, then to find if these couples have elemnts commons and build
> the way
A more detailed description of the algorithm, maybe testing with examples,
is the first step to the solution. Lisp helps, because you can try out some
aspects of the algorithm interactively and then implement the whole
algorithm with these building blocks.
So if I understand your description correctly, you are thinking of
something like this:
This is a sample labyrinth: ((1 2) (7 8) (4 5) (2 3) (7 2) (9 6))
You have to find a way from 1 to 8. First you identify (1 2) and (7 8).
Then you search the rest recursively, by building a chain: for (1 2), 1 is
the entry, so you search the item which contains 2. This could be (7 2), so
next you search the item which contain 7. This is the target item, (7 8),
so you've found a path, if you save the rooms while searching. After
writing this, you can see that you have to search the first from/to item,
only, the target item is not needed, you need only compare every "to" room
of an item for the target, while searching the next element of the chain.
But you have to think about branches. And the description didn't say, if
the ways are unidirectional (trapdoor) or bidirectional. I assume
unidirectional, because the desciption says "(ik, jk) is the existence of a
way from room ik to room jk", and not that there is a way in the other
direction, too. This makes the implementation a bit simpler, assuming that
the start is always a "from" room element and the target is always a "to"
room element.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On 13 avr, 13:32, Frank Buss <····@frank-buss.de> wrote:
> Aliska wrote:
> > I'm use CLISP,
>
> With SLIME or any other descent editor? You can't enjoy Lisp without an
> IDE, where you can hit a compile button (or key stroke) to compile it in a
> running Lisp system and a nice REPL with good editing capabilities.
>
> > I think find all couples of items which containing ie
> > and im, then to find if these couples have elemnts commons and build
> > the way
>
> A more detailed description of the algorithm, maybe testing with examples,
> is the first step to the solution. Lisp helps, because you can try out some
> aspects of the algorithm interactively and then implement the whole
> algorithm with these building blocks.
>
> So if I understand your description correctly, you are thinking of
> something like this:
>
> This is a sample labyrinth: ((1 2) (7 8) (4 5) (2 3) (7 2) (9 6))
> You have to find a way from 1 to 8. First you identify (1 2) and (7 8).
> Then you search the rest recursively, by building a chain: for (1 2), 1 is
> the entry, so you search the item which contains 2. This could be (7 2), so
> next you search the item which contain 7. This is the target item, (7 8),
> so you've found a path, if you save the rooms while searching. After
> writing this, you can see that you have to search the first from/to item,
> only, the target item is not needed, you need only compare every "to" room
> of an item for the target, while searching the next element of the chain.
>
> But you have to think about branches. And the description didn't say, if
> the ways are unidirectional (trapdoor) or bidirectional. I assume
> unidirectional, because the desciption says "(ik, jk) is the existence of a
> way from room ik to room jk", and not that there is a way in the other
> direction, too. This makes the implementation a bit simpler, assuming that
> the start is always a "from" room element and the target is always a "to"
> room element.
>
> --
> Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
I compile in LISP.BAT of the command line, i write the function in
a .txt document and ai write in command line (load"filename")
On 13 avr, 13:56, Aliska <················@gmail.com> wrote:
> On 13 avr, 13:32, Frank Buss <····@frank-buss.de> wrote:
>
>
>
>
>
> > Aliska wrote:
> > > I'm use CLISP,
>
> > With SLIME or any other descent editor? You can't enjoy Lisp without an
> > IDE, where you can hit a compile button (or key stroke) to compile it in a
> > running Lisp system and a nice REPL with good editing capabilities.
>
> > > I think find all couples of items which containing ie
> > > and im, then to find if these couples have elemnts commons and build
> > > the way
>
> > A more detailed description of the algorithm, maybe testing with examples,
> > is the first step to the solution. Lisp helps, because you can try out some
> > aspects of the algorithm interactively and then implement the whole
> > algorithm with these building blocks.
>
> > So if I understand your description correctly, you are thinking of
> > something like this:
>
> > This is a sample labyrinth: ((1 2) (7 8) (4 5) (2 3) (7 2) (9 6))
> > You have to find a way from 1 to 8. First you identify (1 2) and (7 8).
> > Then you search the rest recursively, by building a chain: for (1 2), 1 is
> > the entry, so you search the item which contains 2. This could be (7 2), so
> > next you search the item which contain 7. This is the target item, (7 8),
> > so you've found a path, if you save the rooms while searching. After
> > writing this, you can see that you have to search the first from/to item,
> > only, the target item is not needed, you need only compare every "to" room
> > of an item for the target, while searching the next element of the chain.
>
> > But you have to think about branches. And the description didn't say, if
> > the ways are unidirectional (trapdoor) or bidirectional. I assume
> > unidirectional, because the desciption says "(ik, jk) is the existence of a
> > way from room ik to room jk", and not that there is a way in the other
> > direction, too. This makes the implementation a bit simpler, assuming that
> > the start is always a "from" room element and the target is always a "to"
> > room element.
>
> > --
> > Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
>
> I compile in LISP.BAT of the command line, i write the function in
> a .txt document and ai write in command line (load"filename")- Masquer le texte des messages précédents -
>
> - Afficher le texte des messages précédents -
And path is bidirectional
On 13 avr, 13:57, Aliska <················@gmail.com> wrote:
> On 13 avr, 13:56, Aliska <················@gmail.com> wrote:
>
>
>
>
>
> > On 13 avr, 13:32, Frank Buss <····@frank-buss.de> wrote:
>
> > > Aliska wrote:
> > > > I'm use CLISP,
>
> > > With SLIME or any other descent editor? You can't enjoy Lisp without an
> > > IDE, where you can hit a compile button (or key stroke) to compile it in a
> > > running Lisp system and a nice REPL with good editing capabilities.
>
> > > > I think find all couples of items which containing ie
> > > > and im, then to find if these couples have elemnts commons and build
> > > > the way
>
> > > A more detailed description of the algorithm, maybe testing with examples,
> > > is the first step to the solution. Lisp helps, because you can try out some
> > > aspects of the algorithm interactively and then implement the whole
> > > algorithm with these building blocks.
>
> > > So if I understand your description correctly, you are thinking of
> > > something like this:
>
> > > This is a sample labyrinth: ((1 2) (7 8) (4 5) (2 3) (7 2) (9 6))
> > > You have to find a way from 1 to 8. First you identify (1 2) and (7 8).
> > > Then you search the rest recursively, by building a chain: for (1 2), 1 is
> > > the entry, so you search the item which contains 2. This could be (7 2), so
> > > next you search the item which contain 7. This is the target item, (7 8),
> > > so you've found a path, if you save the rooms while searching. After
> > > writing this, you can see that you have to search the first from/to item,
> > > only, the target item is not needed, you need only compare every "to" room
> > > of an item for the target, while searching the next element of the chain.
>
> > > But you have to think about branches. And the description didn't say, if
> > > the ways are unidirectional (trapdoor) or bidirectional. I assume
> > > unidirectional, because the desciption says "(ik, jk) is the existence of a
> > > way from room ik to room jk", and not that there is a way in the other
> > > direction, too. This makes the implementation a bit simpler, assuming that
> > > the start is always a "from" room element and the target is always a "to"
> > > room element.
>
> > > --
> > > Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
>
> > I compile in LISP.BAT of the command line, i write the function in
> > a .txt document and ai write in command line (load"filename")- Masquer le texte des messages précédents -
>
> > - Afficher le texte des messages précédents -
>
> And path is bidirectional- Masquer le texte des messages précédents -
>
> - Afficher le texte des messages précédents -
I have the list L=((A B)(A C)(A G)(B D)(B F)(D H)(E F)(E G))
it existe two ways ( (A B)(B E)(E F)) other ((A G) (G E)(E F)), but i
don't show both ways, it is enough to show one way
Aliska wrote:
>> I compile in LISP.BAT of the command line, i write the function in
>> a .txt document and ai write in command line (load"filename")
Ok, this is not a good idea, because it slows down your development and
makes interactivly testing more difficult, which is one of the major
advantages of Lisp compared to other languages. Try the evaluation version
of LispWork (I think the only limitation was less memory or time limit for
one session), use Tools->Preferencs->Emulation to change to MS Windows key
bindings, if you are not familar with Emacs keybindings and have fun :-)
> And path is bidirectional
This doesn't make it much more difficult, you just have to check both
elements in an item for input and output.
Next you have to think about the algorithm. For the example labyrinth,
((1 2) (7 8) (4 5) (2 3) (7 2) (9 6)), if you write a recursive search
function, you have to think about branches, because if you search all the
time the next element for start 1 and end 8, you'll get stuck in the dead
end (2 3). One idea would be backtracking. Wikipedia has a nice explanation
of it:
http://en.wikipedia.org/wiki/Backtracking
Can you describe the full algorithm now? Can you try to write some
functions, which implements parts of the algorithm?
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On 13 avr, 14:16, Frank Buss <····@frank-buss.de> wrote:
> Aliska wrote:
> >> I compile in LISP.BAT of the command line, i write the function in
> >> a .txt document and ai write in command line (load"filename")
>
> Ok, this is not a good idea, because it slows down your development and
> makes interactivly testing more difficult, which is one of the major
> advantages of Lisp compared to other languages. Try the evaluation version
> of LispWork (I think the only limitation was less memory or time limit for
> one session), use Tools->Preferencs->Emulation to change to MS Windows key
> bindings, if you are not familar with Emacs keybindings and have fun :-)
>
> > And path is bidirectional
>
> This doesn't make it much more difficult, you just have to check both
> elements in an item for input and output.
>
> Next you have to think about the algorithm. For the example labyrinth,
> ((1 2) (7 8) (4 5) (2 3) (7 2) (9 6)), if you write a recursive search
> function, you have to think about branches, because if you search all the
> time the next element for start 1 and end 8, you'll get stuck in the dead
> end (2 3). One idea would be backtracking. Wikipedia has a nice explanation
> of it:
>
> http://en.wikipedia.org/wiki/Backtracking
>
> Can you describe the full algorithm now? Can you try to write some
> functions, which implements parts of the algorithm?
>
> --
> Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
Frank, can I try to find a solution for my probleme and after those I
show in this discussion mes efforts for be examinate?
Aliska wrote:
> Frank, can I try to find a solution for my probleme and after those I
> show in this discussion mes efforts for be examinate?
Bien s�r, Aliska.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
A quick thought:
The current form of the labyrinth data isn't very intuitive.
It'd be better to regroup the data so that each room is linked to a
list of all the rooms that link to it. Since you might have to operate
on a large labyrinth, and you want quick access to any room, a hash
table sounds like the best option.
Here's a function pulled together in 5 minutes for just this purpose:
(defun zip-labyrinth (labyrinth)
(do* ((hash (make-hash-table :test #'eq))
(lab labyrinth (cdr lab))
(pair (car lab) (car lab)))
((null lab) hash)
(push (car pair) (gethash (cadr pair) hash))
(push (cadr pair) (gethash (car pair) hash))))
This returns a hash table as follows:
(inspect (zip-labyrinth '((A B)(A C)(A G)(B D)(B F)(D H)(E F)(E G))))
0 KEY ----------> The symbol C
1 VALUE --------> (A), a proper list with 1 element
2 KEY ----------> The symbol D
3 VALUE --------> (H B), a proper list with 2 elements
4 KEY ----------> The symbol E
5 VALUE --------> (G F), a proper list with 2 elements
6 KEY ----------> The symbol F
7 VALUE --------> (E B), a proper list with 2 elements
8 KEY ----------> The symbol G
9 VALUE --------> (E A), a proper list with 2 elements
10 KEY ----------> The symbol H
11 VALUE --------> (D), a proper list with 1 element
12 KEY ----------> The symbol A
13 VALUE --------> (G C B), a proper list with 3 elements
14 KEY ----------> The symbol B
15 VALUE --------> (F D A), a proper list with 3 elements
Hope that helps you with finding an intuitive solution.
-Adlai
On 13 avr, 15:49, Adlai <·········@gmail.com> wrote:
> A quick thought:
>
> The current form of the labyrinth data isn't very intuitive.
>
> It'd be better to regroup the data so that each room is linked to a
> list of all the rooms that link to it. Since you might have to operate
> on a large labyrinth, and you want quick access to any room, a hash
> table sounds like the best option.
>
> Here's a function pulled together in 5 minutes for just this purpose:
>
> (defun zip-labyrinth (labyrinth)
> (do* ((hash (make-hash-table :test #'eq))
> (lab labyrinth (cdr lab))
> (pair (car lab) (car lab)))
> ((null lab) hash)
> (push (car pair) (gethash (cadr pair) hash))
> (push (cadr pair) (gethash (car pair) hash))))
>
> This returns a hash table as follows:
> (inspect (zip-labyrinth '((A B)(A C)(A G)(B D)(B F)(D H)(E F)(E G))))
> 0 KEY ----------> The symbol C
> 1 VALUE --------> (A), a proper list with 1 element
> 2 KEY ----------> The symbol D
> 3 VALUE --------> (H B), a proper list with 2 elements
> 4 KEY ----------> The symbol E
> 5 VALUE --------> (G F), a proper list with 2 elements
> 6 KEY ----------> The symbol F
> 7 VALUE --------> (E B), a proper list with 2 elements
> 8 KEY ----------> The symbol G
> 9 VALUE --------> (E A), a proper list with 2 elements
> 10 KEY ----------> The symbol H
> 11 VALUE --------> (D), a proper list with 1 element
> 12 KEY ----------> The symbol A
> 13 VALUE --------> (G C B), a proper list with 3 elements
> 14 KEY ----------> The symbol B
> 15 VALUE --------> (F D A), a proper list with 3 elements
>
> Hope that helps you with finding an intuitive solution.
>
> -Adlai
thanks a lot, I will try
Adlai wrote:
> A quick thought:
>
> The current form of the labyrinth data isn't very intuitive.
>
> It'd be better to regroup the data so that each room is linked to a
> list of all the rooms that link to it. Since you might have to operate
> on a large labyrinth, and you want quick access to any room, a hash
> table sounds like the best option.
A hastable sounds like premature optimization, which could be even slower
for small labyrinths and could lead to a more complicated solution, because
usually a more pure functional approach is easier to implement and to test.
> Here's a function pulled together in 5 minutes for just this purpose:
>
> (defun zip-labyrinth (labyrinth)
> (do* ((hash (make-hash-table :test #'eq))
> (lab labyrinth (cdr lab))
> (pair (car lab) (car lab)))
> ((null lab) hash)
> (push (car pair) (gethash (cadr pair) hash))
> (push (cadr pair) (gethash (car pair) hash))))
"eq" is a premature optimization, too, and not a good idea, because if the
labyrinth contains numbers, this can be a problem, because in some Common
Lisp implementations it is possible that (eq 1 1) is false.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On Apr 13, 5:04 pm, Frank Buss <····@frank-buss.de> wrote:
> Adlai wrote:
> > A quick thought:
>
> > The current form of the labyrinth data isn't very intuitive.
>
> > It'd be better to regroup the data so that each room is linked to a
> > list of all the rooms that link to it. Since you might have to operate
> > on a large labyrinth, and you want quick access to any room, a hash
> > table sounds like the best option.
>
> A hastable sounds like premature optimization, which could be even slower
> for small labyrinths and could lead to a more complicated solution, because
> usually a more pure functional approach is easier to implement and to test.
>
> > Here's a function pulled together in 5 minutes for just this purpose:
>
> > (defun zip-labyrinth (labyrinth)
> > (do* ((hash (make-hash-table :test #'eq))
> > (lab labyrinth (cdr lab))
> > (pair (car lab) (car lab)))
> > ((null lab) hash)
> > (push (car pair) (gethash (cadr pair) hash))
> > (push (cadr pair) (gethash (car pair) hash))))
>
> "eq" is a premature optimization, too, and not a good idea, because if the
> labyrinth contains numbers, this can be a problem, because in some Common
> Lisp implementations it is possible that (eq 1 1) is false.
>
> --
> Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de
I guess that if you're not worried about large labyrinths, you could
make it an alist with the same organization as the hash table -- in
each assoc pair, the car would be a room, the cdr a list of rooms.
Should be pretty similar to the hash-table-generating code, except you
need to create each node in the alist.
> Hold your left hand against the "wall". Walk forward, never removing
> your hand. If you reach the destination, then print the path. If you
> end up back where you started, then no path. Simple enough.
>
> -Jason
Not quite that simple -- you can make "islands" in the middle of a
labyrinth which can't be accessed this way.
A very simple example would be a 5x5 set of rooms, where the 8 rooms
on the rim of the the inner 3x3 square all connect to eachother.
Regardless of the configuration of the other room connections, it's
impossible to use Jason's method to get from one of the outer cells to
the inmost cell.
-Adlai
On 13 avr, 10:34, Adlai <·········@gmail.com> wrote:
> > Hold your left hand against the "wall". Walk forward, never removing
> > your hand. If you reach the destination, then print the path. If you
> > end up back where you started, then no path. Simple enough.
>
> > -Jason
>
> Not quite that simple -- you can make "islands" in the middle of a
> labyrinth which can't be accessed this way.
>
> A very simple example would be a 5x5 set of rooms, where the 8 rooms
> on the rim of the the inner 3x3 square all connect to eachother.
> Regardless of the configuration of the other room connections, it's
> impossible to use Jason's method to get from one of the outer cells to
> the inmost cell.
>
> -Adlai
So what's easier and faster for implimentat?
On Mon, 13 Apr 2009 00:46:58 -0700 (PDT), Aliska
<················@gmail.com> wrote:
>On 13 avr, 10:34, Adlai <·········@gmail.com> wrote:
>> > Hold your left hand against the "wall". Walk forward, never removing
>> > your hand. If you reach the destination, then print the path. If you
>> > end up back where you started, then no path. Simple enough.
>>
>> > -Jason
>>
>> Not quite that simple -- you can make "islands" in the middle of a
>> labyrinth which can't be accessed this way.
>>
>> A very simple example would be a 5x5 set of rooms, where the 8 rooms
>> on the rim of the the inner 3x3 square all connect to eachother.
>> Regardless of the configuration of the other room connections, it's
>> impossible to use Jason's method to get from one of the outer cells to
>> the inmost cell.
>>
>> -Adlai
>
>So what's easier and faster for implimentat?
You haven't adequately described the problem even though some of the
people here have asked you some important questions. You have given a
simple example using a list of adjacency pairs, stated that the paths
between adjacent "rooms" are bidirectional and that you need only give
one solution if there are multiple.
You have not said
- whether you are required to use lists,
- whether there may be circular paths,
- whether you need the shortest path(s) or just any path(s)
You should investigate the Dyjkstra, Euler and Floyd-Warshall path
algorithms and see if they are applicable. The answer lies in how you
look at the maze.
George
George Neuner wrote:
> You have not said
> - whether you are required to use lists,
> - whether there may be circular paths,
> - whether you need the shortest path(s) or just any path(s)
Aliska wrote somewhere that any path is sufficient. But thinging about
circular paths could be interesting. Solution should be in Lisp, so I guess
all of Common Lisp is allowed.
> You should investigate the Dyjkstra, Euler and Floyd-Warshall path
> algorithms and see if they are applicable. The answer lies in how you
> look at the maze.
I think these algorithms are too difficult, a simple backtracking algorithm
should work. This sounds more like a homework assigment for learning how to
program, and not a task for implementing a fast algorithm for solving
arbitrary large labyrinths.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
I have the algorithm of Backtraking:
k:=1;init(1,st);
while k>0 do
begin
repeat
succesor(as,st,k);
if as then valid(ev,st,k);
until (not as) or (as and ev );
if as then
if solutie(k) then
print
else
begin
k:=k+1;
init(k,st);
end
else
k:=k-1;
end;
Aliska <················@gmail.com> writes:
> I have the algorithm of Backtraking:
>
> k:=1;init(1,st);
>
> while k>0 do
>
> begin
>
> repeat
>
> succesor(as,st,k);
>
> if as then valid(ev,st,k);
>
> until (not as) or (as and ev );
>
> if as then
>
> if solutie(k) then
>
> print
>
> else
>
> begin
>
> k:=k+1;
>
> init(k,st);
>
> end
>
> else
>
> k:=k-1;
>
> end;
It's not very good. Try it like this:
k:=1;
init(1,st);
while
k>0
do
begin
repeat
succesor(as,st,k);
if
as
then
valid(ev,st,k);
until
(not
as)
or
(as
and
ev
);
if
as
then
if
solutie(k)
then
print
else
begin
k:=k+1;
init(k,st);
end
else
k:=k-1;
end;
--
__Pascal Bourguignon__
Aliska wrote:
> I have the algorithm of Backtraking:
Fine. Looks like you have copied it from this webpage:
http://www.preferatele.com/docs/informatica/3/backtracking-recursi18.php
Usually it is fair to cite the origin, but at least you have demonstrated
that you can copy-and-paste source code (better formatting is an advanced
topic and not necessary for a copy-and-paste beginner). Next step: write
something on your own. Maybe a good is to learn what the backtracking
algorithm does:
http://en.wikipedia.org/wiki/Backtracking
Then think about why you need it, if you want to use it. There are other
possible solutions for your labyrinth problem, too.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On Tue, 14 Apr 2009 07:50:02 +0200, Frank Buss <··@frank-buss.de>
wrote:
>George Neuner wrote:
>
>> You have not said
>> - whether you are required to use lists,
>> - whether there may be circular paths,
>> - whether you need the shortest path(s) or just any path(s)
>
>Aliska wrote somewhere that any path is sufficient. But thinging about
>circular paths could be interesting. Solution should be in Lisp, so I guess
>all of Common Lisp is allowed.
>
>> You should investigate the Dyjkstra, Euler and Floyd-Warshall path
>> algorithms and see if they are applicable. The answer lies in how you
>> look at the maze.
>
>I think these algorithms are too difficult, a simple backtracking algorithm
>should work. This sounds more like a homework assigment for learning how to
>program, and not a task for implementing a fast algorithm for solving
>arbitrary large labyrinths.
You're right about it sounding like homework, but the point is to get
the person thinking about graph solutions and what representations of
data are appropriate rather than thinking too quickly about code. The
code (at least in Lisp) falls out rather easily once you have a good
representation.
Simple DFS won't handle cycles in the graph and that's why I suggested
the OP look at these other ways to solve the problem ... so the OP
would think about that.
These kinds of "help me" threads result from people being taught
programming languages without having studied algorithms.
George