' Implementation of the Buneman-Levy Algorith (1980)
'
' Source:  slides entered at
'
' http://elvis.rowan.edu/~shenton/sr-proj/Hanoi/hanoi8-txt.html
'
' NOTE:  this is likely to be a transient site, as slides for a
'        senior project presentation.
'
' WHILE not all disks have been moved
'    Move the smallest disk clockwise (increasing modulo size)
'    Move the smaller of the remaining disks to the OTHER peg;
'         i.e., make the only move legal for it.
' END WHILE
'
' Original reference (provided by the author):
'
' O.Peter Buneman and Leon Levy
' The Towers of Hanoi Problem
'
' Implementer:  Timothy Rolfe
'
' This program, however, implements an alternative statement of
' the algorithm provided by Peter Buneman:
'
'    Date: Thu, 28 Jan 1999 19:35:52 -0500 (EST)
'    From: Peter Buneman <peter@cis.upenn.edu>
'    Subject: Re: Request for information
'
'    ... [providing the reference given above]
'
'    In fact the version I like best is
'
'    start: put your finger on an empty peg;
'           while (you can do a legal move on the other two pegs)
'           {
'               do it;
'               move your finger clockwise;
'           }
'
' tjr Note:
'
' Actually, move your finger so that it blocks the smallest disk
' if that is the one just moved.  Then continue to rotate in that
' direction.  Otherwise your finger just ends up chasing the smallest
' disk around the board.

DEFINT A-Z

' Procedure to perform the actual disk movement:
DECLARE SUB Hanoi (Board(), Top(), Src, Dst)

' Procedure to display the state of the board
DECLARE SUB ShowBoard (Board(), Size)

' Array to hold the position of the top disk on each of the
' three pegs --- zero meaning that no disks are on the peg.

DIM Top(0 TO 2)

' Data collection to specify the problem:

CLS

INPUT "How many disks"; Ndisks
INPUT "Desired source pin"; Src
INPUT "Desired destination pin"; Dst

IF Src < 0 THEN
   Src = 0
ELSEIF Src > 2 THEN
   Src = 2
END IF

IF Dst < 0 THEN
   Dst = 0
ELSEIF Dst > 2 THEN
   Dst = 2
END IF

IF Dst = Src THEN Dst = (Src + 1) MOD 3

' Dynamically sized Board array

'    Row:  the peg on the board
'    Col:  size of disk in that position
'          Column zero holds a flag value that guarantees
'          this pin will never be used as source when the
'          peg is empty --- i.e., subscript zero for top disk.

DIM Board(0 TO 2, 0 TO Ndisks)

' Set in the flag value that insure Board(Idx,0) can never be source
FOR Idx = 0 TO 2
   Board(Idx, 0) = Ndisks + 1
NEXT

' Put all the disks onto peg Src:
FOR Idx = 1 TO Ndisks
   Board(Src, Idx) = Ndisks + 1 - Idx
NEXT

Top(Src) = Ndisks       ' BASIC gives us the rest as zero

' If the number of Ndisks is odd, the first move is to the ultimate
' destination.  If, however, it is even, the first move is to the
' SPARE pin.

IF Ndisks MOD 2 = 0 THEN
   Dst = 3 - Src - Dst  ' Since we know 0 + 1 + 2 = 3
END IF

CALL Hanoi(Board(), Top(), Src, Dst)

PRINT "That is all.": LOCATE 21, 30
INPUT "Press <ENTER> to exit  ", Dmy$


END

SUB Hanoi (Board(), Top(), Src, Dst)

'    Board() --- State of the board as  Board(pin #, disk position)
'    Top()   --- 3-dimensional array tracking the top disk on the three pins
'    Src     --- on entry, pin with all of the disks
'    Dst     --- on entry, the FIRST move of the smallest disk

   Size = Board(Src, 1)      ' Retain for the ShowBoard routine

   CLS   ' Wipe screen before first display.

   CALL ShowBoard(Board(), Size)

   Block = 3 - (Src + Dst)

   Clockwise = (Dst = (Block + 1) MOD 3)

   DO UNTIL Top(Src) = 0 AND Top(Dst) = 0
 
'     NOTE:  Thanks to a flag value in Board(x,0), we can dispense with
'            checking for an empty pin.  See if guess on Src is good
      IF Board(Src, Top(Src)) > Board(Dst, Top(Dst)) THEN
            Tmp = Src
            Src = Dst
            Dst = Tmp
      END IF

'     Move the disk

      Top(Dst) = Top(Dst) + 1
      Board(Dst, Top(Dst)) = Board(Src, Top(Src))
      Board(Src, Top(Src)) = 0    ' Zero out for display purposes
      Top(Src) = Top(Src) - 1

      CALL ShowBoard(Board(), Size)

'     Rotate the blocked pin designation

      Src = Block       ' Trial Src --- old blocked pin

      IF Clockwise THEN
         Block = (Block + 1) MOD 3
      ELSE
         IF Block > 0 THEN Block = Block - 1 ELSE Block = 2
      END IF

      Dst = 3 - (Src + Block)     ' Only one left for Dst

   LOOP

END SUB

SUB ShowBoard (Board(), Size)
   STATIC Selah         ' Just ask once for this; hence STATIC
   IF Selah = 0 THEN
      LOCATE 19, 20
      INPUT "Number of seconds per display (0 for none): ", Selah
      IF Selah = 0 THEN Selah = -1
'     Wipe out the dialog line
      LOCATE 19, 20
      PRINT SPACE$(59)
   END IF

   FOR Level = Size TO 1 STEP -1
      LOCATE 15 - Level, 30
      FOR Pin = 0 TO 2
         IF Board(Pin, Level) = 0 THEN
            PRINT USING "\    \"; " ";
         ELSE
            PRINT USING "######"; Board(Pin, Level);
         END IF
      NEXT
   NEXT
  
   LOCATE 15, 30        ' Print the base
   FOR Pin = 0 TO 2
      PRINT "-----+";
   NEXT
   PRINT "-----"

   LOCATE 19, 30        ' Pause --- fixed time or until user action
   IF Selah > 0 THEN
      SLEEP (Selah)
   ELSE
      INPUT "Press Enter to continue:  "; Dmy$
      LOCATE 19, 30
      PRINT SPACE$(49)  ' Wipe out user dialog
   END IF

END SUB