How to recursively add nodes to n-ary tree in Python-CodePudding

So I have an n-ary tree with a root node that I have manually added 5 child nodes too. Each of these children nodes represents a state of its parent that has had some calculations done to its data.

For example: child1.value = root.value -1, child2.value = root.value 2, child3.value = root.value 1, etc.

Essentially, I want to create a method (recursive generator) that will go to each child, and for each child will create 5 more children for that child with the same calculations done to it, and so on for multiple levels of the tree until one of the children contains data in a desired state.

**Edit to add desired state and calculations**
Basically I am trying to solve the sheep and wolves crossing a river problem.
My values are:
leftsheep = 3
leftwolves = 3
rightsheep = 0
rightwolves = 0
boatposition = 0 (is always 0 when on left side of river)

The desired state should look like so:
leftsheep = 0
leftwolves = 0
rightsheep = 3
rightwolves = 3
boatposition = 1 (is on right side of river, and all animals are moved)

The catch is that when the animals are left alone (the boat is on the opposite side of the river), the number of wolves can never outnumber the number of sheep (or they will eat them). 

So for each node, I generate 5 possible nodes from it. 
1. leftsheep-1   # 1 sheep is moved from left to right
2. leftwolves-1  # 1 wolf is moved from left to right
3. leftsheep-2   # 2 sheep are moved from left to right
4. leftwolves-2  # 2 wolves are moved from left to right
5. leftsheep-1 and leftwolf-1 # 1 sheep and 1 wolf are moved to the right
and boat 1       # Boat is always 1 when on the right side, 0 on left

Then once the desired node is found, I plan to use a search algorithm (BFS, DFS, etc.) to find the path from that node back to the root.

So far, I have created my Tree like this:

class Node:
    def __init__(self, value1, value2, value3, value4, value5):
        self.children = []
        self.value1 = value1
        self.value2 = value2
        self.value3 = value3
        self.value4 = value4
        self.value5 = value5
        self.parent = None

And I have a function def build_initial_tree() to build the tree with root node and 5 children. These 5 children are instances of the root with calculations performed on some of their data.

Finally, my recursive method looks like this:

def build_tree(self):
    #first check if initial state is goal state:
    if self.value4 == initial_value1 and self.value5 == initial_value2:
        return self

        #If current node has children
    elif len(self.children) > 0:
        #For each child that node has
        for child in self.children:
            #add 5 children to each node
            child.add_child(child)
            #rebuild the tree with each child added
            child.build_tree()
        #print the tree
        return self.print_tree()

    #if node has no children, it is a leaf node so just return the tree
    else:
        return self

It is the for loop in this method that is giving me trouble. If I run as is, the line child.add_child(child) gives me a maximum recursion error (I know why it does this but I am not sure how to fix it or what this line should be). I have tried looking at many examples but they almost all apply to Binary Trees so I am getting confused. I just want to build the tree by adding children to it (with calculations applied to the data) until one of the nodes reaches a desired state (value4 = initial_value1 and value5 = initial_value2). Should I do the calculations at the same time I add them to the tree? (Checking against constraints and removing/not adding nodes that break these constraints once the calculation is performed), or should I add all calculated nodes first, and then remove unwanted ones during my search algorithm function?

CodePudding user response：

There should not be a recursion depth problem. There can be several reasons why your code that determines the children leads to this problem:

The number of sheep/wolves is allowed to go negative, leading to an infinite repetition of subtraction of animals
A state that was already moved away from is encountered again, but the search continues, and leads to "running in a circle".
...

It would make sense to try to find a shortest path to the solution (fewest boat moves), and then it is more appropriate to use a BFS traversal. Note that you don't actually need the graph as you can perform a BFS immediately. When the target node is found, you can derive the path from that, by walking backwards to the source state.

Here is an implementation:

from collections import namedtuple

# sheep & wolves are the animal counts at the side opposite to the boat:
Node = namedtuple("Node", "sheep, wolves, boat")
Move = namedtuple("Move", "sheep, wolves")

moves = (
    Move(1, 0),
    Move(2, 0),
    Move(0, 1),
    Move(0, 2),
    Move(1, 1)
)

# Apply a move: the boat travels to the other side taking the given number of animals
#    If the move turns out to be invalid: return None
#    Else return the new state
def apply(state, move):
    newstate = Node(3 - state.sheep - move.sheep, 3 - state.wolves - move.wolves, 1 - state.boat)
    if 0 <= newstate.wolves <= (newstate.sheep or 3):
        return newstate

def bfs(source, target):
    frontier = [source]
    camefrom = { source: None }
    while frontier:
        nextfrontier = []
        for state in frontier:
            for move in moves:
                newstate = apply(state, move)
                if newstate is not None and newstate not in camefrom:
                    if newstate == target:
                        path = [target]
                        while state:
                            path.append(state)
                            state = camefrom[state]
                        return path[::-1]
                    nextfrontier.append(newstate)
                    camefrom[newstate] = state
        frontier = nextfrontier

def stringify(state):
    a = f"({state.sheep} sheep, {state.wolves} wolves)"
    b = f"({3-state.sheep} sheep, {3-state.wolves} wolves)"
    return f"{a}------boat{b}" if state.boat else f"{b}boat------{a}"


path = bfs(Node(0, 0, 0), Node(0, 0, 1))
for state in path:
    print(stringify(state))

This outputs this solution:

(3 sheep, 3 wolves)boat------(0 sheep, 0 wolves)
(3 sheep, 1 wolves)------boat(0 sheep, 2 wolves)
(3 sheep, 2 wolves)boat------(0 sheep, 1 wolves)
(3 sheep, 0 wolves)------boat(0 sheep, 3 wolves)
(3 sheep, 1 wolves)boat------(0 sheep, 2 wolves)
(1 sheep, 1 wolves)------boat(2 sheep, 2 wolves)
(1 sheep, 2 wolves)boat------(2 sheep, 1 wolves)
(1 sheep, 0 wolves)------boat(2 sheep, 3 wolves)
(1 sheep, 1 wolves)boat------(2 sheep, 2 wolves)
(0 sheep, 0 wolves)------boat(3 sheep, 3 wolves)