CODEWITHSUNDEEP
calgorithmrecursion
Ahmad Aboud
Ahmad Aboud

Reputation: 51

Card Game Algorithm

I'm asked to develop a card game in c language between 2 players where a player can select the left most or the right most card from a list of cards ex: If the list is : [2,14,12,6,20,10] the player may select 2 or 10. Finally the player with higher score(sum of cards selected by player) wins the game. Is there a way to optimize the selection of a player knowing that not always the best choice is the maximum (ex: choosing 10 in the above case gives opportunity for the other player to select 20 ). (Sounds to be a recursive function...)

Upvotes: 3

Views: 4162

Answers (4)

lpcclown
lpcclown

Reputation: 11

@asaelr answer is simple and easy to understand, it is a really nice trick for this problem. However, this solution only can make sure the first player not to lose, cannot make sure he earns the most points than the opponent. If we want to get the optimal solution, we have to use DP. For example: { 3, 2, 2, 3, 1, 2 }, by using the trick we can win 2, by using DP we can win 3 points. The detailed explanation can be found from here. Really nice article. http://articles.leetcode.com/coins-in-line/

Upvotes: 0

Ante
Ante

Reputation: 5448

Playing optimal, for given game, players will get some score. Let input be list L and define F(i,l) and S(i,l) as first and second player scores for part of a list starting from i'th element with length l. If (part of) list is of length 1 than that card will go to the first player.

F(i,1) = L[i]
S(i,1) = 0

If (part of) list is longer than first player wants to maximize sum of card he choose and what he will get as second player with list what is left.

F(i,l) = max( L[i] + S(i+1,l-1), L[i+l-1] + S(i,l-1) )

Since second player is not choosing card he will get what first player get in shorter list.

S(i,l) = F(i+1,l-1) if L[i] + S(i+1,l-1) >= L[i+l-1] + S(i,l-1), or
         F(i,l-1)   if L[i] + S(i+1,l-1) < L[i+l-1] + S(i,l-1).

Implementation is done by filling two n^2 arrays for F and S. Result is F(1, length(L) ).

Upvotes: 0

Timo
Timo

Reputation: 5176

We had this exercise on one of our programming courses, and this is the solution I came up with (in c++ but it's easily translated to c). It uses dynamic programming with O(n^2) time and O(n) space. First it calculates the optimal play score for each sublist of length 1, then uses them to calculate the scores for length 2 lists and so on. Finally there are two lists of length n-1 and we pick the one that gives better overall score.

int f(const vector<int>& numbers) // return 0 if left is optimal pick, 1 if right 
{
    vector<int> s(numbers);

    for(size_t len = 1; len < numbers.size() - 1; ++len)
        for(size_t i = 0; i < numbers.size() - len; ++i)
            s[i] = max(numbers[i] - s[i + 1], numbers[i + len] - s[i]);

    return numbers.front() - s[1] < numbers.back() - s[0];
}

Upvotes: 0

asaelr
asaelr

Reputation: 5456

I don't know about maximize. but if (at the start) there is even number of cards, there is a simple algorithm for the first player:

First, mark the cards by red and black (alternately), so the cards in the edges will be in different colors. Sum (separately) the black cards and the red cards, and choose the color you prefer. Assuming (for example) that the sum of black cards is higher, keep choosing black cards, and your opponent will have to choose red cards - and you will win!

Upvotes: 2

Related Questions