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

Yay, tilly seems to have a correct (and prettier than mine) solution! I knew there was a way to make the basic algorithm neater. For those of you doing the pairs method, can you come up with a solution with a best score of 65 for the following 100 numbers? 
16 16 9 5 12 14 18 10 12 20 20 10 10 20 11 18 5 7 19 11 2 6 15 5 20 5 
+6 18 2 6 20 4 4 18 8 12 7 14 10 10 9 12 12 8 7 11 19 3 12 12 2 20 13 
+18 15 12 2 8 3 19 20 20 1 15 14 19 17 13 9 15 20 13 5 3 19 2 8 14 15 
+7 11 11 7 11 9 3 2 7 14 12 20 20 1 17 5 5 11 4 15 15

[download]
My order is:

shift 16, shift 16, shift 9, pop 15, pop 15, pop 4, shift 5, shift 12, pop 11, pop 5, shift 14, shift 18, shift 10, shift 12, shift 20, shift 20, shift 10, shift 10, shift 20, shift 11, shift 18, shift 5, shift 7, shift 19, shift 11, shift 2, pop 5, pop 17, pop 1, pop 20, pop 20, pop 12, pop 14, pop 7, pop 2, pop 3, pop 9, pop 11, pop 7, pop 11, pop 11, pop 7, pop 15, pop 14, pop 8, pop 2, pop 19, pop 3, shift 6, shift 15, shift 5, shift 20, shift 5, shift 6, shift 18, shift 2, shift 6, shift 20, shift 4, shift 4, shift 18, shift 8, shift 12, shift 7, shift 14, shift 10, shift 10, shift 9, shift 12, shift 12, shift 8, shift 7, shift 11, shift 19, shift 3, shift 12, shift 12, shift 2, shift 20, shift 13, shift 18, shift 15, shift 12, shift 2, shift 8, shift 3, shift 19, shift 20, shift 20, shift 1, shift 15, shift 14, shift 19, shift 17, shift 13, shift 9, shift 15, shift 20, shift 13, ? 5

tilly's order is:

pop 15, pop 15, shift 16, pop 4, shift 16, pop 11, shift 9, pop 5, shift 5, pop 5, pop 17, shift 12, pop 1, shift 14, shift 18, shift 10, shift 12, pop 20, pop 20, pop 12, pop 14, pop 7, pop 2, pop 3, pop 9, pop 11, pop 7, pop 11, pop 11, pop 7, pop 15, pop 14, pop 8, shift 20, pop 2, shift 20, pop 19, shift 10, pop 3, pop 5, pop 13, shift 10, pop 20, shift 20, pop 15, pop 9, pop 13, shift 11, shift 18, shift 5, shift 7, pop 17, pop 19, shift 19, shift 11, shift 2, shift 6, pop 14, pop 15, pop 1, pop 20, shift 15, shift 5, pop 20, shift 20, pop 19, shift 5, pop 3, pop 8, pop 2, pop 12, shift 6, shift 18, shift 2, shift 6, pop 15, shift 20, pop 18, shift 4, shift 4, shift 18, shift 8, shift 12, shift 7, pop 13, pop 20, pop 2, shift 14, shift 10, shift 10, shift 9, pop 12, pop 12, pop 3, pop 19, pop 11, pop 7, pop 8, pop 12, shift 12

I'm still trying to figure out why our solutions are different, while still arriving at the same solution.

  • Comment on Re: Puzzle: Given an array of integers, find the best sequence of pop / shift...
  • Download Code

Replies are listed 'Best First'.
Re^2: Puzzle: Given an array of integers, find the best sequence of pop / shift...
by tilly (Archbishop) on Mar 20, 2006 at 19:11 UTC
    My solution was correct. But the printing of my solution was incorrect. Here is the corrected solution. 
    #! /usr/bin/perl -w
use strict;

my @numbers = @ARGV ? @ARGV : qw(2 8 4 5);

# Scores is a 2-dim array, $scores[$i][$j] is the best score
# that you can get given a string of $j numbers starting at
# $numbers[$i].
my @scores;
for (0..$#numbers) {
  $scores[$_][1] = $numbers[$_];
}

for my $j (2..@numbers) {
  for my $i (0..(@numbers - $j)) {
    my $a = $numbers[$i] - $scores[$i+1][$j-1];
    my $b = $numbers[$i+$j-1] - $scores[$i][$j-1];
    $scores[$i][$j] = ($a > $b) ? $a : $b;
  }
}

my $i = 0;
my $score = 0;
for my $j (reverse 1..$#numbers) {
#  print "@numbers[$i..($i+$j)]\n";
  if ($numbers[$i] - $scores[$i+1][$j] > $numbers[$i+$j] - $scores[$i]
+[$j]) {
    print "shift $numbers[$i]\n";
    $score = $numbers[$i] - $score;
    $i++;
  }
  else {
    print "pop $numbers[$i+$j]\n";
    $score = $numbers[$i+$j] - $score;
  }
}

print "shift $numbers[$i]\n\n";
$score = $numbers[$i] - $score;
$score *= -1;
print "Score: $score\n";
print "Best score: $scores[0][scalar @numbers]\n";

    [download]
[reply]
[d/l]

In Section Seekers of Perl Wisdom