blob: 466c579ec4ff36b712b0007610ded623036a437d (
plain)
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
|
#! /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;
|
