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
77
78
|
#!/usr/bin/perl
use warnings;
use strict;
use experimental qw( signatures );
use Math::Combinatorics;
sub squareful(@ints) {
my %results;
my @r = wrap([$ints[0]], @ints[1 .. $#ints]);
@results{map "@$_", @r} = ();
return [map [split], keys %results]
}
sub wrap($done, @rest) {
return $done unless @rest;
my %results;
for my $i (0 .. $#rest) {
for my $edge (0, -1) {
my $sqrt = sqrt($rest[$i] + $done->[$edge]);
next unless int($sqrt) == $sqrt;
@results{ map "@$_",
wrap($edge ? [@$done, $rest[$i]] : [$rest[$i], @$done],
@rest[grep $_ != $i, 0 .. $#rest])
} = ();
}
}
return map [split], keys %results
}
sub squareful_bruteforce(@ints) {
my $permutator = 'Math::Combinatorics'->new(data => \@ints);
my %results;
PERMUTATION:
while (my @permutation = $permutator->next_permutation) {
for my $i (1 .. $#permutation) {
my $sqrt = sqrt($permutation[$i] + $permutation[ $i - 1 ]);
next PERMUTATION unless int($sqrt) == $sqrt;
}
undef $results{"@permutation"};
}
return [map [split], keys %results]
}
use Test2::V0;
plan 9;
for my $s (*squareful{CODE}, *squareful_bruteforce{CODE}) {
is $s->(1, 17, 8), bag { item $_ for [1, 8, 17], [17, 8, 1] }, 'Example 1';
is $s->(2, 2, 2), [[2, 2, 2]], 'Example 2';
is $s->(1, 2, 3, 4, 5), [], 'Empty';
is $s->(3, 6, 3, 6, 30, 19), bag { item $_ for [3, 6, 3, 6, 30, 19],
[19, 30, 6, 3, 6, 3],
[30, 19, 6, 3, 6, 3],
[3, 6, 3, 6, 19, 30],
[3, 6, 30, 19, 6, 3],
[3, 6, 19, 30, 6, 3];
end},
'Longer';
}
use Benchmark qw{ cmpthese };
my @l = (1, 3, 9, 0, 16, 9, 27, 22, 14, 11);
is squareful(@l), bag { item $_ for @{ squareful_bruteforce(@l) } }, 'same';
cmpthese(-60, {
bruteforce => sub { squareful_bruteforce(@l) },
optimised => sub { squareful(@l) },
});
__END__
s/iter bruteforce optimised
bruteforce 19.2 -- -100%
optimised 3.30e-02 58110% --
|
