How to develop an algorithm for brute-forcing / backtracking?

Question

As a beginner programmer, I don't know how to conceptually think about brute-forcing. My mind can't really fathom how to write code that will try every possibility.

I have a problem that I want to solve. Here is a code snippet (there are other functions, but no reason to include them here, they just do background work):

main():
    step_segment = []           # contains current segment
        STATS = [250,0,0,0,13,0]        # contains 1 step (current step stats)
        # STATS = [step_id, danger, danger_limit, rnd, b_loop, enc]

    # Temporary Interface
    choice = None
    while choice != "0":
        print \
        "\n1 - Benchmark Run"
        choice = raw_input("Choice: ")
        if choice == "0":
            print "\nGoodbye."

        elif choice == "1":
            while (len(step_segment)) < 128:
                step_segment, STATS = take_step(step_segment, STATS)
                if STATS[5] == "B":
                    "Dont know what to do here. Try every possibility!?"

The goal: I want to produce a list of every possible 'route' through a segment, along with how long it takes.

Description:

1. I will take a step in the route (There's only one direction: forward). Every time I take a step, my stats are updated. This takes a step and updates the stats: step_segment, STATS = take_step(step_segment, STATS)

2. A list of steps taken, along with the stats, are kept in step_segment. This is so I can 'undo' an arbitrary amount of steps, if I want. To undo a step call the function: step_segment, STATS = undo_step(step_segment, STATS)

3. I can see how long my current route has taken by doing: time = frames(step_segment).

4. At some point, I will get into a Battle. I get into a Battle when STATS[5] == "B"

5. When there is a battle, I simply have two choices: i. Fight the battle, or, ii. Run away.

6. If I want to Fight, I do: step_segment = do_fight(step_segment, STATS). This also records that I chose to fight, along with the stats, in step_segment. (So I can undo it, if i want).

7. If I want to Run Away, I do: step_segment = run_away(step_segment,STATS).

Can someone advise me, how I can code a brute forcer for this problem?

Specifically, I would like to know how I can tell the computer to try every possibility; I simply cannot think how to... >.<'

I want to see every possible combination of Run & Fight (the only two choices, when I reach a battle).

There are only around 200 possibilities. I only need to take 128 steps, so there are a finite amount of possibilities, hence: while (len(step_segment)) < 128.

I just don't know how to accomplish such a thing in Python. My whole reason for learning how to program is to solve this problem..

I think I can explain the solution in English, as I have done above, but I don't know how to code it. I would be very appreciative if someone could advise me on this!!

Thank you.

Answer 1

There are more "possibilities" than you might think, I will explain to you why:

As I understand your explanation of your scenario, you have effectively a tree structure of steps. You start at the "root" (your first step) and then go up.

At every point where you encounter a battle and thus get to choose, you create a branch of possibilites: Your path splits into a "do fight" path and a "don't fight" path, on which you will continue your journey.

These branches will branch again at every battle point. When you reach your "end", you will backtrack to the previous decision and take the opposite action.

From a programmers perspective, this would be an ideal situation for a recursive algorithm, as you know you have a finite amount of steps.

The keywords to look for are "recursive tree traversal". I can not help you with specific code, as I have no experience with python.