Apllying Dijkstra's algorithm to a specific problem in Python

[king_koder]

Hello, I got stuck trying to solve the following problem in Python. I understand that I somehow need to implement Dijkstra's algorithm to solve this problem, but how I've no idea.

Inside a room, there is a monster with N heads, and a human (with 1 head). The human has two laser guns. The first gun, A destroys C1 heads when fired and the second gun,B destroys C2 heads when fired [The guns may destroy both the monster's as well as human heads, but the guns prioritize monster heads over human ones].

Also, if after the firing of the gun the monster has a positive non-zero number of heads left, the monster will grow additional heads. The monster grows G1 heads when gun A is used and it grows G2 heads when gun B is used.

The problem is to input N, C1, C2, G1 and G2, then find out what would be the shortest combination of gun-choice(A or B) the human must use to kill the monster(the monster dies when No. of heads=0).

Could anyone please help me with this one. Just some hints would be really helpful. I have written some code, but its not making sense at all.

[Gribouillis]

Assuming N > 0, when you fire the last time, the monster must have C1 or C2 heads. Assuming you fired x times with gun A and y times with gun B before this last shot, then you have the equation N + x*(G1-C1) + y*(G2-C2) = C1 or C2. You could start iterating over the pairs x, y >= 0 satisfying this equation (they can be found by the Bezout theorem). Then see if these pairs work. The total number of shots will be x+y+1.

[slate]

The possible shots build a directed graph with dead ends, not an undirected one.
If you have this algo in mind, then it is unsuitable for that without modification...

However you can mark dead ends visited, and backtrack.

I would maintain a list of current path, and a set of visited nodes and a current node. If dead end is reached, then the current node is marked visited, the previous node in path made current, and the current path last element is removed.

A node is a dead end if no shots are possible without the dead of the human or all shots lead to visited nodes.

If you are interested, I can make a sample code for that, as proof of my concept.

Are you?

[king_koder]

@slate- I'll be really glad if you could do that!! Please also explain your code(as you see, I'm very much a beginner)

[slate]

def find_shortest(N,C1,C2,G1,G2):
    dead=set()
    path=[N]
    current=N
    bigshot=max(C1-G1,C2-G2)
    lowshot=min(C1-G1,C2-G2)
    while current!=C1 and current!=C2:
        for shot in (bigshot,lowshot):
            if current-shot not in dead and current-shot>0:
                path.append(current-shot)
                current=current-shot
                break
        else:
            #dead end
            dead.add(current)
            path.pop(-1)
            current=path[-1]
        if N in dead:
            return None
    else:
        return path+[0]


print "solution (monster headcounts):",find_shortest(10,5,3,2,1)

[slate]

Another problem with applying dijkstra algo here is, that there is not always a path...

[king_koder]

What invokes the else in line 13?? And what is being done in that whole section of the program (line 13 to 17)?? Could you explain please. Thanks!!

[slate]

Line 13 else is invoked if no break is executed inside the loop. That means all shots lead to already dead marked nodes or overshut.

Line 13-17 is: Add the current node to the dead nodes, and backtrack. Backtracking is to remove last element from path, make the last element of the remaining path the current node.

Try inserting "print path" at the beginning of the while loop to see what is happening.

[Gribouillis]

Here is my attempt, which doesn't use graph algorithms, but the Bezout theorem in arithmetics

Note: this code should be tested more intensively, and it remains to prove that
the solution always work theoretically (find counter example ?)

def bezout(n, m, u):
    """return (a, b, g) such that a * n + b * m = u
    and g = gcd(n, m)"""
    if m:
        q, r = divmod(n, m)
        a, b, g = bezout(m, r, u)
        return b, a - q * b, g
    else:
        q, r = divmod(u, n)
        if r:
            raise ValueError, "No solution"
        return q, 0, n


def pairs(d1, d2, u):
    """yield the pairs x, y such that x * d1 + y * d2 = u
    and x >=0 and y >= 0 with x + y increasing.
    """
    a, b, g = bezout(d1, d2, u)
    e1, e2 = d2 / g, -d1 / g
    if e1 + e2 < 0:
        e1, e2 = -e1, -e2
    if e1 > 0:
        q, r  = divmod(-a, e1)
        kmin = q + (r > 0)
        if e2 > 0:
            q, r = divmod(-b, e2)
            kmin = max(kmin, q + (r > 0))
    else:
        q, r = divmod(-b, e2)
        kmin = q + (r > 0)
    while True:
        x, y = a + kmin * e1, b + kmin * e2
        if x < 0 or y < 0:
            break
        yield x, y
        kmin += 1

def shots(N, C1, C2, G1, G2):
    """try to give a solution x, y with
    x = number of shots with the first gun
    y = number of shots with the second gun
    the returned pair is derived from the pair of integers such that
    N + xx * (G1-C1) + yy * (G2-C2) = C1 or C2
    with the smallest sum xx + yy
    The orders of the shots is not specified and should be checked.
    Raise ValueError if the problem doesn't have a solution.
    """
    if not N:
        return 0, 0
    d1, d2 = G1 -C1, G2 - C2
    P, Q = iter(pairs(d1, d2, C1-N)), iter(pairs(d1, d2, C2-N))
    try:
        xp, yp = next(P)
    except (ValueError, StopIteration):
        xp, yp = None, None
    try:
        xq, yq = next(Q)
    except (ValueError, StopIteration):
        xq, yq = None, None
     #print xp, yp, xq, yq
    if xp is None and xq is None:
        raise ValueError, "No Solution"
    if xp is None:
        return xq, yq+1
    elif xq is None:
        return xp+1, yp
    else:
        return (xp+1, yp) if xp+yp < xq+yq else (xq, yq+1)
    
print shots(36, 7, 3, 3, 8)

[king_koder]

@slate- Sorry, I'm still not sure about how your program works. Could you explain in more detail. Also how do I modify the program to print the results something like 'ABAAB'??

@Gribouillis- Thanks for the program. I'm not familiar with Bezout's theorem yet, but I'll check out Wikipedia as soon as I can.

[Gribouillis]

@slate- Sorry, I'm still not sure about how your program works. Could you explain in more detail. Also how do I modify the program to print the results something like 'ABAAB'??

@Gribouillis- Thanks for the program. I'm not familiar with Bezout's theorem yet, but I'll check out Wikipedia as soon as I can.

Actually, there are different Bézout's theorems. This one is an elementary one called Bézout's identity. See here
http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity.

[slate]

@slate- Sorry, I'm still not sure about how your program works. Could you explain in more detail. Also how do I modify the program to print the results something like 'ABAAB'??

I am not sure I undestand, what you are asking for.

I apply dijkstra algo with the following definitions and modifications:

• The nodes are the number of monster headcount in the process of shooting.
• The edges are the shots. The weight of the edge is the shot's damage.
• The path list keeps track of the shot demages.
• If no shot is possible, then the node is dead.
• The choosing among nodes is modified to exclude dead nodes. Also a backtrack is implemented if all child nodes are dead.
• If all nodes of the root node is dead, then there is no solution.

The solution giving back the shots' letters.

def find_shortest(N,C1,C2,G1,G2):
    dead=set()
    path=[N]
    current=N
    shotdict={C1:"A",C1-G1:"A",C2:"B",C2-G2:"B"}
    bigshot=max(C1-G1,C2-G2)
    lowshot=min(C1-G1,C2-G2)
    while current!=C1 and current!=C2:
        for shot in (bigshot,lowshot):
            if current-shot not in dead and current-shot>0:
                path.append(current-shot)
                current=current-shot
                break
        else:
            #dead end
            dead.add(current)
            path.pop(-1)
            if not path: # backtracked to the root
                return None
            current=path[-1]
    else:
        return "".join(shotdict[path[i]-path[i+1]] for i in range(len(path)-1))

print find_shortest(10,5,3,2,1)
print find_shortest(36, 7, 3, 3, 8)