🔒 Locked

Python problem

Started by daniel_i_l Jan 12, 2008 at 5:20 PM 2 replies 900+ views

Original Post

Jan 12, 2008 at 5:20 PM

I just learned python and wanted to practice by implementing the A* algorithm and using it to solve the 8-puzzle. So I made a node class that looks like this:


class Node:
    def  __init__(self, data):
        self.data = data
    parent = 0
    f,g,h=0,0,0

where data is a 1D representation of the 2D board (so that data[x+3*y] is the (x,y) square) where the emty square has the value 0. I also have a function called GenerateNeighbors(node) which takes a node as input and returns a list of neighboring nodes. Now, just to check that everything was working I made a function that shuffles a board using the GenerateNeighbors function:


def Shuffle(node, depth):
    if depth==0:
        return node.data, depth
    print node.data , depth
    Shuffle(GenerateNeighbors(node)[0],depth-1)

I know that it's not random at all but I did it just to see if it would work. So then I did:


start = [1,2,3,4,5,6,7,8,0]
print Shuffle(Node(start),10)

and got: [1, 2, 3, 4, 5, 6, 7, 8, 0] 10 [1, 2, 3, 4, 5, 0, 7, 8, 6] 9 [1, 2, 0, 4, 5, 3, 7, 8, 6] 8 [1, 2, 3, 4, 5, 0, 7, 8, 6] 7 [1, 2, 0, 4, 5, 3, 7, 8, 6] 6 [1, 2, 3, 4, 5, 0, 7, 8, 6] 5 [1, 2, 0, 4, 5, 3, 7, 8, 6] 4 [1, 2, 3, 4, 5, 0, 7, 8, 6] 3 [1, 2, 0, 4, 5, 3, 7, 8, 6] 2 [1, 2, 3, 4, 5, 0, 7, 8, 6] 1 None So I know that the functions are working but why did I get None at the end? Thanks.

Hollower

Jan 12, 2008 at 10:05 PM

print Shuffle(Node(start),10)

This prints only the return value of the first or outermost call to Shuffle. Shuffle only returns (node.data, depth) if depth == 0. But depth == 10, and since there is no return statement in the remaining part of the function, it returns None. A function that doesn't specify a return value returns None. It's similar to void in C++.

The rest of the printed lines come from the print statement within the Shuffle function. Since this is being called recursively, the first call returns last, hence the None is printed last rather than first.

daniel_i_l

Author

daniel_i_l

Jan 12, 2008 at 10:37 PM

So how do I make it return the innermost (shuffled) value?
Thanks.

Hollower

Jan 13, 2008 at 9:21 PM

You would have to return it all the way back down the call stack.

def Shuffle(node, depth):    if depth==0:        return node.data, depth    return Shuffle(GenerateNeighbors(node)[0],depth-1)

Returning depth is redundant though. It will always == 0 at the point it is returned.
Recursion seems unnecessary in this case. Consider an iterative approach:

def Shuffle(node, depth):    for i in xrange(depth):        node = GenerateNeighbors(node)[0]    return node.data

As far as I can tell, this is equivelent to the recursive version.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.