HackerRank: Counting Sort 1

Question

I've just solved this challenge, though I feel that there is a problem with stack growth or something because the 5th testcase has a runtime error

import Control.Monad
import Data.Sequence hiding (replicateM, replicate, take, drop)
import Data.List

main :: IO ()
main = do n <- getLine
          input <- getLine
          putStrLn (unwords (map show (calc (map read (words input)) (output))))

output :: [Int]
output = replicate 100 0

calc :: [Int] -> [Int] -> [Int]
calc [] y      = y
calc (x:xs) ys = calc xs ((take (x) ys) ++ ((ys!!x) + 1):(drop (x+1) ys))

I feel that there should be a much neater solution, which doesn't cause an overflow as this is quite messy.

It would be nice to get everyone's thoughts on more efficient/nicer solutions

Answer 1

Let's imagine this problem as building a histogram. We draw out an X axis of 100 (0 <= x < 100, as given by the problem). For each element that we're given, we move the bar up by one in the histogram.

For something like this we have Data.Array. We can build an Array Int Frequency that will map each number to the frequency of the number. Each insertion into the array will be O(1). Initializing the array will also be O(1) since the size of the array is fixed. We'll just have the computer set aside 100 slots of memory for us up top, every time. This should lead to a running time of initialization + n * insertion = O(n), which indeed beats O(n lg n).

Our function will have this type:

count :: [Int] -> Array Int Int
count input = _

The best way to build an array is to ... uh ... I never remember. So we consult the docs, specifically the array construction section. There's a function here called accumArray that folds over a list of (index, value) tuples – that is, it walks each tuple and uses it to accumulate into a value into the array that is returned back to us. In our case, each tuple will be (number, 1): we'll have it so that each tuple represents a single count of the number. Our job is then to convert a bunch of tuples like this

(2, 1) (5, 1) (5, 1) (3, 1)

to a histogram like this

0: 0
1: 0
2: 1
3: 1
4: 0
5: 2

Back to our code:

count :: [Int] -> Array Int Int
count input = accumArray _ _ (0, 99) (zip input (repeat 1))

The trick here is that repeat 1 is an infinite array, but we know input is finite and zip terminates when either argument terminates.

It remains to specify the accumulating function, which takes two arguments (the frequency of the number thus far and then second value of our tuple, which is always the number 1) and is supposed to return the new frequency. This is as simple as incrementing the old number, or just adding one.

count :: [Int] -> Array Int Int
count input = accumArray (\old one -> old + one) _ (0, 99) (zip input (repeat 1))

This being Haskell, we can simplify this to

count :: [Int] -> Array Int Int
count input = accumArray (+) _ (0, 99) (zip input (repeat 1))

For the greater good. And we're done! Oh, and we need to specify a default frequency for values that we didn't encounter in the list. For us, that's a simple zero.

Combining this with your IO code that reads from stdin, we get:

import Data.Array
import Data.List

main :: IO ()
main = do
  _ <- getLine
  numbers <- getLine
  (putStr . unwords . map show . elems . count . map read . words) numbers

count :: [Int] -> Array Int Int
count input =
  accumArray (+) 0 (0, 99) (zip input (repeat 1))

And if we wanted to be a smart-ass we could golf the solution into a one-liner:

import Data.Array
import Data.List

main :: IO ()
main = getLine >> getLine >>= (putStr . unwords . map show . elems . accumArray (+) 0 (0, 99) . flip zip (repeat 1) . map read . words)

I think that last line even fits into a tweet.