Hi guys
I have been trying to write a functon that will solve the Towers of
Hanoi problem, and I think I have come a lot farther on my own than I
origanlly anticapated. If you aren't familer with the Towers of Hanoi,
here is a good link:
http://www.cut-the-knot.org/recurrence/hanoi.shtml
I think that the applet in there solves the problem sub-optimally.
Anyways here are the function defintions that I have tried:
Number 1
(defun hanoi (ring-move ring-a ring-b ring-c)
(cond ((zerop n) nil)
((setf (ring-a 1) (ring-b 2) (ring-c 3)))
((ring-move (list 'left 'middle 'right)))
((hanoi (ring-move ring-c) 'right))
((print (list '(ring-c moved to right))))
((hanoi (ring-move (ring-a ring-b) 'right)))
((print (list '(ring-a and ring-b moved to right))))
(t (ring-a ring-b ring-c) 'right eq 0)))
I shudder to even look at that now, but at the time sadly enough, it
looked ok :(
Number 2
(defun hanoi (ring-move ring-a ring-b ring-c)
(cond ((zerop ring-c) nil)
((setf ring-a 1) (setf ring-b 2) (setf ring-c 3))
((setf ring-move (list 'left 'middle 'right)))
((hanoi (ring-move ring-a 'right) (ring-move ring-b 'right)))
((print (list '(MOVE ONE COMPLETE))))
((hanoi (ring-move ring-c 'right)))
((print (list '(FINAL MOVE COMPLETE))))
(t (ring-move 'right) nil)))
This one seemed a little better, but was still not what I wanted. So
on to try 3
(defun hanoi (ring-move ring-a ring-b ring-c)
(cond ((zerop ring-move) nil)
((hanoi (1 'right 'middle 'left))) ;; Why is this illegal?
((print (list '(MOVES ONE AND TWO COMPLETE))))
((hanoi (2 'right 'right 'middle)))
((print (list '(MOVES THREE FOUR AND FIVE COMPLETE))))
(t (hanoi (3 'right 'right 'right) nil))))
Which returned some strange errors. After this one, I reread the hints
in my textbook, and found that I had been giving hanoi bad arguments,
so I rewrote it once again. This is the most recent version:
(defun hanoi (ring peg-a peg-b peg-c)
(cond ((zerop ring) nil)
((hanoi ring 3 peg-a peg-c))
((print (list '(3 FROM LEFT TO RIGHT))))
(t (hanoi ring 2 peg-a peg-c) nil)))
As you can see this one is much better than the first two anyways. I'm
still not sure if this is what I want. It returned three errors three
warnings and 11 notes when compiled. I know that I can just look in
the back of my textbook for the answer, but I really don't want to. I
decided I might as well ask for some pointers and tips though. Just an
FYI: This is how the function will be called:
(hanoi 3 'left 'middle 'right)
and it should return
NIL
The textbook does give me several hints, such as how many arguments to
give hanoi, etc. It obviously says that it must be a recursive
function as well, but since I've only known what those were for 48
hours now, my first couple of tries at this were misrible. The
textbook also says:
"Assume that hanoi can already move a smaller tower of rings from left
to middle. So you should ask yourself what then needs to be done to
convert that situation into the desired result"
My answer is "I have no clue" I don't really see how I'm supposed to
get this function to be called like I showed above. The final try at
this function that I have, is the one closest to what the textbook
recommends: one cond statement, two calls to hanoi, and one call to
print. I don't see how it can be solved in that little amount of code.
BTW, in case you were wondering, there is only three rings that we are
dealing with here, decided to start out small.
That said, any tips or pointers you guys could give me? How am I
looking so far? Have my functions improved any? Please don't give me a
function that will work correctly and solve the problem, as I want to
find the solution on my own, but little snippets are good, esspically
if incorperated in my code.
Sidenote: This is NOT homework. I am learning Lisp pretty much on my
own with help from c.l.l and #lisp and some textbooks, as well as Net
resources.
Thanks for any suggestions, tips, and pointers.
--
May the Source be with you.
neo88 (Philip Haddad)
Emacs has an included Hanoi module in elisp. I haven't looked at it
though.
--
An ideal world is left as an excercise to the reader.
--- Paul Graham, On Lisp 8.1
······@truevine.net (neo88) writes:
[...]
> "Assume that hanoi can already move a smaller tower of rings from left
> to middle. So you should ask yourself what then needs to be done to
> convert that situation into the desired result"
>
> My answer is "I have no clue"
If you can move n rings, then you can move n+1 rings by moving n rings
to one peg, moving the n+1'th ring to the other peg, then moving the n
rings on top of it.
[...]
On Thu, 29 Jul 2004 01:18:57 +0100, Bruce Stephens wrote:
> ······@truevine.net (neo88) writes:
>
> [...]
>
>> "Assume that hanoi can already move a smaller tower of rings from left
>> to middle. So you should ask yourself what then needs to be done to
>> convert that situation into the desired result"
>>
>> My answer is "I have no clue"
>
> If you can move n rings, then you can move n+1 rings by moving n rings
> to one peg, moving the n+1'th ring to the other peg, then moving the n
> rings on top of it.
It might help if you call the arguments 'n', 'from-peg', 'to-peg' and
'spare-peg'. It may be that just using these names (rather than ring-a,
ring-b and ring-c) will lead you to the solution.
For recursive problems I personally find it easier to think in terms "If I
know how to move n-1 rings, can I move n?". With recursion the beauty is
that you can assume that your function knows how to handle the n-1 case.
You know that you want a recursive solution. All recursive solutions look
like
(defun hanoi (n from-peg to-peg spare-peg)
(cond ((are_we_in_the_base_case?) base_case_solution)
(t do_something_with_n-1)))
You have already worked out that "(are_we_in_the_base_case?)" is "(= n
0)", and that "base_case_solution" is "nil".
So all that is needed is to fill in "do_something_with_n-1".
One thing that it looks to me that you are doing wrong is trying to use
fixed names inside the routine like 'left, 'middle and 'right. You should
be using the values of the parameters from-peg, to-peg and spare-peg. If
you want to move n disks from 'from-peg' to 'to-peg', you move n-1 disks
from 'from-peg' to 'spare-peg', move disk n from 'from-peg' to 'to-peg'
(This will be a "print" of a list, or else a "format" statement, unless
you are controlling a robot arm) and then move the n-1 disks from
'spare-peg' to 'to-peg'.
The standard solution looks like
(defun hanoi (n from-peg to-peg spare-peg)
(cond ((= n 0) nil)
(t (hanoi (- n 1) .....)
(print (list 'Move n 'from from-peg 'to to-peg))
(hanoi (- n 1) .....))))
······@truevine.net (neo88) writes:
> I have been trying to write a functon that will solve the Towers of
> Hanoi problem, and I think I have come a lot farther on my own than I
> origanlly anticapated.
> [...]
Bruce and Icarus gave you hints about the procedure.
Let me give you a hint about the data.
The problem is to move rings from one peg (tower) to the other.
So I'd say that you need to decide how to represent rings and pegs,
and how to manipulate them.
Here his what I'd do:
- let rings be represented by small integers corresponding to
their size.
- let pegs be represented by stacks implemented with lists. The
top of stack being the car of the list, and the cdr being what's
below.
For example, this tower:
|
-|-
---|---
--|--
===right===
would be represented by the list: (1 3 2 :right).
Of course, a valid hanoi tower would either be empty or have the ring
in increasing size top to bottom:
(defun valid-tower-p (peg)
(or (null (cdr peg)) (apply (function <) (butlast peg))))
;; (let's ignore the inefficiency of butlast please!)
Now, given two pegs, let's compute two new pegs with one ring moved
from the first peg to the second. With my representation, that'd give:
(defun move-ring (from-peg to-peg)
(print (list 'move 'ring (car from-peg) 'from from-peg 'to to-peg))
(values (cdr from-peg) (cons (car from-peg) to-peg)))
Now, you can play:
(defparameter left '(1 2 3 4 :left))
(defparameter middle '(:middle))
(defparameter right '(:right))
(multiple-value-setq (left middle) (move-ring left middle))
(print (list :left left :middle middle :right right))
(assert (every (function valid-tower-p) (list left middle right)))
(multiple-value-setq (left middle) (move-ring left middle))
(print (list :left left :middle middle :right right))
(assert (not (every (function valid-tower-p) (list left middle right))))
(defun hanoi (n src dst tmp)
(assert (every (function valid-tower-p) (list src dst tmp)))
(unless (= 0 n)
(multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?))
(multiple-value-setq (? ?) (move-ring ? ?))
(multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?)))
(assert (every (function valid-tower-p) (list src dst tmp)))
(values src dst tmp))
(defparameter left '(1 2 3 4 :left))
(defparameter middle '(:middle))
(defparameter right '(:right))
(hanoi (1- (length left)) left right middle)
--> (MOVE RING 1 FROM (1 2 3 4 :LEFT) TO (:MIDDLE))
(MOVE RING 2 FROM (2 3 4 :LEFT) TO (:RIGHT))
(MOVE RING 1 FROM (1 :MIDDLE) TO (2 :RIGHT))
(MOVE RING 3 FROM (3 4 :LEFT) TO (:MIDDLE))
(MOVE RING 1 FROM (1 2 :RIGHT) TO (4 :LEFT))
(MOVE RING 2 FROM (2 :RIGHT) TO (3 :MIDDLE))
(MOVE RING 1 FROM (1 4 :LEFT) TO (2 3 :MIDDLE))
(MOVE RING 4 FROM (4 :LEFT) TO (:RIGHT))
(MOVE RING 1 FROM (1 2 3 :MIDDLE) TO (4 :RIGHT))
(MOVE RING 2 FROM (2 3 :MIDDLE) TO (:LEFT))
(MOVE RING 1 FROM (1 4 :RIGHT) TO (2 :LEFT))
(MOVE RING 3 FROM (3 :MIDDLE) TO (4 :RIGHT))
(MOVE RING 1 FROM (1 2 :LEFT) TO (:MIDDLE))
(MOVE RING 2 FROM (2 :LEFT) TO (3 4 :RIGHT))
(MOVE RING 1 FROM (1 :MIDDLE) TO (2 3 4 :RIGHT))
(:LEFT) ; (1 2 3 4 :RIGHT) ; (:MIDDLE)
Of course, one interesting property (but you should prove it!) is that
n is equal to the size of the ring at the top of the src peg after the
first recursive hanoi call (with the condition that the sizes are
consecutive):
(defun hanoi (n src dst tmp)
(assert (every (function valid-tower-p) (list src dst tmp)))
(unless (= 0 n)
(multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?))
(assert (= n (car src)))
(multiple-value-setq (? ?) (move-ring ? ?))
(multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?)))
(assert (every (function valid-tower-p) (list src dst tmp)))
(values src dst tmp))
The proof of this property, if you have it is the reason why you can
provide the same output without actually manipulating the towers.
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
> Here his what I'd do:
>
> - let rings be represented by small integers corresponding to
> their size.
>
> - let pegs be represented by stacks implemented with lists. The
> top of stack being the car of the list, and the cdr being what's
> below.
That is an interesting idea, I'll keep that in mind.
> For example, this tower:
>
> |
> -|-
> ---|---
> --|--
> ===right===
>
> would be represented by the list: (1 3 2 :right).
>
> Of course, a valid hanoi tower would either be empty or have the ring
> in increasing size top to bottom:
Right. The two rules governing this are:
1) Move only one ring at a time; and
2) never place a larger ring on top of a smaller one.
> (defun valid-tower-p (peg)
> (or (null (cdr peg)) (apply (function <) (butlast peg))))
> ;; (let's ignore the inefficiency of butlast please!)
>
> Now, given two pegs, let's compute two new pegs with one ring moved
> from the first peg to the second. With my representation, that'd give:
>
> (defun move-ring (from-peg to-peg)
> (print (list 'move 'ring (car from-peg) 'from from-peg 'to to-peg))
> (values (cdr from-peg) (cons (car from-peg) to-peg)))
>
> Now, you can play:
>
> (defparameter left '(1 2 3 4 :left))
> (defparameter middle '(:middle))
> (defparameter right '(:right))
>
> (multiple-value-setq (left middle) (move-ring left middle))
> (print (list :left left :middle middle :right right))
> (assert (every (function valid-tower-p) (list left middle right)))
>
> (multiple-value-setq (left middle) (move-ring left middle))
> (print (list :left left :middle middle :right right))
> (assert (not (every (function valid-tower-p) (list left middle right))))
>
> (defun hanoi (n src dst tmp)
> (assert (every (function valid-tower-p) (list src dst tmp)))
> (unless (= 0 n)
> (multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?))
> (multiple-value-setq (? ?) (move-ring ? ?))
> (multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?)))
> (assert (every (function valid-tower-p) (list src dst tmp)))
> (values src dst tmp))
>
> (defparameter left '(1 2 3 4 :left))
> (defparameter middle '(:middle))
> (defparameter right '(:right))
> (hanoi (1- (length left)) left right middle)
>
> --> (MOVE RING 1 FROM (1 2 3 4 :LEFT) TO (:MIDDLE))
> (MOVE RING 2 FROM (2 3 4 :LEFT) TO (:RIGHT))
> (MOVE RING 1 FROM (1 :MIDDLE) TO (2 :RIGHT))
> (MOVE RING 3 FROM (3 4 :LEFT) TO (:MIDDLE))
> (MOVE RING 1 FROM (1 2 :RIGHT) TO (4 :LEFT))
> (MOVE RING 2 FROM (2 :RIGHT) TO (3 :MIDDLE))
> (MOVE RING 1 FROM (1 4 :LEFT) TO (2 3 :MIDDLE))
> (MOVE RING 4 FROM (4 :LEFT) TO (:RIGHT))
> (MOVE RING 1 FROM (1 2 3 :MIDDLE) TO (4 :RIGHT))
> (MOVE RING 2 FROM (2 3 :MIDDLE) TO (:LEFT))
> (MOVE RING 1 FROM (1 4 :RIGHT) TO (2 :LEFT))
> (MOVE RING 3 FROM (3 :MIDDLE) TO (4 :RIGHT))
> (MOVE RING 1 FROM (1 2 :LEFT) TO (:MIDDLE))
> (MOVE RING 2 FROM (2 :LEFT) TO (3 4 :RIGHT))
> (MOVE RING 1 FROM (1 :MIDDLE) TO (2 3 4 :RIGHT))
>
> (:LEFT) ; (1 2 3 4 :RIGHT) ; (:MIDDLE)
>
> Of course, one interesting property (but you should prove it!) is that
> n is equal to the size of the ring at the top of the src peg after the
> first recursive hanoi call (with the condition that the sizes are
> consecutive):
I assume you mean "prove" it with mathematics? In that case, I would
try a proof by induction, since they are the only type of proofs I
know (besides the geometric of course). And I know it has something to
do with the recursive process, so my proof will have to include an n-1
state somewhere in it. Hmmm.
/me scratches his head. So I guess you are trying to prove the n-2
state "after the first recursive hanoi call" which I believe would be
n-1. So if you go down three recursive levels to n-3, which is 0
according to the rules of my function, you reach the terminating
condition, which I suppose would prove that n-2 is at the src peg?
Then you jsut move them over to finish the problem. Whew. That was
interesting.
> (defun hanoi (n src dst tmp)
> (assert (every (function valid-tower-p) (list src dst tmp)))
> (unless (= 0 n)
> (multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?))
> (assert (= n (car src)))
> (multiple-value-setq (? ?) (move-ring ? ?))
> (multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?)))
> (assert (every (function valid-tower-p) (list src dst tmp)))
> (values src dst tmp))
>
> The proof of this property, if you have it is the reason why you can
> provide the same output without actually manipulating the towers.
Makes some sense. I assume you mean "manipulating the towers" in the
function? I don't really understand what you mean by "same output"
though....
--
May the Source be with you.
neo88 (Philip Haddad)
······@truevine.net (neo88) writes:
> I assume you mean "prove" it with mathematics? In that case, I would
> try a proof by induction, since they are the only type of proofs I
> know (besides the geometric of course). And I know it has something to
> do with the recursive process, so my proof will have to include an n-1
> state somewhere in it. Hmmm.
Indeed.
> /me scratches his head. So I guess you are trying to prove the n-2
> state "after the first recursive hanoi call" which I believe would be
> n-1. So if you go down three recursive levels to n-3, which is 0
> according to the rules of my function, you reach the terminating
> condition, which I suppose would prove that n-2 is at the src peg?
> Then you jsut move them over to finish the problem. Whew. That was
> interesting.
Isn't it!
> > (defun hanoi (n src dst tmp)
> > (assert (every (function valid-tower-p) (list src dst tmp)))
> > (unless (= 0 n)
> > (multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?))
> > (assert (= n (car src)))
> > (multiple-value-setq (? ?) (move-ring ? ?))
> > (multiple-value-setq (? ? ?) (hanoi (1- n) ? ? ?)))
> > (assert (every (function valid-tower-p) (list src dst tmp)))
> > (values src dst tmp))
> >
> > The proof of this property, if you have it is the reason why you can
> > provide the same output without actually manipulating the towers.
>
> Makes some sense. I assume you mean "manipulating the towers" in the
> function? I don't really understand what you mean by "same output"
> though....
Same "printed" output:
> --> (MOVE RING 1 FROM (1 2 3 4 :LEFT) TO (:MIDDLE))
> (MOVE RING 2 FROM (2 3 4 :LEFT) TO (:RIGHT))
> (MOVE RING 1 FROM (1 :MIDDLE) TO (2 :RIGHT))
> [...]
is printed and you can get the same (well, almost, the exact state of
each tower would not be tracked).
The result:
> (:LEFT) ; (1 2 3 4 :RIGHT) ; (:MIDDLE)
is the manipulated towers. Rings 1 2 3f4 were on :LEFT at the start,
they're on :RIGHT now.
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
Yay! I have the function to solve the problem! Unfortanlty I am at
work now, so I can't post it, I'll be putting it up here later tonight
:)
--
May the Source be with you.
neo88 (Philip Haddad)
Yay! I have the function to solve the problem! Unfortanlty I am at
work now, so I can't post it, I'll be putting it up here later tonight
:)
--
May the Source be with you.
neo88 (Philip Haddad)
Does an automated solution get much harder if one cannot move
directly between the left and right pegs? ... Apparently not.
(let ((depth 3)) ; at most 36
(dotimes (step (expt 3 depth))
(format t "~R~3,V,'0R;" depth step)
(let ((pegs (make-array depth :initial-element "")))
(loop for level below depth
for scaled = step then (floor scaled 3)
for peg = (aref #(0 1 2 2 1 0) (mod scaled 6))
do (setf (elt pegs peg)
(concatenate 'string (elt pegs peg)
(string (digit-char level depth)))))
(dotimes (peg 3)
(format t " ~V,,,··@A" depth (elt pegs peg))))
(terpri)))
Here is the function that I wrote that solves the problem:
(defun hanoi (n from-peg to-peg spare-peg)
(cond ((= n 0) nil)
(t (hanoi (- n 1) to-peg from-peg spare-peg)
(print (list '(1 from-peg to-peg)))
(hanoi (- n 1) to-peg from-peg spare-peg))))
The print statement is not wuite right, but the function works :)
I think that the print statement should be:
(print (list '(Moved n) '(from-peg) '(to-peg)))
or some such. The print statement wasn't as important to me as getting
the function to work. After about four or five tries and some stack
overflows, I finally got the function down. Thanks to everyone who
gave me hints!
Aside: Does this kind of premote me from newbie to advanced newbie? :P
Well I had a lot of fun writing this, and I learned an aweful lot.
--
May the Source with you.
neo88 (Philip Haddad)
······@truevine.net (neo88) writes:
> Here is the function that I wrote that solves the problem:
>
> (defun hanoi (n from-peg to-peg spare-peg)
> (cond ((= n 0) nil)
> (t (hanoi (- n 1) to-peg from-peg spare-peg)
> (print (list '(1 from-peg to-peg)))
> (hanoi (- n 1) to-peg from-peg spare-peg))))
>
> The print statement is not wuite right, but the function works :)
> I think that the print statement should be:
>
> (print (list '(Moved n) '(from-peg) '(to-peg)))
>
> or some such. The print statement wasn't as important to me as getting
> the function to work. After about four or five tries and some stack
> overflows, I finally got the function down. Thanks to everyone who
> gave me hints!
> Aside: Does this kind of premote me from newbie to advanced newbie? :P
> Well I had a lot of fun writing this, and I learned an aweful lot.
Of course not.
You blindly produced a wrong version.
If I put your algorithm into my framework where the rings are really
moved, the computer will soon check that something is dead wrong:
(defun hanoi-neo88 (n src dst tmp)
(assert (every (function valid-tower-p) (list src dst tmp)))
(unless (= n 0)
(multiple-value-setq (src dst tmp) (hanoi-neo88 (1- n) src dst tmp))
(assert (= n (car src)))
(print (list '(1 src dst)))
(multiple-value-setq (src dst) (move-ring src dst))
(multiple-value-setq (src dst tmp) (hanoi-neo88 (1- n) src dst tmp)))
(assert (every (function valid-tower-p) (list src dst tmp)))
(values src dst tmp))
(defparameter left '(1 2 3 4 5 :left))
(defparameter middle '(:middle))
(defparameter right '(:right))
(hanoi-neo88 (1- (length left)) left right middle)
((1 SRC DST))
(MOVE RING 1 FROM (1 2 3 4 5 :LEFT) TO (:RIGHT))
((1 SRC DST))
(MOVE RING 2 FROM (2 3 4 5 :LEFT) TO (1 :RIGHT))
(EVERY #'VALID-TOWER-P (LIST SRC DST TMP)) must evaluate to a non-NIL value.
[Condition of type SIMPLE-ERROR]
You're trying to put ring 2 over ring 1!
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
> You're trying to put ring 2 over ring 1!
Well, then it would appear that I have my arguments to the recursive
calls to hanoi mixed up a bit. What if I did (have not tested this
out):
(defun hanoi (n from-peg spare-peg to-peg)
;; I thought the goal here was to get all
;; of the pegs from from-peg to to-peg
(cond ((= n 0) nil)
(t (hanoi (- n 1) from-peg to-peg spare-peg)
(print (list 'Moved n 'from peg 'to spare-peg 'to to-peg))
(hanoi (- n 1) spare-peg from-peg to-peg))))
BTW, here is what my textbook has (I took a peek seeing as I thought I
had it down):
(defun hanoi (n a b c)
(cond ((zerop n) nil)
(t (hanoi (1- n) a c b)
(print (list 'move n 'from a 'to c))
(hanoi (1- n) b a c))))
Which would appear it does the same thing that my function does,
perhaps with different names and a slighlty different print statement.
I did notice last night that the output from my original function was
a little weird, I just couldn't figure out what it was. I guess I had
the args to hanoi mixed up.
BTW Pascal, nice little sanity checker you have there. I don't really
understand a whole lot of the code, but it seems to work real nice. I
liked the was you origanally wrote the functions, writing more than
one, and then using them all to solve the problem. That's the coding
style I'm used to more coming from C++ and dare I say Perl.
Once again thanks for all of the hints, rebukes :P, and help.
--
May the Source be with you.
neo88 (Philip Haddad)
······@truevine.net (neo88) wrote in message news:<····························@posting.google.com>...
> > You're trying to put ring 2 over ring 1!
>
> Well, then it would appear that I have my arguments to the recursive
> calls to hanoi mixed up a bit. What if I did (have not tested this
> out):
>
> (defun hanoi (n from-peg spare-peg to-peg)
> ;; I thought the goal here was to get all
> ;; of the pegs from from-peg to to-peg
> (cond ((= n 0) nil)
> (t (hanoi (- n 1) from-peg to-peg spare-peg)
> (print (list 'Moved n 'from peg 'to spare-peg 'to to-peg))
> (hanoi (- n 1) spare-peg from-peg to-peg))))
>
> BTW, here is what my textbook has (I took a peek seeing as I thought I
> had it down):
>
> (defun hanoi (n a b c)
> (cond ((zerop n) nil)
> (t (hanoi (1- n) a c b)
> (print (list 'move n 'from a 'to c))
> (hanoi (1- n) b a c))))
>
> Which would appear it does the same thing that my function does,
> perhaps with different names and a slighlty different print statement.
> I did notice last night that the output from my original function was
> a little weird, I just couldn't figure out what it was. I guess I had
> the args to hanoi mixed up.
> BTW Pascal, nice little sanity checker you have there. I don't really
> understand a whole lot of the code, but it seems to work real nice. I
> liked the was you origanally wrote the functions, writing more than
> one, and then using them all to solve the problem. That's the coding
> style I'm used to more coming from C++ and dare I say Perl.
> Once again thanks for all of the hints, rebukes :P, and help.
Here is my function rewriten and working correctly (I tested it on
your program Pascal):
(defun hanoi (n from-peg to-peg spare-peg)
(cond ((= n 0) nil)
(t (hanoi (- n 1) from-peg spare-peg to-peg)
(print (list 'Moved n 'from from-peg 'to spare-peg))
(hanoi (- n 1) to-peg from-peg spare-peg))))
and here is the output:
(MOVED 1 FROM LEFT TO RIGHT)
(MOVED 2 FROM LEFT TO MIDDLE)
(MOVED 1 FROM RIGHT TO MIDDLE)
(MOVED 3 FROM LEFT TO RIGHT)
(MOVED 1 FROM MIDDLE TO LEFT)
(MOVED 2 FROM MIDDLE TO RIGHT)
(MOVED 1 FROM LEFT TO RIGHT)
Which is the correct output. I may try to rewrite this in a manner
similar to Pascal's since I like that style, but for now, this works
fine. I might add graphics too sometime....
--
May the Source be with you.
neo88 (Philip Haddad)
······@truevine.net (neo88) writes:
> Here is my function rewriten and working correctly (I tested it on
> your program Pascal):
>
> (defun hanoi (n from-peg to-peg spare-peg)
> (cond ((= n 0) nil)
> (t (hanoi (- n 1) from-peg spare-peg to-peg)
> (print (list 'Moved n 'from from-peg 'to spare-peg))
> (hanoi (- n 1) to-peg from-peg spare-peg))))
>
> and here is the output:
>
> (MOVED 1 FROM LEFT TO RIGHT)
> (MOVED 2 FROM LEFT TO MIDDLE)
> (MOVED 1 FROM RIGHT TO MIDDLE)
> (MOVED 3 FROM LEFT TO RIGHT)
> (MOVED 1 FROM MIDDLE TO LEFT)
> (MOVED 2 FROM MIDDLE TO RIGHT)
> (MOVED 1 FROM LEFT TO RIGHT)
Congratulations!
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
> Congratulations!
Thanks! BTW, your hanoi-sim function has one error on the line
finally return (....) ;; in the loop statement
it should be:
finally (return (.....))
Just thought I'd let you know. Also I was trying to get all the rings
on the left peg, and it appears your program tries to get them all on
the middle peg.
--
May the Source be with you.
neo88 (Philip Haddad)
······@truevine.net (neo88) writes:
> > Congratulations!
>
> Thanks! BTW, your hanoi-sim function has one error on the line
>
> finally return (....) ;; in the loop statement
>
> it should be:
>
> finally (return (.....))
>
> Just thought I'd let you know. Also I was trying to get all the rings
> on the left peg, and it appears your program tries to get them all on
> the middle peg.
You should rather check the reference.
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
Pascal Bourguignon <····@thalassa.informatimago.com> writes:
> You should rather check the reference.
Which reference? According to the CLHS, at least one compound
form must follow "finally" in LOOP.
Kalle Olavi Niemitalo <···@iki.fi> writes:
> Pascal Bourguignon <····@thalassa.informatimago.com> writes:
>
> > You should rather check the reference.
>
> Which reference? According to the CLHS, at least one compound
> form must follow "finally" in LOOP.
Ok, my fault. I'm using an implementation that implements:
initial-final::= initially compound-form+ | finally compound-form*
instead of specified:
initial-final::= initially compound-form+ | finally compound-form+
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
······@truevine.net (neo88) writes:
> Here is the function that I wrote that solves the problem:
>
> (defun hanoi (n from-peg to-peg spare-peg)
> (cond ((= n 0) nil)
> (t (hanoi (- n 1) to-peg from-peg spare-peg)
> (print (list '(1 from-peg to-peg)))
> (hanoi (- n 1) to-peg from-peg spare-peg))))
>
> The print statement is not wuite right, but the function works :)
> I think that the print statement should be:
>
> (print (list '(Moved n) '(from-peg) '(to-peg)))
>
> or some such. The print statement wasn't as important to me as getting
> the function to work. After about four or five tries and some stack
> overflows, I finally got the function down. Thanks to everyone who
> gave me hints!
> Aside: Does this kind of premote me from newbie to advanced newbie? :P
> Well I had a lot of fun writing this, and I learned an aweful lot.
I've pasted a hanoi simulator at: http://paste.lisp.org/display/2001
When applied to your algorithm:
(defun neo88-hanoi (n from-peg to-peg spare-peg)
(cond ((= n 0) nil)
(t (neo88-hanoi (- n 1) to-peg from-peg spare-peg)
(print `(move ring 1 from ,from-peg to ,to-peg))
(neo88-hanoi (- n 1) to-peg from-peg spare-peg))));;neo88-hanoi
it stops with this error:
CL-USER> (simulate-hanoi 3 (function neo88-hanoi))
| | |
-|- | |
--|-- | |
---|--- | |
###########################
SRC DST TMP
Al says: (MOVE RING 1 FROM :SRC TO :DST)
| | |
| | |
--|-- | |
---|--- -|- |
###########################
SRC DST TMP
Al says: (MOVE RING 1 FROM :DST TO :SRC)
| | |
-|- | |
--|-- | |
---|--- | |
###########################
SRC DST TMP
Al says: (MOVE RING 1 FROM :SRC TO :DST)
| | |
| | |
--|-- | |
---|--- -|- |
###########################
SRC DST TMP
Al says: (MOVE RING 1 FROM :SRC TO :DST)
ERROR: Top ring of tower :SRC is not 1, but 2
Even a random algorithm finally finds success:
CL-USER> (simulate-hanoi 3 (function smart-random-hanoi))
| | |
-|- | |
--|-- | |
---|--- | |
###########################
SRC DST TMP
Al says: (MOVE RING 1 FROM :SRC TO :TMP)
| | |
| | |
--|-- | |
---|--- | -|-
###########################
SRC DST TMP
Al says: (MOVE RING 2 FROM :SRC TO :DST)
| | |
| | |
| | |
---|--- --|-- -|-
###########################
SRC DST TMP
Al says: (MOVE RING 1 FROM :TMP TO :DST)
| | |
| | |
| -|- |
---|--- --|-- |
###########################
SRC DST TMP
Al says: (MOVE RING 1 FROM :DST TO :SRC)
[...and finally after a lot of random steps...]
| | |
| | |
| | |
-|- ---|--- --|--
###########################
SRC DST TMP
Al says: (MOVE RING 2 FROM :TMP TO :DST)
| | |
| | |
| --|-- |
-|- ---|--- |
###########################
SRC DST TMP
Al says: (MOVE RING 1 FROM :SRC TO :DST)
| | |
| -|- |
| --|-- |
| ---|--- |
###########################
SRC DST TMP
SUCCESS!
T
CL-USER>
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein