This week in CSC148 we spent time looking at the details of our first assignment this semester. An advanced version of the classic game of the Tower of Hanoi, where the goal is to move a stack of disks of descending sizes from one peg to another, using three pegs. The only rules are:
1. You’re only allowed to move one disk at a time, and, 2. You cannot stack a bigger disk on top of a smaller one.
here’s where the excitement comes Professor Danny, changed the traditional Tower of Hanoi story around so we had to figure out the algorithm to optimally transfer Anne Hoy’s stacks of cheese, rather than discs from one stool to another, using four stools (the extra being her recent investment) to reduce the number of steps necessary for moving larger and larger piles of cheeses. The optimal solution for the traditional Tower of Hanoi problem is said to have a run time of 2^n – 1.
“Ann Hoy kept her high-quality cheese stacked on stools, the largest rounds underneath the smaller rounds, to stop rats and mice from getting at them. Occasionally the stool holding the cheese would need some maintenance (for example, the legs would start to buckle under the weight), and Anne would shift the entire stack from one stool to another. Since she could only move a single (hundred-pound plus) round of cheese at one time, and she refused to stack a larger-diameter cheese round on a smaller one (the outer part of the larger cheese would droop) she used three stools: one was her destination for her entire stack of cheese, one was the source (which likely needed its legs reinforced), and the third was for intermediate stacking. Chaucer immortalized the complicated routine Anne endured, lugging rounds of cheese from stool to stool as “The tour of Anne Hoy.”
Prof Danny, really emphasized the importance of recursive functions to be used for the expected solution, as this assignment was a means to teach us how to use recursion. After days of frustrating sessions of coding I couldn’t wrap my head around how a simple solvable problem with 3 pegs can be made dramatically more difficult by slightly loosening one of the constraints (i.e 4 pegs). After writing pages and pages of Psuedo code it suddenly hit me! I was thinking about how to implement the recursion too complexly, recursion an art an art where simple thinking is highly regarded. So pretty much my four stool function can call itself over and over again until it reaches a certain threshold (base case), where the all the cheeses are moved to the destination peg which allows the operation to terminate. This 4 stool solution required me to find the least number of moves required to move any given number of cheeses using 4 stools and pass that value into the recursive function. To me implementing this part was the certainly one of the more challenging aspects of this assignment. When I finally figured out the logic behind it I felt a great deal of satisfaction! I am now confident in my capabilities to implement recursive function. Who’s excited for assignment 2, I know I am!
That is all for this week folks, Stay Hungry. Stay Foolish!
yours truly, – “CodeShark”