-
Notifications
You must be signed in to change notification settings - Fork 319
/
ch-1.pl
76 lines (64 loc) · 2.08 KB
/
ch-1.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
64
65
66
67
68
69
70
71
72
73
74
75
76
#!/usr/local/bin/perl
use strict;
use warnings;
use feature qw(say);
use Test::More;
use Benchmark qw(cmpthese timethis);
use Data::Dumper qw(Dumper);
my @TESTS = (
[ [4,5,1,6], 2, 2 ],
[ [1,2,3,4], 2, 2 ],
[ [1,3,4,5], 3, 2 ],
[ [5,1,2,3], 4, 2 ],
[ [7,2,4,5], 4, 1 ],
);
is( divisible_pairs_x($_->[0], $_->[1] ), $_->[2] ) for @TESTS;
is( divisible_pairs($_->[0], $_->[1] ), $_->[2] ) for @TESTS;
is( dp_nd( $_->[0], $_->[1] ), $_->[2] ) for @TESTS;
is( dp_other( $_->[1], @{$_->[0]} ), $_->[2] ) for @TESTS;
is( dp( [@{$_->[0]}],$_->[1] ), $_->[2] ) for @TESTS;
is( dp_index( $_->[0], $_->[1] ), $_->[2] ) for @TESTS;
done_testing();
cmpthese( 250_000, {
'd_pairs' => sub { divisible_pairs($_->[0], $_->[1] ) for @TESTS },
'd_pairx' => sub { divisible_pairs_x($_->[0], $_->[1] ) for @TESTS },
'dp_index'=> sub { dp_index( $_->[0], $_->[1] ) for @TESTS },
'dp_nd' => sub { dp_nd( $_->[0], $_->[1] ) for @TESTS },
'd_other' => sub { dp_other( $_->[1], @{$_->[0]} ) for @TESTS },
'dp' => sub { dp( [@{$_->[0]}], $_->[1] ) for @TESTS },
});
sub divisible_pairs {
my( $c, $k, @l ) = ( 0, $_[1], @{$_[0]} );
while(@l>1){
my $a = shift@l;
$c+=grep{ !(($a+$_)%$k) } @l;
}
$c
}
sub divisible_pairs_x {
my( $c, $k, @l ) = ( 0, $_[1], @{$_[0]} );
while(@l>1){
$a = shift@l;
($a+$_)%$k || $c++ for @l;
}
$c
}
sub dp {
0 + map { $a = pop @{$_[0]}; grep { !(($a+$_)% $_[1]) } @{$_[0]} } 1..@{$_[0]}
}
sub dp_nd {
my @T=@{$_[0]};
0 + map { $a = pop @T; grep { !(($a+$_)%$_[1]) } @T} 1..@T
}
## dp_other - flips around k and the list - so we can pass the list
## in as a list rather than a reference - because this is a list
## rather than a reference it is non-destructive without explicitly
## converting it to an array within function (like dp_nd)
sub dp_other { $b=shift; 0+map{$a=pop;grep{!(($a+$_)%$b)}@_}1..@_ }
sub dp_index {
my( $t,$list,$k ) = (0,@_);
for my $i (0..$#$list-1) {
($list->[$i]+$list->[$_]) % $k || $t++ for $i+1..$#$list;
}
$t;
}