re: Daily Coding Puzzles - Nov 4th - Nov 9th VIEW POST

TOP OF THREAD FULL DISCUSSION
re: Thursday Scramblies (5 KYU): Complete the function scramble(str1, str2) that returns true if a portion of str1 characters can be rearranged to m...
 

F#

let scramble str1 str2 =
    let letterLookup = str1 |> Seq.countBy id |> Map.ofSeq
    let requiredCounts = str2 |> Seq.countBy id
    requiredCounts |> Seq.forall (fun (letter, requiredCount) ->
        match letterLookup |> Map.tryFind letter with
        | None -> false // letter missing
        | Some count -> requiredCount <= count
    )

Edit: I had previously posted a version that had ever-so-slightly more performance but was more code. I'm also including that version below since it solves the problem differently.

let scramble str1 str2 =
    let letterPool = str1 |> Seq.sort |> List.ofSeq
    let requiredLetters = str2 |> Seq.sort |> List.ofSeq
    let rec loop requiredLetters letterPool =
        match requiredLetters, letterPool with
        | [], _ -> true // found all
        | _ :: _, [] -> false // pool ran out
        | letter :: _, next :: pool when letter > next ->
            loop requiredLetters pool // skip next in pool
        | letter :: required, next :: pool when letter = next ->
            loop required pool
        | _, _ -> false // letter not available in the pool
    loop requiredLetters letterPool

Here are the tests (console).

    [
        "rkqodlw", "world", true
        "cedewaraaossoqqyt", "codewars", true
        "katas", "steak", false
    ]
    |> List.iter (fun (str1, str2, expected) ->
        let actual = scramble str1 str2
        let e = if expected = actual then "√" else "X"
        printfn "%s %A ==> %b, %b" e (str1, str2) expected actual
    )
    // √ ("rkqodlw", "world") ==> true, true
    // √ ("cedewaraaossoqqyt", "codewars") ==> true, true
    // √ ("katas", "steak") ==> false, false
 

Nice! yeah -- I only sometimes think about the efficiencies of these. They're contrived and we're doing them for fun. Part of me cares, part of me doesn't haha

I agree. I would have posted a much more expressive version, but you beat me to it! I did find an alternative way of solving the problem that was a little more expressive and nearly the same perf. I updated my post to include it.

code of conduct - report abuse