| 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 #2: Recreate Binary Tree | ||||||||||||||||||||||
| 13 | |||||||||||||||||||||||
| 14 | You are given a Binary Tree. | ||||||||||||||||||||||
| 15 | |||||||||||||||||||||||
| 16 | Write a script to replace each node of the tree with the sum of all the remaining nodes. | ||||||||||||||||||||||
| 17 | |||||||||||||||||||||||
| 18 | =head1 NOTE | ||||||||||||||||||||||
| 19 | |||||||||||||||||||||||
| 20 | There is a L<blog post about this|http://functional-perl.org/docs/blog/perl-weekly-challenges-113.xhtml>. | ||||||||||||||||||||||
| 21 | |||||||||||||||||||||||
| 22 | =cut | ||||||||||||||||||||||
| 23 | |||||||||||||||||||||||
| 24 | 1 | ▶ | use strict; | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 25 | 1 | ▶ | use utf8; | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 26 | 1 | ▶ | use warnings; | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 27 | 1 | ▶ | use warnings FATAL => 'uninitialized'; | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 28 | 1 | ▶ | use experimental 'signatures'; | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 29 | |||||||||||||||||||||||
| 30 | 1 | my ($mydir, $myname); | |||||||||||||||||||||
| 31 | |||||||||||||||||||||||
| 32 | 1 | ▶ | BEGIN { | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=2 SCAR=7.2
| |||||||||||||||||||||||
| 33 | 1 | ▶ | $0 =~ /(.*?)([^\/]+)\z/s or die "?"; | ||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||
| 34 | 1 | ($mydir, $myname) = ($1, $2); | |||||||||||||||||||||
| 35 | } | ||||||||||||||||||||||
| 36 | 1 | ▶ | use lib "$mydir/../../lib"; | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 37 | |||||||||||||||||||||||
| 38 | 1 | ▶ | use FP::Docstring; | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 39 | 1 | ▶ | use Chj::TEST ":all"; | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 40 | 1 | ▶ | use FP::Equal; | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 41 | |||||||||||||||||||||||
| 42 | 1 | package PFLANZE::Node { | |||||||||||||||||||||
| 43 | 1 | ▶ | use FP::Predicates qw(is_string maybe instance_of); | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 44 | 1 | *is_maybe_Node = maybe instance_of("PFLANZE::Node"); | |||||||||||||||||||||
| 45 | |||||||||||||||||||||||
| 46 | 1 | ▶ | use FP::Struct [ | ||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 47 | 1 | [\&is_maybe_Node, "left"], | |||||||||||||||||||||
| 48 | [\&is_string, "value"], | ||||||||||||||||||||||
| 49 | [\&is_maybe_Node, "right"] | ||||||||||||||||||||||
| 50 | 1 | ] => ("FP::Struct::Show", "FP::Struct::Equal"); | |||||||||||||||||||||
| 51 | |||||||||||||||||||||||
| 52 | 28 | ▶ | sub map ($self, $fn) { | ||||||||||||||||||||
|
Subroutine
map: called CC=3 SCAR=11.0
| |||||||||||||||||||||||
| 53 | 28 | my $l = $self->left; | |||||||||||||||||||||
| 54 | 28 | my $r = $self->right; | |||||||||||||||||||||
| 55 | 28 | ▶ | my $l2 = defined($l) ? $l->map($fn) : undef; | ||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||
| 56 | 28 | ▶ | my $r2 = defined($r) ? $r->map($fn) : undef; | ||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||
| 57 | 28 | $fn->($l2, $self->value, $r2) | |||||||||||||||||||||
| 58 | } | ||||||||||||||||||||||
| 59 | |||||||||||||||||||||||
| 60 | 1 | _END_ | |||||||||||||||||||||
| 61 | } | ||||||||||||||||||||||
| 62 | 1 | PFLANZE::Node::constructors->import; | |||||||||||||||||||||
| 63 | |||||||||||||||||||||||
| 64 | 1 | my $in = Node(Node(Node(undef, 4, Node(undef, 7, undef)), 2, undef), | |||||||||||||||||||||
| 65 | 1, Node(Node(undef, 5, undef), 3, Node(undef, 6, undef))); | ||||||||||||||||||||||
| 66 | |||||||||||||||||||||||
| 67 | 1 | ▶ | TEST { equal $in, $in->map(\&Node) } 1; | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 68 | |||||||||||||||||||||||
| 69 | 2 | ▶ | sub tree_sum($t) { | ||||||||||||||||||||
|
Subroutine
tree_sum: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 70 | $t->map( | ||||||||||||||||||||||
| 71 | 14 | ▶ | sub ($l, $value, $r) { | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=3 SCAR=11.0
| |||||||||||||||||||||||
| 72 | 14 | ▶ | $value + ($l // 0) + ($r // 0) | ||||||||||||||||||||
|
Condition100%4/4
$l // 0
$r // 0
MC/DC100%1/1
$l // 0
$l
MC/DC100%1/1
$r // 0
$r
Truth table100%2/2
A
A= $l
Truth table100%2/2
A
A= $r
| |||||||||||||||||||||||
| 73 | } | ||||||||||||||||||||||
| 74 | ) | ||||||||||||||||||||||
| 75 | 2 | } | |||||||||||||||||||||
| 76 | |||||||||||||||||||||||
| 77 | 1 | ▶ | TEST { tree_sum $in } 28; | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 78 | |||||||||||||||||||||||
| 79 | 1 | ▶ | sub tree_recreate($t) { | ||||||||||||||||||||
|
Subroutine
tree_recreate: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 80 | 1 | my $sum = tree_sum($t); | |||||||||||||||||||||
| 81 | $t->map( | ||||||||||||||||||||||
| 82 | 7 | ▶ | sub ($l, $value, $r) { | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 83 | 7 | Node($l, $sum - $value, $r) | |||||||||||||||||||||
| 84 | } | ||||||||||||||||||||||
| 85 | ) | ||||||||||||||||||||||
| 86 | 1 | } | |||||||||||||||||||||
| 87 | |||||||||||||||||||||||
| 88 | 1 | ▶ | TEST { tree_recreate $in } | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 89 | 1 | Node(Node(Node(undef, 24, Node(undef, 21, undef)), 26, undef), | |||||||||||||||||||||
| 90 | 27, Node(Node(undef, 23, undef), 25, Node(undef, 22, undef))); | ||||||||||||||||||||||
| 91 | |||||||||||||||||||||||
| 92 | # ---------------------------------------------------------------------- | ||||||||||||||||||||||
| 93 | |||||||||||||||||||||||
| 94 | 0 | ▶ | sub help { | ||||||||||||||||||||
|
Subroutine
help: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||
| 95 | 0 | print "Usage: $0 --repl | --test\n"; | |||||||||||||||||||||
| 96 | 0 | exit 1 | |||||||||||||||||||||
| 97 | } | ||||||||||||||||||||||
| 98 | |||||||||||||||||||||||
| 99 | &{ | ||||||||||||||||||||||
| 100 | 1 | @ARGV | |||||||||||||||||||||
| 101 | ? { | ||||||||||||||||||||||
| 102 | 0 | ▶ | "--repl" => sub { | ||||||||||||||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||||||||||||||
| 103 | 0 | require FP::Repl::Trap; | |||||||||||||||||||||
| 104 | 0 | FP::Repl::repl(); | |||||||||||||||||||||
| 105 | }, | ||||||||||||||||||||||
| 106 | 1 | ▶ | "--test" => sub { | ||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||
| 107 | 1 | run_tests __PACKAGE__; | |||||||||||||||||||||
| 108 | } | ||||||||||||||||||||||
| 109 | 1 | ▶ | }->{ $ARGV[0] } // \&help | ||||||||||||||||||||
|
Branch: 1 branch
Condition50%1/2
{"--repl", sub {
require FP::Repl::Trap;
FP::Repl::repl();
}
, "--test", sub {
run_tests(__PACKAGE__);
}
}->{$ARGV[0]} // \&main::help
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]}
| |||||||||||||||||||||||
| 110 | : \&help | ||||||||||||||||||||||
| 111 | }; | ||||||||||||||||||||||
| 112 | |||||||||||||||||||||||