FindMax.hs

FindMax.hs

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)