How to redo the yes / no decision tree?

Question

I want to solve a riddle. But I just don’t know what code is needed for this. The task is exponential.

Description:

The player walks / works one step at a time. Sometimes a decision will be made; this is a yes / no question. After answering the question, the player continues to go until the next decision / question. Continue this until the general cover is closed.

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 that I have written so far: (Player is in the Player() class, I deleted it because it doesn’t matter 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 as follows:

• Go through until the question is reached.
• Make a copy of the route
• On route A say yes
• On Route B (copy), indicate No

Route A:
repeat the one above (this unfolds two more routes)

Route B:
repeat the one above (this unfolds two more routes)

Using the code that I have 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 with each solution, the route develops two more routes. I need all the features; I know that there are less than 512 possibilities, so a computer can solve this in an instant.

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

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

Answer 1

Actually, such a data structure - a binary tree - is used to simply avoid the exponential problem you were talking about. Or, in other words, the intended list of 'y' and 'n' will grow exponentially, but usually you don't need it because you have a binary tree. You know that each of you receives a yes or no answer.

But if you want to print the list you requested, do it like in this pseudo code (since I lost C ++, I still can not 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 call the function starting at the root or head of the node, i.e. recurse(root_node) .

Answer 2

This seems like a pretty simple task for recursion, and you already have a pretty simple tree structure. Perhaps you should just transfer the decision-making process to an explicit tree structure and implement a recursive traversal of nodes? This is probably the smartest decision, considering what looks like what you are trying to do. I think you're looking for “brute force” ... but an alternative iterative solution would be much less elegant (and harder to write).

Answer 3

A naive, but probably suitable way to generate permutations like this is to run the numbers 0..512 , convert them to binary (with the correct complement), and treat zeros as “No” and “Yes”. Nine bits are enough for 512 values, so create a line like this:

 '{0:0>9b}'.format(123)