diff options
| -rw-r--r-- | challenge-121/mark-anderson/raku/ch-2.raku | 64 |
1 files changed, 20 insertions, 44 deletions
diff --git a/challenge-121/mark-anderson/raku/ch-2.raku b/challenge-121/mark-anderson/raku/ch-2.raku index 0b872a9dad..87272e2819 100644 --- a/challenge-121/mark-anderson/raku/ch-2.raku +++ b/challenge-121/mark-anderson/raku/ch-2.raku @@ -6,28 +6,24 @@ plan 4; is branch-and-bound([ ∞, 5, 2, 7 ], [ 5, ∞, 5, 3 ], [ 3, 1, ∞, 6 ], - [ 4, 5, 4, ∞ ]), 10, - 'Example 1'; + [ 4, 5, 4, ∞ ]), 10, 'Example 1'; is branch-and-bound([ ∞, 15, 30, 4 ], [ 6, ∞, 4, 1 ], [ 10, 15, ∞, 16 ], - [ 7, 18, 13, ∞ ]), 36, - 'https://www.youtube.com/watch?v=cSY82XtVqYg&t=761s'; + [ 7, 18, 13, ∞ ]), 36, '<a href>https://www.youtube.com/watch?v=cSY82XtVqYg&t=761s</a>'; is branch-and-bound([ ∞, 20, 30, 10, 11 ], [ 15, ∞, 16, 4, 2 ], [ 3, 5, ∞, 2, 4 ], [ 19, 6, 18, ∞, 3 ], - [ 16, 4, 7, 16, ∞ ]), 28, - 'https://www.youtube.com/watch?v=1FEP_sNb62k'; + [ 16, 4, 7, 16, ∞ ]), 28, 'https://www.youtube.com/watch?v=1FEP_sNb62k'; is branch-and-bound([ ∞, 14, 4, 10, 20 ], [ 14, ∞, 7, 8, 7 ], [ 4, 5, ∞, 4, 16 ], [ 11, 7, 9, ∞, 2 ], - [ 18, 7, 17, 4, ∞ ]), 30, - 'https://www.youtube.com/watch?v=HjSbaKF8Gi0'; + [ 18, 7, 17, 4, ∞ ]), 30, 'https://www.youtube.com/watch?v=HjSbaKF8Gi0'; say branch-and-bound(random-matrix(15)); say branch-and-bound(random-matrix(20)); @@ -40,28 +36,21 @@ class Node method Reduce { - my @cost; - for ^2 { for @.matrix -> @r { my $min = @r.min; - $min = 0 if $min == ∞; - @cost.push($min); - for @r -> $n is rw + unless $min == 0|∞ { - $n -= $min; - $n = ∞ if $n ~~ NaN; + $.cost += $min; + @r.map(* -= $min); } } - @.matrix = [Z] @.matrix; - @.matrix .= map(*.Array); + @.matrix = ([Z] @.matrix)>>.Array; } - - $.cost = @cost.sum; } method paths @@ -86,47 +75,34 @@ class Node multi branch-and-bound(+@matrix) { my $node = Node.new(:path([1]), :matrix(@matrix)) andthen .Reduce; - branch-and-bound($node, []); + my Node @a = [ $node, Node.new(:cost(∞)) ]; + + branch-and-bound(@a); } -multi branch-and-bound($n, @leaves) +multi branch-and-bound(Node @nodes) { - return $n.cost if $n.path == $n.matrix; + my $n = @nodes.shift; - my $node; - my @nodes = Empty; + return $n.cost if $n.path == $n.matrix; for $n.paths -> @p { - $node = Node.new(:path(@p)); + my $node = Node.new(:path(@p)); $node.matrix = $n.matrix.duckmap(*.clone); $node.set-Infs; $node.Reduce; - $node.cost += sum $n.cost, $n.matrix[@p[*-2]-1;@p[*-1]-1]; - @nodes.push($node); - } - - my $min = @nodes.map(*.cost).min; - my $k = @leaves.first(*.cost < $min, :k); - - if $k.defined - { - $node = @leaves.splice($k, 1).head; - } - - else - { - $k = @nodes.first(*.cost == $min, :k); - $node = @nodes.splice($k, 1).head; + $node.cost += $n.cost + $n.matrix[@p[*-2]-1;@p[*-1]-1]; + my $i = @nodes.first(*.cost >= $node.cost, :k); + @nodes.splice($i, 0, $node); } - @leaves.append(@nodes); - branch-and-bound($node, @leaves); + branch-and-bound(@nodes); } sub random-matrix($n) { - my @m = ([ roll $n, (1..$n*2) ] xx $n); + my @m = [ roll $n, (1..$n*2) ] xx $n; @m.map({ .[$++] = ∞ }); @m; } |