How to brute force a tree of 'yes/no' decisions?

Question

I want to solve a puzzle. But I simply don't know what kind of code is required for it. The problem is an exponential one.

Description:

The Player walks/runs one step at a time. Sometimes there will be a decision to be made; that is a yes/no question. Once the question is answered, the player continues walking until the next decision/question is reached. Continue this until the total distance is covered.

The problem is I want to see every possible route through this (many python lists such as ['y','y','n','y','n']). Here is the code I have written so far: (the Player is in a Player() class, I have removed it because it is unimportant here.)

class Solver(object):
    """ Solver object. """

def __init__(self, field):
    self.field = field
    self.dinc = 113
    self.distance = 128

def take_step(self, player):
    """ Takes a step and records players route. """
    # Adds 0 if there is no decision to be made on this step
    # Adds 1 if there is a decision to be made on this step

    player.run(self.dinc)
    if self._is_decision_time(player):
        player.route.append((player.step_id, 1))
    else:
        player.route.append((player.step_id, 0))

def next_decision(self, player):
    """ Accepts a player object. Walks until reaches next decision. """
    while not self._is_decision_time(player):
        self.take_step(player)
    self.display_stats(player)

def say_no(self, player):
    """ Simulates a no response. Resets danger. Updates route with decision. """
    player.route[-1] = (player.step_id, 'n')
    player.danger = 0
    print 'no!'

def say_yes(self, player):
    """ Simulates a yes response. Updates route with decision. """
    player.route[-1] = (player.step_id, 'y')
    print 'yes!'

The solution of what I'm looking for is like this:

• Walk until a question is reached
• Make a copy of the route
• On route A say Yes
• On route B (the copy) say No

Route A:
repeat what is above (this forks another two routes)

Route B:
repeat what is above (this forks another two routes)

Using the code I have so far, it is something like:

route_a = Player()
solver = Solver()

# walk until a battle is reached
solver.next_decision(route_a)
# make a copy of the route (there are now two routes A + route B)
route_b = copy.deepcopy(route_a)

# on route A say 'yes'
solver.say_yes(route_a)
# on route B say 'no'
solver.say_no(route_b)
# walk until the next decision is reached
solver.next_battle(route_a)
solver.next_battle(route_b)
# Then?

This problem is exponential, because at each decision the route forks into two more routes. I need all of the possibilities; I happen to know there are less than 512 possibilities so a computer can solve it in an instant.

Each route will be stored in a Player.route instance (as a list, eg: ['y','y','n','y'])

I just have no idea how to solve a problem like this programmatically. I would appreciate some ideas as to how to structure code to solve a problem like this.

Answer 1

Actually, such a data structure -- a binary tree -- is used in order to just avoid the exponential problem you mentioned. Or, in other words, the supposed list of 'y' and 'n' will grow exponentially, but usually you don't need it, because you have the binary tree. You know that you get each way by a yes-or-no question.

But, if you want to print the list you were asking for, do it like in this pseudo-code (since I'm lost to C++, I still can't program in Python ;-) )

def recurse(node, s=''):
    if node == end_node:
        print s
        return

    recurse(node.left,  s + 'n')
    recurse(node.right, s + 'y')

Then invoke the function starting at the root or head node, i.e. recurse(root_node).