From c7bc515a68bfad1f7c63713449caa0d7ceffa866 Mon Sep 17 00:00:00 2001 From: Mark A Date: Sat, 17 Jul 2021 02:33:03 -0600 Subject: ch-2.raku tidied --- challenge-121/mark-anderson/raku/ch-2.raku | 50 +++++++++--------------------- 1 file changed, 15 insertions(+), 35 deletions(-) diff --git a/challenge-121/mark-anderson/raku/ch-2.raku b/challenge-121/mark-anderson/raku/ch-2.raku index 0b872a9dad..6055cdee76 100644 --- a/challenge-121/mark-anderson/raku/ch-2.raku +++ b/challenge-121/mark-anderson/raku/ch-2.raku @@ -40,28 +40,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 +79,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; + 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; } -- cgit From 3dd3e509c4969c81dce04e53c867dcf0ce9408e6 Mon Sep 17 00:00:00 2001 From: Mark A Date: Sat, 17 Jul 2021 03:56:08 -0600 Subject: ch-2.raku tidied --- challenge-121/mark-anderson/raku/ch-2.raku | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/challenge-121/mark-anderson/raku/ch-2.raku b/challenge-121/mark-anderson/raku/ch-2.raku index 6055cdee76..8aeff99fa7 100644 --- a/challenge-121/mark-anderson/raku/ch-2.raku +++ b/challenge-121/mark-anderson/raku/ch-2.raku @@ -53,7 +53,7 @@ class Node } } - @.matrix = ([Z] @.matrix)>>.Array; + @.matrix = ([Z] @.matrix)>>.Array; } } @@ -96,7 +96,7 @@ multi branch-and-bound(Node @nodes) $node.matrix = $n.matrix.duckmap(*.clone); $node.set-Infs; $node.Reduce; - $node.cost += sum $n.cost, $n.matrix[@p[*-2]-1;@p[*-1]-1]; + $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); } -- cgit From d495c7dec361178bb0778bc435779e7b8c84ee5f Mon Sep 17 00:00:00 2001 From: Mark A Date: Sat, 17 Jul 2021 04:12:45 -0600 Subject: ch-2.raku tidied --- challenge-121/mark-anderson/raku/ch-2.raku | 12 ++++-------- 1 file changed, 4 insertions(+), 8 deletions(-) diff --git a/challenge-121/mark-anderson/raku/ch-2.raku b/challenge-121/mark-anderson/raku/ch-2.raku index 8aeff99fa7..0a824cad53 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, 'https://www.youtube.com/watch?v=cSY82XtVqYg&t=761s'; 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)); -- cgit From e1d6a0a8c1ffe1c2f15ff966ab32be471300cd65 Mon Sep 17 00:00:00 2001 From: Mark A Date: Sat, 17 Jul 2021 04:21:10 -0600 Subject: ch-2.raku tidied --- challenge-121/mark-anderson/raku/ch-2.raku | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/challenge-121/mark-anderson/raku/ch-2.raku b/challenge-121/mark-anderson/raku/ch-2.raku index 0a824cad53..87272e2819 100644 --- a/challenge-121/mark-anderson/raku/ch-2.raku +++ b/challenge-121/mark-anderson/raku/ch-2.raku @@ -11,7 +11,7 @@ is branch-and-bound([ ∞, 5, 2, 7 ], 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, 'https://www.youtube.com/watch?v=cSY82XtVqYg&t=761s'; is branch-and-bound([ ∞, 20, 30, 10, 11 ], [ 15, ∞, 16, 4, 2 ], -- cgit