tag:blogger.com,1999:blog-6272748843257835470Sat, 29 Feb 2020 07:40:25 +0000pythonfsharpgoogleaimathprogrammingjavascriptlispA Mingled Cuphttp://mingledcup.dkjones.org/search/label/lispnoreply@blogger.com (Dave)Blogger1125tag:blogger.com,1999:blog-6272748843257835470.post-9134053132913433280Sun, 31 Oct 2010 20:10:00 +00002010-11-29T18:56:17.602-05:00lispTowers of Hanoi with Four PegsSomehow... this post overwrote a previous one. Not sure how that happened...
<p class="first">I saw a link today on <a href="http://www.johndcook.com/blog/2010/11/26/weekend-miscellany-64/">John Cook's blog</a> mentioning the Tower of Hanoi
with four pegs. This was an extra credit problem in the algorithms
class I took in school, so I looked at the article. The problem of
finding the optimimum number of steps is still open. Well, there is a
possible solution, but no proof that it is correct.</p>
<p>That extra credit problem was one of the more interesting things I
worked on at school. I forgot some of the details of the solution,
but went to the basement and found the copy I handed in. The solution
was ugly 13 year old C code.</p>
<p><a href="http://en.wikipedia.org/wiki/Tower_of_Hanoi#Four_pegs_and_beyond">Wikipedia</a> has the algorithm that is believed to be the best, so I
decided to use it to check my solution. The solution uses dynamic
programming, and I am re-learning lisp at the moment, so I solved the
problem in lisp.</p>
<p>Here is the code. The result is a two by n array, where the last
element in the second row is the final answer.</p>
<pre class="example">
;; From Graham's "ANSI Common Lisp"
(defun map-int (fn n)
"Map fn over integers from 0 to n - 1"
(let ((acc nil))
(dotimes (i n)
(push (funcall fn i) acc))
(nreverse acc)))
(defun hanoi-4 (n)
"Return the number of moves needed to solve the tower of hanoi
with four poles"
(let ((memo (make-array (list 2 (1+ n))
:initial-element 0)))
;; Set up the "three pole" numbers
(dotimes (i (1+ n))
(setf (aref memo 0 i) (- (expt 2 i) 1)))
;; Do the dynamic programming.
;; For each i less than n, find the best solution to using
;; four poles. The best solution is the min of
;; 2 * T(k, 4) + T(i-k, 3) for 0 <= k < i.
;; T(u, v) is the number of moves needed to move u disks
;; using v poles.
(do ((i 1 (1+ i)))
((= i (1+ n)) memo)
(setf (aref memo 1 i)
(apply #'min
(map-int
(lambda (j)
(+ (* 2 (aref memo 1 j))
(aref memo 0 (- i j))))
i))))))
</pre>
<p>Running the test I get:</p>
<pre class="example">
CL-USER> (hanoi-4 36)
#2A((0 1 3 7 15 31 63 127 255 511 1023 2047
4095 8191 16383 32767 65535 131071
262143 524287 1048575 2097151 4194303
8388607 16777215 33554431 67108863
134217727 268435455 536870911 1073741823
2147483647 4294967295 8589934591
17179869183 34359738367 68719476735)
(0 1 3 5 9 13 17 25 33 41 49 65 81 97
113 129 161 193 225 257 289 321 385
449 513 577 641 705 769 897 1025
1153 1281 1409 1537 1665 1793))
</pre>
<p>Here, 1793 is the solution for four pegs and 36 discs.</p>
<p>With dynamic programming, this solution is pretty straight forward.
My memory is hazy about what I did, but basically, I did the dynamic
programming part the hard way by figuring out the recursive steps
ahead of time, for each value up to 36. I had a sense of what worked,
but no real proof that it would work beyond the value I tried. People
talk about reading their own code after a few months... I am not sure
if I want to look at this close enough to figure out what exactly I
was thinking.</p>
<p>In college, I never understood dynamic programming. We didn't spend
much time on it, and it was a short chapter in our textbook. After
doing a few TopCoder competitions, I finally got it.</p>
<p>The lisp solution took a little while, because I was trying
to remember all sorts of stuff. I am sure that there are much
better ways to do this... Recursion with memoization would
probably be easier, but I haven't tried it yet.</p>
<!-- Page published by Emacs Muse ends here -->http://mingledcup.dkjones.org/2010/10/javascript-tic-tac-toe.htmlnoreply@blogger.com (Dave)0