8
\$\begingroup\$

I came across an interesting method of solution for the Tower of Hanoi puzzle and wrote a short version of it as a programming exercise.

The program produces the correct results but I have two questions.

First is there simpler way to write the alternating step of determining the only valid move which does not involve the smallest disk.

Second when I try to make the two primary routines (move smallest disk and make alternating move) into functions the handling of variables becomes unwieldy.

/* tower.c

   Tower of Hanoi -- mechanical solution
   
   Place one of the three rods upright at each corner of a triangle.

   Alternate between moving the smallest disk and making the only valid move
   which does not involve the smallest disk.

   The smallest disk always moves in the same direction: counter-clockwise if
   there are an odd number of disks in the puzzle; clockwise if there are an even
   number of disks in the puzzle.

   from "The Icosian Game and the Tower of Hanoi" in THE SCIENTIFIC AMERICAN BOOK OF
   MATHEMATICAL PUZZLES & DIVERSIONS by Martin Gardner, (Simon and Schuster, 1959),
   pp. 55 - 62
*/

#include <stdio.h>
#include <stdbool.h>

int destinationCount (int array[], int numberOfElements)
{
    int count = 0, i;
    
    for ( i = 1; i <= numberOfElements; ++i )
        if ( array[i] == 3 )
            ++count;

    return count;
}

int main (void)
{ 
    int numberOfDisks, i, smallestDir, moveCount = 0;  
    bool everyOtherMove = false;
    int rodFrom, rodTo, disk;
    int topDisk[4];
    int temp;
                
    printf ("\nTower of Hanoi puzzle\n");
    
    printf ("\nnumber of disks? ");
    scanf ("%i", &numberOfDisks);
    
    int rod[numberOfDisks + 1];
    
    // all disks start on rod 1
    
    for ( i = 1; i <= numberOfDisks; ++i )
        rod[i] = 1;
    
    // set direction to move smallest disk
    
    if ( (numberOfDisks & 1) == 0 )
        smallestDir = 1;
    else
        smallestDir = -1;    
    
    printf("\nsolution\n\n");
        
    do {
        
        ++moveCount;
    
        if ( ! everyOtherMove ) {
        
            // move smallest disk
            
            rodFrom = rod[1];
            
            rodTo = rodFrom + smallestDir;
            if ( rodTo > 3 )
                rodTo = 1;
            if ( rodTo < 1 )
                rodTo = 3;
            
            disk = 1;

        }
        else {
        
            // make only valid move not involving the smallest disk
            
            // find disk at the top of each rod

            for ( i = 1; i <= 3; ++i )
                topDisk[i] = numberOfDisks + 1;
                
            for ( i = numberOfDisks; i >= 1; --i )
                topDisk[rod[i]] = i;            

            // find which disk to move
            
            switch ( rod[1] )
            {
                case 1:
                    rodFrom = 2;
                    rodTo = 3;
                    break;
                case 2:
                    rodFrom = 1;
                    rodTo = 3;
                    break;
                case 3:
                    rodFrom = 1;
                    rodTo = 2;
                   break;
                default:
                    printf ("error");
                    break;
            }            

            if ( topDisk[rodFrom] > topDisk[rodTo] ) {
                // swap values
                temp = rodFrom;
                rodFrom = rodTo;
                rodTo = temp;            
            }
            
            disk = topDisk[rodFrom]; 

        }    
            
        printf ("%i: disk %i rod %c to rod %c\n", moveCount, disk, 
                 rodFrom + 64, rodTo + 64);
        
        // move disk
        
        rod[disk] = rodTo;
                
        // toggle everyOtherMove
        
        everyOtherMove = ! everyOtherMove;
        
    }
    while ( destinationCount (rod, numberOfDisks) != numberOfDisks );
    
    return 0;
}   
\$\endgroup\$
1

2 Answers 2

4
\$\begingroup\$

Remove the everyOtherMove flag variable

You use it only once to control the logic of your program:

if ( ! everyOtherMove ) {

and this usage may be substitued with a evenness check of the moveCount variable that you would have anyway.

Do not declare vars so much before using them

At line 36 temp is declared as an int, at line 113 temp is used for the first time. How can the reader remember the type of temp 77 lines later? Declare it just before using it.

Loop variables should be declared inside the loop statement as C99 allows it.

Use ternary when it clearly simplifies

if ( (numberOfDisks & 1) == 0 )
    smallestDir = 1;
else
    smallestDir = -1;    

Becomes

int smallestDir = (numberOfDisks & 1) == 0 ? 1 : -1

Much shorter and without the smallestDir = repetition.

Using % instead of bitwise operations to check evenness would be a further improvement.

Reduce main (both code and vertical whitespace)

I introduce this helper function:

int wrap_around(int min, int max, int value)
{
    return value < min ? max : (value > max ? min : value);
}

(Please note that it could also be written with if conditionals, I wrote it like this just because of my familiarity with ternary).

The first if branch now is:

    if (moveCount % 2 == 0) {
        // move smallest disk
        rodFrom = rod[1];
        rodTo = wrap_around(1, 3, rodFrom + smallestDir);
        disk = 1;
    }

while before it was:

    if ( ! everyOtherMove ) {

        // move smallest disk

        rodFrom = rod[1];

        rodTo = rodFrom + smallestDir;
        if ( rodTo > 3 )
            rodTo = 1;
        if ( rodTo < 1 )
            rodTo = 3;

        disk = 1;

    }

The same concept is expressed in much less space, and this is a good attribute in my view because:

  • Some logic is modularized in other functions, the reader gets a more abstract overview.
  • If all code is compacted this way an overall view of the program becomes possible helping understanding.

Compacting the else clause

    else {

        // make only valid move not involving the smallest disk

        // find disk at the top of each rod

        for ( i = 1; i <= 3; ++i )
            topDisk[i] = numberOfDisks + 1;

        for ( i = numberOfDisks; i >= 1; --i )
            topDisk[rod[i]] = i;            

        // find which disk to move

        switch ( rod[1] )
        {
            case 1:
                rodFrom = 2;
                rodTo = 3;
                break;
            case 2:
                rodFrom = 1;
                rodTo = 3;
                break;
            case 3:
                rodFrom = 1;
                rodTo = 2;
               break;
            default:
                printf ("error");
                break;
        }            

        if ( topDisk[rodFrom] > topDisk[rodTo] ) {
            // swap values
            temp = rodFrom;
            rodFrom = rodTo;
            rodTo = temp;            
        }

        disk = topDisk[rodFrom]; 

    }    

I do not fully understand the uppermost two for loops but both the switch and the body of the if ( topDisk[rodFrom] > topDisk[rodTo] ) statement are performing very clear, specific tasks, so:

    else {
        // make only valid move not involving the smallest disk
        // find disk at the top of each rod
        for ( i = 1; i <= 3; ++i )
            topDisk[i] = numberOfDisks + 1;
        for ( i = numberOfDisks; i >= 1; --i )
            topDisk[rod[i]] = i;            

        // find which disk to move
        find_start_and_destination(rod[1], *rodFrom, *rodTo);
        if ( topDisk[rodFrom] > topDisk[rodTo] ) {
            SWAP(rodFrom, rodTo);    
        }
        disk = topDisk[rodFrom]; 

    }    

I just removed the unnecessary blanklines (blanklines should separate logically separated blocks of code, not each line / statement), and used a function to incorporate the switch and a macro to swap variables. The function must use pointers because two values may not be returned from a function in C, but I think the modularization is still an advantage.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for the review. I use the toggled everyOtherMove flag to emphasize the alternating nature of the algorithm. The bitwise AND operator -- instead of the MOD operator -- reflects a bit of background in assembly language. Also, I've always found the conditional (ternary) operator cryptic -- although it does have a nice underlying if-then-else structure. The uppermost 2 for loops above the switch statement just calculate the smallest disk on each of the 3 rods. I genuinely appreciate the comments. \$\endgroup\$
    – Verbatim
    Aug 6, 2016 at 22:18
  • \$\begingroup\$ @ringzero The flag is another variable to initialise maintain and keep track of, it adds complexity while not being necessary. % is just more intuitive (remainder from division) and the compiler can optimiza it anyway. And ternary is very underrated in my opinion conditon ? Iftrue : Iffalse that's all, nesting them may get complex but a single one is clear. Ok thanks for explaining those loops. Thanks to you too for the fine question. \$\endgroup\$
    – Caridorc
    Aug 6, 2016 at 22:20
2
\$\begingroup\$

Here is the most recent version of this Tower of Hanoi program.

This self-answer includes a description of the changes made to the original program.

/* Tower.c

   Tower of Hanoi -- mechanical solution

   Place one of the three rods upright at each corner of a triangle.

                                      rod B
                                        /\
                                       /  \
                                      /    \
                                     /      \
                                    /        \
                                   /          \
                            rod A /------------\ rod C
                           (start)              (finish)

   Alternate between moving the smallest disk and making the only valid move
   which does not involve the smallest disk.

   The smallest disk always moves in the same direction: counter-clockwise if
   there are an odd number of disks in the puzzle; clockwise if there are an
   even number of disks in the puzzle.

   from "The Icosian Game and the Tower of Hanoi" in THE SCIENTIFIC AMERICAN
   BOOK OF MATHEMATICAL PUZZLES & DIVERSIONS by Martin Gardner, (Simon and
   Schuster, 1959), pp. 55 - 62
*/

#include <stdio.h>

#define MAXNUM 10
#define START   0
#define FINISH  2

int isSolved(int arr[], int n)
{
    for (int i = 0; i < n; ++i) {
        if (arr[i] != FINISH) {
            return 0;
        }
    }

    return 1;
}

void swap(int *px, int *py)
{
    int temp = *px;
    *px = *py;
    *py = temp;
}

int isOdd(int x)
{
    return ((x % 2) == 1);
}

int main (void)
{
    printf("\n"
           "Tower of Hanoi puzzle\n"
           "\n");
    int numberOfDisks;
    do {
        printf("number of disks (1 to %d): ", MAXNUM);
        scanf("%d", &numberOfDisks);
    } while ((numberOfDisks < 1) || (numberOfDisks > MAXNUM));

    int rod[numberOfDisks];
    for (int i = 0; i < numberOfDisks; ++i) {
        rod[i] = START;
    }
    int smallestDir = (isOdd(numberOfDisks)) ? -1 : 1;
    int alternateRodTable[3][2] = { {1, 2}, {0, 2}, {0, 1} };

    printf("\n"
           "solution\n"
           "\n");

    int moveCount = 0;
    do {
        ++moveCount;

        int disk, rodFrom, rodTo;
        if (isOdd(moveCount)) {
            // move smallest disk
            disk = 0;
            rodFrom = rod[disk];
            rodTo = rodFrom + smallestDir;
            if (rodTo < START) {
                rodTo = FINISH;
            }
            if (rodTo > FINISH) {
                rodTo = START;
            }
        }
        else {
            // move alternate disk
            // determine which disk is at the top of each rod
            // set default value (empty rod) to greater than the largest disk
            int topDisk[3] = { numberOfDisks, numberOfDisks, numberOfDisks };
            // stack each disk on its respective rod
            // smaller disks overwrite larger disks
            for (int i = numberOfDisks - 1; i > -1; --i) {
                topDisk[rod[i]] = i;
            }
            // select the two rods which do not involve the smallest disk
            rodFrom = alternateRodTable[rod[0]][0];
            rodTo = alternateRodTable[rod[0]][1];
            // check which of the two possible "From => To" moves is valid
            if (topDisk[rodFrom] > topDisk[rodTo]) {
                swap(&rodFrom, &rodTo);
            }
            disk = topDisk[rodFrom];
        }
        rod[disk] = rodTo;

        printf("%4d: disk %2d rod %c => %c\n", moveCount, disk + 1, rodFrom + 'A', rodTo + 'A');
    } while (! isSolved(rod, numberOfDisks));

    return 0;
}

The following changes, suggested by Caridorc, have been included in this version of the program:

Variables are declared just before use (instead of at the beginning of the program). Loop index variables are declared within the loop itself.

Vertical whitespace, mostly in the form of blank lines, has been reduced.

The Boolean flag variable, everyOtherMove, which controlled the alternating moves has been dropped; the alternating moves are now handled by simply testing the odd/even condition of the variable moveCount. This same odd/even test is also used at the beginning of the program to set the value of the variable which determines the direction of movement for the smallest disk.

The more commonly used MOD operator (%) has replaced the bitwise AND operator (&).

The conditional (ternary) statement appears just once: to set the direction to move the smallest disk in the puzzle. This is a simple IF ELSE expression in a single line. I resisted the temptation to use a conditional in two other instances -- when checking whether the smallest disk wraps around when being moved and when selecting the two rods to use in moving the alternate disk. In those two instances the conditionals seemed overly complicated or cryptic.

Other changes include:

A more detailed explanation of the algorithm in the top comment section.

Using 0-based arrays (instead of an array which leaves the zeroth element of the array unused).

Providing a more complete description on determining which disk is at the top of each of the three rods when moving the alternate disk.

Replacing the lengthy Switch statement -- which selects the two rods to use when moving the alternate disk -- with a 3 by 2 element table and just 2 related statements.

The swap routine is now a separate function.

If your compiler does not support variable length arrays the statement int rod[numberOfDisks]; will generate an error -- an error such as "expected constant expression ... array allocation." To resolve this error, in the simplest possible way, change the statement from int rod[numberOfDisks]; to int rod[MAXNUM];

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.