-
Notifications
You must be signed in to change notification settings - Fork 320
/
ch-1.pl
executable file
·96 lines (67 loc) · 2.17 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#!/usr/bin/perl -s
use v5.16;
use Test2::V0;
use List::Util 'sum';
use experimental 'postderef';
use Benchmark 'cmpthese';
our ($tests, $examples, $benchmark, $single);
run_tests() if $tests || $examples || $benchmark; # does not return
die <<EOS unless @ARGV;
usage: $0 [-examples] [-tests] [-benchmark] [-single] [--] [N...]
-examples
run the examples from the challenge
-tests
run some tests
-benchmark
benchmark different branches
-single
assume one single missing value as suggested by the examples
N...
list of unique numbers
EOS
### Input and Output
say for find_missing($single, @ARGV);
### Implementation
# If the given unique numbers were in the range 0 .. N, then exactly one
# number would be missing and this could easily be found as the
# difference between the sum over all numbers up to N and the sum over
# the given numbers. The examples conform to this pattern but it is not
# stated explicitly. Therefore the more efficient implementation must be
# chosen with a 'true' first argument.
sub find_missing {
# The easy way:
return @_ * (@_ + 1) / 2 - sum @_ if shift;
# The hard way:
(\my %num)->@{0 .. @_} = ();
delete @num{@_};
sort {$a <=> $b} keys %num;
}
### Examples and tests
sub run_tests {
SKIP: {
skip "examples" unless $examples;
is [find_missing(-single, 0, 1, 3)], [2], 'example 1, single';
is [find_missing(undef, 0, 1, 3)], [2], 'example 1, multi';
is [find_missing(-single, 0, 1)], [2], 'example 2, single';
is [find_missing(undef, 0, 1)], [2], 'example 2, multi';
}
SKIP: {
skip "tests" unless $tests;
is [find_missing(undef, 4, 7, -1)], [0 .. 3], 'nothing in list';
}
SKIP: {
skip "benchmark" unless $benchmark;
is [find_missing(-single, 1 .. 1000000)], [0], 'sum';
is [find_missing(undef, 1 .. 1000000)], [0], 'hash';
cmpthese(0, {
sum => sub {find_missing(-single, 1 .. 1000000)},
hash => sub {find_missing(undef, 1 .. 1000000)},
});
}
done_testing;
exit;
}
__DATA__
Rate hash sum
hash 1.47/s -- -97%
sum 48.2/s 3187% --