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

Question

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

Answer 1

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

  -- print answer
  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

   putStrLn $ if a then "Yes" else "No"

But at that point the code get's rather terse and unreadable, and that's up to personal preference.