Greedy Algorithms and Time Complexity #2

Question

We have a bomb that is ticking and may explode. This bomb has n switches, that can be moved up or down. Certain combinations of these switches trigger the bomb, but only one combination disables it.

Our task is to move the switches from the current position to a position that disables the bomb, without exploding it in the meantime. The switches are big and awkward, so we can move only one switch at a time.

We have, lets say, n = 4 switches currently in position ^vvv. We need to get them to the position ^v^^. Forbidden positions are vvv^, ^vv^, ^v^v, and ^^^v.

a.) I had to draw this by hand and find the shortest sequence of switch movements that solves the task - result I got was 4 ...and I found two such sequences, if i am right...

b.) this is where it gets a hard - write a code that answers the above question/questions (the shortest sequence and how many). The code should be generalized so that it would work with another number of switches and other starting, targeted, and forbidden combinations; targeted and forbidden combinations may be multiple or even fewer. Only thing we know for sure is that the switches have only two positions. It should also provide the possibility that the desired condition is unavailable; in this case, the program should of course tell.

c.) Next questions is the time complexity of the code this but for now I think I will just stop here...

I used '0' and '1' instead, because it is easier for me to imagine this.

So my approach towards this was something of a greedy algorithm (I think) - starting position, you think of all the possible (allowed) positions, you ignore the forbidden ones, then pick the one that the sequence of positions has the fewest difference from our targeting sequence.

The key part of the code I am yet to write and that's the part I need help with.

all_combinations = ['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011' , '1100', '1101', '1110', '1111']


def distance (position1, position2):
     distance = 0
     for i in range (len (position1)):
         if position1 [i]! = position2 [i]:
             distance + = 1
     return distance


def allowed_positions (current, all_combinations):
     allowed = set ()
     for combination and all combinations:
         if the distance (current, combination) == 1:
             allowed.add (combination)
     return allowed


def best_name (current, all_combinations, target):
     list = []
     for option and permitted_mood (current, all_combinations):
         list.append (distance (option, target), option)

Answer 1

start = 8
target = 11
forbidden = {1: -1 , 9: -1, 10: -1, 14: -1}
dimensions = 4

def distance(start, target, forbidden, dimensions):
stack1 = []

stack1.append(start)
forbidden[start] = -1

while(len(stack1) > 0):
    top = stack1.pop()
    for i in range(dimensions):
        testVal = top ^ (1 << i)

        if testVal is target:
            forbidden[testVal] = top
            result = [testVal]
            while testVal is not start:
                testVal = forbidden[testVal]
                result.insert(0, testVal)
            return result


        if testVal not in forbidden:
            forbidden[testVal] = top
            stack1.append(testVal)

return [-1]


print(distance(start, target, forbidden, dimensions))

Here is my code for your example in your question. Instead of using bits, I went ahead and used the base 10 number to represent the codes. Forbidden codes are mapped to a hashmap which is used later to trace the path upwards after the target is found. I use a stack to keep track of which code to try. Each time the while loop passes, the last code added is popped and it's unvisited neighbors are added to the stack. Importantly, to prevent cycles, codes on the stack or seen before are added to the list of forbidden nodes. When the target code is found for the first time, an early return is called and the path is traced through the hashmap.

This solution uses breadth first search and returns the first time the target is found. That means it does not guarantee the shortest path from start to target, but it does guarantee a working path if it's available. Since all possible codes are possibly traversed and there are 2^dimensions number of nodes, the time complexity of this algorithm is also O(2^n)

Answer 2

The task at hand is finding a shortest path in a graph. For this there is one typical approach and that is a breadth-first search algorithm (https://en.wikipedia.org/wiki/Breadth-first_search).

There is no real need to go into the details of how this is done because it can be read elsewhere in more detail and far better explained than I can do this in a StackOverflow answer.

But what might need to be explained is how the switch-combinations you have at hand are represented by a graph.

Imagine you have just two switches. Then you have exactly this graph:

^^---^v
|     |
|     |
v^---vv

If your starting position is ^^ and your ending (defusing) position is vv while the position ^v is an exploding position, then your graph is reduced to this:

^^   ^v
|       
|       
v^---vv

In this small example the shortest path is obvious and simple.

The graph at hand is easily sketched out in 2D, each dimension (x and y) representing one of the switches. If you have more switches, then you just add one dimension for each switch. For three switches this would look like this:

^^^--------^^v
 |\         |\
 | \        | \
 |  \       |  \
 |   \      |   \
 |   ^v^--- | --^vv
 |    |     |    |
 |    |     |    |
v^^--------v^v   |
  \   |      \   |
   \  |       \  |
    \ |        \ |
     \|         \|
     vv^--------vvv

If the positions ^^v, v^^, and vv^ are forbidden, then this graph is reduced to this:

^^^        ^^v
  \           
   \           
    \           
     \           
     ^v^--------^vv
                 |
                 |
v^^        v^v   |
             \   |
              \  |
               \ |
                \|
     vv^        vvv

Which already shows the clear way and the breadth-first search will easily find it. It gets interesting only for many dimensions/switches, though.

Drawing this for more dimensions/switches gets confusing of course (look up tesseracts for 4D). But it isn't necessary to have a visual image. Once you have written the algorithm for creating the graph in 2D and 3D in a general way it easily scales to n dimensions/switches without adding any complexity.