Feeds:
Posts
Comments

Posts Tagged ‘Functional Programming’

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!

Advertisements

Read Full Post »

I was given a puzzle to solve recently. The puzzles is a cryptarithmetic problem: 5’s twelve + thirty = ninety.

T W E L V E
T W E L V E
T W E L V E
T W E L V E
T W E L V E
T H I R T Y
————
N I N E T Y

Each letter represents a unique number from 0 to 9.

As a software engineer, I naturally wanted to solve this problem by writing a program, and I decided to use F#, in functional way.

Here is the code I wrote:

open System

let digits = [0..9] |> Set.ofList

let remainingDigits removedDigits =
    Set.difference digits (Set.ofList removedDigits)

let toNumber digits =
    digits |> List.fold (fun number i -> number * 10 + i) 0

type PuzzleSolver() =
    member this.Bind(xs, f) =
        xs
        |> Set.map (fun x -> f(x))
        |> Set.filter (fun x -> x |> List.isEmpty |> not)
        |> Set.toList
        |> List.concat

    member this.Return(x) = [x]
    member this.ReturnFrom(x) = x

let solver = PuzzleSolver()

let solutions = solver {
    let! t = remainingDigits [0]
    let! w = remainingDigits [t]
    let! e = remainingDigits [t; w]
    let! l = remainingDigits [t; w; e]
    let! v = remainingDigits [t; w; e; l]
    let! h = remainingDigits [t; w; e; l; v]
    let! i = remainingDigits [t; w; e; l; v; h]
    let! r = remainingDigits [t; w; e; l; v; h; i]
    let! y = remainingDigits [t; w; e; l; v; h; i; r]
    let! n = remainingDigits [t; w; e; l; v; h; i; r; y]

    let TWELVE = toNumber [t; w; e; l; v; e]
    let THIRTY = toNumber [t; h; i; r; t; y]
    let NINETY = toNumber [n; i; n; e; t; y]

    if (TWELVE * 5 + THIRTY = NINETY) then
        return! [ ("T", t); ("W", w); ("E", e); ("L", l); ("V", v); 
                  ("H", h); ("I", i); ("R", r); ("Y", y); ("N", n) ]
    else return! []
}

solutions |> List.iter (fun (l, v) -> printfn "%s = %d" l v)

And the following is the result copied from the F# Interactive console of Visual Studio:

T = 1
W = 3
E = 0
L = 7
V = 6
H = 9
I = 4
R = 2
Y = 5
N = 8

val digits : Set<int> = set [0; 1; 2; 3; 4; 5; 6; 7; 8; ...]
val remainingDigits : removedDigits:int list -> Set<int>
val toNumber : digits:int list -> int
type PuzzleSolver =
    class
        new : unit -> PuzzleSolver
        member
            Bind : xs:Set<'c> * f:('c -> 'd list) -> 'd list
                when 'c : comparison and 'd : comparison
        member Return : x:'b -> 'b list
        member ReturnFrom : x:'a -> 'a
end

val solver : PuzzleSolver

val solutions : (string * int) list =
[("T", 1); ("W", 3); ("E", 0); ("L", 7); ("V", 6); ("H", 9); ("I", 4);
("R", 2); ("Y", 5); ("N", 8)]
val it : unit = ()

Let’s look at the F# code. The digits value is a set of 10 integers from 0 to 9. The remainingDigits function removes the given integers from the digits set and returns the remaining digits. The toNumber function converts the given digits to an integer.

At the heart of the algorithm is the PuzzleSolver computation expression. The Bind method takes a Set and a function that maps a value to a list, and returns a list.

member this.Bind(xs, f) =
    xs
    |> Set.map (fun x -> f(x))
    |> Set.filter (fun x -> x |> List.isEmpty |> not)
    |> Set.toList
    |> List.concat

The Bind() method pipes the given set to the Set.map function to create a set of list by mapping each element in the set to a list by calling the f function passed in. It then pipes the set of lists to Set.filter to create a new set by removing all empty lists. The new set of lists is then converted to a list of lists, which is passed to List.concat to flatten to a list.

The Return method just wraps the given value as a list. And the ReturnFrom method just returns the given value.

With the PuzzleSolver computation expression, we can solve the puzzle with following code:

let solutions = solver {
    let! t = remainingDigits [0]
    let! w = remainingDigits [t]
    let! e = remainingDigits [t; w]
    let! l = remainingDigits [t; w; e]
    let! v = remainingDigits [t; w; e; l]
    let! h = remainingDigits [t; w; e; l; v]
    let! i = remainingDigits [t; w; e; l; v; h]
    let! r = remainingDigits [t; w; e; l; v; h; i]
    let! y = remainingDigits [t; w; e; l; v; h; i; r]
    let! n = remainingDigits [t; w; e; l; v; h; i; r; y]

    let TWELVE = toNumber [t; w; e; l; v; e]
    let THIRTY = toNumber [t; h; i; r; t; y]
    let NINETY = toNumber [n; i; n; e; t; y]

    if (TWELVE * 5 + THIRTY = NINETY) then
        return! [ ("T", t); ("W", w); ("E", e); ("L", l); ("V", v);
                  ("H", h); ("I", i); ("R", r); ("Y", y); ("N", n) ]
    else return! []
}

The code essentially says that:

Let the identifier t be one of the digits from 1 to 9,

Let the identifier w be one of the digits from 0 to 9 except for t,

We bind each of the 10 identifiers to a different digit, we then calculate the values of TWELVE, THIRTY, and NINETY, if the 3 values meet the condition, which is TWELVE * 5 + THIRTY = NINETY, we return a list of pairs of a letter and the digit it represents, otherwise, an empty list is returned.

The let! Expression is just a syntax sugar for the Bind method. So

let! t = remainingDigits [0]

is essentially translated into

solver.Bind(remainingDigits [0], (fun t -> …) )

And the whole solutions expression is translated into nested method calls to the solver.Bind() method:

let solutions =
    solver.Bind(remainingDigits [0], fun t ->
    solver.Bind(remainingDigits [t], fun w ->
    solver.Bind(remainingDigits [t; w], fun e ->
    solver.Bind(remainingDigits [t; w; e], fun l ->
    solver.Bind(remainingDigits [t; w; e; l], fun v ->
    solver.Bind(remainingDigits [t; w; e; l; v], fun h ->
    solver.Bind(remainingDigits [t; w; e; l; v; h], fun i ->
    solver.Bind(remainingDigits [t; w; e; l; v; h; i], fun r ->
    solver.Bind(remainingDigits [t; w; e; l; v; h; i; r], fun y ->
    solver.Bind(remainingDigits [t; w; e; l; v; h; i; r; y], fun n ->

    let TWELVE = toNumber [t; w; e; l; v; e]
    let THIRTY = toNumber [t; h; i; r; t; y]
    let NINETY = toNumber [n; i; n; e; t; y]

    if (TWELVE * 5 + THIRTY = NINETY) then
        solver.ReturnFrom([ ("T", t); ("W", w); ("E", e); ("L", l); ("V", v);
                            ("H", h); ("I", i); ("R", r); ("Y", y); ("N", n) ])
    else solver.ReturnFrom([])
))))))))))

This is not too difficult to understand compared to the nested for loops if we were to solve it in imperative way.

let solutions2 =
    for t in (remainingDigits [0]) do
    for w in (remainingDigits [t]) do
    for e in (remainingDigits [t; w]) do
    for l in (remainingDigits [t; w; e]) do
    for v in (remainingDigits [t; w; e; l]) do
    for h in (remainingDigits [t; w; e; l; v]) do
    for i in (remainingDigits [t; w; e; l; v; h]) do
    for r in (remainingDigits [t; w; e; l; v; h; i]) do
    for y in (remainingDigits [t; w; e; l; v; h; i; r]) do
    for n in (remainingDigits [t; w; e; l; v; h; i; r; y]) do

        let TWELVE = toNumber [t;w;e;l;v;e]
        let THIRTY = toNumber [t;h;i;r;t;y]
        let NINETY = toNumber [n;i;n;e;t;y]

        if (TWELVE * 5 + THIRTY = NINETY) then
            printfn "TWELVE=%d, THIRTY=%d, NINETY=%d" TWELVE THIRTY NINETY

Read Full Post »

These are the notes I took when reading the slides written by Scott Wlaschin.

Functional Design Patterns Scott Wlaschin

Read Full Post »

 

 

 

 

The following are the notes I took (using XMind) when reading the “Thinking Functionally” series on F# for fun and profit.
Thinking Functionally

Read Full Post »