pop 5
shift 2
shift 8
? 4

Best score: 7
[download]

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:

shift 16
pop 13
pop 7
pop 13
pop 9
pop 11
pop 10
pop 11
pop 19
pop 19
pop 20
pop 14
pop 15
pop 8
pop 5
pop 17
pop 9
shift 2
shift 10
? 2

Best score: 10
[download]

With the following code:

use strict;
use warnings;

my (@n, @s, $n, $i, $flip, $l, $total);

#for (1..1000) {
#    push @n, (int rand 20) + 1;
#}

@n = split / /, '16 2 10 2 9 17 5 8 15 14 20 19 19 11 10 11 9 13 7 13'
+;
print "@n\n\n";

for (0..($#n-1)) {
    if ($n[$_] > $n[$_+1]) {
        push @{$s[0]}, ['L', $n[$_] - $n[$_+1]];
    }
    else {
        push @{$s[0]}, ['R', $n[$_+1] - $n[$_]];
    }
}
for ($i = 0; $i < ($#n-1); $i++) {
    for (0..($#n-($i+2))) {
        if ($s[$i][$_][1] - $n[$_+($i+2)] < $s[$i][$_+1][1] - $n[$_]) 
+{
            push @{$s[($i+1)]}, ['R', $s[$i][$_][1] - $n[$_+($i+2)]];
        }
        else {
            push @{$s[($i+1)]}, ['L', $s[$i][$_+1][1] - $n[$_]];
        }
    }
    $i++;
    for (0..($#n-($i+2))) {
        if ($s[$i][$_][1] + $n[$_+($i+2)] > $s[$i][$_+1][1] + $n[$_]) 
+{
            push @{$s[($i+1)]}, ['R', $s[$i][$_][1] + $n[$_+($i+2)]];
        }
        else {
           push @{$s[($i+1)]}, ['L', $s[$i][$_+1][1] + $n[$_]];
        }
    }
}

$flip = 1;
$l = 0;
for (reverse 0..($#n-1)) {
    if ($s[$_][$l][0] eq 'L') {
        print "shift ";
        $n = shift @n;
        $l++;
    }
    else {
        print "pop ";
        $n = pop @n;
    }
    print "$n\n";
    $total += $n * $flip;
    $flip *= -1;
}
$n = pop @n;
$total += $n * $flip;
print "? $n\n\n";

print "Best score: $total\n";
[download]

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.