How to solve the ransom note problem functionally

user_366817 0
Viewed 109

Write a function that given a list of letters what and a word, returns true if the word can be spelt using the letters from the list and false if not. For example a list like

['a';'b';'d';'e';'a']

and the word

bed

the function should return true. If the word was bbed it should also return false because there is only one b in the list.

This is easy enough to do imperatively by mutating the state of the dictionary in a for loop but how can one do it in a more functional style without mutation?

Here's the imperative version I did:

open System.Collections.Generic

let letters = new Dictionary<char,int>()
[ ('a', 2); ('b', 1); ('c', 1); ('e', 1) ] |> Seq.iter letters.Add

let can_spell (word : string) =
    let mutable result = true
    for x in word do
        if letters.ContainsKey x && letters.[x] > 0 then
            let old = letters.[x]
            letters.[x] <- old - 1
        else
            result <- false
    done
    result
f# functional-programming
2 Answers

You can use 2 dictionaries to keep track of the counts by letter of the word and the existing letters and then check that the letter count is greater than the word letter count:

let contains (word:string)(letters:IDictionary<char,int>) = 
    let w = word
            |>Seq.countBy id
            |>dict

    w.Keys
    |>Seq.map(fun k-> letters.ContainsKey k && letters.[k] >= w.[k])
    |>Seq.reduce(&&)

and you can use it like this

let letters = 
    [ ('a', 2); ('b', 1); ('c', 1); ('e', 1); ('d', 1)] 
    |> dict

contains "bed" letters // True
user_78462760

I would do like this:

let can_spell2 letters word =
    let uniqueLettersCount =    //group unique letters from words and count them
        word |> Seq.groupBy id
        |> Seq.map (fun (l,s) -> l,Seq.length s)
    
    uniqueLettersCount          //keep taking the sequence until you don't find a key or the key count is below the unique letter number
    |> Seq.takeWhile (fun (c,n) ->
        match Map.tryFind c letters with
        | Some n' -> if n' >= n then true else false
        | None -> false)
    |> fun s -> if Seq.length s = Seq.length uniqueLettersCount then true else false //if takeWhile didn't stop, the word is allowed

EDIT:

Examples of usage:

let letters = ['a',2;'b',1;'c',1;'e',1] |> Map.ofList

can_spell2 letters "aab" //true
can_spell2 letters "aaba" //false
can_spell2 letters "bf" //false
can_spell2 letters "ecaba" //true
user_58315650
Related