From 194e0de26203c1460061faa3c50b12a884d296cf Mon Sep 17 00:00:00 2001 From: arnesom Date: Sat, 22 May 2021 23:09:14 +0200 Subject: Arne Sommer --- challenge-113/arne-sommer/blog.txt | 1 + challenge-113/arne-sommer/misc/tree1.dot | 16 +++ challenge-113/arne-sommer/misc/tree1.svg | 119 +++++++++++++++++++++ challenge-113/arne-sommer/misc/tree2.dot | 16 +++ challenge-113/arne-sommer/misc/tree2.svg | 109 +++++++++++++++++++ challenge-113/arne-sommer/misc/tree3.dot | 16 +++ challenge-113/arne-sommer/misc/tree3.svg | 119 +++++++++++++++++++++ challenge-113/arne-sommer/perl/ch-1.pl | 37 +++++++ challenge-113/arne-sommer/perl/ch-2.pl | 29 +++++ .../arne-sommer/perl/recreate-binary-tree-perl | 29 +++++ .../arne-sommer/perl/represent-integer-perl | 37 +++++++ challenge-113/arne-sommer/raku/ch-1.raku | 19 ++++ challenge-113/arne-sommer/raku/ch-2.raku | 98 +++++++++++++++++ .../arne-sommer/raku/recreate-binary-tree | 18 ++++ .../arne-sommer/raku/recreate-binary-tree-truly | 87 +++++++++++++++ .../arne-sommer/raku/recreate-binary-tree-truly2 | 98 +++++++++++++++++ challenge-113/arne-sommer/raku/represent-integer | 19 ++++ 17 files changed, 867 insertions(+) create mode 100644 challenge-113/arne-sommer/blog.txt create mode 100644 challenge-113/arne-sommer/misc/tree1.dot create mode 100644 challenge-113/arne-sommer/misc/tree1.svg create mode 100644 challenge-113/arne-sommer/misc/tree2.dot create mode 100644 challenge-113/arne-sommer/misc/tree2.svg create mode 100644 challenge-113/arne-sommer/misc/tree3.dot create mode 100644 challenge-113/arne-sommer/misc/tree3.svg create mode 100755 challenge-113/arne-sommer/perl/ch-1.pl create mode 100755 challenge-113/arne-sommer/perl/ch-2.pl create mode 100755 challenge-113/arne-sommer/perl/recreate-binary-tree-perl create mode 100755 challenge-113/arne-sommer/perl/represent-integer-perl create mode 100755 challenge-113/arne-sommer/raku/ch-1.raku create mode 100755 challenge-113/arne-sommer/raku/ch-2.raku create mode 100755 challenge-113/arne-sommer/raku/recreate-binary-tree create mode 100755 challenge-113/arne-sommer/raku/recreate-binary-tree-truly create mode 100755 challenge-113/arne-sommer/raku/recreate-binary-tree-truly2 create mode 100755 challenge-113/arne-sommer/raku/represent-integer diff --git a/challenge-113/arne-sommer/blog.txt b/challenge-113/arne-sommer/blog.txt new file mode 100644 index 0000000000..a116d654dc --- /dev/null +++ b/challenge-113/arne-sommer/blog.txt @@ -0,0 +1 @@ +https://raku-musings.com/re-re.html diff --git a/challenge-113/arne-sommer/misc/tree1.dot b/challenge-113/arne-sommer/misc/tree1.dot new file mode 100644 index 0000000000..24fbd39802 --- /dev/null +++ b/challenge-113/arne-sommer/misc/tree1.dot @@ -0,0 +1,16 @@ +digraph foogrph { + node [shape = record,height=.1]; + node27[label = " |
27| "]; + "node27":left -> "node26":center; + node26[label = " |
26| "]; + "node26":left -> "node24":center; + node24[label = " |
24| "]; + "node24":right -> "node21":center; + node21[label = " |
21| "]; + "node27":right -> "node25":center; + node25[label = " |
25| "]; + "node25":left -> "node23":center; + node23[label = " |
23| "]; + "node25":right -> "node22":center; + node22[label = " |
22| "]; +} diff --git a/challenge-113/arne-sommer/misc/tree1.svg b/challenge-113/arne-sommer/misc/tree1.svg new file mode 100644 index 0000000000..f0099653c7 --- /dev/null +++ b/challenge-113/arne-sommer/misc/tree1.svg @@ -0,0 +1,119 @@ + + + + + + +foogrph + + + +node27 + + + +27 + + + + + +node26 + + + +26 + + + + + +node27:left->node26:center + + + + + +node25 + + + +25 + + + + + +node27:right->node25:center + + + + + +node24 + + + +24 + + + + + +node26:left->node24:center + + + + + +node21 + + + +21 + + + + + +node24:right->node21:center + + + + + +node23 + + + +23 + + + + + +node25:left->node23:center + + + + + +node22 + + + +22 + + + + + +node25:right->node22:center + + + + + diff --git a/challenge-113/arne-sommer/misc/tree2.dot b/challenge-113/arne-sommer/misc/tree2.dot new file mode 100644 index 0000000000..adcd85cdbf --- /dev/null +++ b/challenge-113/arne-sommer/misc/tree2.dot @@ -0,0 +1,16 @@ +digraph foogrph { + node [shape = record,height=.1]; + node21[label = " |
21| "]; + "node21":left -> "node20":center; + node20[label = " |
20| "]; + "node20":left -> "node18":center; + node18[label = " |
18| "]; + "node18":right -> "node21":center; + node21[label = " |
21| "]; + "node21":right -> "node19":center; + node19[label = " |
19| "]; + "node19":left -> "node17":center; + node17[label = " |
17| "]; + "node19":right -> "node16":center; + node16[label = " |
16| "]; +} diff --git a/challenge-113/arne-sommer/misc/tree2.svg b/challenge-113/arne-sommer/misc/tree2.svg new file mode 100644 index 0000000000..a52f38f373 --- /dev/null +++ b/challenge-113/arne-sommer/misc/tree2.svg @@ -0,0 +1,109 @@ + + + + + + +foogrph + + + +node21 + + + +21 + + + + + +node20 + + + +20 + + + + + +node21:left->node20:center + + + + + +node19 + + + +19 + + + + + +node21:right->node19:center + + + + + +node18 + + + +18 + + + + + +node20:left->node18:center + + + + + +node18:right->node21:center + + + + + +node17 + + + +17 + + + + + +node19:left->node17:center + + + + + +node16 + + + +16 + + + + + +node19:right->node16:center + + + + + diff --git a/challenge-113/arne-sommer/misc/tree3.dot b/challenge-113/arne-sommer/misc/tree3.dot new file mode 100644 index 0000000000..acd1c7376d --- /dev/null +++ b/challenge-113/arne-sommer/misc/tree3.dot @@ -0,0 +1,16 @@ +digraph foogrph { + node [shape = record,height=.1]; + node94557370778344[label = " |
21| "]; + "node94557370778344":left -> "node94557370778232":center; + node94557370778232[label = " |
20| "]; + "node94557370778232":left -> "node94557370778064":center; + node94557370778064[label = " |
18| "]; + "node94557370778064":right -> "node94557370778008":center; + node94557370778008[label = " |
21| "]; + "node94557370778344":right -> "node94557370778288":center; + node94557370778288[label = " |
19| "]; + "node94557370778288":left -> "node94557370778120":center; + node94557370778120[label = " |
17| "]; + "node94557370778288":right -> "node94557370778176":center; + node94557370778176[label = " |
16| "]; +} diff --git a/challenge-113/arne-sommer/misc/tree3.svg b/challenge-113/arne-sommer/misc/tree3.svg new file mode 100644 index 0000000000..008b0f8d4e --- /dev/null +++ b/challenge-113/arne-sommer/misc/tree3.svg @@ -0,0 +1,119 @@ + + + + + + +foogrph + + + +node94557370778344 + + + +21 + + + + + +node94557370778232 + + + +20 + + + + + +node94557370778344:left->node94557370778232:center + + + + + +node94557370778288 + + + +19 + + + + + +node94557370778344:right->node94557370778288:center + + + + + +node94557370778064 + + + +18 + + + + + +node94557370778232:left->node94557370778064:center + + + + + +node94557370778008 + + + +21 + + + + + +node94557370778064:right->node94557370778008:center + + + + + +node94557370778120 + + + +17 + + + + + +node94557370778288:left->node94557370778120:center + + + + + +node94557370778176 + + + +16 + + + + + +node94557370778288:right->node94557370778176:center + + + + + diff --git a/challenge-113/arne-sommer/perl/ch-1.pl b/challenge-113/arne-sommer/perl/ch-1.pl new file mode 100755 index 0000000000..9d6a3af8dc --- /dev/null +++ b/challenge-113/arne-sommer/perl/ch-1.pl @@ -0,0 +1,37 @@ +#! /usr/bin/env perl + +use strict; +use feature 'say'; + +use Algorithm::Combinatorics 'combinations'; +use List::Util 'sum'; +use Getopt::Long; + +my $verbose = 0; +GetOptions("verbose" => \$verbose); + +my $N = shift(@ARGV) // die "Please specify an integer > 0"; +die "Please specify an integer > 0" unless $N =~ /^[1-9]\d*$/; + +my $D = shift(@ARGV) // die "Please specify a digit"; +die "Please specify a digit" unless $D =~ /^\d$/; + +my @candidates = grep { /$D/ } (1 .. $N); + +say ": Candidates " . join(', ', @candidates) if $verbose; + +for my $size (1 .. @candidates) +{ + for my $comb (combinations(\@candidates, $size)) + { + say ": Considering " . join(' + ', @$comb) if $verbose; + + if (sum(@$comb) == $N) + { + say 1; + exit; + } + } +} + +say 0; diff --git a/challenge-113/arne-sommer/perl/ch-2.pl b/challenge-113/arne-sommer/perl/ch-2.pl new file mode 100755 index 0000000000..6cdb10322f --- /dev/null +++ b/challenge-113/arne-sommer/perl/ch-2.pl @@ -0,0 +1,29 @@ +#! /usr/bin/env perl + +use strict; +use warnings; +use feature 'say'; + +use Getopt::Long; +use List::Util qw(sum); + +my $verbose = 0; + +GetOptions("verbose" => \$verbose); + +my $tree = shift(@$ARGV) // '1 | 2 3 | 4 * 5 6 | * 7'; + +my $sum = sum(grep(/\d/, split(/\s+/, $tree))); + +say ": Sum: $sum" if $verbose; + +my @elems; + +for my $elem (split(/\s+/, $tree)) +{ + $elem =~ /\d/ + ? push(@elems, $sum - $elem) + : push(@elems, $elem); +} + +say join(" ", @elems); diff --git a/challenge-113/arne-sommer/perl/recreate-binary-tree-perl b/challenge-113/arne-sommer/perl/recreate-binary-tree-perl new file mode 100755 index 0000000000..6cdb10322f --- /dev/null +++ b/challenge-113/arne-sommer/perl/recreate-binary-tree-perl @@ -0,0 +1,29 @@ +#! /usr/bin/env perl + +use strict; +use warnings; +use feature 'say'; + +use Getopt::Long; +use List::Util qw(sum); + +my $verbose = 0; + +GetOptions("verbose" => \$verbose); + +my $tree = shift(@$ARGV) // '1 | 2 3 | 4 * 5 6 | * 7'; + +my $sum = sum(grep(/\d/, split(/\s+/, $tree))); + +say ": Sum: $sum" if $verbose; + +my @elems; + +for my $elem (split(/\s+/, $tree)) +{ + $elem =~ /\d/ + ? push(@elems, $sum - $elem) + : push(@elems, $elem); +} + +say join(" ", @elems); diff --git a/challenge-113/arne-sommer/perl/represent-integer-perl b/challenge-113/arne-sommer/perl/represent-integer-perl new file mode 100755 index 0000000000..9d6a3af8dc --- /dev/null +++ b/challenge-113/arne-sommer/perl/represent-integer-perl @@ -0,0 +1,37 @@ +#! /usr/bin/env perl + +use strict; +use feature 'say'; + +use Algorithm::Combinatorics 'combinations'; +use List::Util 'sum'; +use Getopt::Long; + +my $verbose = 0; +GetOptions("verbose" => \$verbose); + +my $N = shift(@ARGV) // die "Please specify an integer > 0"; +die "Please specify an integer > 0" unless $N =~ /^[1-9]\d*$/; + +my $D = shift(@ARGV) // die "Please specify a digit"; +die "Please specify a digit" unless $D =~ /^\d$/; + +my @candidates = grep { /$D/ } (1 .. $N); + +say ": Candidates " . join(', ', @candidates) if $verbose; + +for my $size (1 .. @candidates) +{ + for my $comb (combinations(\@candidates, $size)) + { + say ": Considering " . join(' + ', @$comb) if $verbose; + + if (sum(@$comb) == $N) + { + say 1; + exit; + } + } +} + +say 0; diff --git a/challenge-113/arne-sommer/raku/ch-1.raku b/challenge-113/arne-sommer/raku/ch-1.raku new file mode 100755 index 0000000000..ef6e2f7c93 --- /dev/null +++ b/challenge-113/arne-sommer/raku/ch-1.raku @@ -0,0 +1,19 @@ +#! /usr/bin/env raku + +unit sub MAIN (Int $N where $N > 0, Int $D where $D.chars == 1, :v($verbose)); + +my @candidates = (1 .. $N).grep( * ~~ /$D/); + +say ": Candidates { @candidates.join(', ') }" if $verbose; + +for @candidates.combinations(1..*) -> @comb +{ + say ": Considering { @comb.join(' + ') }" if $verbose; + if @comb.sum == $N + { + say 1; + exit; + } +} + +say 0; \ No newline at end of file diff --git a/challenge-113/arne-sommer/raku/ch-2.raku b/challenge-113/arne-sommer/raku/ch-2.raku new file mode 100755 index 0000000000..caf24b1596 --- /dev/null +++ b/challenge-113/arne-sommer/raku/ch-2.raku @@ -0,0 +1,98 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $tree = '1 | 2 3 | 4 * 5 6 | * 7', :v($verbose), :g(:$graph)); + +class BinaryNode +{ + has Numeric $.value is rw; + has BinaryNode $.left is rw; + has BinaryNode $.right is rw; + + method id + { + self.Str ~~ /(\d+)/; return $0.Str; + } + + method sum + { + my $sum = self.value; + $sum += self.left.sum if self.left.defined; + $sum += self.right.sum if self.right.defined; + return $sum; + } +} + +my @btree = $tree.split("|")>>.words; + +my @old-nodes; +my @new-nodes; + +for @btree.reverse -> $row +{ + my @current = @$row; + @old-nodes = @new-nodes; + @new-nodes = (); + + for @current -> $value + { + if $value eq "*" + { + @new-nodes.push("*"); + next; + } + + my $left = @old-nodes.shift // "*"; $left = Nil if $left eq "*"; + my $right = @old-nodes.shift // "*"; $right = Nil if $right eq "*"; + + @new-nodes.push(BinaryNode.new(value => $value.Int, + left => $left // Nil, + right => $right // Nil)); + } +} + +my $btree = @new-nodes[0]; + +say ": Sum: { $btree.sum }" if $verbose; + +say ": { $btree.raku }\n" if $verbose; + +traverse($btree); + +say ": { $btree.raku }\n" if $verbose; + +graph($btree) if $graph; + +sub traverse ($current) +{ + $current.value = $sum - $current.value; + + traverse($current.left) if $current.left.defined; + traverse($current.right) if $current.right.defined; +} + +sub graph ($graph) +{ + say 'digraph foogrph {'; + say ' node [shape = record,height=.1];'; + + do-it($graph); + + say '}'; + + sub do-it ($current) + { + say " node{ $current.id }[label = \" |
{ $current.value }| \"];"; + + if $current.left.defined + { + say " \"node{ $current.id }\":left -> \"node{ $current.left.id }\":center;"; + do-it($current.left); + } + + if $current.right.defined + { + say " \"node{ $current.id }\":right -> \"node{ $current.right.id }\":center;"; + do-it($current.right); + } + } +} diff --git a/challenge-113/arne-sommer/raku/recreate-binary-tree b/challenge-113/arne-sommer/raku/recreate-binary-tree new file mode 100755 index 0000000000..44b8783893 --- /dev/null +++ b/challenge-113/arne-sommer/raku/recreate-binary-tree @@ -0,0 +1,18 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $tree = '1 | 2 3 | 4 * 5 6 | * 7', :v($verbose)); + +my $sum = $tree.words.grep( * ~~ /\d/ ).sum; + +say ": Sum: $sum" if $verbose; + +my @elems; + +for $tree.words -> $elem +{ + $elem ~~ /\d/ + ?? @elems.push: $sum - $elem + !! @elems.push: $elem; +} + +say @elems.join(" "); diff --git a/challenge-113/arne-sommer/raku/recreate-binary-tree-truly b/challenge-113/arne-sommer/raku/recreate-binary-tree-truly new file mode 100755 index 0000000000..9616ad6c66 --- /dev/null +++ b/challenge-113/arne-sommer/raku/recreate-binary-tree-truly @@ -0,0 +1,87 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $tree = '1 | 2 3 | 4 * 5 6 | * 7', :v($verbose), :g(:$graph)); + +my $sum = $tree.words.grep( * ~~ /\d/ ).sum; + +say ": Sum: $sum" if $verbose; + +class BinaryNode +{ + has Numeric $.value is rw; + has BinaryNode $.left is rw; + has BinaryNode $.right is rw; +} + +my @btree = $tree.split("|")>>.words; + +my @old-nodes; +my @new-nodes; + +for @btree.reverse -> $row +{ + my @current = @$row; + @old-nodes = @new-nodes; + @new-nodes = (); + + for @current -> $value + { + if $value eq "*" + { + @new-nodes.push("*"); + next; + } + + my $left = @old-nodes.shift // "*"; $left = Nil if $left eq "*"; + my $right = @old-nodes.shift // "*"; $right = Nil if $right eq "*"; + + @new-nodes.push(BinaryNode.new(value => $value.Int, + left => $left // Nil, + right => $right // Nil)); + } +} + +my $btree = @new-nodes[0]; + +say ": { $btree.raku }\n" if $verbose; + +traverse($btree); + +say ": { $btree.raku }\n" if $verbose; + +graph($btree) if $graph; + +sub traverse ($current) +{ + $current.value = $sum - $current.value; + + traverse($current.left) if $current.left.defined; + traverse($current.right) if $current.right.defined; +} + +sub graph ($graph) +{ + say 'digraph foogrph {'; + say ' node [shape = record,height=.1];'; + + do-it($graph); + + say '}'; + + sub do-it ($current) + { + say " node{ $current.value }[label = \" |
{ $current.value }| \"];"; + + if $current.left.defined + { + say " \"node{ $current.value }\":left -> \"node{ $current.left.value }\":center;"; + do-it($current.left); + } + + if $current.right.defined + { + say " \"node{ $current.value }\":right -> \"node{ $current.right.value }\":center;"; + do-it($current.right); + } + } +} diff --git a/challenge-113/arne-sommer/raku/recreate-binary-tree-truly2 b/challenge-113/arne-sommer/raku/recreate-binary-tree-truly2 new file mode 100755 index 0000000000..caf24b1596 --- /dev/null +++ b/challenge-113/arne-sommer/raku/recreate-binary-tree-truly2 @@ -0,0 +1,98 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $tree = '1 | 2 3 | 4 * 5 6 | * 7', :v($verbose), :g(:$graph)); + +class BinaryNode +{ + has Numeric $.value is rw; + has BinaryNode $.left is rw; + has BinaryNode $.right is rw; + + method id + { + self.Str ~~ /(\d+)/; return $0.Str; + } + + method sum + { + my $sum = self.value; + $sum += self.left.sum if self.left.defined; + $sum += self.right.sum if self.right.defined; + return $sum; + } +} + +my @btree = $tree.split("|")>>.words; + +my @old-nodes; +my @new-nodes; + +for @btree.reverse -> $row +{ + my @current = @$row; + @old-nodes = @new-nodes; + @new-nodes = (); + + for @current -> $value + { + if $value eq "*" + { + @new-nodes.push("*"); + next; + } + + my $left = @old-nodes.shift // "*"; $left = Nil if $left eq "*"; + my $right = @old-nodes.shift // "*"; $right = Nil if $right eq "*"; + + @new-nodes.push(BinaryNode.new(value => $value.Int, + left => $left // Nil, + right => $right // Nil)); + } +} + +my $btree = @new-nodes[0]; + +say ": Sum: { $btree.sum }" if $verbose; + +say ": { $btree.raku }\n" if $verbose; + +traverse($btree); + +say ": { $btree.raku }\n" if $verbose; + +graph($btree) if $graph; + +sub traverse ($current) +{ + $current.value = $sum - $current.value; + + traverse($current.left) if $current.left.defined; + traverse($current.right) if $current.right.defined; +} + +sub graph ($graph) +{ + say 'digraph foogrph {'; + say ' node [shape = record,height=.1];'; + + do-it($graph); + + say '}'; + + sub do-it ($current) + { + say " node{ $current.id }[label = \" |
{ $current.value }| \"];"; + + if $current.left.defined + { + say " \"node{ $current.id }\":left -> \"node{ $current.left.id }\":center;"; + do-it($current.left); + } + + if $current.right.defined + { + say " \"node{ $current.id }\":right -> \"node{ $current.right.id }\":center;"; + do-it($current.right); + } + } +} diff --git a/challenge-113/arne-sommer/raku/represent-integer b/challenge-113/arne-sommer/raku/represent-integer new file mode 100755 index 0000000000..ef6e2f7c93 --- /dev/null +++ b/challenge-113/arne-sommer/raku/represent-integer @@ -0,0 +1,19 @@ +#! /usr/bin/env raku + +unit sub MAIN (Int $N where $N > 0, Int $D where $D.chars == 1, :v($verbose)); + +my @candidates = (1 .. $N).grep( * ~~ /$D/); + +say ": Candidates { @candidates.join(', ') }" if $verbose; + +for @candidates.combinations(1..*) -> @comb +{ + say ": Considering { @comb.join(' + ') }" if $verbose; + if @comb.sum == $N + { + say 1; + exit; + } +} + +say 0; \ No newline at end of file -- cgit