Objective C - Towers of Hanoi

So I was playing around with Objective-C. Got an idea of the basic syntax of the language, setup the GNUStep environment to compile objective-c code without a MAC and wrote the following tutorial. Still not close to IPhone development yet, the problem is though that it is difficult to do without a MacOS. Or, maybe I'll use the toolchain with iphone 2 sdk, but then, that will be outdated.

This is a short tutorial on implementation of Towers of Hanoi in Objective-C. Of course, there is not much to implement in the algorithm itself, the code is useful to give some nitty-gritty of objective-c syntax and coding methodoloy.

The code is available for free download. Please link back and use as desired.

Problem Description:

Read more about the "Towers of Hanoi" problem on wikipedia here. Short description (borrowed from wikipedia for completeness of tutorial):

The puzzle starts with the disks neatly stacked in order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

• Only one disk may be moved at a time.
• Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
• No disk may be placed on top of a smaller disk.

Algorithm Solution:

The solution to the problem involves recursion. Let's say there are n disks and three pegs numbered 1, 2, 3. Further, assume that initially all the disks are stacked on Peg #1 and the goal is to move all the disks on Peg #3. This can be achieved by moving n-1 disks to Peg #2 and then moving the last disk to Peg #3. After this n-1 disks can be moved from Peg #2 to Peg #3. We have to use the same algorithm for (n-1) disks until we reach n=1 (disk) for which the solution is simply to move from Peg #1 to Peg #3.

Here is the pseudo-code for solving the problem:

def Hanoi(PegFrom, PegTo, PegVia, numDisks):
 if numDisks == 1:
     print 'Move the disk from', PegFrom, 'to', PegTo
 else:
     Hanoi(PegFrom, PegVia, PegTo, numDisks - 1)
        Hanoi(PegFrom, PegTo, PegVia, 1)
        Hanoi(PegVia, PegTo, PegFrom, numDisks - 1)

where
    numDisk = number of disks,
    PegFrom = labeled Peg from which the disks will be moved,
    PegTo = label Peg to which the disks will be moved,
    PegVia = the third peg which is used to help the transition.

Objective-C Implementation:

This code has been tested on GNUStep but should work on XCode/Cocoa framework too.

For a short tutorial to Objective-C read here.

Lets get started. First you'll need GNUStep installed or XCode (for Mac users).

On Ubuntu linux, this is straight forward by the following command: sudo apt-get install gnustep gnustep-devel gnustep-games

To check whether GNUStep is successfully installed, execute the following command: gnustep-config --variable=GNUSTEP_MAKEFILES,
the output should give you the location of GNUstep/Makefiles directory e.g. /usr/share/GNUstep/Makefiles.

At this point you are ready to write code. Please create all the following files mentioned below in the same directory or ensure proper path linkages if that is not going to be the case. The entire source code package can be downloaded here.

The Interface:

Create a file named TowersOfHanoi.h and put the following code in it:

//Filename: TowersOfHanoi.h
//Author: Vinod Shukla

#import

@interface TowersOfHanoi: NSObject {
int pegFrom;
int pegTo;
int pegVia;
int numDisks;
}

-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks;
-(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks;
@end

Explanation of the code:

• Create of TowersOfHanoi object which extends the NSObject.
• Define the instance variables.
• Create setters.
• Create the move peg function.

The Implementation:

Create a file named TowersOfHanoi.m and put the following code in it:

//FileName: TowersOfHanoi.m
//Author: Vinod Shukla
#import "TowersOfHanoi.h"
@implementation TowersOfHanoi

-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks {
pegFrom = from;
pegTo = to;
pegVia = via;
numDisks = disks;
}

-(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks {
if (disks == 1) {
printf("Move disk from pole %i to pole %i", from, to);
printf("\n");
} else {
[self movePegFrom: from andMovePegTo: via andMovePegVia: to andWithNumDisks: disks-1];
[self movePegFrom: from andMovePegTo: to andMovePegVia: via andWithNumDisks: 1];
[self movePegFrom: via andMovePegTo: to andMovePegVia: from andWithNumDisks: disks-1];
}
}
@end

Explanation of the code:

• Implement the setter function.
• Implement the recursive algorithm for moving the disks. Notice the self keyword which is akin to this in Java and C++. We are calling the function recursively with n-1 disks.
  

Thus we have successfully written the code to solve Towers of Hanoi in Objective-C.

A Test Harness:

Let's create a main method to test our implemenation above. Create a file named TowersTest.m and put the following code in it.

//FileName: TowersTest.m
//Author: Vinod Shukla
#import
#import "TowersOfHanoi.h"

int main( int argc, const char *argv[] ) {
TowersOfHanoi *tower = [[TowersOfHanoi alloc] init];

int from = 1;
int to = 3;
int via = 2;
int disks = 3;

[tower setPegFrom: from andSetPegTo: to andSetPegVia: via andSetNumDisks: disks];

[tower movePegFrom: from andMovePegTo: to andMovePegVia: via andWithNumDisks: disks];

return 0;
}


The code above solves the case of three disks to be moved from Peg 1 to Peg 3. You can increases disks = any positive number n to tests for n disks.

Makefile:

A simple makefile to compile and run the above code. Create a file called GNUmakefile and put the following snippet:

#FileName: GNUmakefile
#Borrowed from: http://www.gnustep.it/nicola/Tutorials/WritingMakefiles/node2.html
include $(GNUSTEP_MAKEFILES)/common.make

TOOL_NAME = TowersTest
TowersTest_OBJC_FILES = TowersOfHanoi.m TowersTest.m

include $(GNUSTEP_MAKEFILES)/tool.make


Install Script:

A one line utility script to generate the executables. You can also use the command line instead. Create a file called install.sh and copy the following:

#FileName: install.sh
make GNUSTEP_MAKEFILES=`gnustep-config --variable=GNUSTEP_MAKEFILES` install

Clean Script:

A one line utility script to clean up the executables directory. Command line can be used too. Create a file called install.sh and copy the following:

#FileName: clean.sh
make GNUSTEP_MAKEFILES=`gnustep-config --variable=GNUSTEP_MAKEFILES` clean

Additional Instructions:

• Assuming your GNUstep is correctly setup, extract the attached TowersOfHanoi.tar.gz to any directory.
• Make the install.sh and clean.sh scripts executable using chmod.
• To compile the code, run ./install.sh from the TowersOfHanoi directory. This will generate a TowersOfHanoi/obj directory containing an executable TowersTest.
• The output of the program is obtained by executing ./obj/TowersTest.

Links:

• Tower of Hanoi - Wikipedia Article
• Objective C - Apple Website
• Objective C - Beginners Guide
• GNUStep - official site
• XCode
• Rosetta Code, Tower of Hanoi. I contributed my code here.
• HanoiMania. The site also presents an alternative unrelated implementation of this problem in objective-c.