examples/perl-weekly-challenges/113-1-represent_integer

filter: Statementstmt 86.0% 129 / 150 Branchbran 57.8% 22 / 38 Conditioncond 44.4% 4 / 9 MC/DCmcdc 0.0% 0 / 3 Subroutinesub 89.3% 42 / 47 Podpod n/a totaltotal 79.7% 197 / 247 CC 21 SCAR 15.0
CC
21
Cov
79%
__ANON__
30.0
maybe_representable
7.1
__ANON__
5.1
CRAP 4.5
« lib/Chj/xIO.pm ↑ Summary lib/FP/Hash.pm »
1 #!/usr/bin/env perl
2  
3 1 my $copyright = <<'COPYRIGHT';
4 # Copyright (c) 2021 by Christian Jaeger <copying@christianjaeger.ch>
5 # This is free software. See the file COPYING.md that came bundled
6 # with this file.
7 COPYRIGHT
8  
9 =pod
10  
11 L<The Weekly Challenge - 113|https://perlweeklychallenge.org/blog/perl-weekly-challenge-113/>,
12 TASK #1: Represent Integer
13  
14 You are given a positive integer $N and a digit $D.
15  
16 Write a script to check if $N can be represented as a sum of positive
17 integers [all] having $D at least once [in their decimal
18 representation]. If check passes print 1 otherwise 0.
19  
20 =head1 NOTE
21  
22 There is a Haskell version of this script in the file
23 L<113-1-represent_integer_haskell.hs>.
24  
25 There is a L<blog post about this|http://functional-perl.org/docs/blog/perl-weekly-challenges-113.xhtml>.
26  
27 =cut
28  
29 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
30 1 ▶use utf8;
Subroutine BEGIN: called CC=1 SCAR=0.0
31 1 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
32 1 ▶use warnings FATAL => 'uninitialized';
Subroutine BEGIN: called CC=1 SCAR=0.0
33 1 ▶use experimental 'signatures';
Subroutine BEGIN: called CC=1 SCAR=0.0
34 1 ▶use feature 'current_sub'; # __SUB__
Subroutine BEGIN: called CC=1 SCAR=0.0
35  
36 1 my ($mydir, $myname);
37  
38 1 ▶BEGIN {
Subroutine BEGIN: called CC=2 SCAR=7.2
39 1 ▶ $0 =~ /(.*?)([^\/]+)\z/s or die "?";
Branch: 1 branch
BranchTrueFalseTotal
$0 =~ m[(.*?)([^/]+)\z]s or die "?" 1 0 1
40 1 ($mydir, $myname) = ($1, $2);
41 }
42 1 ▶use lib "$mydir/../../lib";
Subroutine BEGIN: called CC=1 SCAR=0.0
43  
44 1 ▶use FunctionalPerl v0.72.65;
Subroutine BEGIN: called CC=1 SCAR=0.0
45 1 ▶use FP::Docstring;
Subroutine BEGIN: called CC=1 SCAR=0.0
46 1 ▶use FP::Show;
Subroutine BEGIN: called CC=1 SCAR=0.0
47 1 ▶use FP::List;
Subroutine BEGIN: called CC=1 SCAR=0.0
48 1 ▶use FP::PureArray;
Subroutine BEGIN: called CC=1 SCAR=0.0
49 1 ▶use FP::Lazy;
Subroutine BEGIN: called CC=1 SCAR=0.0
50 1 ▶use FP::Either ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
51 1 ▶use FP::Predicates qw(is_defined);
Subroutine BEGIN: called CC=1 SCAR=0.0
52 1 ▶use Chj::TEST ":all";
Subroutine BEGIN: called CC=1 SCAR=0.0
53 1 ▶use Chj::time_this;
Subroutine BEGIN: called CC=1 SCAR=0.0
54  
55 1 our $verbose = $ENV{VERBOSE};
56  
57 2 ▶sub maybe_choose_brute ($N, $ns) {
Subroutine maybe_choose_brute: called CC=1 SCAR=0.0
58 2 __ 'Choose a combination of numbers from $ns (repetitions allowed)
59 that added together equal $N; undef if not possible. This
60 solution is brute force in that it is picking additional
61 numbers from the left end of $ns, one after another,
62 depth-first.';
63  
64 277 ▶ sub ($chosen) {
Subroutine __ANON__: called CC=4 SCAR=13.9
65 277 my $check = __SUB__;
66 277 ▶ warn "check (brute): " . show($chosen) if $verbose;
Branch: 1 branch
BranchTrueFalseTotal
if $main::verbose 0 277 277
67 277 my $sum = $chosen->sum;
68 277 ▶ if ($sum == $N) {
Branch: 2 branches
BranchTrueFalseTotal
if ($sum == $N) { } 2 275 277
elsif ($sum > $N) { } 224 51 275
69 2 $chosen
70 } elsif ($sum > $N) {
71 undef
72 224 } else {
73 $ns->any(
74 275 ▶ sub ($n) {
Subroutine __ANON__: called CC=1 SCAR=0.0
75 275 $check->(cons($n, $chosen))
76 }
77 )
78 51 }
79 }
80 2 ->(null)
81 }
82  
83 0 ▶sub maybe_choose_optim_1 ($N, $ns) {
Subroutine maybe_choose_optim_1: not called CC=1 SCAR=6.9
84 0 __ 'Choose a combination of numbers from $ns (repetitions allowed)
85 that added together equal $N; undef if not possible. This
86 solution uses a hashtable to check for each additional number;
87 i.e. it tries to minimize the number of numbers taken from
88 $ns (it is still searching depth-first).';
89 0 my %ns = map { $_ => 1 } $ns->values;
90  
91 0 ▶ sub ($chosen) {
Subroutine __ANON__: not called CC=5 SCAR=34.0
92 0 my $check = __SUB__;
93 0 ▶ warn "check (optim 1): " . show($chosen) if $verbose;
Branch: 1 branch
BranchTrueFalseTotal
if $main::verbose 0 0 0
94 0 my $sum = $chosen->sum;
95 0 my $missing = $N - $sum;
96 0 ▶ if (not $missing) {
Branch: 2 branches
BranchTrueFalseTotal
if (not $missing) { } 0 0 0
elsif ($missing < 0) { } 0 0 0
97 0 $chosen
98 } elsif ($missing < 0) {
99 undef
100 0 } else {
101 0 ▶ if (exists $ns{$missing}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $ns{$missing}) { } 0 0 0
102 0 cons $missing, $chosen
103 } else {
104 $ns->any(
105 0 ▶ sub ($n) {
Subroutine __ANON__: not called CC=1 SCAR=6.9
106 0 $check->(cons($n, $chosen))
107 }
108 )
109 0 }
110 }
111 }
112 0 ->(null)
113 }
114  
115 9 ▶sub maybe_choose_optim_2 ($N, $_ns) {
Subroutine maybe_choose_optim_2: called CC=1 SCAR=0.0
116 9 __ 'Choose a combination of numbers (repetitions allowed) from $ns
117 which must be sorted in decrementing order that added together
118 equal $N; undef if not possible. This solution does a
119 breadth-first search (and uses the hashtable check to see if
120 there will be a match with the next level like
121 maybe_choose_optim_1)';
122  
123 # We want to use lazy evaluation to allow for the descriptive
124 # solution below, thus turn the purearray to a lazy list:
125 9 my $ns = $_ns->stream;
126  
127 9 my %ns = map { $_ => 1 } $_ns->values;
128  
129 13 ▶ sub ($chosen) {
Subroutine __ANON__: called CC=3 SCAR=11.1
130 13 my $check = __SUB__;
131 13 ▶ warn "check (optim 2): " . show($chosen) if $verbose;
Branch: 1 branch
BranchTrueFalseTotal
if $main::verbose 0 13 13
132  
133 # Given an additional choice of a number $n (out of $ns) on
134 # top of $chosen, decide whether there's a solution either
135 # with the given numbers or when adding one more missing
136 # number by looking at %ns; or whether the chosen numbers are
137 # adding up to too much already (in which case undef is
138 # returned), or the search needs to resume via recursively
139 # calling $check. The latter case is not carried out
140 # immediately, but returned as a lazy term (a promise), to
141 # allow to delay diving deeper into the next recursion level
142 # to *after* checking all numbers in the current level
143 # (breadth-first search).
144  
145 # Using FP::Either's `Right` to indicate an immediate
146 # solution, `Left` to indicate a case that needs recursion
147 # (and only potentially yields a result), undef to signify a
148 # dead end.
149  
150 75 ▶ my $decide = sub ($n) {
Subroutine __ANON__: called CC=5 SCAR=16.3
151 75 ▶ warn "decide: checking $n on top of " . show($chosen) if $verbose;
Branch: 1 branch
BranchTrueFalseTotal
if $main::verbose 0 75 75
152 75 my $chosen = cons $n, $chosen;
153 75 my $missing = $N - ($chosen->sum);
154 75 ▶ if (not $missing) {
Branch: 2 branches
BranchTrueFalseTotal
if (not $missing) { } 0 75 75
elsif ($missing < 0) { } 4 71 75
155 0 Right $chosen
156 } elsif ($missing < 0) {
157 undef
158 4 } else {
159 71 ▶ if (exists $ns{$missing}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $ns{$missing}) { } 9 62 71
160 9 Right cons($missing, $chosen)
161 } else {
162 4 ▶ Left lazy {
Subroutine __ANON__: called CC=1 SCAR=0.0
163 4 $check->($chosen)
164 }
165 62 }
166 }
167 13 };
168  
169 # Since $ns are sorted in decrementing order, if $decide
170 # returns undef, any subsequent number will fail, too, so we
171 # can stop further checks; `take_while` will only take the
172 # results up to that point.
173  
174 # Since $ns is a stream (a lazily computed list), the
175 # following `map` and `take_while` steps are lazy, too;
176 # $decide will never be evaluated for $n's that are smaller
177 # (coming further along in the reverse-ordered $ns) than any
178 # $n that can lead to a solution.
179  
180 13 my $decisions = $ns->map($decide)->take_while(\&is_defined);
181  
182 # Check for immediate solutions (solutions on our level)
183 # first, if that fails, get and evaluate the promises to
184 # recurse (go deeper):
185  
186 13 my $solutions = rights $decisions;
187 13 my $recursions = lefts $decisions;
188 13 ▶ unless ($solutions->is_null) {
Branch: 1 branch
BranchTrueFalseTotal
if ($solutions->is_null) { } 5 8 13
189 8 $solutions->first
190 } else {
191 5 $recursions->any(\&force)
192 }
193 }
194 9 ->(null)
195 }
196  
197 # (But there may be smarter algorithms.)
198  
199 11 ▶sub valid_numbers ($N, $D) {
Subroutine valid_numbers: called CC=1 SCAR=0.0
200 11 purearray grep {/$D/} (1 .. $N)
201 }
202  
203 # You can explicitely choose the algorithm it via setting
204 # `MAYBE_CHOOSE` env var to its name, or by passing its reference as
205 # the 4th argument to maybe_representable.
206 1 my $MAYBE_CHOOSE = do {
207 1 ▶ if (my $str = $ENV{MAYBE_CHOOSE}) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $str = $ENV{'MAYBE_CHOOSE'}) { } 0 1 1
208 +{
209 maybe_choose_brute => \&maybe_choose_brute,
210 maybe_choose_optim_1 => \&maybe_choose_optim_1,
211 maybe_choose_optim_2 => \&maybe_choose_optim_2
212 0 ▶ }->{$str}
Condition0%0/2
{'maybe_choose_brute', \&main::maybe_choose_brute, 'maybe_choose_optim_1', \&main::maybe_choose_optim_1, 'maybe_choose_optim_2', \&main::maybe_choose_optim_2}->{$str} || die('invalid MAYBE_CHOOSE value')
l!l
00
MC/DC0%0/1
{'maybe_choose_brute', \&main::maybe_choose_brute, 'maybe_choose_optim_1', \&main::maybe_choose_optim_1, 'maybe_choose_optim_2', \&main::maybe_choose_optim_2}->{$str} || die('invalid MAYBE_CHOOSE value')
{'maybe_choose_brute', \&main::maybe_choose_brute, 'maybe_choose_optim_1', \&main::maybe_choose_optim_1, 'maybe_choose_optim_2', \&main::maybe_choose_optim_2}->{$str}
Truth table0%0/2
A
A= {'maybe_choose_brute', \&main::maybe_choose_brute, 'maybe_choose_optim_1', \&main::maybe_choose_optim_1, 'maybe_choose_optim_2', \&main::maybe_choose_optim_2}->{$str}
Aresult
11
00
213 or die "invalid MAYBE_CHOOSE value"
214 } else {
215 undef
216 1 }
217 };
218  
219 11 ▶sub maybe_representable ($N, $D, $prefer_large = 1,
Subroutine maybe_representable: called CC=7 SCAR=19.6
220 11 $maybe_choose = $MAYBE_CHOOSE)
221 {
222 11 __ 'Returns the numbers containing $D that sum up to $N, or undef.
223 If $prefer_large is true, tries to use large numbers,
224 otherwise small (which is (much) less efficient).';
225 11 my $ns = valid_numbers($N, $D);
226 $maybe_choose
227 //= ($prefer_large and not $ENV{NO_OPTIM})
228 11 ▶ ? \&maybe_choose_optim_2
Branch: 1 branch
BranchTrueFalseTotal
$prefer_large && !$ENV{'NO_OPTIM'} ? : 9 2 11
Condition60%3/5
$maybe_choose //= $prefer_large && !$ENV{"NO_OPTIM"} ? \&main::maybe_choose_optim_2 : \&main::maybe_choose_brute
l!l
011
$prefer_large and not $ENV{"NO_OPTIM"}
!ll&&!rl&&r
209
MC/DC0%0/1
$maybe_choose //= $prefer_large && !$ENV{"NO_OPTIM"} ? \&main::maybe_choose_optim_2 : \&main::maybe_choose_brute
$maybe_choose
Truth table50%1/2
A
A= $maybe_choose
Aresult
11
00
229 : \&maybe_choose_brute;
230 11 ▶ $maybe_choose->($N, $prefer_large ? $ns->reverse : $ns)
Branch: 1 branch
BranchTrueFalseTotal
$prefer_large ? : 9 2 11
231 }
232  
233 1 ▶TEST { maybe_representable 25, 7 } undef;
Subroutine __ANON__: called CC=1 SCAR=0.0
234 1 ▶TEST { maybe_representable 24, 7 } list(7, 17);
Subroutine __ANON__: called CC=1 SCAR=0.0
235  
236 1 ▶TEST { maybe_representable 200, 9 } list(9, 191);
Subroutine __ANON__: called CC=1 SCAR=0.0
237 1 ▶TEST { maybe_representable 200, 9, 0 }
Subroutine __ANON__: called CC=1 SCAR=0.0
238 1 list(29, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9);
239  
240 # The comments to the right in the following show the results that
241 # maybe_choose_optim_1 gave:
242  
243 1 ▶TEST { maybe_representable 200, 8 } list(18, 182); # list(8, 8, 184);
Subroutine __ANON__: called CC=1 SCAR=0.0
244 1 ▶TEST { maybe_representable 200, 8, 0 }
Subroutine __ANON__: called CC=1 SCAR=0.0
245 1 list(8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8);
246  
247 1 ▶TEST { maybe_representable 200, 7 } list(27, 173); # list(7, 7, 7, 179);
Subroutine __ANON__: called CC=1 SCAR=0.0
248  
249 1 ▶TEST { maybe_representable 200, 6 } list(36, 164); # list(6, 6, 6, 6, 176);
Subroutine __ANON__: called CC=1 SCAR=0.0
250  
251 1 ▶unless ($ENV{NO_EXPENSIVE_TESTS}) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($ENV{"NO_EXPENSIVE_TESTS"}) 1 0 1
252 1 ▶ TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
253 1 ▶ time_this { maybe_representable 20000, 8 }
Subroutine __ANON__: called CC=1 SCAR=0.0
254 1 }
255 1 list(18, 19982); # list(8, 8, 19984);
256 1 ▶ TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
257 1 ▶ time_this { maybe_representable 40000, 8 }
Subroutine __ANON__: called CC=1 SCAR=0.0
258 1 }
259 1 list(18, 39982); # list(8, 8, 39984);
260 1 ▶ TEST {
Subroutine __ANON__: called CC=1 SCAR=0.0
261 1 ▶ time_this { maybe_representable 40000, 6 }
Subroutine __ANON__: called CC=1 SCAR=0.0
262 1 }
263 1 list(36, 39964); # list(6, 6, 6, 6, 39976);
264 }
265  
266 # ----------------------------------------------------------------------
267  
268 0 ▶sub help {
Subroutine help: not called CC=1 SCAR=6.9
269 0 print "Usage: $0 --repl | --test\n";
270 0 exit 1
271 }
272  
273 &{
274 1 @ARGV
275 ? {
276 0 ▶ "--repl" => sub {
Subroutine __ANON__: not called CC=1 SCAR=6.9
277 0 require FP::Repl::Trap;
278 0 FP::Repl::repl();
279 },
280 1 ▶ "--test" => sub {
Subroutine __ANON__: called CC=1 SCAR=0.0
281 1 run_tests __PACKAGE__;
282 }
283 1 ▶ }->{ $ARGV[0] } // \&help
Branch: 1 branch
BranchTrueFalseTotal
@ARGV ? : 1 0 1
Condition50%1/2
{"--repl", sub { require FP::Repl::Trap; FP::Repl::repl(); } , "--test", sub { run_tests(__PACKAGE__); } }->{$ARGV[0]} // \&main::help
l!l
10
MC/DC0%0/1
{"--repl", sub { require FP::Repl::Trap; FP::Repl::repl(); } , "--test", sub { run_tests(__PACKAGE__); } }->{$ARGV[0]} // \&main::help
{"--repl", sub { require FP::Repl::Trap; FP::Repl::repl(); } , "--test", sub { run_tests(__PACKAGE__); } }->{$ARGV[0]}
Truth table50%1/2
A
A= {"--repl", sub { require FP::Repl::Trap; FP::Repl::repl(); } , "--test", sub { run_tests(__PACKAGE__); } }->{$ARGV[0]}
Aresult
11
00
284 : \&help
285 };
286  
« lib/Chj/xIO.pm ↑ Summary lib/FP/Hash.pm »