So I have beein working on a Towers of Hanoi code using Stack and no recursion and came up with the following logic according the the Wikipedia section on solving ToH using iteration.
if (tower[1].isEmpty() == false && tower[1].peek() != 1) {
if (tower[2].isEmpty() || tower[1].peek() < tower[2].peek()) {
int disk = tower[1].pop();
tower[2].push(disk);
movedSmallest = false;
showTowers();
} else if (tower[3].isEmpty() || tower[1].peek() < tower[3].peek()) {
int disk = tower[1].pop();
tower[3].push(disk);
movedSmallest = false;
showTowers();
}
} else if (tower[2].isEmpty() == false && tower[2].peek() != 1) {
if (tower[3].isEmpty() || tower[2].peek() < tower[3].peek()) {
int disk = tower[2].pop();
tower[3].push(disk);
movedSmallest = false;
showTowers();
} if (tower[1].isEmpty() || (tower[2].isEmpty() == false && tower[2].peek() < tower[1].peek())) {
int disk = tower[2].pop();
tower[1].push(disk);
movedSmallest = false;
showTowers();
}
} else if (tower[3].isEmpty() == false && tower[3].peek() != 1) {
if (tower[2].isEmpty() || (tower[3].isEmpty() == false && tower[3].peek() < tower[2].peek())) {
int disk = tower[3].pop();
tower[2].push(disk);
movedSmallest = false;
showTowers();
} else if (tower[1].isEmpty() || (tower[3].isEmpty() == false && tower[3].peek() < tower[1].peek())) {
int disk = tower[3].pop();
tower[1].push(disk);
movedSmallest = false;
showTowers();
}
}
}
I don't want to show the full code since I'm not trying to ask for a solution or for someone to fix it, I would just like some pointers on how this could lead to an infinite loop, as it seems to be doing specifically in this section of my code. Just to clarify some details any of you might need, the Wikipedia page states that with iteration, you move the disks alternating between the smallest disk and a disk that isn't the smallest disk. If you are to move the smallest disk constantly in one direction and looping back around (think A->B->C->A) and moving another disk in between each of those moves, there should theoretically be only one legal move. This is why I have the variable movedSmallest = false; in each of those, so that the program will make a move using the small disk next.
Enter number of disks
5
[5, 4, 3, 2, 1]
[]
[]
---------------------------------------------------------
[5, 4, 3, 2]
[]
[1]
---------------------------------------------------------
[5, 4, 3]
[2]
[1]
---------------------------------------------------------
[5, 4, 3]
[2, 1]
[]
---------------------------------------------------------
[5, 4]
[2, 1]
[3]
---------------------------------------------------------
[5, 4, 1]
[2]
[3]
---------------------------------------------------------
[5, 4, 1]
[]
[3, 2]
---------------------------------------------------------
[5, 4]
[]
[3, 2, 1]
---------------------------------------------------------
[5]
[4]
[3, 2, 1]
---------------------------------------------------------
[5]
[4, 1]
[3, 2]
---------------------------------------------------------
When I input 5, this is the output I get and then it gets stuck here, infinitely looping.
Assuming tower[1] is tower with 5, then it's no empty and peek is not 1, so therefore it hits first if. When you look into the subsequent if statement then it doesn't hit neither one because there is not any empty tower and tower[1] - 5 is greater than both tower[2] - 1 and tower[3] - 2.
TLDR; It goes into first if and does nothing. Therefore state does not change and it keeps executing the same thing forever.
So check that and figure out what needs to be changed. Btw in these kind of cases you could try to add debug log into each if and see which path it's taking and why it is stuck. Even better debug the values it's checking the if's against for better understanding.
Good luck!