a-conjecture-of-mine

An exercise on polyglossy: the same problem solved on multiple languages

commit 637f5d917cfea52e68099b9275e3a349a1a7ec5c
parent c39e241cf1022dbdf765dc7c22cbaa3e544de349
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date:   Tue, 21 Jan 2020 10:17:02 -0200

Improved the efficiency of the Haskell implementation by caching the results of `sum'` in a `Vector Int` instead of accumulating them into a map.

Diffstat:
MHaskell/Main.hs | 46+++++++++++-----------------------------------
1 file changed, 11 insertions(+), 35 deletions(-)
diff --git a/Haskell/Main.hs b/Haskell/Main.hs
@@ -10,8 +10,7 @@ import Numeric.Natural
 import System.Environment
 import System.Exit
 import Control.Monad (foldM)
-import Data.Map (Map, insert, empty)
-import qualified Data.Map
+import Data.Vector (Vector, unsafeIndex, generate, (!))
 
 main :: IO Int
 main = do
@@ -26,51 +25,28 @@ main = do
           head' xs = Just (head xs)
 
 -- Calculates the sum of the digits of `n`.
-sum' :: Natural -> Int
+sum' :: Int -> Int
 sum' n
-     | n < 10 = fromEnum n
-     | otherwise = fromEnum (n `mod` 10) + sum' (n `div` 10)
+     | n < 10 = n
+     | otherwise = (n `mod` 10) + sum' (n `div` 10)
 
 -- Returns `Just updated` if the if the conjecture holds for pair, where
 -- `updated` is an updated versions of the sums cache provided by `sums`.
 -- Otherwise returns `Nothing`.
-test' :: Map Natural Int -> (Natural, Natural) -> Maybe (Map Natural Int)
-test' sums pair =
-    case diff sums pair of
-        Left updated ->
-            test' updated pair
-
-        Right dif ->
-            if dif `mod` 9 == 0 then Just sums else Nothing
-
--- Given a cache of the image of `sum'`, attemps to lookup `sum' a`, `sum' b`
--- and `sum' $ a + b`.
--- If the lookup succeeds, returns `Right (sum' (a + b) - sum' a - sum' a)`.
--- Otherwise inserts the value that caused the failure to `sums` and returns
--- `Left sums`.
-diff :: Map Natural Int -> (Natural, Natural) -> Either (Map Natural Int) Int
-diff sums (a, b) = do
-    sa  <- lookupOrInsert a
-    sb  <- lookupOrInsert b
-    sab <- lookupOrInsert $ a + b
-
-    pure $ sab - sa - sb
-    where lookupOrInsert x =
-            case Data.Map.lookup x sums of
-                Just sx -> Right sx
-                
-                Nothing -> Left (insert x (sum' x) sums)
+test' :: Vector Int -> (Int, Int) -> Bool
+test' sums (a, b) = diff `mod` 9 == 0
+    where diff = sums ! (a + b) - sums ! a - sums ! b
+          (!) = unsafeIndex
 
 -- Checks if there is any counterexample in
 -- [(a, b) | a <- [0..max], b <- [a..max]].
 --
 -- Returns `True` if a counter example was found.
 -- Otherwise returns `False`.
-counterexempl :: Natural -> Bool
+counterexempl :: Int -> Bool
 counterexempl max =
-    case foldM test' empty [(a, b) | a <- [0..max], b <- [a..max]] of
-        Nothing -> True
-        Just _  -> False
+    all (test' sums) [(a, b) | a <- [0..max], b <- [a..max]]
+    where sums = generate (2 * max + 1) sum'
 
 exitInvalidInput :: IO Int
 exitInvalidInput = exitWith $ ExitFailure 2