- Commit
- 73b681f35dfccb4ed1a15453731e0fc5a4649a1e
- Parent
- 1d939a73ebaa54ec82c586544ce9f4e5d7cdc933
- Author
- Pablo Escobar Gaviria <gark.garcia@protonmail.com>
- Date
Further optimized the Haskell implementation.
An exercise on polyglossy: the same problem solved on multiple languages
Further optimized the Haskell implementation.
1 file changed, 28 insertions, 18 deletions
Status | File Name | N° Changes | Insertions | Deletions |
Modified | Haskell/app/Main.hs | 46 | 28 | 18 |
diff --git a/Haskell/app/Main.hs b/Haskell/app/Main.hs @@ -5,13 +5,13 @@ module Main where -import Numeric +import Numeric (readDec) import Numeric.Natural import System.Environment import System.Exit import Control.Monad (foldM) -import Data.Map (Map, insert, lookup, empty) -import qualified Data.Map as Map +import Data.Map (Map, insert, empty) +import qualified Data.Map main :: IO Int main = do @@ -19,12 +19,13 @@ main = do if length args > 0 then case readDec (args !! 0) :: [(Natural, String)] of - [(max, "")] -> if counter' max empty then exitFailure else exitSuccess - + [(max, "")] -> + if counter' max then exitFailure else exitSuccess _ -> exitInvalidInput else exitInvalidInput +-- Calculates the sum of the digits of `n`. sum' :: Natural -> Int sum' n | n < 10 = fromEnum n @@ -46,19 +47,28 @@ test' a b sums = Nothing -> retry a where retry x = test' a b $ insert x (sum' x) sums - lookup x = Map.lookup x sums + lookup x = Data.Map.lookup x sums -counter' :: Natural -> Map Natural Int -> Bool -counter' max sums = - case foldM f (max, sums) [0..max] of - Nothing -> True - Just _ -> False - where f (a, sums) b = iter' b max sums +-- Checks if there is any counterexample in +-- [(a, b) | a <- [0..max], b <- [0..max]]. +-- +-- Returns `True` if a counter example was found. +-- Otherwise returns `False`. +counter' :: Natural -> Bool +counter' max = + case foldM f empty [0..max] of + Nothing -> True + Just _ -> False + where f accSums a = iter' a max accSums -iter' :: Natural -> Natural -> Map Natural Int -> Maybe (Natural, Map Natural Int) -iter' a max sums = foldM f sums [a..max] >>= continue - where continue updated = Just (a - 1, updated) - f sums b = test' a b sums +-- Checks if there is any counter example in [(a, b)| b <- [a..max]]. +-- Returns `Nothing` if a counter example was found. +-- +-- Otherwise returns `Just accSums`, where `accSums` maps every +-- computed value to the sum of it's digits. +iter' :: Natural -> Natural -> Map Natural Int -> Maybe (Map Natural Int) +iter' a max sums = foldM f sums [a..max] + where f accSums b = test' a b accSums exitInvalidInput :: IO Int -exitInvalidInput = exitWith (ExitFailure 2)- \ No newline at end of file +exitInvalidInput = exitWith $ ExitFailure 2+ \ No newline at end of file