Merge pull request #2598 from jeongoon/master

[ch-083/jeongoon] add more versions of Task #2 for Perl, Haskell, and another blog for Task #2

8 files changed, 154 insertions, 11 deletions

diff --git a/challenge-083/jeongoon/blog.txt b/challenge-083/jeongoon/blog.txt
new file mode 100644
index 0000000000..1ebcc375d9
--- /dev/null
+++ b/challenge-083/jeongoon/blog.txt
@@ -0,0 +1 @@
+https://dev.to/jeongoon/weekly-challenge-083-task-2-perl-8d0
diff --git a/challenge-083/jeongoon/go/ch-2.go b/challenge-083/jeongoon/go/ch-2.go
index 60433a850f..6aa302f909 100644
--- a/challenge-083/jeongoon/go/ch-2.go
+++ b/challenge-083/jeongoon/go/ch-2.go
@@ -101,6 +101,9 @@ func combinationsIndex( M int, N int ) [][]int {
 	return combis
 }
 
+// Comment: I used half length of combination in Perl, Haskell
+// but Go is already fast with full length of combinations. impressive.
+
 func main() {
 	if len(os.Args[1:]) < 1 {
 		usage();
diff --git a/challenge-083/jeongoon/haskell/Combinations.hs b/challenge-083/jeongoon/haskell/Combinations.hs
index f8c5324f43..3e2a2d8a30 100644
--- a/challenge-083/jeongoon/haskell/Combinations.hs
+++ b/challenge-083/jeongoon/haskell/Combinations.hs
@@ -8,16 +8,16 @@ combinations :: [a] -> Int -> [[a]]
 combinations []     _  = []
 combinations (m:ms) 1 = [m] : (combinations ms 1)
 combinations [_]    2 = []
-combinations [e,f]  2 = sequence [ [e],[f] ]
-combinations (m:ms) 2 = sequence [ [m],  ms ] ++ (combinations ms 2)
+combinations [e,f]  2 = [[e,f]]
+combinations (m:ms) 2 = sequence [[m], ms] ++ (combinations ms 2)
 combinations mls    n =
   case totalLen `compare` n of
     LT -> []
     EQ -> [mls]
-    _  -> [ let leaders = map (mls!!) ids
+    _  -> [ let leaders = map (fst) tups
             in  leaders ++ followers |
-            ids <- combinations [ 0 .. room ] n',
-            let skipCount = (last ids) + 1,
+            tups <- combinations (zip mls [0 .. room])  n',
+            let skipCount = ((snd.last) tups) + 1,
                 followers <- (combinations (drop skipCount mls) 2) ]
   where
     totalLen    = length mls
diff --git a/challenge-083/jeongoon/haskell/ch-2.hs b/challenge-083/jeongoon/haskell/ch-2.hs
index c64170400a..66b12b09c0 100644
--- a/challenge-083/jeongoon/haskell/ch-2.hs
+++ b/challenge-083/jeongoon/haskell/ch-2.hs
@@ -5,18 +5,17 @@ import Data.Maybe (isJust, catMaybes)
 import Data.List (sum)
 import Combinations (combinations)
 
-
 {- test with:
    runhaskell ch-2.hs 12 7 4 # answer: 12
    runhaskell ch-2.hs 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8 # answer: 6
  # or in order to get faster result, you can compile and execute:
-   ghc ch-2.hs
+   ghc -O2 ch-2.hs
    ./ch-2 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8 # answer: 6
 -}
 
 answerFlipArray :: (Integral a) => [a] -> Int
 answerFlipArray nums
-  | totalSum == 1 = 0
+  | totalLen == 1 = 0
   | otherwise = answerWith totalSum totalLen numCombis
   where
     totalSum  = sum nums
diff --git a/challenge-083/jeongoon/haskell/ch-2.simple-combinations.hs b/challenge-083/jeongoon/haskell/ch-2.simple-combinations.hs
new file mode 100644
index 0000000000..4fbdbd599d
--- /dev/null
+++ b/challenge-083/jeongoon/haskell/ch-2.simple-combinations.hs
@@ -0,0 +1,56 @@
+import System.Environment
+import System.Exit
+import Data.Char (isNumber)
+import Data.Maybe (isJust, catMaybes)
+import Data.List (sum)
+
+-- credit: https://wiki.haskell.org/99_questions/Solutions/26
+combinations :: Int -> [a] -> [[a]]
+combinations 0 _ = [[]]
+combinations n xs = [ xs !! i : x | i <- [0..(length xs)-1]
+                                  , x <- combinations (n-1) (drop (i+1) xs) ]
+{- test with:
+   runhaskell ch-2.hs 12 7 4 # answer: 12
+   runhaskell ch-2.hs 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8 # answer: 6
+ # or in order to get faster result, you can compile and execute:
+   ghc -O2 ch-2.hs
+   ./ch-2 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8 # answer: 6
+-}
+
+answerFlipArray :: (Integral a) => [a] -> Int
+answerFlipArray nums
+  | totalLen == 1 = 0
+  | otherwise = answerWith totalSum totalLen numCombis
+  where
+    totalSum  = sum nums
+    totalLen  = length nums
+    halfLen   = totalLen `div` 2
+    numCombis = (foldr1 (++) .
+                    map (`combinations` nums))
+                   [ 1 .. halfLen ]
+
+    answerWith _      minElems [] = minElems
+    answerWith minSum minElems (aCombi:otherCombis) =
+      case (positiveSum `compare` minSum) of
+        LT -> answerWith positiveSum newElems otherCombis
+        EQ -> answerWith minSum (min newElems minElems) otherCombis
+        GT -> answerWith minSum minElems otherCombis
+      where
+        len  = length aCombi
+        sm   = sum aCombi
+        sm'  = totalSum - sm
+        (positiveSum, newElems) =
+            case (sm `compare` sm') of
+              LT -> ( sm' - sm, len )
+              EQ -> (        0, (min len (totalLen - len)) )
+              GT -> ( sm - sm', (totalLen - len) )
+
+main = do
+    (catMaybes.map (\nStr ->
+                       if (all isNumber nStr) then Just(read nStr :: Int)
+                       else Nothing )) `fmap` getArgs
+      >>= (\nums ->
+              if length nums < 1 then
+                die "Usage: runhaskell ch-2.hs <natural num> ..."
+              else
+                putStrLn $ show ( answerFlipArray nums ) )
diff --git a/challenge-083/jeongoon/perl/CombinationsIndex.pm b/challenge-083/jeongoon/perl/CombinationsIndex.pm
index 385c8905cd..9d04337229 100644
--- a/challenge-083/jeongoon/perl/CombinationsIndex.pm
+++ b/challenge-083/jeongoon/perl/CombinationsIndex.pm
@@ -66,7 +66,7 @@ sub combinationsIndex ( $$ ) {
 
     # set initial values ...
     {
-        # each finger can move to right number of ( M-N ) space(s).
+        # each cursor can move to right number of ( M-N ) space(s).
         @room     = ( $M-$N ) x $N;
         @pos      = 0 .. ($N - 1);
         $next_csr = $N - 1; # last cursor at rightmost
@@ -102,14 +102,14 @@ sub combinationsIndex ( $$ ) {
                 # $next_csr to last one
                 @pos[ $next_csr .. ($N-1) ]
                     = map { $pos[$next_csr] + $_ } 1 .. ($N-$next_csr);
-                # note: all these finger has same room when moved
+                # note: all these cursors have the same size of room when moved
                 @room[ $next_csr .. ($N-1) ]
                   = ( $room[ $next_csr ] - 1 ) x        ($N-$next_csr);
 
                 # and make a record
                 push @result, [ @pos ];
 
-                # next finger to move will be ($N-1)
+                # next cursor to move will be ($N-1)
                 # or even if it is not next loop will find anohter
                 $next_csr = ($N-1);
 
diff --git a/challenge-083/jeongoon/perl/ch-2.pl b/challenge-083/jeongoon/perl/ch-2.pl
index 75af463b95..c8369c0597 100644
--- a/challenge-083/jeongoon/perl/ch-2.pl
+++ b/challenge-083/jeongoon/perl/ch-2.pl
@@ -2,6 +2,8 @@
 # -*- Mode: cperl; cperl-indent-level:4 tab-width: 8; indent-tabs-mode: nil -*-
 # -*- coding: utf-8 -*-
 
+# personal-blog: https://dev.to/jeongoon/weekly-challenge-083-task-2-perl-8d0
+
 use strict; use warnings;
 use v5.26;
 use List::Util qw(all sum);
diff --git a/challenge-083/jeongoon/perl/ch-2.using-algorithm-combinatorics.pl b/challenge-083/jeongoon/perl/ch-2.using-algorithm-combinatorics.pl
new file mode 100644
index 0000000000..49b01bddfd
--- /dev/null
+++ b/challenge-083/jeongoon/perl/ch-2.using-algorithm-combinatorics.pl
@@ -0,0 +1,82 @@
+#!/usr/bin/env perl
+# -*- Mode: cperl; cperl-indent-level:4 tab-width: 8; indent-tabs-mode: nil -*-
+# -*- coding: utf-8 -*-
+
+use strict; use warnings;
+use v5.26;
+use List::Util qw(all sum);
+
+
+use Algorithm::Combinatorics;
+# comment: I don't know why but this version is slow.
+
+use FindBin;
+use lib ( $FindBin::Bin );
+
+sub usage {
+    say 'Usage: perl ch-2.pl [-d|--debug] <natural num> ... ', "\n",
+        'ex) perl ch-2.pl 12 2 10';
+}
+
+sub combinations ($$$) {
+    my ( $list, $minSelection, $maxSelection ) = @_;
+    map { Algorithm::Combinatorics::combinations( $list, $_ ) }
+      $minSelection .. $maxSelection;
+}
+
+package main;
+
+my @N = grep { ! /-(h|-*help)/ } @ARGV;
+@N == @ARGV or usage, exit 0;
+
+@N = grep { ! /-(d|-*debug)/ } @ARGV;
+our $d = @N != @ARGV;
+
+(  @N > 0
+   and
+   all { int($_) eq $_ and $_ > 0 } @N  ) or usage, exit 1;
+
+@N == 1 and ( say( "0" ), exit 0 ); # already mimimum
+
+my $totalSum = sum @N;
+my $halfLen  = int( .5 * @N ); # reduce the combinations in half
+
+# initial values ...
+my $minElems = +@N;
+my $minSum  = $totalSum;
+
+for my $combi ( combinations( \@N, 1, $halfLen ) ) {
+    my $aSum = sum @$combi;
+    my $bSum = $totalSum - $aSum;
+
+    my $curr =
+      ( # $aSum == $bSum
+       [ 0, ( scalar @$combi < $halfLen
+              ? scalar @$combi : scalar( @N - @$combi) ) ],
+        # $aSum  > $bSum
+       [ $aSum - $bSum, scalar ( @N - @$combi) ],
+        # $aSum  < $bSum
+       [ $bSum - $aSum, scalar @$combi ] )[ $aSum <=> $bSum ];
+
+    print "[sum: $$curr[0], elems: $$curr[1]] with @$combi ... " if $d;
+
+    if ( $$curr[0] > $minSum ) {        # minimum sum not changed
+        say "skipped." if $d;
+        next;
+    }
+    elsif ( $$curr[0] < $minSum ) {     # minimum sum cahnged
+                                        # so does minimum elements
+        say "**minium sum changed**" if $d;
+        ( $minSum, $minElems ) = @$curr;
+    }
+    elsif ( $$curr[1] < $minElems ) {   # minimum sum is same
+        # also elements is less
+        say "**minimum count changed**" if $d;
+        $minElems = $$curr[1];
+    }
+    else {
+        say "" if $d;
+    }
+}
+
+say $minElems;