5

This is my code:

    static int cardGameValue(List<int> D, int myScore, int opponentScore)
    {
        if (D.Count == 0) return myScore;
        else if (D.Count == 1)
        {
            opponentScore += D[0];
            return myScore;
        }
        else
        {
            if (D[0] <= D[D.Count - 1])
            {
                opponentScore += D[D.Count - 1];
                D.RemoveAt(D.Count - 1);
            }
            else
            {
                opponentScore += D[0];
                D.RemoveAt(0);
            }

            int left = cardGameValue(new List<int>(D.GetRange(1, D.Count - 1)), myScore + D[0], opponentScore);

            int right = cardGameValue(new List<int>(D.GetRange(0, D.Count - 1)), myScore + D[D.Count - 1], opponentScore);

            if (left >= right)
            {
                return left;
            }
            else
            {
                return right;
            }
        }
    }
}

My code takes a set of cards and represents your maximum possible score when playing against a deterministic opponent. After each of your opponent's plays you have 2 choices until cards are all picked. Is there a way to somehow store my results of the iterations so I can improve my algorithm? So the recursion doesn't do unnecessary iterations? Because after 40 or 50 cards it becomes very slow.

Improve this question
1
  • But I don't have a tree itself, it's just a recursion process. Is there a way to prune it while executing it? Commented Jan 13, 2012 at 6:37

3 Answers 3

Reset to default
3

You only access the first or the last element in the list D. Rather than pass the exact list around, you can pass the full list of cards (or even better: as an int array) together with the index of the first and last position.

It's much faster to calculate the opponent's score after the calculation is complete: myScore and opponentScore add up to the sum of the values of the cards, so you can do this in O(n) time. This way, you can eliminate all the code that updates opponentScore.

You don't need to pass myScore either. If you let cardGameValue return the best score obtained from only the remaining cards.

Finally, if you work with the first and last index, you can store the score in a 2D array, indexed by first and last. If all the cards have positive values, then the score must be positive if there are at least two cards remaining.

So at the beginning of the call, you check if the cached score is positive. If it is, you can return it right away. If not, you have to calculate it, and then store it in the cache array.

This is what you end up with:

static int cardGameValue(int[] D, int first, int last) {
    scores = new int[last + 1, last + 1];
    return cardGameValue(D, first, last, scores);
}

static int cardGameValue(int[] D, int first, int last, int[,] scores) {
    // If we have at most 1 card, our score is 0:
    if (first >= last)
        return 0;

    // Otherwise, get the score from the cache array. 
    // If it is positive, return the value.
    int score = scores[first, last];
    if (score > 0)
        return score;

    // Keep the original first and last 
    // for filling in the computed value later.
    int firstOriginal = first;
    int lastOriginal = last;

    // Let the opponent pick a card:
    if (D[first] <= D[last])
        last--;
    else
        first++;

    // Choose our best card:
    int left = D[first] + cardGameValue(D, first + 1, last, scores);
    int right = D[last] + cardGameValue(D, first, last - 1, scores);
    score = Math.Max(left, right);

    // and enter the score into the cache array:
    scores[firstOriginal, lastOriginal] = score;

    // Finally, return the computed score.
    return score;
}

Even for 300 cards, this runs in less than 1 millisecond on my machine.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks a lot for your help! Indeed, a very wise solution!
2

You can try dynamic programming, just store the intermediate results in some suitable data structure, and when you need to invoke a recursive call, just use the stored value!

You can use a 2-D array of ints to store the results. The element at [i][j] will store the result of the game with the deck D[i] through D[j]. Start with row 0, then using the results fill up row 1, and so on. This will calculate the result in O(n^2) time.

Improve this answer

1 Comment

That's a good idea but I'm not really sure how to do so, as I'm not going through another data estructure, just trying out possibilities from the numbers. I'm kind of new in these things thanks for your patience.
1

These lines are allocating new List objects, not to mention that the GetRange method itself creates a new List object, so there are a total of 4 new List objects being created by these 2 lines of code each time they execute. This could be relatively expensive if you have a large number of items in the list.

        int left = cardGameValue(new List<int>(D.GetRange(1, D.Count - 1)), myScore + D[0], opponentScore);

        int right = cardGameValue(new List<int>(D.GetRange(0, D.Count - 1)), myScore + D[D.Count - 1], opponentScore);

You may be able to modify your method signature to take startIndex and length parameters so that every call to cardGameValue can reuse the same List instance.

static int cardGameValue(List<int> D, int startIndex, int length, int myScore, int opponentScore)

Perhaps make the recursive calls like this:

        int left = cardGameValue(D, startIndex + 1, length - 1, myScore + D[startIndex], opponentScore);

        int right = cardGameValue(D, startIndex, length - 1, myScore + D[startIndex + length - 1], opponentScore);

i.e. Code that refers to index 0 such as D[0] and D.RemoveAt(0) would need to be modified to use startIndex, such as D[startIndex] and D.RemoveAt(startIndex). Code that refers to D.Count would need to be repaced with startIndex + length. Correction: Code that refers to D.Count - 1 would need to be replaced with either length - 1 or startIndex + length - 1 (depending on the context), but code that just refers to D.Count would just be replaced with length.

Improve this answer

3 Comments

Thanks for that last example! I was already asking myself the same.
What should I do with the base cases? They refer to the count of the List, should I leave it like that or still use length?
@Jean Carlos Suárez Marranzini - I'm not sure what base classes you're referring to. I don't think I can answer that question, as it requires understanding the structure of your application.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.