Puzzle: Given an array of integers, find the best sequence of pop / shift...by TedPride (Priest)
|on Mar 20, 2006 at 02:26 UTC||Need Help??|
TedPride has asked for the
wisdom of the Perl Monks concerning the following question:
You are given a random, even number of integers (for testing purposes, let's say the following):
16 2 10 2 9 17 5 8 15 14 20 19 19 11 10 11 9 13 7 13
You and some other player take turns choosing either the leftmost element (shift) or the rightmost element (pop). You go first. The objective is to achieve the highest total score: your choices minus the other player's choices. For instance, if you were given the following:
2 8 4 5
The best sequence of moves would be:
You assume of course that the other player also picks his best move each time.
The big question is, can you write a script that will give you the best moves for the first sequence of numbers above, for a total score of 10? The same script must also be able to generate the sequence of best moves for an array of 1000 numbers without taking more than a minute or running you out of memory. My script produces the following:
With the following code:
I'm pretty sure my code produces the best results, but I'm not 100% sure, and as you can see, the code is somewhat of a hack job. I'd like to get some more submissions so I can check my results :)
No, this is not homework. This is just for personal enjoyment.