# HackerRank Ransom Note, solved using Data.Map as a hash table

I try to solve this hackerrank using Haskell but not sure if I use Data.Map corretly.

Problem in brief:

• given 2 strings, magazine and note
• check if you can make note from words in magazine

Here is my code, which passes all the tests.

import Control.Applicative
import qualified Data.Map as M

readInts =  map read . words <$> getLine :: IO [Int] main = do [a,b] <- readInts ms <- words <$> getLine
ls <- words <$> getLine -- create magazine words table let mss = zip ms (repeat 1) let mms = M.fromListWith (+) mss -- create note words table let lss = zip ls (repeat 1) let lms = M.fromListWith (+) lss -- check for intersections, decrease wordcount for every intersection let dm = M.intersectionWith (-) mms lms -- see if any words need more than it avaliablity let a = M.filter (<0) dm -- print answer putStrLn$ if a == M.empty then "Yes" else "No"


If I would do this problem in python I would use a dictionary of int with string key

for example;

magazine["word"] = 3
note["word"] = 1


would give a Yes answer since there is enougth word to use

This will be a list of "don't"s, since your code is very readable, but contains some code smells. It doesn't actually solve the puzzle, but more on that later.

# Data.Map.Map is not a hashtable

I just want to get something out of the way first: Data.Map isn't a hash table. A hash table needs a function $\text{hash}: A \to I$, where $I$ is some finite, bounded and integral set with $|A|\gg|I|$. An efficient hash map/table uses buckets and provides a best case $\mathcal O(1)$ access if implemented correctly. Data.Map only provides $\mathcal O(\log k)$ access, since it's implemented as a tree. That's why you need the Ord constraint on almost all functions in Data.Map.

However, it's still a nice data structure for this problem.

Python's dictionaries on the other hand are based on hashable functions.

# Don't give names to things you won't use

  [a,b] <- readInts


You don't actually use a or b. You don't actually use that line at all. That line is meant for languages like C, where you need to manage memory yourself, e.g.

int ok = scanf("%d %d",&a,&b);
ptr_t words = malloc(...);
ptr_t words = malloc(...);


You get it. However, since you never use them, just ignore that line, e.g.

main = do
_ <- getLine -- ignore first line
ms <- ...


# Don't repeat yourself

The first thing one notices immediately is duplicate code:

  -- create magazine words table
let mss = zip ms (repeat 1)
let mms = M.fromListWith (+) mss

-- create note words table
let lss = zip ls (repeat 1)
let lms = M.fromListWith (+) lss


That should be a function, e.g.

count :: Ord a => [a] -> Map a Int
count xs = M.fromListWith (+) (zip xs (repeat 1))


# An intersection isn't what you want

Let's think about the following magazine and words:

> let ms = words "this stranger was giving a code review. the next thing will blow your mind"
> let ws = words "we have your daughter"


Lets use count on bothmsandwsand thenintersectionWith:

> intersectionWith (-) (count ms) (count ws)
fromList [("your",0)]


Huh. That's strange. Could we actually form that ransom note? No. We're missing "we", "have", and "daughter". So what can we conclude?

1. intersectionWith isn't correct, since there might be elements in the ransom note that aren't in the magazine.
2. Hackerrank is missing edge cases.

What should we do instead? Well, we can flip the sign on the words map and then use the union:

subtractMap :: (Ord k, Num a) => Map k a -> Map k a -> Map k a
subtractMap a b = M.unionWith (+) a (fmap negate b)


Why is it important to negate, and not simply unionWith (-)? Because the operation will only take effect if there are elements with the same key in both maps.

# Put it all together

So, you've used Data.Map correctly, except for the intersectionWith, which didn't come up because the test cases were borked. Otherwise, everything was fine, except for the things mentioned above.

Here's the code that implements all the suggestions above. Note that type signatures on top-level functions are very recommended:

import Control.Applicative
import           Data.Map (Map)
import qualified Data.Map as M

count :: Ord a => [a] -> Map a Int
count xs = M.fromListWith (+) (zip xs (repeat 1))

subtractMap :: (Ord k, Num a) => Map k a -> Map k a -> Map k a
subtractMap a b = unionWith (+) a (fmap negate b)

main :: IO ()
main = do
_ <- getLine -- ignore first line
mss <- (count . words) <$> getLine lss <- (count . words) <$> getLine

-- subtract occurrences in the words from the magazine
let dm = subtractMap mms lss

-- see if any words need more than it avaliablity
let a = M.filter (<0) dm

putStrLn $if M.null a then "Yes" else "No"  You could also put words into count, if you want to get the duplication even more down, or you could write solve :: String -> String -> Bool solve ms ws = M.null (M.filter (<0) (subtractMap (count ms) (count ws))) main = do getLine a <- solve <$> getLine <*> getLine

• For unused names, I found to be a good practice to also use -fwarn-unused-do-bind, which requires do statements that return a value to be ignored to be written as _ <- statement`. – Petr Pudlák Nov 12 '16 at 18:51