Computer Science Canada Dynamic programing/ Greedy algorithm help |
| Author: | fabiocaravieri [ Sun May 08, 2011 10:46 am ] |
| Post subject: | Dynamic programing/ Greedy algorithm help |
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. |
|
| Author: | mirhagk [ Sun May 08, 2011 2:09 pm ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
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. |
|
| Author: | fabiocaravieri [ Sun May 08, 2011 2:52 pm ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
could you help me to draft a generic algorithm. Something very general |
|
| Author: | Insectoid [ Sun May 08, 2011 3:05 pm ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
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). |
|
| Author: | mirhagk [ Sun May 08, 2011 3:15 pm ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
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. |
|
| Author: | fabiocaravieri [ Sun May 08, 2011 4:23 pm ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
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 |
|
| Author: | Insectoid [ Sun May 08, 2011 4:33 pm ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
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. |
|
| Author: | ccontest [ Sun May 08, 2011 4:40 pm ] |
| Post subject: | Re: Dynamic programing/ Greedy algorithm help |
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. |
|
| Author: | fabiocaravieri [ Sun May 08, 2011 8:11 pm ] |
| Post subject: | Re: Dynamic programing/ Greedy algorithm help |
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 |
|
| Author: | fabiocaravieri [ Sun May 08, 2011 8:32 pm ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
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 |
|
| Author: | Insectoid [ Sun May 08, 2011 8:40 pm ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
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. |
|
| Author: | fabiocaravieri [ Mon May 09, 2011 8:41 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
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. |
|
| Author: | fabiocaravieri [ Mon May 09, 2011 8:42 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
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. |
|
| Author: | fabiocaravieri [ Mon May 09, 2011 9:20 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
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); } |
|
| Author: | fabiocaravieri [ Mon May 09, 2011 9:21 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
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? |
|
| Author: | Brightguy [ Mon May 09, 2011 9:54 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
mirhagk @ Sun May 08, 2011 3:15 pm wrote: I can't picture a case where this is wrong, so I'm going to test this algorithm with my sister.
Try 65413. 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.
Not recommended. This is exponential time. fabiocaravieri @ Sun May 08, 2011 8:11 pm wrote: Forgive me for asking, but you are considering the arrangement of letters as a two dimensional array, could explain this?
The two dimensional array doesn't store the arrangement, it stores the optimal scores for subproblems of your original problem. The idea is, if you know the optimal score for the subproblems with just one card missing, you can use them to easily compute the optimal score for the entire problem. |
|
| Author: | fabiocaravieri [ Mon May 09, 2011 11:09 am ] |
| Post subject: | Re: Dynamic programing/ Greedy algorithm help |
I considered the arrangement of letters as a one-dimensional arry |
|
| Author: | mirhagk [ Mon May 09, 2011 11:13 am ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
Yeah mine was just a suggested algorithm that a human could apply in real time, I doubted it worked under every condition, more of that it is a better strategy than greedy. Doing the exponential time why should not be too difficult, as it's only 2^(n/2) and not 2^(n). That means that for a full deck, n=52 it's only 2^26, which is not that high for a recursive algorithm. |
|
| Author: | A.J [ Mon May 09, 2011 12:01 pm ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
There's actually a simple mathematical solution to this problem. Since there's an even number of cards (i.e. 8 in this case), we notice that the initial configuration is: O E O E O E O E where a card is O if it is in an odd position, and E if it is in an even position. Notice that since you are going first you can force your opponent to either: 1) Take all the O (i.e. odd placed) cards 2) Take all the E (i.e. even placed) cards If you want your opponent to take all the O cards, all you have to to is keep taking the E card during your turn (notice that at your turn you'll always have an O and an E card at the ends, whereas your opponent will always have to pick an O card up). Similarly you can force him to pick up all the E cards by keep taking the O card in your turn. Therefore, you simply sum the numbers on the O cards and then on the E cards; whatever cards yield the higher sum, pick those up. For example, consider the following initial configuration: 1 -3 4 2 4 9 10 3 The O cards sum to: 1 + 4 + 4 + 10 = 19 whereas the E cards sum to: -3 + 2 + 9 + 3 = 11 (which is less). Therefore, you start by taking the leftmost (i.e. the O) card, leaving your opponent to choose from two E cards. Whatever he chooses, he'll then expose an O card for you to choose. Eventually, you'll end up with all the O cards (leaving you with a score of 19) and he'll end up with all the E cards (leaving him with a score of 11). Therefore, if you start with an even number of cards, going first allows you to force a win for yourself. If you have an odd number of cards, going second gives you this advantage (though you might not be able to win die to the firs card picked up by your opponent). I hope this helped. |
|
| Author: | mirhagk [ Mon May 09, 2011 12:39 pm ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
Wow AJ that's actually pretty awesome. See I love stuff like this, there's a whole recursion algorithm to do it, or something super simple that works very easily. Gonna totally beat everyone at this card game now lol. |
|
| Author: | fabiocaravieri [ Mon May 09, 2011 10:01 pm ] |
| Post subject: | Re: Dynamic programing/ Greedy algorithm help |
I took the idea even made an interactive algorithm, but needed help to transform it into recursive. If you could help me have some idea, it would be helpful Thanks for the help |
|
| Author: | A.J [ Tue May 10, 2011 2:02 am ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
To develop a recursive function to implement some goal, there are essentially three things you need to be vary of: 1) The state: Basically, what is the recursive function going to work on? What is the smaller problem you want to break your problem down to? In this case your subproblem will be solving the game for a smaller number of cards (i.e. your state will be two numbers (x, y), where you'll be playing the game from the xth to the yth card);. 2) The base case: What is the smallest subproblem that you already know the answer to? Well, if x = y, then you are playing a game with only one card, and since you are going first, you'll win. Another base case could be when y = x + 1 (i.e. when you are playing with two cards). In this case, you take the bigger of the two cards and win. 3) Recursive step: This is probably the most crucial part of a recursive function; the breaking of the problem into subproblems. In this case, there are two things you can do: take the xth or the yth card of the list. Let's consider these two options. Taking the xth card: If you take the xth card, then assuming your opponent plays optimally, he'll either take the (x+1) th or the yth card (whatever card yields the higher score). Therefore, you'll be left with x + min(if opponent takes x+1 th card, opponent takes yth card), or in other words score(xth card) + min(solve(x+2, y), solve(x+1, y-1)) (since your opponent will play optimally, you'll be left with the minimum of the two choices he has, as he will minimize your winnings). Take the yth card: Similarly, if you initially take the yth card, then your opponent will either take the xth or the (y-1)th card, depending on which of the two will leave a list of cards that will minimize your score. i.e. You'll be left with score(yth card) + min(solve(x, y-2), solve(x+1, y-1)), if you initially take the yth card. So now you have reduced the original problem into smaller subproblems. So, solve(x, y) should return the max of you taking the xth or the yth card: solve(x, y) = max(score(xth card, yth card)) (if x = y, or y = x+1) solve(x, y) = max(score(xth card) + min(solve(x+2, y), solve(x+1, y-1)), score(yth card) + min(solve(x, y-2), solve(x+1, y-1))) I guess the step forward from here would be to realize that you don't need recursion at all, and can work through this process bottom-up indexing everything on a 2D array (i.e. DP). And the final step for this problem is to realize that there's a simple mathematical solution (that I described in my previous post) that doesn't really require a computer. |
|
| Author: | Brightguy [ Tue May 10, 2011 3:37 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
mirhagk @ Mon May 09, 2011 11:13 am wrote: Doing the exponential time why should not be too difficult, as it's only 2^(n/2) and not 2^(n). That means that for a full deck, n=52 it's only 2^26, which is not that high for a recursive algorithm.
So you can solve problems twice the size than you could otherwise. You'll start feeling the pain somewhere around 2^26. A.J: A slight modification: your opponent is known not to play optimally. Your first trick is pretty interesting but not optimal. |
|
| Author: | A.J [ Tue May 10, 2011 4:25 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
Brightguy @ Tue May 10, 2011 3:37 am wrote: A.J: A slight modification: your opponent is known not to play optimally. Your first trick is pretty interesting but not optimal. Wait, what do you mean by that? As in we don't know for sure whether your opponent is playing optimally, or are we given that his moves are made purposely to be sub-optimal? Either ways, don't we assume the worst case scenario and play as if your opponent plays optimally? And regarding the mathematical solution, why isn't it optimal (in the 'even number of cards' case)? I mean, I realize that it doesn't really work with an odd number of cards. I guess this question was initially meant to be an exercise in recursion/DP, so utilizing the recurrence given in my previous post does solve the general case with n cards in O(n^2) time, but for small enough n (like in this case), brute force suffices. |
|
| Author: | Brightguy [ Tue May 10, 2011 6:09 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
We seem to be solving different problems. As I read it the problem was to find the maximum score you can obtain when playing against a greedy opponent. |
|
| Author: | A.J [ Tue May 10, 2011 6:20 am ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
Oh, my bad, I didn't read that part of the question. Well, the O(n^2) Dynamic Programming still works, though like you mentioned a slight modification is required. |
|
| Author: | mirhagk [ Tue May 10, 2011 7:27 am ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
Wait I'm confused brightguy, are you talking about the Odd/Even trick? Cuz that always works regardless of what the opponent does. |
|
| Author: | A.J [ Tue May 10, 2011 8:04 am ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
I think what brightguy was referring to was my explanation regarding the O(n^2) DP. The parity trick does work for all cases iff the number of cards is even (and in certain cases where the number of cards are odd). |
|
| Author: | fabiocaravieri [ Tue May 10, 2011 3:20 pm ] |
| Post subject: | Re: Dynamic programing/ Greedy algorithm help |
I've solved, thanks for the help |
|
| Author: | fabiocaravieri [ Tue May 10, 2011 8:08 pm ] |
| Post subject: | Re: Dynamic programing/ Greedy algorithm help |
I managed to solve. Thanks for the help |
|
| Author: | Quantris [ Wed May 11, 2011 5:39 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
A.J @ Tue May 10, 2011 6:04 am wrote: I think what brightguy was referring to was my explanation regarding the O(n^2) DP. The parity trick does work for all cases iff the number of cards is even (and in certain cases where the number of cards are odd).
The parity trick you described doesn't necessarily give you the optimal score (though it lets the first player always avoid losing). For example: 10 5 1 5 Parity says I get 11 (winning 11-10), but obviously the optimal result is 15-6. The problem is that we can switch from O to E on any of our moves, and can sometimes improve our score by switching at the right times. Also, there are cases where the parity argument gives a tie but the game is actually a guaranteed win for first player: 10 5 5 10 5 5 Parity says 20-20, but player 1 can win 25-15 by waiting for his opponent to "expose" the 2nd 10. |
|
| Author: | A.J [ Wed May 11, 2011 6:44 am ] |
| Post subject: | RE:Dynamic programing/ Greedy algorithm help |
I thought the objective of the game is to win, and not to maximize your score. If you want to do that, then you are correct, the parity check doesn't give you that (it only tells you that you can force a trick). I just thought I'd share it as it is pretty cool. The O(n^2) DP gives you the maximum possible score you can achieve. |
|
| Author: | Quantris [ Thu May 12, 2011 1:29 am ] |
| Post subject: | Re: RE:Dynamic programing/ Greedy algorithm help |
A.J @ Wed May 11, 2011 4:44 am wrote: I thought the objective of the game is to win, and not to maximize your score.
Fair enough; I think others reading your post may not have understood that (myself included). It's also an interesting point that there are some arrangements where the parity method can't tell you how to win (the "tie" game I showed). |
|