Dynamic programing/ Greedy algorithm help

[fabiocaravieri]

I need to solve an exercise and would like to know if someone could help me

You and your eight-year-old nephew Elmo decide to play a simple card game. At the beginning
of the game, the cards are dealt face up in a long row. Each card is worth a different number
of points. After all the cards are dealt, you and Elmo take turns removing either the leftmost or
rightmost card from the row, until all the cards are gone. At each turn, you can decide which of
the two cards to take. The winner of the game is the player that has collected the most points
when the game ends.

Having never taken an algorithms class, Elmo follows the obvious greedy strategy?when it?s
his turn, Elmo always takes the card with the higher point value. Your task is to find a strategy
that will beat Elmo whenever possible. (It might seem mean to beat up on a little kid like this, but
Elmo absolutely hates it when grown-ups let him win.)

(a) Prove that you should not also use the greedy strategy. That is, show that there is a game
that you can win, but only if you do not follow the same greedy strategy as Elmo.
(b) Describe and analyze an algorithm to determine, given the initial sequence of cards, the
maximum number of points that you can collect playing against Elmo.

[mirhagk]

Well I don't know much about dynamic algorithms, but since elmo always takes the highest point card only your turn is a variable. You have two cards to choose from, so a brute force algorithm would only be 2^(n/2) options, (n being the number of cards).

Coming up with an example of how the greedy algorithm fails shouldn't be too difficult, and as for a better strategy, I think I have one, but I don't want to just give it away. Just think of it this way, if you take the highest of the two cards, when exactly would this fail.

ie for the series 32195 why should you not take the 5. This should lead you in the right direction.

[fabiocaravieri]

could you help me to draft a generic algorithm. Something very general

[Insectoid]

Use recursion. Since you know, in any given case, what card Elmo will pick, you can plan ahead. If you pick card X, Elmo will pick card Y. Then you can pick a new card X, and Elmo will pick a new card Y. You can simulate this in your own 'turn' to figure out which selection leads to a win (in the event both cases win, select the one that results in a greater lead).

[mirhagk]

Actually I'm pretty sure theres a very simple trick, but I'm not 100% sure, since I'm not sure if it's the answer I'm just going through the hypothesis out there, pick the card that satisifies the condition
x1 being the card
x2 being the card behind it
x1-x2 is the greatest value. so for instance in the series

321395 you choose 3 since the next card is 1 point below it (compared to 4 points above). Then Elmo picks 5, and you pick 9, and he picks 3 you pick 2 and he gets 1.

I can't picture a case where this is wrong, so I'm going to test this algorithm with my sister.

[fabiocaravieri]

Insectoid @ Sun May 08, 2011 3:05 pm wrote:

Use recursion. Since you know, in any given case, what card Elmo will pick, you can plan ahead. If you pick card X, Elmo will pick card Y. Then you can pick a new card X, and Elmo will pick a new card Y. You can simulate this in your own 'turn' to figure out which selection leads to a win (in the event both cases win, select the one that results in a greater lead).

Insectoid could give me some tips on how to use recursion in this case, I am beginner in this

[Insectoid]

At the beginning of the game, once you know the set of cards, you simulate the entire game (before the actual game is played). You pick a card, simulate elmo picking his, and continue to the end of the game. If elmo in your pre-game simulation, you back up to the last turn, pick the other card, and then continue the simulation to the end again. If elmo still won, you back up to the 2nd last turn, simulate the rest of the game, etc. Repeat until you win. Alternatively, you can simulate every possible outcome and determine the greatest victory magin. Once you've found the winning set of moves, you play the game, with those moves.

Since the game will always play out exactly as predicted at the beginning, you don't need to check the best move every turn.

[ccontest]

Since the whole point of this forum is to help, not do hw for you, i'll just give you a hint.

Hint: Denote best[i][j] to be the maximum point you can obtain after some cards are removed, where the leftmost card is the ith card and the rightmost card is the jth card in the original card sequence.

Then, it should be fairly easy to set up the recurrence relation.

Of course, the answer would be best[1][N], where N is the number of the cards.

[fabiocaravieri]

ccontest @ Sun May 08, 2011 4:40 pm wrote:

Since the whole point of this forum is to help, not do hw for you, i'll just give you a hint.

Hint: Denote best[i][j] to be the maximum point you can obtain after some cards are removed, where the leftmost card is the ith card and the rightmost card is the jth card in the original card sequence.

Then, it should be fairly easy to set up the recurrence relation.

Of course, the answer would be best[1][N], where N is the number of the cards.

Forgive me for asking, but you are considering the arrangement of letters as a two dimensional array, could explain this?
Sorry once again its tip was not completely clear. Sorry once again its tip was not completely clear. If you could detail a little more, I would be grateful

[fabiocaravieri]

Insectoid @ Sun May 08, 2011 4:33 pm wrote:

At the beginning of the game, once you know the set of cards, you simulate the entire game (before the actual game is played). You pick a card, simulate elmo picking his, and continue to the end of the game. If elmo in your pre-game simulation, you back up to the last turn, pick the other card, and then continue the simulation to the end again. If elmo still won, you back up to the 2nd last turn, simulate the rest of the game, etc. Repeat until you win. Alternatively, you can simulate every possible outcome and determine the greatest victory magin. Once you've found the winning set of moves, you play the game, with those moves.

Since the game will always play out exactly as predicted at the beginning, you don't need to check the best move every turn.

Thanks, you're helping me a lot.
Could you help me develop a function of the level algorithm, using this solution

[Insectoid]

fabiocaravieri @ Sun May 08, 2011 8:32 pm wrote:

Insectoid @ Sun May 08, 2011 4:33 pm wrote:

At the beginning of the game, once you know the set of cards, you simulate the entire game (before the actual game is played). You pick a card, simulate elmo picking his, and continue to the end of the game. If elmo in your pre-game simulation, you back up to the last turn, pick the other card, and then continue the simulation to the end again. If elmo still won, you back up to the 2nd last turn, simulate the rest of the game, etc. Repeat until you win. Alternatively, you can simulate every possible outcome and determine the greatest victory magin. Once you've found the winning set of moves, you play the game, with those moves.

Since the game will always play out exactly as predicted at the beginning, you don't need to check the best move every turn.

Thanks, you're helping me a lot.
Could you help me develop a function of the level algorithm, using this solution

Sure, if you try yourself first.

[fabiocaravieri]

Insectoid @ Sun May 08, 2011 4:33 pm wrote:

At the beginning of the game, once you know the set of cards, you simulate the entire game (before the actual game is played). You pick a card, simulate elmo picking his, and continue to the end of the game. If elmo in your pre-game simulation, you back up to the last turn, pick the other card, and then continue the simulation to the end again. If elmo still won, you back up to the 2nd last turn, simulate the rest of the game, etc. Repeat until you win. Alternatively, you can simulate every possible outcome and determine the greatest victory magin. Once you've found the winning set of moves, you play the game, with those moves.

Since the game will always play out exactly as predicted at the beginning, you don't need to check the best move every turn.

I did some testing and observeri that if I get the player and the first letter of each extreminadade lower in the first move will force the Helm catch most of the second, so I can about it so I can catch most of the game.
Now I'm trying to turn this into an algorithm. But an interactive algorithm then transforms it into recursive.

[fabiocaravieri]

mirhagk @ Sun May 08, 2011 2:09 pm wrote:

Well I don't know much about dynamic algorithms, but since elmo always takes the highest point card only your turn is a variable. You have two cards to choose from, so a brute force algorithm would only be 2^(n/2) options, (n being the number of cards).

Coming up with an example of how the greedy algorithm fails shouldn't be too difficult, and as for a better strategy, I think I have one, but I don't want to just give it away. Just think of it this way, if you take the highest of the two cards, when exactly would this fail.

ie for the series 32195 why should you not take the 5. This should lead you in the right direction.

Your idea is right, if I take the first card and is smaller, I can reach most of the game played.
Now I'm trying to turn this into recursive algorithm. If you have any idea, it will be appreciated.

[fabiocaravieri]

Insectoid @ Sun May 08, 2011 3:05 pm wrote:

Use recursion. Since you know, in any given case, what card Elmo will pick, you can plan ahead. If you pick card X, Elmo will pick card Y. Then you can pick a new card X, and Elmo will pick a new card Y. You can simulate this in your own 'turn' to figure out which selection leads to a win (in the event both cases win, select the one that results in a greater lead).

I did the following iterative algorithm, see what you think?
I think the base case is when i> n or has no more cards.
I tested with several sequences and it worked
Can you give me some tips on how to improve it and how to convert it into a recursive function (this is my biggest hurdle)

int[] c={3,2,1,3,9,5}; //cards
int me, elmo; //sum points me and Elmo
int i=0;
int n=c.length-1;
int move=1;//controls the play, since the first move should be mine
me=0;
elmo=0;

while (i<=n)
{
if (move==1){
if (c[i]< c[n]){
me=me+c[i];
move++;
i++;}

else
{

me=me+c[n];
move++;
n--;
}
}


else
{ if (move%2==0)// I thought in controlling the numbers of moves. In my play would be odd (since I start the game) and the pair of Elmo
{ if (c[i]>c[n]){
elmo=elmo+c[i];
move++;
i++;}
else{
elmo=elmo+c[n];
move++;
n--;}

}
else{
if(c[i]>c[n]){
eu=eu+c[i];
i++;
move++;}
else{
me=me+c[n];

n--;
move++;
}}



}
}
System.out.println(eu+ elmo);
}

[fabiocaravieri]

mirhagk @ Sun May 08, 2011 3:15 pm wrote:

Actually I'm pretty sure theres a very simple trick, but I'm not 100% sure, since I'm not sure if it's the answer I'm just going through the hypothesis out there, pick the card that satisifies the condition
x1 being the card
x2 being the card behind it
x1-x2 is the greatest value. so for instance in the series

321395 you choose 3 since the next card is 1 point below it (compared to 4 points above). Then Elmo picks 5, and you pick 9, and he picks 3 you pick 2 and he gets 1.

I can't picture a case where this is wrong, so I'm going to test this algorithm with my sister.

I posted an idea solution. take a look and see what you think?