How would I count the number of moves of this recursive function?

Question

How would I go about adding another parameter to this function which counts how many moves were needed, i.e how many times the move function was called? And then return (mycurrentanswer, count). Where count is the new parameter added to my function and must be initially added as zero?

def playHanoi(pos,a,b,c,n):
        if n == 0:
           return pos
        if n == 1:
           return move(pos, a, b)
        else:
           return playHanoi(move(playHanoi(pos,a,c,b,n-1),a,b),c,b,a,n-1)

Here is my move function:

def move(pos, a, b):
        if pos[a] == []:
           return pos
        elif pos[b] == [] or pos[b][-1] >= pos[a][-1]:
           pos[b].append(pos[a].pop(-1))
           return pos
        else:
           raise ValueError('This is an illegal move')

I want the function to do be like this

def playHanoi(pos,a,b,c,n,counter):
            if n == 0:
               return pos
            if n == 1:
               return move(pos, a, b)
            else:
               return (playHanoi(move(playHanoi(pos,a,c,b,n-1),a,b),c,b,a,n-1),j)

Pseudocode

Input a dictionary of the form {1: [5,4,3,2,1], 2: [], 3: []} (where the numbers are discs of that size, left of the list being the bottom of a pile) along with a,b,c being the poles of the Hanoi problem, so 1,2 and 3 in some order.
And then n is how many discs I want to move from Pile 1 to 3, i.e if n = 3 my pos will become {1: [5,4], 2: [], 3: [3,2,1]}.
And then a final component counter that will count how many 'steps' i.e times I've had to move a disc to reach my desired goal.

The output for playHanoi({1: [5,4,3,2,1], 2: [], 3: []},1,3,2,3,0) would be ({1: [5,4], 2: [], 3: [3,2,1]}, #ofsteps).

Can you add some pseudo code to show 1) which function you are going to modify, and 2) what kind effect it will be like? — Zealseeker, Feb 22 '20 at 00:03
The implementations of Hanoi, that I'm used to are a little different and do not have a play function and a move function. They also have less parameters. Could you please show how to call playHanoi() in order to move a tower with 5 disks from place 1 to place 2 by using place 3? — gelonida, Feb 22 '20 at 00:15
I don't need to complete the entire game of Hanoi, just for an amount of discs from a set amount of discs. All of that is working, I now need to count the number of steps required to do so — jksjkashalskajdjalaklskalska, Feb 22 '20 at 00:30
please show an example of how you call the function now without counting and how you want to call the function with counting and how you want to retrieve the moves. — gelonida, Feb 22 '20 at 00:36
I don't want to retrieve the moves. In this exercise I just need to show the end position, which this does. But now From this function need to add an extra component to count the steps. Sorry I'm new to python and stack overflow so if I'm not helping, I apologise. — jksjkashalskajdjalaklskalska, Feb 22 '20 at 00:41

gelonida · Answer 1 · 2020-02-22T16:39:16.503

Here one solution it returns moves and prints out the changes to pos Feel free to rename the variables to one letter names if this is what is required for your exercise. I personally prefer longer variable names.

def hanoi(pos, p_from, p_to, p_help, n_disks, moves=0):
    if n_disks == 1:
        disk = pos[p_from].pop()
        pos[p_to].append(disk)
        moves += 1
        print("move %d: move a disk from %s to %s: pos: %s" % (moves, p_from, p_to, pos))
        return moves
    moves = hanoi(pos, p_from, p_help, p_to, n_disks-1, moves)
    moves = hanoi(pos,  p_from, p_to, p_help,1 , moves)
    moves = hanoi(pos, p_help, p_to, p_from, n_disks-1, moves)
    return moves

if __name__ == '__main__':
    pos = {1: [5,4,3,2,1], 2: [], 3: []}
    moves = hanoi(pos, 1,3,2,5,0)
    print("Total moves = %d" % moves)
    print("Final pos = ", pos)

The output will look like:

move 1: move a disk from 1 to 3: pos: {1: [5, 4, 3, 2], 2: [], 3: [1]}
move 2: move a disk from 1 to 2: pos: {1: [5, 4, 3], 2: [2], 3: [1]}
move 3: move a disk from 3 to 2: pos: {1: [5, 4, 3], 2: [2, 1], 3: []}
move 4: move a disk from 1 to 3: pos: {1: [5, 4], 2: [2, 1], 3: [3]}
move 5: move a disk from 2 to 1: pos: {1: [5, 4, 1], 2: [2], 3: [3]}
move 6: move a disk from 2 to 3: pos: {1: [5, 4, 1], 2: [], 3: [3, 2]}
move 7: move a disk from 1 to 3: pos: {1: [5, 4], 2: [], 3: [3, 2, 1]}
move 8: move a disk from 1 to 2: pos: {1: [5], 2: [4], 3: [3, 2, 1]}
move 9: move a disk from 3 to 2: pos: {1: [5], 2: [4, 1], 3: [3, 2]}
move 10: move a disk from 3 to 1: pos: {1: [5, 2], 2: [4, 1], 3: [3]}
move 11: move a disk from 2 to 1: pos: {1: [5, 2, 1], 2: [4], 3: [3]}
move 12: move a disk from 3 to 2: pos: {1: [5, 2, 1], 2: [4, 3], 3: []}
move 13: move a disk from 1 to 3: pos: {1: [5, 2], 2: [4, 3], 3: [1]}
move 14: move a disk from 1 to 2: pos: {1: [5], 2: [4, 3, 2], 3: [1]}
move 15: move a disk from 3 to 2: pos: {1: [5], 2: [4, 3, 2, 1], 3: []}
move 16: move a disk from 1 to 3: pos: {1: [], 2: [4, 3, 2, 1], 3: [5]}
move 17: move a disk from 2 to 1: pos: {1: [1], 2: [4, 3, 2], 3: [5]}
move 18: move a disk from 2 to 3: pos: {1: [1], 2: [4, 3], 3: [5, 2]}
move 19: move a disk from 1 to 3: pos: {1: [], 2: [4, 3], 3: [5, 2, 1]}
move 20: move a disk from 2 to 1: pos: {1: [3], 2: [4], 3: [5, 2, 1]}
move 21: move a disk from 3 to 2: pos: {1: [3], 2: [4, 1], 3: [5, 2]}
move 22: move a disk from 3 to 1: pos: {1: [3, 2], 2: [4, 1], 3: [5]}
move 23: move a disk from 2 to 1: pos: {1: [3, 2, 1], 2: [4], 3: [5]}
move 24: move a disk from 2 to 3: pos: {1: [3, 2, 1], 2: [], 3: [5, 4]}
move 25: move a disk from 1 to 3: pos: {1: [3, 2], 2: [], 3: [5, 4, 1]}
move 26: move a disk from 1 to 2: pos: {1: [3], 2: [2], 3: [5, 4, 1]}
move 27: move a disk from 3 to 2: pos: {1: [3], 2: [2, 1], 3: [5, 4]}
move 28: move a disk from 1 to 3: pos: {1: [], 2: [2, 1], 3: [5, 4, 3]}
move 29: move a disk from 2 to 1: pos: {1: [1], 2: [2], 3: [5, 4, 3]}
move 30: move a disk from 2 to 3: pos: {1: [1], 2: [], 3: [5, 4, 3, 2]}
move 31: move a disk from 1 to 3: pos: {1: [], 2: [], 3: [5, 4, 3, 2, 1]}
Total moves = 31
Final pos = {1: [], 2: [], 3: [5, 4, 3, 2, 1]}

Below my previous answers, which might be interesting for some people.

One way to do such kind of book keeping would be to add one parameter with a persistent object, for example a dict. This solution is implemented such, that one does not have to pass the state if one is not interested in getting information about the number of moves.

def playHanoi(pos,a,b,c,n,state=None):
        if state is None:
            state = {"moves": 0}
        if n == 0:
           return pos
        if n == 1:
           return move(pos, a, b)
        else:
           return playHanoi(move(playHanoi(pos,a,c,b,n-1, state),a,b, state),c,b,a,n-1, state)

def move(pos, a, b, state):
        state["moves"] += 1
        if pos[a] == []:
           return pos
        elif pos[b] == [] or pos[b][-1] >= pos[a][-1]:
           pos[b].append(pos[a].pop(-1))
           return pos
        else:
           raise ValueError('This is an illegal move')


state = { "moves": 0 }
pos = playHanoi({1: [5,4,3,2,1], 2: [], 3: []}, 1,3,2,5, state)
print("I needed %d moves" % state["moves"])

In this particular case I could have written:

def playHanoi(pos,a,b,c,n,state={"moves": 0})

and removed the if statement, that assigns a dict to state if None,

but in general this is not good practice as changes to the dict persist Optional parameters in Python functions and their default values Knowing, that quite some code from SO is copy pasted into real apps I didn't want to do that as out of context this can be dangerous.

Simple version without book keeping of disks (pos) Here a simple version of hanoi, that prints out what disk to move and returns the total number of disks being moved

def hanoi(n_disks, p_from, p_to, p_help, moves=0):
    if n_disks == 1:
        moves += 1
        print("move %d: move a disk from %s to %s" % (moves, p_from, p_to))
        return moves
    moves = hanoi(n_disks-1, p_from, p_help, p_to, moves)
    moves = hanoi(1, p_from, p_to, p_help, moves)
    moves = hanoi(n_disks-1, p_help, p_to, p_from, moves)
    return moves

moves = hanoi(5, "stackA", "stackB", "stackC")
print("Total moves = %d" % moves)

The output would look like:

move a disk from stackA to stackB
move a disk from stackA to stackC
move a disk from stackB to stackC
move a disk from stackA to stackB
move a disk from stackC to stackA
move a disk from stackC to stackB
move a disk from stackA to stackB
move a disk from stackA to stackC
move a disk from stackB to stackC
move a disk from stackB to stackA
move a disk from stackC to stackA
move a disk from stackB to stackC
move a disk from stackA to stackB
move a disk from stackA to stackC
move a disk from stackB to stackC
move a disk from stackA to stackB
move a disk from stackC to stackA
move a disk from stackC to stackB
move a disk from stackA to stackB
move a disk from stackC to stackA
move a disk from stackB to stackC
move a disk from stackB to stackA
move a disk from stackC to stackA
move a disk from stackC to stackB
move a disk from stackA to stackB
move a disk from stackA to stackC
move a disk from stackB to stackC
move a disk from stackA to stackB
move a disk from stackC to stackA
move a disk from stackC to stackB
move a disk from stackA to stackB
Total moves = 31

Another (hopefully the final) solution after the ongoing discussion:

pos and j (the number of moves) are returned. Only one function is used instead of two.

Just remove the print() inside the function if you do not want it. It helps to understand how the code works, but is perhaps not needed in your case.

Another note. Exactly as in your initial code the dict, that has been passed to the playHanoi function is also modified.

In some situations this is not desirable. If interested I'm able to provide a version, where initial_pos will not be modified.

def playHanoi(pos, a, b, c, n, j=0):
    if n == 1:
        disk = pos[a].pop()
        pos[b].append(disk)
        j += 1
        print("move %d: move a disk from %s to %s: pos: %s" % (j, a, b, pos))
        return pos, j
    pos, j = playHanoi(pos, a, c, b, n-1, j)
    pos, j = playHanoi(pos,  a, b, c,1 , j)
    pos, j = playHanoi(pos, c, b, a, n-1, j)
    return pos, j

initial_pos = {1: [5,4,3,2,1], 2: [], 3: []}
pos, j = playHanoi(initial_pos, 1,3,2,5,0)
print("Final pos", pos)
print("Total j = %d" % j)
print("look even initial_pos has been modified", initial_pos)

I have to input the counting component as 0 initially,so i'm unable to do this — jksjkashalskajdjalaklskalska, Feb 22 '20 at 00:34
What means `I have to input`? Please try to explain better of how you want to call the function and I will probably able to adapt the function to your exact requirements. However please note, that my above suggestion is one rather generic way of performing stats or accumulating information with a recursive function. You initialize one persistent object, pass it to the recursive function and read the state afterwards. — gelonida, Feb 22 '20 at 00:39
So my input will be playHanoi({1: [5,4,3,2,1], 2: [], 3: []}, 1,3,2,5,0) and it will only ever be a zero that will go in the last part of the function. The zero being the count, as initially the count is 0 as the game hasn't begun. — jksjkashalskajdjalaklskalska, Feb 22 '20 at 00:45
So once I've defined my function I wish to input that as mentioned in the previous comment into the console and it will output ({1: [], 2: [], 3: [5,4,3,2,1]}, #ofsteps) — jksjkashalskajdjalaklskalska, Feb 22 '20 at 00:46
so `pos={1: [5,4,3,2,1], 2: [], 3: []}` and `a=1` and `b=3` and `c=2` and `n=5` and the `0` should be the parameter `moves`, that's so far missing in your function? — gelonida, Feb 22 '20 at 00:53
Yes that is exactly right, and I know it seems confusing with why the b is 3 and what not but that is how I have been told to define it — jksjkashalskajdjalaklskalska, Feb 22 '20 at 00:58
the fact, that you have two functions and that the move function uses pos as return value makes it a little more complicated to count. Will perhaps see tomorrow if I can restructure the code. Do you have to have a playHanoi() function and a move() function or could you have a valid solution with only one function? — gelonida, Feb 22 '20 at 01:02
It's been advised to use both of these however, I don't specifically have to no — jksjkashalskajdjalaklskalska, Feb 22 '20 at 01:06
for such kind of homework / lab exercise the exact phrasing is quite important. If not the solution will not match the requirements — gelonida, Feb 22 '20 at 01:09
Define a function PlayHanoi(pos,a,b,c,n) that takes as input a game position pos, piles a,b,c (which will be 1,2,3 in some order), and a number of discs n, which will (if possible), through a sequence of legal moves, move the top n discs in pile a to pile b using pile c as a auxiliary pile. It should produce as output the resulting new position. — jksjkashalskajdjalaklskalska, Feb 22 '20 at 01:14
Amend your code to keep track of the total number of moves in the game, by writing a function PlayHanoi2(pos,a,b,c,n,j) which has an additional input j (which will be zero on the initial input) to serve as a move-counter, and which outputs suitably modified (pos,j). — jksjkashalskajdjalaklskalska, Feb 22 '20 at 01:15
OK I understand a little better, but I don't see any output in the functions, that you implemented. What do they mean with output? They mean prints? Or do they mean return values of the function? For me returning or outputting is not exactly the same. — gelonida, Feb 22 '20 at 01:28
funny, that they teach to use meaningless one letter variable names. — gelonida, Feb 22 '20 at 01:36
I enhanced my answer. I use however just one recursive function instead of two. — gelonida, Feb 22 '20 at 01:41
By output they mean return values of the function. From this I've been able to find out the total moves, but not been able to return it in the way asked; that being (pos, j). — jksjkashalskajdjalaklskalska, Feb 22 '20 at 11:52
Thank you very much for your help gelonida. It's very much appreciated :) — jksjkashalskajdjalaklskalska, Feb 22 '20 at 12:55
I got an edit suggestion, that suggested to replace `def playHanoi(pos,a,b,c,n,state=None)` with `def playHanoi(pos,a,b,c,n,state={"moves": 0})` assigning dicts as default values of functions is discourageg, as it can cause some difficult to find bugs. if the dict is changed, then the next time the function is called the default value will have changed. That is easy to demonstrate if the function is called twice. — gelonida, Feb 22 '20 at 15:50
made some more edits to my answer. I hope it is clearer than before — gelonida, Feb 22 '20 at 16:16

score 0 · Answer 2 · answered Feb 22 '20 at 12:55

0

I've managed to play around with what you have provided and what I am seeking and have found a solution for what i'm after. I'm sure there's countless amounts of more elegant ways however, this does as is required.

def playHanoi2(pos,a,b,c,n,j):
    def playHanoi3(pos,a,b,c,n,j):
        if n == 1:
            disk = pos[a].pop()
            pos[b].append(disk)
            j += 1
            return j
        j = playHanoi3(pos, a, c, b, n-1, j)
        j = playHanoi3(pos,  a, b, c,1 , j)
        j = playHanoi3(pos, c, b, a, n-1, j)
        return j
    j = playHanoi3(pos,a,b,c,n,j)
    return (playHanoi(pos,a,b,c,n),j)

answered Feb 22 '20 at 12:55

jksjkashalskajdjalaklskalska

19
4

I now have a problem where if n < the number of discs in a it says that this is an illegal move due to the playHanoi function within the final return however, when I run this function normally the problem doesn't appear. I feel like this has something to do with there being two function using the same variables. Any advice? – jksjkashalskajdjalaklskalska Feb 22 '20 at 13:50
I don't really understand why you are using two functions and why the functions are nested. I will enhance my answer with another suggestion. – gelonida Feb 22 '20 at 15:11
Another solution added at the end of the answer. This 'outputs' (funny word for 'returns') pos and j I have the same variable names as suggested in the question. but I repeat, that one letter variables are not really a good idea. Especially something like `j`, which is supposed to be the number of moves. This is not intuitive and good programs should almost be self documenting. – gelonida Feb 22 '20 at 15:15
just a general comment. declaring functions within functions is something one doesn't do that often in Python. (creating closures and some other special cases are exceptions) And I'm not even sure you you have to create more than one function in any case (Please look at my adapted answer) – gelonida Feb 22 '20 at 16:19
The problem that you have with your suggested solution is, that pos is an object, that is passed by reference. Which means, that pos is changed by calling playHanoi3. when you call lateron playHanoi() it is working with the already modified pos. If you want I can adapt my answer such, that the input pos is not modified – gelonida Feb 22 '20 at 16:27

How would I count the number of moves of this recursive function?

Pseudocode

2 Answers2