From 1c9d28484fe0cca463f5b0a55fdf9e0015dc868c Mon Sep 17 00:00:00 2001 From: rir Date: Sun, 28 May 2023 16:09:33 -0400 Subject: 218- --- challenge-218/0rir/raku/ch-1.raku | 130 ++++++++++++++++++++++++++++++++++++ challenge-218/0rir/raku/ch-2.raku | 137 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 267 insertions(+) create mode 100644 challenge-218/0rir/raku/ch-1.raku create mode 100644 challenge-218/0rir/raku/ch-2.raku diff --git a/challenge-218/0rir/raku/ch-1.raku b/challenge-218/0rir/raku/ch-1.raku new file mode 100644 index 0000000000..330c2aa768 --- /dev/null +++ b/challenge-218/0rir/raku/ch-1.raku @@ -0,0 +1,130 @@ +#!/usr/bin/env raku +# :vim ft=raku sw=4 expandtab # 🦋 ∅∪∩∋∈∉ ≡ ≢ «␤ » ∴ +use v6.d; +use lib $?FILE.IO.parent(2).add("lib"); +use Test; + +=begin comment +218-1: Maximum Product Submitted by: Mohammad S Anwar +Given a list of 3 or more integers, find the 3 integers whose product +is the maximum and return it. + +Example 1 +Input: @list = (3, 1, 2) +Output: 6 + +1 x 2 x 3 => 6 +Example 2 +Input: @list = (4, 1, 3, 2) +Output: 24 + +2 x 3 x 4 => 24 +Example 3 +Input: @list = (-1, 0, 1, 3, 1) +Output: 3 + +1 x 1 x 3 => 3 +Example 4 +Input: @list = (-8, 2, -9, 0, -4, 3) +Output: 216 + +-9 × -8 × 3 => 216 + +=end comment + +my @Test = + # in exp + (3, 1, 2), 6, # given + (4, 1, 3, 2), 24, + (-8, 2, -9, 0, -4, 3), 216, + (-1, 0, 1, 3, 1), 3, + +# (-3, -2, -1, 0), 0, + + ( 2, 3, 5), 30, # three elems + + ( 0, 1, 2, 3), 6, # quads + ( 1, 2, 3, 4), 24, + (-3, -2, -1, 0), 0, + (-4, -3, -2, -1), -6, + (-1, 1, 2, 3), 6, + (-1, -1, -2, 3), 6, + (-1, -1, 2, 3), 3, + (-3, -2, 3, 3), 18, + (-3, -3, 3, 3), 27, + + ( 0, 1, 2, 3, 4), 24, # all pos + ( 1, 2, 3, 4, 5), 60, + (-4, -3, -2, -1, 0), 0, # max zed + (-5, -4, -3, -2, -1), -6, # all neg + (-2, 0, 1, 2, 3), 6, # 1 neg + (-2, 1, 2, 3, 4), 24, # 1 neg + (-2, -3, -1, -1, 4), 24, # 1 pos + + (-1, -1, 2, 3, 4), 24, # 2 neg + (-3, -2, 1, 3, 3), 18, + (-3, -2, 3, 3, 3), 27, + (-3, -2, 1, 3, 3, 3), 27, + + (-2, -1, -1, 3, 4), 8, # 2 pos + (-3, -2, -1, 3, 3), 18, + (-3, -2, -1, -1, 1, 2), 12, + (-3, -2, 1, 3, 3, 3), 3³, + + (-9, -2, -2, 2, 3, 6), 108, # default + (-8, -4, -2, 2, 4, 9), 288, + (-8, -4, -2, 5, 6, 9), 288, + (-8, -4, -2, 5, 7, 9), 315, + (-8, -5, -2, 5, 7, 9), 360, + ; + +plan @Test ÷ 2 + 1 + 2_005_000; + + +multi max3prod( @a where *.elems < 3) { die( 'oospec') } +#multi max3prod( @a where *.elems == 3) { [×] @a } # triad +#multi max3prod( @a where *.elems == 4) { # quad +# @a.combinations(3).map( {[*] $_} ).max } +multi max3prod( @a ) { + multi func {…} + return func @a.sort; + + # more than 4 elems +# multi func( @a where *[*-1] == 0) { 0 } # max0 + multi func( @a where 0 ≤ *[0]) { [×] @a[*-3..*-1] } # all pos + multi func( @a where *[*-1] < 0) { [×] @a[*-3..*-1] } # all neg + # mixed signs +# multi func( @a where $_[0] < 0 < $_[1] ) { [×] @a[*-3..*-1] } # 1 neg +#multi func( @a where $_[*-2] < 0 < $_[*-1]) { [×] @a[0,1,*-1] } # 1 pos +# multi func( @a where $_[*-3] < 0 < $_[*-2]) { # 2 pos +# max ([×] @a[0,1,*-1]), ([×] @a[*-3..*-1]); } +# multi func( @a where $_[1] < 0 < $_[2] ) { # 2 neg +# max ([×] @a[0,1,*-1]), ([×] @a[*-3..*-1]); } + multi func( @a ) { # default + max ([×] @a[0,1,*-1]), ([×] @a[*-3..*-1]); } +} + +for @Test -> @in, $exp { + is max3prod(@in), $exp, "$exp\t<- @in.sort()"; +} +srand(104571); +hyper for 1..2_005_000 { + my @t; + for 1..4 + (^5).pick -> $l { + for (^20).pick - 10 -> $r { + @t.push: $r; + } + } + my $res = @t.combinations(3).map( {[*] $_} ).max; + is max3prod(@t), $res, "$res\t<- @t.sort()"; +} + +dies-ok { max3prod( (1,2)) }, "(1,2) dies-ok"; +done-testing; + +my $list = (-8, 2, -9, 0, -4, 3); +say "\nInput: @list = @$list[]\nOutput: &max3prod(@$list).sort()"; + + +exit; + diff --git a/challenge-218/0rir/raku/ch-2.raku b/challenge-218/0rir/raku/ch-2.raku new file mode 100644 index 0000000000..c3ea07ad02 --- /dev/null +++ b/challenge-218/0rir/raku/ch-2.raku @@ -0,0 +1,137 @@ +#!/usr/bin/env raku +# :vim ft=raku sw=4 expandtab # 🦋 ∅∪∩∋∈∉ ≡ ≢ «␤ » ∴ +use v6.d; +use lib $?FILE.IO.parent(2).add("lib"); +use Test; + +=begin comment +Task 2: Matrix Score Submitted by: Mohammad S Anwar +Given a m x n binary matrix i.e. having only 1 and 0, make as many +moves as you want to get the highest score. + +A move can be either toggling each value in a row or column. + +To get the score, convert the each row's binary value to decimal and +return the sum. + +Example 1: +Input: @matrix = [ [0,0,1,1], + [1,0,1,0], + [1,1,0,0], ] +Output: 39 + +Move #1: convert row #1 => 1100 + [ [1,1,0,0], [1,0,1,0], [1,1,0,0], ] + +Move #2: convert col #3 => 101 + [ [1,1,1,0], [1,0,0,0], [1,1,1,0], ] + +Move #3: convert col #4 => 111 + [ [1,1,1,1], [1,0,0,1], [1,1,1,1], ] + +Score: 0b1111 + 0b1001 + 0b1111 => 15 + 9 + 15 => 39 +Example 2: +Input: @matrix = [ [0] ] +Output: 1 +=end comment + +my @Test = + [ [0,0,0,1], [0,0,0,1], [0,0,0,1],], 45, + [ [0,0,1,1], [1,0,1,0], [1,1,0,0],], 39, + [ [0],], 1, + [ [1,0], [0,1], [0,0],], 8, + [ [1,0], [0,1], [1,0], [0,0],], 11, + [ [0,0,1,1], [1,0,1,0], [1,1,0,0], [ 0,1,0,1],], 48, + [ [0,1,0,1,1], [1,0,1,1,0], [1,1,0,0,1], [ 0,1,0,0,1],], 107, + [ [0,0,0,0,1], [1,0,0,0,0], [0,0,0,0,0], [ 1,0,0,0,1],], 94, +; + +plan @Test ÷ 2; + +sub max-row-base2( @m -->Int) { + my @mat = @m.raku.EVAL; + for @mat -> @row { + if @row[0] == 0 { invert @row;} + } + for ^@mat[0] -> $c { + my @col := bind-col( @mat, $c); + if +@col.grep(1) < +@col.grep(0) { invert @col; } + } + return [+] @mat.map( { parse-base .join, 2}); +} + +sub invert( @a -->Nil) { for @a -> $e is rw { $e = (!$e.Bool).Int }} +sub is-row( @m, UInt $i -->Bool) { $i < @m.elems } +sub bind-col( @m, $col-num -->Array) { + my @col; + @col[$_] := @m[$_][$col-num] for ^@m; + @col +} + +# A very stupid brute. +# Identify @matrix rows by their natural indices, and columns starting +# after @matrix.end. Permute this sequence and use the results to "toggle" +# the matrix in all permutations. Score after every toggle. +sub brute( @matrix -->Int) { + my $ct = 0; + my @mat = @matrix.raku.EVAL; + my $theo-best = theo-best(@mat); + my $best = score( @mat); + my @plan = ( ^(@mat.end +@mat[0] + 1)).Array.permutations; + for @plan -> @p { + my @m = @mat; + for @p -> $id { + toggle( $id, @m); + my $s = score @m; + $best = $s if $best < $s; + } + return $best if $best == $theo-best; + } + return $best; + + sub score( @m -->Int) { [+] @m.map: {parse-base .join, 2 }} + sub theo-best( @m -->Int) { @m.elems × ( 2**@m[0].elems - 1) } +} + +sub toggle( UInt $id, @a -->Nil) { + if is-row( @a, $id) { + for ^@a[0] -> $i { + @a[$id][$i] = (!@a[$id][$i].Bool).Int; + } + } else { + my $cid = $id - @a.elems; + for ^@a -> $r { + @a[$r][$cid] = (!@a[$r][$cid].Bool).Int; + } + } +} + +sub idsay( @m, $id -->Bool) { # Display a row or column. + if is-row @m, $id { + say @m[$id].raku(); + } else { + my $cid = $id - @m.elems; + my @col; + for 0..^@m -> $i { print " @m[$i][$cid]"; } + } +} +sub msay( @m --> Nil) { # Display a matrix. + print "["; + for 0..^(@m - 1) -> $i { say "\t@m[$i].raku()"; } + say "\t@m[*-1].raku() ]"; +} + + +for @Test -> @in, $exp { + is max-row-base2( @in), $exp, "$exp <-\t@in.raku()"; +# is brute( @in), $exp, "$exp <-\t@in.raku()"; +} + +done-testing; + +my @matrix = [ [0,0,1,1], [1,0,1,0], [1,1,0,0], ]; +my $preface = "Input: @matrix = ["; + +print "\n$preface ["; +print @matrix.join( "],\n " ~ (' ' x $preface.chars) ~ '[' ); +say "], ]" ~ "\nOutput: &max-row-base2( @matrix)"; -- cgit From f6a6cea4b1f736b511072170beae118bb1ee243f Mon Sep 17 00:00:00 2001 From: rir Date: Sun, 28 May 2023 18:08:18 -0400 Subject: 218 --- challenge-218/0rir/raku/ch-1.raku | 33 +++++++--------------------- challenge-218/0rir/raku/ch-2.raku | 46 +++++++++++++-------------------------- 2 files changed, 23 insertions(+), 56 deletions(-) diff --git a/challenge-218/0rir/raku/ch-1.raku b/challenge-218/0rir/raku/ch-1.raku index 330c2aa768..287fd175f5 100644 --- a/challenge-218/0rir/raku/ch-1.raku +++ b/challenge-218/0rir/raku/ch-1.raku @@ -29,7 +29,6 @@ Input: @list = (-8, 2, -9, 0, -4, 3) Output: 216 -9 × -8 × 3 => 216 - =end comment my @Test = @@ -39,9 +38,7 @@ my @Test = (-8, 2, -9, 0, -4, 3), 216, (-1, 0, 1, 3, 1), 3, -# (-3, -2, -1, 0), 0, - - ( 2, 3, 5), 30, # three elems + (-2, 3, 5), -30, # three elems ( 0, 1, 2, 3), 6, # quads ( 1, 2, 3, 4), 24, @@ -77,46 +74,32 @@ my @Test = (-8, -4, -2, 5, 7, 9), 315, (-8, -5, -2, 5, 7, 9), 360, ; - -plan @Test ÷ 2 + 1 + 2_005_000; - +plan @Test ÷ 2 + 1 + 1000; multi max3prod( @a where *.elems < 3) { die( 'oospec') } -#multi max3prod( @a where *.elems == 3) { [×] @a } # triad -#multi max3prod( @a where *.elems == 4) { # quad -# @a.combinations(3).map( {[*] $_} ).max } multi max3prod( @a ) { multi func {…} return func @a.sort; - # more than 4 elems -# multi func( @a where *[*-1] == 0) { 0 } # max0 multi func( @a where 0 ≤ *[0]) { [×] @a[*-3..*-1] } # all pos multi func( @a where *[*-1] < 0) { [×] @a[*-3..*-1] } # all neg # mixed signs -# multi func( @a where $_[0] < 0 < $_[1] ) { [×] @a[*-3..*-1] } # 1 neg -#multi func( @a where $_[*-2] < 0 < $_[*-1]) { [×] @a[0,1,*-1] } # 1 pos -# multi func( @a where $_[*-3] < 0 < $_[*-2]) { # 2 pos -# max ([×] @a[0,1,*-1]), ([×] @a[*-3..*-1]); } -# multi func( @a where $_[1] < 0 < $_[2] ) { # 2 neg -# max ([×] @a[0,1,*-1]), ([×] @a[*-3..*-1]); } - multi func( @a ) { # default - max ([×] @a[0,1,*-1]), ([×] @a[*-3..*-1]); } + multi func( @a){ max ([×] @a[0,1,*-1]), ([×] @a[*-3..*-1]); } } for @Test -> @in, $exp { - is max3prod(@in), $exp, "$exp\t<- @in.sort()"; + is max3prod(@in), $exp, "$exp\t<- @in.sort() sorted"; } -srand(104571); -hyper for 1..2_005_000 { +srand(102); +for 1..1_000 { my @t; for 1..4 + (^5).pick -> $l { for (^20).pick - 10 -> $r { @t.push: $r; } } - my $res = @t.combinations(3).map( {[*] $_} ).max; - is max3prod(@t), $res, "$res\t<- @t.sort()"; + my $res = @t.combinations(3).map( {[*] $_} ).max; # brute + is max3prod(@t), $res, "$res\t<- @t.sort() sorted"; } dies-ok { max3prod( (1,2)) }, "(1,2) dies-ok"; diff --git a/challenge-218/0rir/raku/ch-2.raku b/challenge-218/0rir/raku/ch-2.raku index c3ea07ad02..2decd60d85 100644 --- a/challenge-218/0rir/raku/ch-2.raku +++ b/challenge-218/0rir/raku/ch-2.raku @@ -1,7 +1,6 @@ #!/usr/bin/env raku # :vim ft=raku sw=4 expandtab # 🦋 ∅∪∩∋∈∉ ≡ ≢ «␤ » ∴ use v6.d; -use lib $?FILE.IO.parent(2).add("lib"); use Test; =begin comment @@ -9,15 +8,13 @@ Task 2: Matrix Score Submitted by: Mohammad S Anwar Given a m x n binary matrix i.e. having only 1 and 0, make as many moves as you want to get the highest score. -A move can be either toggling each value in a row or column. +A move can be either toggling all values in a row or column. -To get the score, convert the each row's binary value to decimal and +To get the score, convert each row's binary value to decimal and return the sum. Example 1: -Input: @matrix = [ [0,0,1,1], - [1,0,1,0], - [1,1,0,0], ] +Input: @matrix = [ [0,0,1,1], [1,0,1,0], [1,1,0,0], ] Output: 39 Move #1: convert row #1 => 1100 @@ -58,26 +55,28 @@ sub max-row-base2( @m -->Int) { if +@col.grep(1) < +@col.grep(0) { invert @col; } } return [+] @mat.map( { parse-base .join, 2}); + + sub invert( @a -->Nil) { for @a -> $e is rw { $e = (!$e.Bool).Int }} } -sub invert( @a -->Nil) { for @a -> $e is rw { $e = (!$e.Bool).Int }} -sub is-row( @m, UInt $i -->Bool) { $i < @m.elems } sub bind-col( @m, $col-num -->Array) { my @col; @col[$_] := @m[$_][$col-num] for ^@m; @col } -# A very stupid brute. -# Identify @matrix rows by their natural indices, and columns starting -# after @matrix.end. Permute this sequence and use the results to "toggle" -# the matrix in all permutations. Score after every toggle. +# A very stupid, stupid brute. Was I redundent? +# +# Every row and column is named. Rows use their index and columns are +# named with the @matrix.end + the value of the index into @matrix[0]. +# Permute this list; go thru each list; toggle each column or row; update +# score and repeat. Quit early if theoretical best score is found. sub brute( @matrix -->Int) { my $ct = 0; my @mat = @matrix.raku.EVAL; my $theo-best = theo-best(@mat); my $best = score( @mat); - my @plan = ( ^(@mat.end +@mat[0] + 1)).Array.permutations; + my @plan = ( ^(@mat.elems +@mat[0])).Array.permutations; for @plan -> @p { my @m = @mat; for @p -> $id { @@ -104,27 +103,12 @@ sub toggle( UInt $id, @a -->Nil) { @a[$r][$cid] = (!@a[$r][$cid].Bool).Int; } } + sub is-row( @m, UInt $i -->Bool) { $i < @m.elems } } -sub idsay( @m, $id -->Bool) { # Display a row or column. - if is-row @m, $id { - say @m[$id].raku(); - } else { - my $cid = $id - @m.elems; - my @col; - for 0..^@m -> $i { print " @m[$i][$cid]"; } - } -} -sub msay( @m --> Nil) { # Display a matrix. - print "["; - for 0..^(@m - 1) -> $i { say "\t@m[$i].raku()"; } - say "\t@m[*-1].raku() ]"; -} - - for @Test -> @in, $exp { - is max-row-base2( @in), $exp, "$exp <-\t@in.raku()"; -# is brute( @in), $exp, "$exp <-\t@in.raku()"; + is max-row-base2( @in), $exp, "$exp <-\t@in.raku()"; +# is brute( @in), $exp, "$exp <-\t@in.raku()"; } done-testing; -- cgit