diff options
| -rw-r--r-- | challenge-083/jeongoon/go/ch-2.go | 3 | ||||
| -rw-r--r-- | challenge-083/jeongoon/haskell/Combinations.hs | 25 | ||||
| -rw-r--r-- | challenge-083/jeongoon/haskell/ch-2.hs | 12 | ||||
| -rw-r--r-- | challenge-083/jeongoon/haskell/ch-2.simple-combinations.hs | 56 |
4 files changed, 88 insertions, 8 deletions
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 new file mode 100644 index 0000000000..3e2a2d8a30 --- /dev/null +++ b/challenge-083/jeongoon/haskell/Combinations.hs @@ -0,0 +1,25 @@ +{- Copyright (c) 2020 JEON Myoungjin <jeongoon@g... > -} + +module Combinations + ( combinations + ) where + +combinations :: [a] -> Int -> [[a]] +combinations [] _ = [] +combinations (m:ms) 1 = [m] : (combinations ms 1) +combinations [_] 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 (fst) tups + in leaders ++ followers | + tups <- combinations (zip mls [0 .. room]) n', + let skipCount = ((snd.last) tups) + 1, + followers <- (combinations (drop skipCount mls) 2) ] + where + totalLen = length mls + room = totalLen - 2 + n' = n - 2 diff --git a/challenge-083/jeongoon/haskell/ch-2.hs b/challenge-083/jeongoon/haskell/ch-2.hs index dfc1066e31..d9584ede0f 100644 --- a/challenge-083/jeongoon/haskell/ch-2.hs +++ b/challenge-083/jeongoon/haskell/ch-2.hs @@ -3,30 +3,26 @@ import System.Exit import Data.Char (isNumber) import Data.Maybe (isJust, catMaybes) import Data.List (sum) +import Combinations (combinations) --- 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 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 - | totalLen == 1 = 0 + | totalSum == 1 = 0 | otherwise = answerWith totalSum totalLen numCombis where totalSum = sum nums totalLen = length nums halfLen = totalLen `div` 2 numCombis = (foldr1 (++) . - map (`combinations` nums)) + map (combinations nums)) [ 1 .. halfLen ] answerWith _ minElems [] = minElems 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 ) ) |