towers of hanoi

Hi there all,
I am working on the towers of hanoi problem. I do know the algorithm for it but there is some fancy stuff i need to do with it. I need to print all the moves for the discs as in below
|_        |       |
|_ _      |       |
|_ _ _   |       |  

|        |       |
|_ _    |       |
|_ __  |_      |  

|         |        |
|         |        |
|_ _ _  |_      |_ _   and so on....

I need to use structures for the pegs.
I am aware i need to keep the track of the peg numbers and the corresponding discs.  I am also confused in movin the discs from one peg to another. I just need to know that how would i incorporate this into a structure so that it'll be convenient to move items in the structure.
Here is my code(although its not correct syntax wise, but this is what i am trying to do)
#include<stdio.h>

typedef char TowerEntry;    
typedef struct towernode{      
        TowerEntry peg,disc;  
        struct TowerNode *next;
}TowerNode;

typedef struct tower{
        TowerNode *top;
        char initialdisc;
}Tower;

TowerNode *MakeNode(TowerEntry item1, TowerEntry item2);
void Move(int num, Tower *t1, Tower *t2, Tower *t3);

int N; /*global variable*/

TowerNode *MakeNode(TowerEntry item1, TowerEntry item2){
        TowerNode *nodepointer;
        if((nodepointer=malloc(sizeof(TowerNode)))==NULL)
            printf("Out of memory\n");
        else
        {
                nodepointer->peg=item1;
                nodepointer->disc=item2;
                nodepointer->next = NULL;
               
        }
        return nodepointer;
}

/*to be used initially*/
void TowerPush(TowerEntry item1, TowerEntry item2, Tower *s){
        TowerNode *np=MakeNode(item1, item2);
        if(np==NULL)
                printf("Can't push on an non existing node\n");
        else
        {
                np->next=s->top;
                s->top=np;
        }

}
void CreateTower(Tower *s){
        s->top=NULL;
        s->size=N;
}

int main(int argc, char *argv[]){
     
        int i;
        N=atoi(argv[1]);
        Tower *t1,*t2,*t3;
        CreateTower(t1);
        CreateTower(t2);
        CreateTower(t3);
        for(i=0;i<N;i++)
        {
         printf("%s|%s   %s|     %s|\n   ",t1,t1->initialdisc,t2,t3);
  }
        Move(N,t1,t2,t3);
        return 0;
}

void Move(int count, Tower *one, Tower *two, Tower *three)
{
    if (count > 0) {
        Move(count-1, one, two, three);
        printf("Move a disk from %d to %d.\n", one, three);
        Move(count-1, two, three, one);
    }
}

Could someone, give me suggestions on what changes i need to make or what am i missing or what strategy should i follow?

Thank You

Aik_21


aik_21Asked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
HI Aik-21,

Sorry for not getting back sooner, I missed your reply.


You're back to making things harder than they have to be.  :)

You're only managing two type of objects.  Pegs and disks.  Pegs are "fixed" commodities.  The don't move, they don't change shape, they don't do anything, except house the disks.  The Peg definitions are kept as arrays.

The definition of the disks is equally stable.  Define a disk structure for every disk in the game and initialize it to the correct values.

Now the only things that you have are:

Pegs peg[3];
Disks disk[SomeNumber];


And the entire structure is controlled with two if statements:


if (peg[0]->disk != NULL)   /*  This peg has a disk on it  */

if (disk->next != NULL)   /*  this disk has a disk on top of it  */


The 3 pegs are a simple array and the disks on top of the pegs are kept as linked lists.
Kent

0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi aik_21,

Unless your assignment specifically tells you to use a linked list, throw it in the trash.  This isn't an application for it.

Instead, create an array of nodes.

Finding node 5 is a lot easier in an array than a linked list.  :)


Kent
0
 
aik_21Author Commented:
Hi Kent,

Correct me if i am wrong, but isn't an array of nodes similar to linked lists?  I mean linked lists have nodes!

Thanks

Aik_21
0
Will You Be GDPR Compliant by 5/28/2018?

GDPR? That's a regulation for the European Union. But, if you collect data from customers or employees within the EU, then you need to know about GDPR and make sure your organization is compliant by May 2018. Check out our preparation checklist to make sure you're on track today!

 
brettmjohnsonCommented:
Yes, but an array makes it much easier to access the nodes.  
A linked list is usually accessed sequentially, whereas an array can be accessed randomly.

But then again, I can't figure out why you "need to use structures" for the Tower of Hanoi game.
Structures are not really any more suitable a tool to use for the problem than linked lists are.
(A 3-peg ToH puzzle needs only an array of 3 nibbles  to solve).

Are CS instructors actually so lame that they cannot think up suitable problems for which the
concept-to-be-taught is actually useful?

0
 
jhshuklaCommented:
use a stack of ints.
0
 
jhshuklaCommented:
its true that you can only access the top element but in towers of hanoi you are not allowed to other discs. can't think of a better way to store unless it is requierd to access lower discs.
0
 
Amritpal SinghCommented:
i'll go with jhshukla in implementing this problem using stacks
coz keeping track of lower disks will be much easy
0
 
stefan73Commented:
Yes, the ToH is basically copying one stack to another in the same order, using only a 3rd stack as temporary storage.

solving ToH with nested target.push(source.pop()) is quite an elegant way.

And yes, you should use an array. The maximum size is known, as ToH is O(2^n). If you have a max array size of, say, 32, you'll never likely run out of tower stacks :-)

Cheers!

Stefan
0
 
jhshuklaCommented:
why arrays? for storing moves?
0
 
Kent OlsenData Warehouse Architect / DBACommented:

One of the features of these kinds of games (simulations) is that you often want to change the dynamics of the game.  Increase the number of towers, number of disks, etc.  This can easily be done with both arrays and lists.

typedef struct
{
  int DiskNumber;
}  disk_t;

typedef struct
{
  int DiskCount;  /*  Number of disks on the tower  */
  disk_t Disk[MAX_DISKS];
}  tower_t;

tower_t Tower[MAX_TOWERS];

AddDisk (TowerNumber, DiskNumber);
RemoveDisk (TowerNumber);

etc are trivial.



Kent
0
 
aik_21Author Commented:
Hi guys,
first of all thank you very much for your answers.

I need to use stacks for this program, not cuz we have to but i do have a sound understanding for the topic and need to do it in a way I would understand.  I needed to use the move function such that it uses POP and PUSH functions for the tower entries to be moved.

Can someone tell me if the structure below makes sense, or i would fall into problems?

typedef char TowerEntry;    
typedef struct towernode{      
        TowerEntry peg; // '|'
TowerEntry disc; // '_'
        struct TowerNode *next;
}TowerNode;

typedef struct tower{
        TowerNode *top;
}Tower;


Thank You

Aik_21
0
 
Kent OlsenData Warehouse Architect / DBACommented:

It makes sense.  Though you're mixing typedefs and structs in the TowerNode.  

A simple forward reference will allow you to typedef the structure and remove the need for a struct qualifier within the structure.


Kent


0
 
aik_21Author Commented:
Hey Kent,

Thank you for the quick tip!

I have made some changes to my structure.
typedef char Disc;
typedef struct peg{
        Disc dsc[5]; // '_'
}Peg; // '|'
typedef struct towernode{
        Peg pos[5];
        struct TowerNode *next;
}TowerNode;

typedef struct tower{
        TowerNode *top;
}Tower;  

This is what i am saying: have a type for Bars '|', type for Discs '_', now have a Peg structure and add array of bars to it!
So that i could do Peg abc[5];
then i could say abc[i]->dsc[i]='_' and abc[i]='|'  // i dont know if i got the right syntax/logic
i.e. |_ _ _

Was that correct logically/syntax wise or i am missing something?


Thank You

Aik-21
ps: i know i m bad at this :D, i m still learning :D
0
All Courses

From novice to tech pro — start learning today.