4 replies to this topic

[king_koder]

Hi, I am a C++ beginner (and somewhat new to programming itself). I need help with a programming problem which I am sure you guys can solve. The question goes like this:

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).

A sample output would be somewhat like AAB. I tried using recursion to solve this problem, but I was unsuccessful. What do you suggest?

Thanks for taking the time to go through this overly lengthened description by me.

[zoranh]

I'd like to know if G values have to be smaller than C values? It might turn out to be extremely difficult to solve the problem if Gi >= Ci is allowed.

Also, is it required that human must survive? If so, then last firing must be done with a gun which exactly matches number of remaining heads. This in turn means that there are use cases where there is no solution.

Now let's state the new task with these added conditions.
There are parameters C1, C2, G1, G2, such that C1 > G1 and C2 > G2. Number of heads is N. Guns are fired F1 and F2 times respectively.

Solution is required to find F1 and F2, plus one legal firing sequence such that N never goes below zero (or otherwise human will die). Another condition is to minimize F1+F2.

And finally, let's construct solution which uses Dijkstra's algorithm.

1. There are N+1 possible values for number of heads (0, 1, 2, ... , N).
2. Each value can be achieved in different ways, but only one minimal solution is tracked. For each value remember number of firings made to reach it, and gun which was last fired to reach it. Knowing the gun index i you can add (Ci-Gi) to current head count to find head count before gun i was fired.
3. Keep track of unprocessed head counts, initially consisting of only value N, which is starting position with monster in good health.
4. In each step take one unprocessed head count with smallest path length. Note that each firing increases path length by one, so just push new unprocessed head counts to the end of the queue and queue is guaranteed to be in non-descending order, as required by Dijkstra's algorithm.
5. For each unprocessed head count at hand, try to fire each of the guns. Gun is fired if head count is not greater than Ci. If gun i is fired, then new head count is n1=n-Ci+Gi, where n is current head count. If path length to n1 has not been found this far, then this is the shortest path length - remember it, and remember that gun i was fired to reach it.
6. You can stop executing when n1=0, because it means that shortest solution has been found. Also if queue of unprocessed head counts becomes empty, then it means that n1=0 has not been reached and solution does not exist.
7. Once done, start with head count 0 and unfold firing sequence. Don't forget to print it in reverse order, because it guarantees that number of heads never goes below zero along the path!

One simplification to this algorithm is NOT to track firing sequence length to each of the head counts, but just to remember gun index fired to reach it (with illegal index indicating that head count was not reached). Then calculate sequnece length by unfolding the firing sequence.

[king_koder]

Thank you very much for your detailed solution. As far as I'm concerned, the conditions you have considered are okay, and your logic makes sense to me.

But could you please also suggest how I could implement this in code, especially the part in step 5 (try to fire each of the guns). I understand that separate paths will be set up for each combination but I don't know how to put this into code.

[zoranh]

This is working solution in C++:

#include<stdio.h>

void Enqueue(int value, int *queue, int queueSize, int *queueTail, int *queueLen)
{
    queue[*queueTail] = value;
    *queueTail = (*queueTail + 1) % queueSize;
    *queueLen += 1;
}

int Dequeue(int *queue, int queueSize, int *queueHead, int *queueLen)
{    // Returns negative value if queue is empty

    int value = -1;

    if (*queueLen > 0)
    {
        value = queue[*queueHead];
        *queueHead = (*queueHead + 1) % queueSize;
        *queueLen -= 1;
    }

    return value;

}

int main()
{

    int n = 0;
    int gunsCount = 0;
    int *c = NULL;
    int *g = NULL;
    int *solution = NULL;
    int *queue = NULL;

    int queueSize = 0;    // These variables implement queue as circular buffer
    int queueLen = 0;    // That's because it's known that number of enqueued items 
    int queueHead = 0;    // can never be larger than n+1
    int queueTail = 0;

    do
    {

        printf("Heads count (0 to exit): ");
        scanf("%d", &n);

        if (n <= 0)
            break;

        printf("Guns count: ");
        scanf("%d", &gunsCount);

        c = new int[gunsCount];
        g = new int[gunsCount];

        for (int i = 0; i < gunsCount; i++)
        {
            printf("c[i]: ");
            scanf("%d", c + i);
            printf("g[i]: ");
            scanf("%d", g + i);
        }

        // Initialize vector of remaining heads
        solution = new int[n + 1];
        for (int i = 0; i <= n; i++)
            solution[i] = -1;    // Indicates that no gun was fired to reach i remaining heads

        queueSize = n + 1;
        queue = new int[queueSize];
        queueLen = 0;
        queueHead = 0;
        queueTail = 0;

        Enqueue(n, queue, queueSize, &queueTail, &queueLen);

        while (queueLen > 0 && solution[0] < 0)
        {
            
            int heads = Dequeue(queue, queueSize, &queueHead, &queueLen);

            for (int gun = 0; gun < gunsCount; gun++)
            {
                if (c[gun] <= heads)
                {    // Fire the gun
                    
                    int newHeads = heads - c[gun];
                    if (newHeads > 0)
                        newHeads += g[gun];    // do not add g unless monster is still alive

                    if (newHeads < n && solution[newHeads] < 0)
                    {
                        solution[newHeads] = gun;    // Mark that this gun has been fired to reach newHeads count
                        Enqueue(newHeads, queue, queueSize, &queueTail, &queueLen);    // Enqueue new heads count for processing
                    }
                }
            }

        }

        if (solution[0] < 0)
            printf("No solution found.\n");
        else
        {
            
            // There is a solution: first find its length, then extract it and finally print it in reverse order.

            int pathLength = 0;
            int curCount = 0;

            while (solution[curCount] >= 0)
            {
                
                pathLength++;
                int gun = solution[curCount];

                if (curCount == 0)
                    curCount = c[gun];
                else
                    curCount += c[gun] - g[gun];

            }

            char *path = new char[pathLength + 1];

            path[pathLength] = '\0';

            int pos = pathLength;
            curCount = 0;

            while (solution[curCount] >= 0)
            {
                int gun = solution[curCount];
                path[--pos] = 'A' + gun;

                if (curCount == 0)
                    curCount = c[gun];
                else
                    curCount += c[gun] - g[gun];

            }

            printf("%s\n", path);

            delete[] path;

        }

        delete[] queue;
        delete[] g;
        delete[] c;

    }
    while (n > 0);

}

Analyze it step by step. That is full implementation of Dijkstra's algorithm applied to this problem. It allows any number of guns, not only two.

Here are some test cases:

Heads count (0 to exit): 1
Guns count: 1
c[i]: 1
g[i]: 0
A
Heads count (0 to exit): 10
Guns count: 2
c[i]: 1
g[i]: 0
c[i]: 3
g[i]: 1
ABBBB
Heads count (0 to exit): 100
Guns count: 2
c[i]: 1
g[i]: 0
c[i]: 9
g[i]: 3
ABBBBBBBBBBBBBBBB

[king_koder]

Thanks a lot! I'll have to study the this program a bit to fully understand, but I'll figure it out. Thanks for giving your valuable time!