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

It seems to me that the best strategy is to always take the element that is best in relation to its neighbor. So if you have a list a b ... c d, you shift if a-b > d-c, and pop if the reverse is true. If the differences are equal, then you should probably resort to lookahead, but it's not clear to me what lookahead strategy should be.

Update: Tilly shot a hole in that strategy, so I'll try again here rather than proliferating response nodes. If the number of nodes is fewer than 6, the above strategy should hold. For > 6, a b c ... d e f, calculate the differences a-b, b-c, e-d, and f-e. Call the "current score" of the field a-b + f-e. Depending on whether you shift or pop, the "new score" would be a-b + e-d or b-c + f-e. Choose whichever makes the bigger negative difference (changing the game the most to your opponent's disadvantage).

Update 2: But it still doesn't get the best result for the example data. :-(

Caution: Contents may have been coded under pressure.

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 22:34 UTC
    I believe that no strategy of that type can possibly work. Here's an example where a number 10 in changes whether it is better to pop or shift first: 
    0.631752274168395
0.502325774658843
0.0553136679912676
0.696650395168113
0.904058789590099
0.83366887317402
0.676563261504992
0.620510190454731
0.835401306610937
0.331025798953092
100
0.460845097973213
0.0150072228842113
0.0863915966693014
0.252652201491809
0.0344964741543734
0.277799160386071
0.358041640281542
0.984148718850204
0.846530682637557

    [download]
    (With the 100 there, you should shift, remove it and you should pop.)

    Here is the program that I wrote to find that strategy: 

    #! /usr/bin/perl -w
use strict;
my $n = shift || 4;
my $tries = shift || 4**$n;

for (1..$tries) {
  my @num = map rand, 1..$n, 1..$n;
  $num[$n] = 0;
  my $iter = get_move_iter(@num);
  my ($move) = $iter->();
  $num[$n] = 100;
  $iter = get_move_iter(@num);
  my ($move2) = $iter->();
  if ($move eq $move2) {
    print "Try $_ was same\n";
  }
  else {
    print "Got $move vs $move2:\n@num\n";
    last;
  }
}

# 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].
sub get_scores {
  my @numbers = @_;
  my @scores;
  for (0..$#numbers) {
    $scores[$_] = [0, $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;
    }
  }
  return @scores;
}

sub get_move_iter {
  my @n = @_;
  my @scores = get_scores(@n);
  my $i = 0;
  my $j = $#n;
  return sub {
    if ($j < 0) {
      return;
    }
    elsif ($n[$i] - $scores[$i+1][$j] > $n[$i+$j] - $scores[$i][$j]) {
      $j--;
      return "shift", $n[$i++];
    }
    else {
      return "pop", $n[$i + $j--];
    }
  };
}

    [download]
[reply]
[d/l]
[select]
Re^2: Puzzle: Given an array of integers, find the best sequence of pop / shift...
by tilly (Archbishop) on Mar 20, 2006 at 18:39 UTC
    Your strategy fails with 3 1 2 100 5 4. (a - b = 2 is greater than 4 - 5 = -1, but you want to pop first.)

    Update: The reason why you want to pop first is because then the game goes: 

    1: pop 4
2: shift 3
1: shift 1
2: pop 5
1: pop 100
2: shift 2
    and your score is 95. If you shift first then the game goes: 
    1: shift 3
2: pop 4
1: shift 3
2: shift 1
1: pop 5
2: pop 100
1: shift 2

    and your score is 90.
    

UPDATE 2: I had the scores right but the sequence of moves wrong.  Sorry.
[reply]

In Section Seekers of Perl Wisdom