Homework 3

Computer Architecture I ShanghaiTech University
HW2 HW3 HW4

General Towers of Hanoi

Your task is to write a program in MIPS assembler that can solve any given Tower of Hanoi status. See a description of the problem here.
Write the program in a file called towers.s and add it to the gradebot repository. The goal of the program is to move all pegs onto the tower 0.
Use MARS (see Lab 2) to test your program (the gradebot uses MARS).
IMPORTANT: In your assembler program you are not allowed to use the registers $t0, $t1, $s0, $s1. Also you cannot use number registers (e.g. $17) but have to use name registeres!

Input Format

The tower will be given to you on the standard in stream as numbers followed by a new line. Positive numbers between 1 and 31 will denote the pegs. The maximum number of pegs is 31. If you read a -1 this tower is finished and the next tower (if there is one) will be populated. There are three towers in total. All inputs will be valid towers of hanoi: There will be no bigger peg ontop of a smaller one, and if there are n pegs in total those will be numbered between 1 and n. Each peg (number) will occur only once. Example:
4
2
-1
-1
3
1
-1

Output Format

For every move that you perform with a peg your program has to print the following output on standard out:
"Peg %d : %d to %d", peg, fromTower, toTower
The gradbot will use this information to judge if this was a valid move or not.
Your towers have to have the numbers 0, 1 and 2.
For example (the Tower output is optional):
Tower number 0 :
Tower number 1 : 3 2 1
Tower number 2 :
Peg 1 : 1 to 0
Peg 2 : 1 to 2
Peg 1 : 0 to 2
Peg 3 : 1 to 0
Peg 1 : 2 to 1
Peg 2 : 2 to 0
Peg 1 : 1 to 0
Tower number 0 : 3 2 1
Tower number 1 :
Tower number 2 :

Grading

The gradebot will assemble and run your program with 4 test cases to see if your program is working in principle. Then your program will have to solve a sizable tower. The gradbot will save the number of moves that your program made as the score. This number will deterimne your score - less moves are better!
The provided algorithm solves the problem in a sub-optimal way and needs 4076 moves. But it is known that there exists a solution to that specific start tower with 3754 moves - but one can also do even better!

Grading: The submission with the least number of moves (moves_min) is found. If moves_min is smaller than 4000 the following grading will be applied to all students with less than 4076 moves:
score = (1 + (4076 - your_moves) / (4076 - moves_min)) * 100
So the student with the best score gets 100% bonus points.
Formula for students with more than 4076 moves (should not happen if you implement the algorithm below):
score = max(0, (8152 - your_moves) / 4076 )

The key to getting less than 4076 moves is a better algorithm - not better assembler programming!

Simple Algorithm

The algorithm can be broken down into two parts:
  1. Moving a stack of consecutive pegs from one tower to another.
  2. Determine what to move where when provided an unsorted tower.

Moving a stack of pegs

movePegs(fromTower, toTower, unusedTower, numberOfPegs)
  if numberOfPegs == 1
    move one peg from 'fromTower' to 'toTower'
  else
    movePegs(fromTower, unusedTower, toTower, numberOfPegs-1) // move all pegs except the lowest to the side
    movePegs(fromTower, toTower, unusedTower, 1) // move lowest of our pegs to the goal
    movePegs(unusedTower, toTower, fromTower, numberOfPegs-1) // move all those pegs to the goal

Deal with the unsorted tower

while not finished:
	find tower having peg 1 on top
	count how many consecutive pegs are on that tower starting from the top (e.g. 7 5 3 2 1 => 3 )
	find the tower that has the next peg on top (e.g. 3 from above - find tower with 4 on top)
	movePegs(towerWithOne, towerWithNextPeg, unusedTower, numberOfConsecutivePegsOnOne)
So basically this algorithm looks for the tower with peg 1 and then moves all pegs that are consecutive below 1 to the tower with the next peg. Thus afterwards the size of your consecutive stack will have grown by (at least) one. If you finish this algorithm and do not end up at tower 0 you have to move your stack to tower 0.

Notes