in reply to
Puzzle: Given an array of integers, find the best sequence of pop / shift...

Unless I'm missing something, I reckon your solution is a lot more complex than it needs to be.

Given that *"the other player also picks his best move"*, then all you need to do is determine which produces the higher score - a pop-first, or a shift-first.

This is my go at it:

`#!/usr/bin/perl -wl
use strict;
my @numbers = qw(16 2 10 2 9 17 5 8 15 14 20 19 19 11 10 11 9 13 7 13)
+;
my $shiftscore = checkscore("shift");
@numbers = qw(16 2 10 2 9 17 5 8 15 14 20 19 19 11 10 11 9 13 7 13);
my $popscore = checkscore("pop");
my $bestscore = $popscore > $shiftscore
? $popscore
: $shiftscore;
print "POP:$popscore:SHIFT:$shiftscore";
print "Best Score:$bestscore";
sub checkscore {
my $first_turn = shift;
my ($player, $opponent);
$player = $first_turn eq "pop"
? pop(@numbers)
: shift(@numbers);
while (@numbers) {
$opponent += $numbers[0] > $numbers[-1]
? shift(@numbers)
: pop(@numbers);
last if !@numbers;
$player += $numbers[0] > $numbers[-1]
? shift(@numbers)
: pop(@numbers);
}
return ($player - $opponent);
}
`

Which gives:

`POP:4:SHIFT:10
Best Score:10
`

**Update:** To test how long it takes with 1000 numbers I added the following lines:.

`use List::Util qw(shuffle);
my @numbers = shuffle(1 .. 1000);
print join(" ", @numbers);
my @copy = @numbers;
my $shiftscore = checkscore("shift");
@numbers = @copy;
my $popscore = checkscore("pop");
`

And I get something like this:

`POP:4354:SHIFT:7452
Best Score:7452
real 0m0.049s
user 0m0.030s
sys 0m0.000s
`

PS: Like the OP, I'm not 100% sure that I'm getting correct results - and I'm not sure how to verify it for very large ranges, I guess I'll just wait for some more responses :)

**Update 2:** - as tilly has pointed out, my solution is wrong. I kindof suspected that it would be - because it seemed too simple. And although I acknowledged further down in the thread that it was wrong, I forgot to add an update here.

Cheers,

Darren :)