Feeds:
Posts
Comments

Archive for the ‘Functional Programming’ Category

Here is a problem to solve:

Open windows notepad and start with a blank document. At one step, you can choose to type one of
the four below on the keyboard:
“A” “CTRL+A” “CTRL+C” “CTRL+V”

What is the maximal number of A’s you can have in the notepad after 10 steps?

Since each step has 4 options, 10 steps will generate 410 = 1,048,576 key stroke combinations. For each combination, we calculate the number of A’s, and find the combination that results in the maximal number.

In order to calculate the number of A’s for a combination, we need to maintain a state that consists of the current number of A’s, the number of A’s in the clipboard, and whether all text is selected.

For each key stroke in a combination, we determine the next state based on the current state and the key stroke. For example, when A is pressed, if the text is all selected, the number of A’s becomes 1 and the text is not all selected; if the text is not all selected, the number of A’s increases by 1 and the text becomes unselected.

We can define a function that takes a state and a key, and returns a new state.

type Key =
    | A
    | CtrlA
    | CtrlC
    | CtrlV

type State = { number: int; numberCopied: int; allSelected: bool }

let keyStroke state key =
    let a state =
        match state.allSelected with
        | true -> { number = 1; numberCopied = state.numberCopied; allSelected = false }
        | false -> { number = state.number + 1; numberCopied = state.numberCopied; allSelected = false }

    let ctrlA state =
        { number = state.number; numberCopied = state.numberCopied; allSelected = true }

    let ctrlC state =
        match state.allSelected with
        | true -> { number = state.number; numberCopied = state.number; allSelected = state.allSelected }
        | false -> { number = state.number; numberCopied = 0; allSelected = state.allSelected }

    let ctrlV state =
        match state.allSelected with
        | true -> { number = state.numberCopied; numberCopied = state.numberCopied; allSelected = false }
        | false -> { number = state.number + state.numberCopied; numberCopied = state.numberCopied; allSelected = false }

    match key with
    | A -> a state
    | CtrlA -> ctrlA state
    | CtrlC -> ctrlC state
    | CtrlV -> ctrlV state

We defined a sub-function for each key stroke option, and call them depending on the key passed in.

Given a combination of key strokes, how do we calculate how many A’s generated? We can use the fold function.

let evaluate combination =
    let state = combination |> List.fold (fun state k -> keyStroke state k) { number = 0; numberCopied = 0; allSelected = false }
    state.number

For each key stroke in the list, the keyStroke function is called to transit to the next state, with { number = 0; numberCopied = 0; allSelected = false } as the initial state. The number field of the last state will be the number of A’s accumulated.

Once we have the combinations, we can pipe the combinations into the Seq.fold function to find the answer. The curr value is the current combination which is a tuple of the key list and the number of A’s the key list generates. The max value is the combination that has the biggest number of A’s so far. The final output value will be the answer.

let answer = 
    combinations()
    |> Seq.fold 
        (fun max curr -> 
            let (_, number) = curr
            let (_, maxNumber) = max
            if maxNumber < number then
                curr
            else
                max
            ) ([], 0)

Now the only thing missing is how to generate those key stroke combinations. There are several options:

Option 1, using computation expression

We can define a workflow builder class, named Solver, that implements the Bind and Return methods.

type Solver() =
    member this.Bind(xs, f) =
        xs
        |> List.map (fun x -> f(x))
        |> List.concat
    member this.Return(x) = [x]
    member this.Delay(f) = f

The Bind method returns a new list by applying the f function to each element of the given list. The Return methods just convert an element to a list.

We can then find all combinations with the following code:

let keyOptions = [ A; CtrlA; CtrlC; CtrlV ]

let solver = Solver()

let combinations = solver {
    let! k0 = keyOptions
    let! k1 = keyOptions
    let! k2 = keyOptions
    let! k3 = keyOptions
    let! k4 = keyOptions
    let! k5 = keyOptions
    let! k6 = keyOptions
    let! k7 = keyOptions
    let! k8 = keyOptions
    let! k9 = keyOptions

    let keys = [k0;k1;k2;k3;k4;k5;k6;k7;k8;k9]
    let state = keys |> List.fold (fun state k -> keyStroke state k) { number = 0; numberCopied = 0; allSelected = false } 
    return (keys, state.number)
}

The code is pretty easy to read once you understand how computation expressions work. I don’t quite like the fact that I had to write 10 let! bindings.

Option 2, using 2 bits to represent a key option

Since there are 4 key options, we can 2 bits to represent all key options, and 20 bits to represent all key combinations meaning we can use the numbers from 0 to 0xfffff to represent all key combinations of 10 steps with each step having 4 options. In the following code, the toCombination function converts a given number of a list of Keys. For each number from 0 to 0xfffff, we call toCombination to convert the number to a list of Keys and generate a sequence of lists of Keys using the sequence expression.

let keyOptions = [| A; CtrlA; CtrlC; CtrlV; |]

let toKey n =
    keyOptions |> Array.item n

let toCombination length number =
    let mask = 0x3
    [0..(length-1)] |> List.map (fun i -> ((number >>> i * 2) &&& mask |> toKey))

let allCombinations = seq {
    for i = 0 to 0xfffff do
        let c = toCombination 10 i
        yield (c, c |> evaluate)
}

The code is very simple, but what if, for example, there are 5 key options whereby using 3 bits is more than enough to represent 5 options?

Option 3, using a number system

We can generalize option 2 by using a number system with any base. Let’s say we want to have 10 steps and 5 key options, there will be totally 510 combinations. We convert each number from 0 to 510 to a base 5 number with 10 digits, each of which represents a key option.

let keyOptions = [| A; CtrlA; CtrlC; CtrlV; |]

let toKey n =
    keyOptions |> Array.item n

let toBase (b: int) (number: bigint) =
    let rec getDigits (n: bigint) digits =
        let bb = b |> bigint
        if n >= bb then
            let d = n % bb |> int
            let nn = n / bb
            getDigits nn (d::digits)
        else
            (n |> int)::digits

    getDigits number []
 
let toCombination b length (number: bigint) =
    let digits = toBase b number
    let diff = length - (digits |> List.length)
    match diff with
    | 0 -> digits
    | 1 -> 0::digits
    | _  -> [0 .. diff - 1] |> List.fold (fun s _ -> 0::s) digits

let allCombinations optionCount length = seq {
    let max = (double)optionCount ** (double)length |> bigint

    let _toCombination = toCombination optionCount length

    for i in 0I .. max do
        let c = _toCombination i |> List.map (fun i -> toKey i)
        yield (c, c |> evaluate)
}

The implementation is similar to option 2. The only difference is how to extract the digits from a number.

Conclusion

There are many ways to generating the key combinations. In fact, we can also use List.collect with List.map in a recursive function to generate the all combinations:

let allCombinations length options = seq {
    let rec expand currLength combinations =
        match currLength = length with
        | true -> combinations
        | false -> 
            expand (currLength + 1) (options |> List.collect (fun o -> combinations |> List.map (fun c -> o::c)))

    yield! expand 1 (options |> List.map (fun o -> [o])) 
}

I’ve gained more knowledge about F# and functional programming in general when I was exploring various solutions. I particularly like the fold function which allows me to mutate a state in purely functional way.

By the way, the answer of the problem is:

val answer : Key list * int =
([A; A; A; A; CtrlA; CtrlC; CtrlV; CtrlV; CtrlV; CtrlV], 16)

Thanks for reading!

Read Full Post »