Python – How to develop an algorithm for brute-forcing / backtracking

algorithmspython

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:

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)
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)
I can see how long my current route has taken by doing: time = frames(step_segment).
At some point, I will get into a Battle. I get into a Battle when
STATS[5] == "B"
When there is a battle, I simply have two choices: i. Fight the
battle, or, ii. Run away.
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).
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.

Best Answer

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.

Related Solutions

Object-oriented – Object oriented vs vector based programming

As you can see, the OOP way gives me a lot of security that people won't be adding Volatility the wrong way, but the vector method is just so crazy fast! Is there a design in which I can get both? I am sure a lot of you have run into similar design choices, how did you work it out?

Design bigger objects. A Pixel object has no breathing room for a parallelized loop or GPU image transformations or anything like that. An Image does provided it doesn't have to go through the barrier of a teeny Pixel object to get at the data.

Algorithm Development – Algorithm for Flattening Overlapping Ranges

Walk from left to right, using a stack to keep track of what color you're on. Instead of a discrete map, use the 10 numbers in your dataset as the break-points.

Starting with an empty stack, and setting start to 0, loop until we reach the end:

If stack is empty:
- Look for the first color starting at or after start, and push it and all lower-ranked colors onto the stack. In your flattened list, mark the beginning of that color.
else (If not empty):
- Find next beginning point for any higher-ranked color at or after start, and find the end of the current color
  - If the next color starts first, push it and anything else on the way to it onto the stack. Update the end of the current color as the beginning of this one, and add the start of this color to the flattened list.
  - If there are none and the current color ends first, set start to the end of this color, pop it off of the stack, and check the next-highest ranked color
    - If start is within the next color's range, add this color to the flattened list, starting at start.
    - If the stack empties, just continue the loop (go back to the first bullet point).

This is a mental run-through given your example data:

# Initial data.
flattened = []
stack = []
start = 0
# Stack is empty.  Look for the next starting point at 0 or later: "b", 0 - Push it and all lower levels onto stack
flattened = [ (b, 0, ?) ]
stack = [ r, b ]
start = 0
# End of "b" is 5.4, next higher-colored start is "g" at 2 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, ?) ]
stack = [ r, b, g ]
start = 2
# End of "g" is 12, next higher-colored start is "y" at 3.5 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, ?) ]
stack = [ r, b, g, y ]
start = 3.5
# End of "y" is 6.7, next higher-colored start is "o" at 6.7 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, ?) ]
stack = [ r, b, g, y, o ]
start = 6.7
# End of "o" is 10, and there is nothing starting at 12 or later in a higher color.  Next off stack, "y", has already ended.  Next off stack, "g", has not ended.  Delimit and continue.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, ?) ]
stack = [ r, b, g ]
start = 10
# End of "g" is 12, there is nothing starting at 12 or later in a higher color.  Next off stack, "b", is out of range (already ended).  Next off stack, "r", is out of range (not started).  Mark end of current color:
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12) ]
stack = []
start = 12
# Stack is empty.  Look for the next starting point at 12 or later: "r", 12.5 - Push onto stack
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, ?) ]
stack = [ r ]
start = 12
# End of "r" is 13.8, and there is nothing starting at 12 or higher in a higher color.  Mark end and pop off stack.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, 13.8) ]
stack = []
start = 13.8
# Stack is empty and nothing is past 13.8 - We're done.

Best Answer

Related Solutions

Object-oriented – Object oriented vs vector based programming

Algorithm Development – Algorithm for Flattening Overlapping Ranges

Related Topic