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 #### #! /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--]; } }; }