Difference between revisions of "CSC231 Analysis of the Towers of Hanoi"

From dftwiki3
Jump to: navigation, search
(Top Down Version 2)
(Top Down Version 2)
Line 134: Line 134:
 
In this version we fully flesh out the recursive function.  It would be hard to go half way with the implementation of '''moveDisks'''.
 
In this version we fully flesh out the recursive function.  It would be hard to go half way with the implementation of '''moveDisks'''.
  
 +
==Source ==
 
<br />
 
<br />
 
<source lang="asm">
 
<source lang="asm">
Line 242: Line 243:
  
 
Here's how.
 
Here's how.
# comment out the '''%define''' statement in the program (this will result in an undefined variable if we assemble as usual)
+
* comment out the '''%define''' statement in the program (this will result in an undefined variable if we assemble as usual)
# when assembling the program, provide a value for the ''macro'' '''N''' as follows:
+
* when assembling the program, provide a value for the ''macro'' '''N''' as follows:
  
 
   nasm -f elf -F stabs '''-dN=4''' hanoi2.asm  ;  ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
 
   nasm -f elf -F stabs '''-dN=4''' hanoi2.asm  ;  ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
  
:And the result will be that your program will be assembled just as if you had included the line  
+
* The result will be that your program will be assembled just as if you had included the line  
  
 
   %define N 4
 
   %define N 4
  
 
:inside your program.
 
:inside your program.
 +
 +
The section below shows how to make the program run for several values of ''N'':
 +
 +
==Output==
 +
 +
<br />
 +
<code><pre>
 +
[231a@beowulf ~/handout]$ nasm -f elf -dN=2 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
 +
A C
 +
A B
 +
C B
 +
[231a@beowulf ~/handout]$ nasm -f elf -dN=3 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
 +
A B
 +
A C
 +
B C
 +
A B
 +
C A
 +
C B
 +
A B
 +
[231a@beowulf ~/handout]$ nasm -f elf -dN=4 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
 +
A C
 +
A B
 +
C B
 +
A C
 +
B A
 +
B C
 +
A C
 +
A B
 +
C B
 +
C A
 +
B A
 +
C B
 +
A C
 +
A B
 +
C B
 +
 +
</pre></code>
 +
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
[[Category:CSC231]]

Revision as of 18:02, 25 November 2012

--D. Thiebaut 16:24, 25 November 2012 (EST)


A High-Level Version in Python


# hanoi.py  (Python V 2.7)
# D. Thiebaut
# implements the game of hanoi in python.
# uses recursion.
#
# to run, type 
#        python hanoi.py 
# at the command line

def moveDisk( source, dest, extra, n ):
    if n==1:
        print "move disk from %s to %s" % ( source, dest )
        return
    
    # more than 1 disk...
    moveDisk( source, extra, dest, n-1)
    print "move disk from %s to %s" % ( source, dest )
    moveDisk( extra, dest, source, n-1)

def main():
    while True:
        n = input( "# of disks? " )
        moveDisk( "A", "B", "C", n )

main()



Top Down Approach: Version 1

Source

In this version all we do is simply set a main program that calls the function moveDisks and passes it

  • the number of disk to move (in al)
  • the source peg (in bl)
  • the destination peg (in cl)
  • and the extra or temporary peg (in dl)

The moveDisks function prints a single move, testing the printMove function that prints "X Y" on a line by itself, indicating that a disk must be move from X to Y.


;;; hanoi1.asm
;;; D.T.
;;; Towers of Hanoi, top down...


;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg

		section	.data
moveStr		db	"X --> X", 10
moveStrLen	equ	$-moveStr
source		equ	moveStr + 0
dest		equ	moveStr	+ 6	

	section	.text
	global	_start
;;; ------------------------------------------------------------
;;; M A I N
;;; ------------------------------------------------------------

_start: 	mov	al, 4	; move 4 disks
		mov	bl, 'A'	; from A
		mov	cl, 'B'	; to B
		mov	dl, 'C'	; using C as extra
	
		call	moveDisks

;;; return to OS
		mov	eax, 1
		mov	ebx, 0
		int	0x80

;;; ------------------------------------------------------------
;;; moveDisks:
;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg
;;; Does not return anything
;;; does not modify registers
;;; ------------------------------------------------------------
moveDisks:	push	ax
		push	bx
		push	cx
		push	dx

		mov	byte[source], bl
		mov	byte[dest], cl
		call	printMove
	
		pop	dx
		pop	cx
		pop	bx
		pop	ax
		ret

;;; ------------------------------------------------------------
;;; printMove
;;; Prints the string moveStr on the screen
;;; Does not alter any register
;;; ------------------------------------------------------------
printMove:	pushad
		mov	eax, 4
		mov	ebx, 1
		mov	ecx, moveStr
		mov	edx, moveStrLen
		int	0x80
		popad
		ret


Output

[231a@beowulf ~/handout]$ nasmld hanoi1
A --> B

Top Down Version 2

In this version we fully flesh out the recursive function. It would be hard to go half way with the implementation of moveDisks.

Source


;;; hanoi2.asm
;;; D.T.
;;; Towers of Hanoi, top down...


;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg

%define		N	6	; number of disks to move
	
		section	.data
moveStr		db	"X X", 10
moveStrLen	equ	$-moveStr
source		equ	moveStr + 0
dest		equ	moveStr	+ 2	

	section	.text
	global	_start
;;; ------------------------------------------------------------
;;; M A I N
;;; ------------------------------------------------------------

_start: 	mov	al,  N	; move 4 disks
		mov	bl, 'A'	; from A
		mov	cl, 'B'	; to B
		mov	dl, 'C'	; using C as extra
	
		call	moveDisks

;;; return to OS
		mov	eax, 1
		mov	ebx, 0
		int	0x80

;;; ------------------------------------------------------------
;;; moveDisks:
;;; assumptions:
;;; al = n   		Number of disk
;;; bl = Source 	character identifying the source
;;; cl = Dest		character identifying the destination
;;; dl = Temp		character identifying the extra peg
;;; Does not return anything
;;; does not modify registers
;;; ------------------------------------------------------------
moveDisks:	push	ax
		push	bx
		push	cx
		push	dx

		cmp	al, 1
		ja	.recurse
	
;;; only 1 to move: move from source to dest!
		mov	byte[source], bl
		mov	byte[dest], cl
		call	printMove
		jmp	.return

.recurse:
;;; move n-1 disk from source to temp
		dec	al	; al <-- n-1
		xchg	cl, dl	; swap dest and temp
		call	moveDisks
		xchg	cl, dl	; swap back dest and temp
	
;;; move 1 from source to dest
		push	ax
		mov	al, 1
		mov	byte[source], bl
		mov	byte[dest], cl
		call	printMove
		pop	ax
	
;;; move n-1 disk from temp to dest
		xchg	bl, dl	; make temp the source
		call	moveDisks
	
.return:	pop	dx
		pop	cx
		pop	bx
		pop	ax
		ret

;;; ------------------------------------------------------------
;;; printMove
;;; Prints the string moveStr on the screen
;;; Does not alter any of the registers
;;; ------------------------------------------------------------
printMove:	pushad
		mov	eax, 4
		mov	ebx, 1
		mov	ecx, moveStr
		mov	edx, moveStrLen
;;; 		int	0x80
		popad
		ret


Note here that we are using a macro, N, defined by the %define statement. This method of defining a constant is interesting as it allows us to modify the constant at assembly time.

Here's how.

  • comment out the %define statement in the program (this will result in an undefined variable if we assemble as usual)
  • when assembling the program, provide a value for the macro N as follows:
  nasm -f elf -F stabs -dN=4 hanoi2.asm  ;  ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
  • The result will be that your program will be assembled just as if you had included the line
  %define N 4
inside your program.

The section below shows how to make the program run for several values of N:

Output


[231a@beowulf ~/handout]$ nasm -f elf -dN=2 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
A C
A B
C B
[231a@beowulf ~/handout]$ nasm -f elf -dN=3 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
A B
A C
B C
A B
C A
C B
A B
[231a@beowulf ~/handout]$ nasm -f elf -dN=4 -F stabs hanoi2.asm ; ld -melf_i386 -o hanoi2 hanoi2.o ; ./hanoi2
A C
A B
C B
A C
B A
B C
A C
A B
C B
C A
B A
C B
A C
A B
C B