/
ch-2.pl
executable file
·63 lines (52 loc) · 1.81 KB
/
ch-2.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#!/usr/bin/perl
use warnings;
use strict;
use experimental qw( signatures );
sub maximise_greatness(@nums) {
my @sorted = sort { $a <=> $b } @nums;
# No greatness at all.
return 0 if $sorted[0] == $sorted[-1];
my $count = 0;
my $less = 0;
my $greater = 1;
while (1) {
++$greater while $greater <= $#sorted
&& $sorted[$greater] == $sorted[$less];
last if $greater > $#sorted;
++$count if $sorted[$less++] < $sorted[$greater++];
last if $greater > $#sorted;
}
return $count
}
use Algorithm::Combinatorics qw{ permutations };
sub maximise_greatness_brute_force(@nums) {
my $iter = permutations(\@nums);
my $max_count = 0;
while (my $p = $iter->next) {
my $count = grep $nums[$_] < $p->[$_], 0 .. $#nums;
$max_count = $count if $count > $max_count;
}
return $max_count
}
use Test::More tests => 2 * (2 + 4) + 1;
for my $maximise_greatness (
\&maximise_greatness, \&maximise_greatness_brute_force
) {
is $maximise_greatness->(1, 3, 5, 2, 1, 3, 1), 4, 'Example 1';
is $maximise_greatness->(1, 2, 3, 4), 3, 'Example 2';
is $maximise_greatness->(1, 1, 1), 0, 'Not great';
is $maximise_greatness->(1, 1, 2, 2, 2), 2, 'More of the greater ones';
is $maximise_greatness->(1, 1, 1, 2, 2), 2, 'More of the less ones';
is $maximise_greatness->(1, 2, 2, 2, 3), 2, 'More of the middle ones';
}
use Benchmark qw{ cmpthese };
my @l = map int rand 7, 1 .. 8;
is maximise_greatness(@l), maximise_greatness_brute_force(@l), "same @l";
cmpthese(-3, {
brute_force => sub { maximise_greatness_brute_force(@l) },
optimised => sub { maximise_greatness(@l) },
});
__END__
Rate brute_force optimised
brute_force 8.74/s -- -100%
optimised 210776/s 2412117% --