0
\$\begingroup\$

I've made an algorithm solving Hanoi Tower puzzles, for n disks and m pegs.

It uses lists as pegs, each list's element contains disks array - {0, 0, 0} means the peg is empty, {1, 2, 0} means the peg contains "1" and "2" disks, {3, 0, 0} means the peg contains the biggest disk only.

The algorithm is iterative (and has to be), to solve for 3 pegs it repeats the following steps:

  1. Move smallest disk to the right is number of disks is odd, move it to the left if even
  2. Make only one possible move left, without toughing the smallest disk

Very simple and cool algorithm. If pegs > 3, I repeat the above (pegs - 2) times - divide and conquer, until the last peg is filled.


My problem is that the algorithm is very ugly. As someone said: "If you need more than 3 levels of indentation, you're screwed anyway, and should fix your program.".

I've been thinking on how can I optimize my code for a couple of days, and I do not know what more I could possibly do.

This is the whole program (console output is not in English though, but variables are, so it should be clear enough): http://ideone.com/Jwt4nN

This is the working algorithm on ideone: http://ideone.com/woEg9o

And I'm pasting it here:

void hanoi(rod **head, rod **tail)
{
    time_start();

    rod *temp, *temp2, *head_t = *head;
    int flag = 0, div = 0;

    for(int i = 0; i < rods - 2; i++)
    {
        while((*tail)->disks[n - 1] != n)
        {
            temp = *head, flag = 0;

            if(div % 2 == 0) // move smallest disk to the right if odd, or left if even
            {
                while(temp != (*tail)->next)
                {
                    if(flag == 1)
                    {
                        unshift(1, &temp->disks);
                        break;
                    }
                    if(temp->disks[0] == 1)
                    {
                        pop(&temp->disks);
                        flag = 1;
                    }

                    if(n % 2 == 0)
                    {
                        temp = (temp->next == (*tail)->next) ? *head : temp->next;
                    }
                    else
                    {
                        temp = (temp->prev == (*head)->prev) ? *tail : temp->prev;
                    }
                }
            }
            else // make first possible move
            {
                while(temp != (*tail)->next && flag == 0)
                {
                    temp2 = *head;
                    while(temp2 != (*tail)->next)
                    {
                        if((temp->disks[0] < temp2->disks[0] || temp2->disks[0] == 0) && temp->disks[0] != 1 && temp->disks[0] != 0 && temp->num != temp2->num)
                        {
                            int t = temp->disks[0];
                            pop(&temp->disks);
                            unshift(t, &temp2->disks);
                            flag = 1;
                            break;
                        }

                        temp2 = temp2->next;
                    }

                    temp = temp->next;
                }
            }

            div++, moves++;
        }

        // divide and conquer
        if(i < rods - 3)
        {
            if((*head)->num <= i + 1)
                *head = (*head)->next;
            if((*tail)->num <= i + 3)
                *tail = (*tail)->next;
        }
    }

    *head = head_t;

    time_stop();
}

/**
 * Input: {1, 2, 3, 4, 0}, el = 5
 * Output: {5, 1, 2, 3, 4}
 * 
 * Input array ALWAYS contains 0's at the end
 */
void unshift(int el, int **arr)
{
    for(int i = (int)n - 1; i > 0; i--)
    {
        (*arr)[i] = (*arr)[i - 1];
    }
    (*arr)[0] = el;
}

/**
 * Input: {1, 2, 3, 4}
 * Output: {2, 3, 4, 0}
 */
void pop(int **arr)
{
    for(int i = 0; i < (int)n - 1; i++)
    {
        (*arr)[i] = (*arr)[i + 1];
    }   
    (*arr)[n - 1] = 0;
}

ROD is the name of the list structure. Head points to the first element, tail to the 3rd (at the beginning). If pegs > 3, head and tail move to the right repeatedly (pegs - 3) times.

If anything would be unclear, please write this in the comment, and I'll try to explain it best as I can.

Any suggestions would be welcomed.

EDIT: You say it does not compile. I am using Visual Studio 2012, and it does compile for me - .cpp extension, C++ file, and I guess the compiler is also for C++.

\$\endgroup\$
  • \$\begingroup\$ Your link to 'the working algorithm' leads to code that does not compile. \$\endgroup\$ – SylvainD Apr 9 '13 at 10:51
  • \$\begingroup\$ As this code contains errors, it should be posted on Stack Overflow instead. Once it does work, you could always edit it into this post and someone could help with other concerns. \$\endgroup\$ – Jamal Apr 9 '13 at 11:42
  • \$\begingroup\$ It compiles in Visual Studio with .cpp extension. (C++ compiler) \$\endgroup\$ – user2251921 Apr 9 '13 at 14:44
  • \$\begingroup\$ Pass input like 3, and 3 for both scanf's. \$\endgroup\$ – user2251921 Apr 9 '13 at 14:45
  • 3
    \$\begingroup\$ @Roland, I'd say the correct close reason for that is Insufficient Context (we're just missing the declarations, just as we're missing the forward-declarations of pop() and unshift()). Broken/Unimplemented is should be used on questions where the code is unfinished, rather than having parts that clearly exist somewhere but omitted from the question. \$\endgroup\$ – Toby Speight Nov 29 '19 at 9:27
3
\$\begingroup\$

The biggest problem is that there is very little abstraction going on here. There are plenty of places where a helper function would come in handy, but isn't used, and an object or abstract data type would be good for the individual rods or the set of rods as a whole. We can't get the big picture of what's going on if we're worried about what this boolean or that pointer are doing, instead of where this disk on that rod is going to go.

I should be able to at least mostly read the hanoi() function with only an understanding of the towers of hanoi problem; I should not need any idea how you implemented the details of the rods or disks. When I tried to read it, I saw a for loop that contained a while loop that contained an if statement that contained a while loop that contained an if statement, and I had no idea what was going on. If it had been a for loop that contained a while loop that had instructions on which disks to put on which rods, it probably would have been easy to read.

Names could also use some work. temp and temp2 should probably be source_rod and target_rod, if I haven't misunderstood their purpose. unshift should probably be push. I don't know what div should be. It does get used with the mod operator, but that isn't what it is, just how it's used. flag is a flag, but I don't know what it means. It might mean that a move has been made. Name flags after what the flag would mean if it were true. If flag == true means the universe is going to blow up, don't name it flag, name it something like universe_is_doomed.

If I've guessed correctly about what everything is doing, then this bit of code:

 int t = temp->disks[0];
 pop(&temp->disks);
 unshift(t, &temp2->disks);
 flag = 1;

should be more like this:

 int disk = pop(&source_rod);
 push(disk, &target_rod);
 moved = 1;
\$\endgroup\$

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