Memoize will work, but it's not magic. The simplest way to write the function is as follows:
sub get_move_score {
my @numbers = @_ or return("end", "", 0);
return "shift", $numbers[0], $numbers[0] if 1 == @numbers;
my $shift = shift @numbers;
my $pop = pop @numbers;
my $score_shift = $shift - (get_move_score(@numbers, $pop))[2];
my $score_pop = $pop - (get_move_score($shift, @numbers))[2];
if ($score_pop > $score_shift) {
return "pop", $pop, $score_pop;
}
else {
return "shift", $shift, $score_shift;
}
}
Now if you memoize that and try to run it for a list of n numbers, the memory requirements are O(n**3). (You wind up calling it for O(n) starting points, with O(n) ending points, with an argument list of length O(n) passed in.) For a list of 1000 numbers, that means that you'll need to store order of a billion or so numbers. (Less a factor of 6 or so, I could work it out.) Given how Perl hogs memory, and what most PCs are capable of, your implementation will probably fail on account of running out of memory.
You can fix that by having @numbers be in a global array, and then only pass in the start and end points of the list. But now if you want to play more than one game, you're hosed. (Unless you read the documentation for Memoize, and correctly call memoize/unmemoize in pairs.)
Which means that in this case it is better to understand what the program is supposed to do, and explicitly build up your own data structure. | [reply]
[d/l] |
Memoize only reduces the work, it doesn't eliminate checking to see if it's already done.
For N=1000, 2^n ~~ 1e301, while n^2/2 ~~ 1e5. The first will never finish in the lifetime of the universe, the second in a blink of an eye.
-QM
--
Quantum Mechanics: The dreams stuff is made of
| [reply]
[d/l] |
