C++

Forum

 
Help with Hanoi Iterative solution. I think I am close.

Bdanielz (506)


Hi All!

I am at that point in the night (morning) where I am about to give up.
We have all been there!!!! I have been at this problem all day...
I digress...

So this is one part of three.. 1. Solve the tower of Hanoi Iterative solution - non recursive.

Here is the basic body of code that I have been using. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
#include <iostream>
#include <list>

const int SIZE = 5;
int pCount = 1;
using namespace std;

list<int> *lhs;
list<int> *mid;
list<int> *rhs;


void initTower(int size);

void printPeg(list<int> p);

bool printTower();

bool isEven(list<int> l);

bool move(list<int> *from, list<int> *to);

int main() {

    lhs = new list<int>;
    mid = new list<int>;
    rhs = new list<int>;


    initTower(SIZE);
    printTower();
    bool run = true;
    
    while (run) {


        // main loop

        if (rhs->size() == SIZE) {
            run = false;

        }
    }


    return 0;
}


bool isEven(list<int> l) {

    return l.size() % 2 == 0;

}

void initTower(int size) {

    while (size--)
        lhs->push_back(size + 1);
}

void printPeg(list<int> p) {

    if (p.empty()) {
        cout << "empty" << endl;
    } else {
        for (int i: p)
            cout << i << " ";
        cout << endl;
    }

}

bool printTower() {

    cout << "==============" << endl;
    cout << "=====top=======" << pCount++ << endl;
    printPeg(*lhs);
    printPeg(*mid);
    printPeg(*rhs);
    cout << "==============" << endl << endl;

    return true;

}

bool move(list<int> *from, list<int> *to) {
    bool vailidMove = false;

    int fVal = from->back();
    int toVal = to->back();

    if ((fVal < toVal || toVal == 0) && (fVal > 0 && fVal != 0)) {
        from->pop_back();
        to->push_back(fVal);
        vailidMove = true;
        printTower();
    }
    return vailidMove;
}




I have mainly been trying to write my algorithm around
https://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution

I have tried implementing


"Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:

For an even number of disks:

make the legal move between pegs A and B
make the legal move between pegs A and C
make the legal move between pegs B and C
repeat until complete

For an odd number of disks:

make the legal move between pegs A and C
make the legal move between pegs A and B
make the legal move between pegs C and B
repeat until complete

In each case, a total of 2n-1 moves are made."

The above solution with the most success.
What I had for this bit of code in my main loop


1
2
3
4
 
       move(lhs,mid);
        move(lhs,rhs);
        move(mid,rhs);


with this output 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
=====top=======1
5 4 3 2 1 
empty
empty
==============

==============
=====top=======2
5 4 3 2 1 
empty
empty
==============

==============
=====top=======3
5 4 3 2 
1 
empty
==============

==============
=====top=======4
5 4 3 
1 
2 
==============

==============
=====top=======5
5 4 3 
empty
2 1 
==============

==============
=====top=======6
5 4 
3 
2 1 
==============


I think I am close, but my mind cannot seem to visualize this step.

"Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:" and work it into my code.

Any ideas to get me on track?


Bdanielz (506)
forgot to add I have tried with odd / even cases... I am just coding in circles all day long... If you have any questions please do not hesitate to ask.
cire (8284)
You have undefined behavior in your move function. When the list pointed to by to is empty, it is undefined behavior to invoke to->back() because no elements exist in to.
ButchCavendish (111)
Good Code
dhayden (5798)
The problem is that you're trying to code an algorithm that you don't understand.

Stop writing code. Fish out 3 or 4 coins from your pocket and see if you can follow the algorithm to a solution. Doing this will help you understand the algo. Once you understand the algo, return to your code.
Bdanielz (506)



You have undefined behavior in your move function. When the list pointed to by to is empty, it is undefined behavior to invoke to->back() because no elements exist in to.

@cire
Thank you for your input. I updated my move function with this.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
bool move(list<int> *from, list<int> *to) {
    bool vailidMove = false;
    int fVal = 0;
    int toVal = 0;

    if (!from->empty())
        fVal = from->back();

    if (!to->empty())
        toVal = to->back();


    if ((fVal < toVal || toVal == 0) && (fVal > 0 && fVal != 0)) {
        from->pop_back();
        to->push_back(fVal);
        vailidMove = true;
        printTower();
    }
    return vailidMove;
}


Still stuck on this algorithm. I would appreciate any other advise about my work you could offer.
Last edited on
Bdanielz (506)
@ButchCavendish

Good Code


I am taking this as sarcasm?
Last edited on
Bdanielz (506)
@dhayden


The problem is that you're trying to code an algorithm that you don't understand.

Stop writing code. Fish out 3 or 4 coins from your pocket and see if you can follow the algorithm to a solution. Doing this will help you understand the algo. Once you understand the algo, return to your code.


Your right. I have tried.

Using an online version of the game, noting each move. writing out the program linearly and still was unable to see a pattern (iterative one) that would work with two different qualities of discs.

Using the Wikipedia example.

Simpler statement of iterative solution

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:

For an even number of disks:

make the legal move between pegs A and B
make the legal move between pegs A and C
make the legal move between pegs B and C
repeat until complete

For an odd number of disks:

make the legal move between pegs A and C
make the legal move between pegs A and B
make the legal move between pegs C and B
repeat until complete

In each case, a total of 2n-1 moves are made.


I am doing this...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 

    while (run) {
   int n = SIZE;

        if (n % 2 == 0) // even
        {
            move(lhs,mid);
            move(lhs,rhs);
            move(mid,rhs);

        }else{

            move(lhs,rhs);
            move(lhs,mid);
            move(rhs,mid);

        }


        if (rhs->size() == SIZE) {
            run = false;

        }
    }


With the these results. 


==============
=====top=======1
5 4 3 2 1 
empty
empty
==============

==============
=====top=======2
5 4 3 2 
empty
1 
==============

==============
=====top=======3
5 4 3 
2 
1 
==============

==============
=====top=======4
5 4 3 
2 1 
empty
==============

==============
=====top=======5
5 4 
2 1 
3 
==============



Where should I be retesting for odd or even? I am assuming that is my error.




Last edited on
dhayden (5798)
I don't think the "simpler statement of iterative solution" on wikipedia works. At least I can't figure it out. I like the "Iterative solution" description much better:
repeat:
- move the smallest disk to the right (or from the right most peg to the left peg)
- make the legal move *not* involving the smallest disk. There will be just one.
until the game is solved.
Bdanielz (506)
I posted on stack Someone helped me out with this..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
#include <iostream>
#include <list>

const int SIZE = 3;
int pCount = 1;
using namespace std;

list<int> *lhs;
list<int> *mid;
list<int> *rhs;


void initTower(int size);

void printPeg(list<int> p);

bool printTower();

bool isEven(list<int> l);

bool move(list<int> *from, list<int> *to);

int main() {

    lhs = new list<int>;
    mid = new list<int>;
    rhs = new list<int>;

    initTower(SIZE);
    printTower();
    bool run = true;
    while (run) {
        int n = SIZE;

        if (n % 2 == 0) // even
        {
            move(lhs,mid);
            move(lhs,rhs);
            move(mid,rhs);
        }else{
            move(lhs,rhs);
            move(lhs,mid);
        }
        if (rhs->size() == SIZE) {
            run = false;
            break;
        }
    }


    return 0;
}


bool isEven(list<int> l) {

    return l.size() % 2 == 0;

}

void initTower(int size) {

    while (size--)
        lhs->push_back(size + 1);
}

void printPeg(list<int> p) {

    if (p.empty()) {
        cout << "empty" << endl;
    } else {
        for (int i: p)
            cout << i << " ";
        cout << endl;
    }

}

bool printTower() {

    cout << "==============" << endl;
    cout << "=====top=======" << pCount++ << endl;
    printPeg(*lhs);
    printPeg(*mid);
    printPeg(*rhs);
    cout << "==============" << endl << endl;

    return true;

}

bool move(list<int> *from, list<int> *to) {
    bool vailidMove = false;
    int fVal = 0;
    int toVal = 0;

    if (!from->empty())
        fVal = from->back();

    if (!to->empty())
        toVal = to->back();


    if ((fVal < toVal || toVal == 0) && (fVal > 0 && fVal != 0)) {
        from->pop_back();
        to->push_back(fVal);
        vailidMove = true;
        printTower();
    }else if ((fVal > toVal || fVal == 0) && (toVal > 0 && toVal != 0)) {
        from->push_back(toVal);
        to->pop_back();
        vailidMove = true;
        printTower();
    }
    return vailidMove;
}




The code works but it is (2^n-2)*2 and not (2^n-1)

Example... with 3 discs...


==============
=====top=======1
3 2 1 
empty
empty
==============

==============
=====top=======2
3 2 
empty
1 
==============

==============
=====top=======3
3 
2 
1 
==============

==============
=====top=======4
3 1 
2 
empty
==============

==============
=====top=======5
3 
2 1 
empty
==============

==============
=====top=======6
empty
2 1 
3 
==============

==============
=====top=======7
1 
2 
3 
==============

==============
=====top=======8
empty
2 
3 1 
==============

==============
=====top=======9
2 
empty
3 1 
==============

==============
=====top=======10
2 1 
empty
3 
==============

==============
=====top=======11
2 
1 
3 
==============

==============
=====top=======12
empty
1 
3 2 
==============

==============
=====top=======13
1 
empty
3 2 
==============

==============
=====top=======14
empty
empty
3 2 1 
==============



I wonder how to optimize it?

Bdanielz (506)
Ok... This is solved!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
#include <iostream>
#include <list>

const int SIZE = 4;
int pCount = 0;
using namespace std;

list<int> *lhs;
list<int> *mid;
list<int> *rhs;


void initTower(int size);

void printPeg(list<int> p);

bool printTower();

bool isEven(list<int> l);

bool move(list<int> *from, list<int> *to);

int main() {

    lhs = new list<int>;
    mid = new list<int>;
    rhs = new list<int>;

    initTower(SIZE);
    printTower();
    bool run = true;
    bool lowest = false;
    while (run) {
        lowest = !lowest;
        int n = SIZE;

        if (n % 2 == 0) // even
        {
            if (lowest){
                move(lhs,mid);
                if (rhs->size() == SIZE) {
                    break;
                }
                move(lhs,rhs);
                move(mid,rhs);
            }else{
                move(mid,lhs);
                if (rhs->size() == SIZE) {
                    break;
                }
                move(rhs,lhs);
                move(rhs,mid);
            }
        }else{
            if (lowest){
                move(lhs,rhs);
                move(lhs,mid);
                if (rhs->size() == SIZE) {
                    break;
                }
                move(mid,rhs);
            }else{
                move(rhs,lhs);
                move(mid,lhs);
                if (rhs->size() == SIZE) {
                    break;
                }
                move(rhs,mid);
            }
        }

        lowest = !lowest;
    }


    return 0;
}


bool isEven(list<int> l) {

    return l.size() % 2 == 0;

}

void initTower(int size) {

    while (size--)
        lhs->push_back(size + 1);
}

void printPeg(list<int> p) {

    if (p.empty()) {
        cout << "empty" << endl;
    } else {
        for (int i: p)
            cout << i << " ";
        cout << endl;
    }

}

bool printTower() {

    cout << "==============" << endl;
    cout << "=====top=======" << pCount++ << endl;
    printPeg(*lhs);
    printPeg(*mid);
    printPeg(*rhs);
    cout << "==============" << endl << endl;

    return true;

}

bool move(list<int> *from, list<int> *to) {
    bool vailidMove = false;
    int fVal = 0;
    int toVal = 0;

    if (!from->empty())
        fVal = from->back();

    if (!to->empty())
        toVal = to->back();

    if ((fVal < toVal || toVal == 0) && fVal > 0) {
        from->pop_back();
        to->push_back(fVal);
        vailidMove = true;
        printTower();
    }else if ((fVal > toVal || fVal == 0) && (toVal > 0 && toVal != 0)) {
        from->push_back(toVal);
        to->pop_back();
        vailidMove = true;
        printTower();
    }
    return vailidMove;
}
Topic archived. No new replies allowed.