Last active
September 13, 2021 17:25
-
-
Save rebeccaskinner/9c5f29516e03a44cb01845225ec6e832 to your computer and use it in GitHub Desktop.
FindMax.hs
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| module FindMax where | |
| import System.Environment (getArgs) | |
| import GHC.Arr | |
| import Control.Monad | |
| import Control.Monad.ST | |
| import Text.Printf | |
| -- | The multiplier that we use when calculating occurrences is the | |
| -- maximum number in the array, plus one. We can only use the modulo | |
| -- offset algorithm when the largest number in the input list is less | |
| -- than, or equal to, the size of the list. | |
| findMultiplier :: [Int] -> Maybe Int | |
| findMultiplier [] = Nothing | |
| findMultiplier nums = | |
| let largestNum = maximum nums | |
| in if largestNum > length nums | |
| then Nothing | |
| else Just (largestNum + 1) | |
| -- | In this function we iterate through the list of numbers. For each | |
| -- number in the list, we read that number and update a different | |
| -- index in the list based on it's value. We do this by taking the | |
| -- element at the current index, and computing a new index with | |
| -- (currentElement % multiplier). We add the multiplier value to the | |
| -- value at the new index. | |
| -- Multiplier is given by the findMultiper function. | |
| findCounts :: [Int] -> Int -> [Int] | |
| findCounts input multiplier = runST $ do | |
| let inputSize = length input - 1 | |
| inputArray <- thawSTArray $ listArray (0, inputSize) input | |
| forM_ [0..inputSize] $ \index -> do | |
| valueAtIndex <- readSTArray inputArray index | |
| let indexToIncrement = valueAtIndex `mod` multiplier | |
| oldValueAtTargetIndex <- readSTArray inputArray indexToIncrement | |
| writeSTArray inputArray indexToIncrement (oldValueAtTargetIndex + multiplier) | |
| finalArray <- freezeSTArray inputArray | |
| pure (elems finalArray) | |
| -- | Find the index of the largest value in the list. | |
| findMaxIndex :: [Int] -> Int | |
| findMaxIndex numbers = | |
| fst $ foldr findMaximumIndex (0,0) (zip [0..] numbers) | |
| where | |
| findMaximumIndex :: (Int, Int) -> (Int,Int) -> (Int,Int) | |
| findMaximumIndex (currentIndex, currentNumber) (largestIndex, largestNumber) = | |
| if currentNumber > largestNumber | |
| then (currentIndex, currentNumber) | |
| else (largestIndex, largestNumber) | |
| -- | Run the program with a given number list and multipliers. | |
| runProgram :: [Int] -> Int -> Int | |
| runProgram numbers multiplier = | |
| findMaxIndex (findCounts numbers multiplier) | |
| -- | get command line arguments in the form of "1 2 3 4" and turn them | |
| -- into a list of integers "[1,2,3,4]" | |
| getArguments :: IO [Int] | |
| getArguments = do | |
| argumentsAsStrings <- getArgs | |
| return (map read argumentsAsStrings) | |
| main = do | |
| numbers <- getArguments | |
| case findMultiplier numbers of | |
| Nothing -> | |
| print "Sorry! There's no valid way to process this" | |
| Just multiplier -> | |
| print (runProgram numbers multiplier) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment