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

First of all, you have to give the sequence of moves. You can't just say how many of each and then give a total - that would be far too easy. Secondly, it is not nearly as simple a problem as it appears. Take, for instance, the following:

4 10 3 1

The 4 is largest, so you take it, right? But wait! This leaves the enemy with the ability to take 10. We can't have that. So we instead take 1, thus forcing the enemy to take 4 or 3 (they pick 4), leaving us with the 10 and them with the 3. Our total score is now 4, vs the -4 we would have had if we'd picked the 4 at the beginning.

My point is that making any choice involves knowing what the best scores are for the two branches, each of which needs to know what the best scores are for the two branches further down, etc. etc. You can do this with recursion (2^n), but it's inefficient since you end up doing a lot of the calculations multiple times, so the best approach is bottom up, starting with all the pairs, then moving to triples, quadruples, etc. until you have only one set. This is (n^2)/2, which is much better.

For instance:

4 10 3 1
R6 L7 L2
L3 L-8 (enemy subtracts and picks smallest)
R4

So the best choices are pop (1), shift (4), shift (10), ? (3).

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

Replies are listed 'Best First'.
Re^2: Puzzle: Given an array of integers, find the best sequence of pop / shift...
by ayrnieu (Beadle) on Mar 20, 2006 at 05:35 UTC

    but it's inefficient since you end up doing a lot of the calculations multiple times,

    use Memoize;
[reply]
[d/l]
      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;
  }
}

      [download]
      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]

In Section Seekers of Perl Wisdom