From 3c9f53e1cd13bb56fbd6f262a8d583cca22a498b Mon Sep 17 00:00:00 2001 From: arnesom Date: Sun, 13 Feb 2022 21:20:32 +0100 Subject: Arne Sommer --- challenge-151/arne-sommer/blog.txt | 1 + challenge-151/arne-sommer/raku/binary-tree-depth | 65 ++++++++++++++++++++++++ challenge-151/arne-sommer/raku/ch-1.raku | 65 ++++++++++++++++++++++++ challenge-151/arne-sommer/raku/ch-2.raku | 37 ++++++++++++++ challenge-151/arne-sommer/raku/rob-the-house | 37 ++++++++++++++ 5 files changed, 205 insertions(+) create mode 100644 challenge-151/arne-sommer/blog.txt create mode 100755 challenge-151/arne-sommer/raku/binary-tree-depth create mode 100755 challenge-151/arne-sommer/raku/ch-1.raku create mode 100755 challenge-151/arne-sommer/raku/ch-2.raku create mode 100755 challenge-151/arne-sommer/raku/rob-the-house diff --git a/challenge-151/arne-sommer/blog.txt b/challenge-151/arne-sommer/blog.txt new file mode 100644 index 0000000000..12266d16d7 --- /dev/null +++ b/challenge-151/arne-sommer/blog.txt @@ -0,0 +1 @@ +https://raku-musings.com/tree-house.html diff --git a/challenge-151/arne-sommer/raku/binary-tree-depth b/challenge-151/arne-sommer/raku/binary-tree-depth new file mode 100755 index 0000000000..466c579ec4 --- /dev/null +++ b/challenge-151/arne-sommer/raku/binary-tree-depth @@ -0,0 +1,65 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $tree = "1 | 2 3 | 4 * * 5 | * 6", :v(:$verbose)); + +class BinaryNode +{ + has Int $.value; + has BinaryNode $.left; + has BinaryNode $.right; +} + +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]; + +my @paths; + +traverse2($btree, ()); + +sub traverse2 ($current, @path is copy) +{ + @path.push: $current.value; + + if ($current.left or $current.right) + { + traverse2($current.left, @path) if $current.left; + traverse2($current.right, @path) if $current.right; + } + else + { + say ": Path: [{ @path.join(", ") }] with length { @path.elems }" if $verbose; + @paths.push: @path; + + return; + } +} + +say @paths>>.elems.min; + diff --git a/challenge-151/arne-sommer/raku/ch-1.raku b/challenge-151/arne-sommer/raku/ch-1.raku new file mode 100755 index 0000000000..466c579ec4 --- /dev/null +++ b/challenge-151/arne-sommer/raku/ch-1.raku @@ -0,0 +1,65 @@ +#! /usr/bin/env raku + +unit sub MAIN (Str $tree = "1 | 2 3 | 4 * * 5 | * 6", :v(:$verbose)); + +class BinaryNode +{ + has Int $.value; + has BinaryNode $.left; + has BinaryNode $.right; +} + +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]; + +my @paths; + +traverse2($btree, ()); + +sub traverse2 ($current, @path is copy) +{ + @path.push: $current.value; + + if ($current.left or $current.right) + { + traverse2($current.left, @path) if $current.left; + traverse2($current.right, @path) if $current.right; + } + else + { + say ": Path: [{ @path.join(", ") }] with length { @path.elems }" if $verbose; + @paths.push: @path; + + return; + } +} + +say @paths>>.elems.min; + diff --git a/challenge-151/arne-sommer/raku/ch-2.raku b/challenge-151/arne-sommer/raku/ch-2.raku new file mode 100755 index 0000000000..ceba41018d --- /dev/null +++ b/challenge-151/arne-sommer/raku/ch-2.raku @@ -0,0 +1,37 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@valuables where @valuables.elems && all(@valuables) ~~ Numeric, :v(:$verbose)); + +my $seq := gather { recurse( (0,), 0, @valuables.elems -1); } + +sub recurse(@done is copy, $index, $todo is copy) +{ + if $todo < 2 + { + say ": Added candidate: @done[]" if $verbose; + take @done; + return; + } + + for 2, 3 -> $add + { + if $todo >= $add + { + my @done1 = @done.clone; + @done1.push: $index + $add; + recurse(@done1, $index + $add, $todo - $add); + } + } +} + +my @candidates = $seq; + +if $verbose +{ + for @candidates -> @list + { + say ": Candidate indices: [{ @list.join(",") }] with sum: { @valuables[@list].sum }"; + } +} + +say @candidates.map({ @valuables[@$_].sum }).max; diff --git a/challenge-151/arne-sommer/raku/rob-the-house b/challenge-151/arne-sommer/raku/rob-the-house new file mode 100755 index 0000000000..ceba41018d --- /dev/null +++ b/challenge-151/arne-sommer/raku/rob-the-house @@ -0,0 +1,37 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@valuables where @valuables.elems && all(@valuables) ~~ Numeric, :v(:$verbose)); + +my $seq := gather { recurse( (0,), 0, @valuables.elems -1); } + +sub recurse(@done is copy, $index, $todo is copy) +{ + if $todo < 2 + { + say ": Added candidate: @done[]" if $verbose; + take @done; + return; + } + + for 2, 3 -> $add + { + if $todo >= $add + { + my @done1 = @done.clone; + @done1.push: $index + $add; + recurse(@done1, $index + $add, $todo - $add); + } + } +} + +my @candidates = $seq; + +if $verbose +{ + for @candidates -> @list + { + say ": Candidate indices: [{ @list.join(",") }] with sum: { @valuables[@list].sum }"; + } +} + +say @candidates.map({ @valuables[@$_].sum }).max; -- cgit