Merge pull request #4536 from andemark/branch-for-challenge-121

ch-2.raku tidied

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;
 }