Feeds:
Posts

## Solving problems with F# – maximal number of A’s

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 =
[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)

## Solving Cryptarithmetic problems using F#

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
```

## Functional design patterns

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

## Lego Robot

I participated in a Lego Robot Competition recently, and our team of 5 persons won the first prize. Our robot successfully accomplished its mission: picking up a treasure, a Lego block in red color, and putting it in the dropping area inside a maze, exiting the maze, and hunting for the next treasure.

## Components of the robot

Figure 1. The Lego Robot

The robot consists of a Samsung Galaxy S4 Android phone, a Rockwell MicroLogix 830 controller, 3 Lego motors, a Xiaomi power bank, and several infra-red distance sensors. The phone connects to the MicroLogix controller via an USB OTG cable, an USB to serial converter, and a serial cable. The communication protocol between the phone and the controller is MODBUS over serial line.

The Android app is the brain of the robot. It captures pictures periodically to detect treasures and the 3 mazes (in blue, green and purple color respectively) and reads the values of the sensors to determine what to do next. It sends commands to the controller to make a move, a turn, pick up or put down a treasure. The controller is not entirely passive: it can stop the robot when it detects that it is too close to a wall.

The PLC (Programmable Logical Controller) logic running in the controller uses PID to control the motors to make accurate moving or turning.

## The Android app

The Android app is built on top of 2 open source libraries: OpenCV (http://opencv.org/) and the jamod Modbus library
(http://jamod.sourceforge.net/). The OpenCV library is used to capture pictures and detect objects from the pictures; while the jamod library is used to send commands and read sensor values to and from the MicroLogix controller. (I’ve made some modification to the jamod library to make it working with Android serial driver.)

At the heart of the Android app is the Robot class. A Robot object has a RobotCommander for sending commands to the MicroLogix controller, a RobotSensors object for reading sensor values, several ObjectDetectors for detecting treasures, mazes, outer walls, and the dropping area.

Figure 2. The class diagram of the Robot class.

## State machines

The behavior of the Robot is controlled by the state machines. The top level state machine has 5 states: Initial, Initialized, Running, Paused, and Stopped. After the Robot is initialized it can be put into the Running state. When in the Running state, it can be Stopped, it can also be Paused and then resumed to the Running state.

Figure 3. The top level state machine

The Running state itself is a state machine that has 9 sub-states, as shown in Figure 4: FindingTreasure, ApproachingTreasure, PickingTreasure, FindingMaze, ApproachingMaze, FindingMazeEntrance, FindingDropArea, DroppingTreasure, and ExitingMaze.

The Robot first searches for a treasure. Once a treasure is found, it moves towards the treasure, and picks it up. It them searches for a maze, approaches it, and finds the entrance. Once it is in a maze, it looks for the drop area, drops the treasure, exits the maze, and starts over again.

Figure 4. The sub-state machine of the Running state

Each sub-state corresponds to a state machine, which we call a Sequence. Figure 5 shows the state diagram of the Finding Treasure state.

Figure 5. Finding Treasure sequence

### The implementation of state machines

Two interfaces, IStateMachine and IState, as shown in Figure 6, are defined for implementing the state machines. IState represents a state. Upon entering or exiting a state, the enter() or exit() method is called respectively. The move() method will be called one or more times when the state is active to allow the Robot to make a move. IStateMachine represents a state machine. It can change the current active state and have the current state to make a move.

Figure 6. IStateMachine and IState

Figure 7 shows all classes that implement the IStateMachine interface. Class RobotStateMachine implements the top-level state machine as shown in Figure 3 and class RobotRunningStateMachine implements the sub-state machine as shown in Figure 4. Class RobotRunningSequence is the base class of sequences. Each sub-class of RobotRunningSequence corresponds to a state of the sub-state machine.

Figure 7. State machines

When the Robot object is in the Running state, the continueMission() method is called periodically, which calls move() on the RobotStateMachine object, which calls move() on the current state, Running, which calls move() on the RobutRunningStateMachine object, which calls move() on the current sequence. If the m_nextState member variable is not null, it calls changeState(), which calls exit() on the current state, makes m_nextState the current state, and calls enter() on it. It finally calls move() on the current state, which would most likely calls sendCommand on the Robot object to send a command to the controller.

Figure 8. State machines sequence diagram

The states of a state machine are implemented using a Java enum, with each enum field representing a state. The following code shows how the top-level states are defined.

```public enum RobotState implements IState {
Initial {
@Override
public void enter(IStateMachine machine) {
}
@Override
public void move(IStateMachine machine) {
machine.robot().initialize();
machine.changeState(Initialized);
}
@Override
public void exit(IStateMachine machine) {
}
},
Initialized {
@Override
public void enter(IStateMachine machine) {
machine.robot().ensureArmAtHome();
}
@Override
public void move(IStateMachine machine) {
// wait
}
@Override
public void exit(IStateMachine machine) {
}

},
Running {
@Override
public void enter(IStateMachine machine) {
m_runningMachine.afterResume();
machine.robot().log("Enter Running state", 2);
}
@Override
public void move(IStateMachine machine) {
m_runningMachine.move();
}
@Override
public void exit(IStateMachine machine) {
// do nothing
}

},
Paused {<
@Override
public void enter(IStateMachine machine) {
m_runningMachine.beforePause();
}
@Override
public void move(IStateMachine machine) {
machine.waitForResume();
}
@Override
public void exit(IStateMachine machine) {
}

},
Stopped {
@Override
public void enter(IStateMachine machine) {
machine.robot().sendCommand(RobotAction.Stop);
}
@Override
public void move(IStateMachine machine) {
machine.robot().sleep(200);
}
@Override
public void exit(IStateMachine machine) {
}
}
}```

ThreadingEvery enum field is in fact a class. This makes the code more concise by not having to explicitly define a Java class for each state.

In an Android app, if the UI thread is blocked for more than 5 seconds the app will be forced to be stopped. To avoid running into this scenario, the entire state machine is running on a worker thread. When a Robot object is created, a work thread is created with a Runnable object whose run() method periodically calls the continueMission() method, which calls the move() method on the RobotStateMachine object.

In the TestSequenceActivity, a RobotTask class, inheriting from AsyncTask, is defined to test individual sequences using a worker thread.

In order to avoid the changeState() and move() methods of RobotStateMachine to be called by the UI thread, the methods throw an exception if the calling thread is the main thread.

```public void move() {
if (Looper.myLooper() == Looper.getMainLooper()) {
throw new RuntimeException("move() cannot be called by the main thread");
}
…
}```

## Debugging

When the Android app is running, we cannot use Eclipse to debug the app as the USB port is used to connect to the controller. We chose to use log to help us understand what is going on. We create some Android Activities specially for debugging, e.g. an Activity for testing Modbus communication, an Activity for testing sending commands to the controller, and an Activity for testing individual sequences. The log of the debugging Activities provides much detailed information, while the log of the run mode Activity, RobotActivity, provides only important information.

An interface named IRobotLogger is defined for the Activities to implement to display logging information. When the log() method is called, if the logging level is equal to or higher than the lowest  logging level it is interested in, it appends the string passed in to the TextView.

Since the state machines are all running on a worker thread, the log() method cannot directly call the append() method on the TextView, instead it should send a request to the UI thread to do so by calling the runOnUiThread() on the Activity.

```public void log(final String msg) {
public void run() {
TextView logDisplay = (TextView) findViewById(R.id.text_log);
logDisplay.append(msg + "\n");
}
});
}
```

## Points of Interest

Adopting the State design pattern makes our code much easier to understand and debug. Even though only myself was working on the Java code debugging, the well understood behavior of each state machine plus the detailed log allow other team member to help me understand what was going on, and thus greatly shorten our debugging time.

When we designed the classes of the model, we had unit-testability in mind, although we hadn’t written much unit tests, as we were implementing the App in a rush. We defined some interfaces, such as IRobotCommander, IRobotSensors, to make them mockable.

Debuggability is the key for us to develop the app in such a short time with relatively good quality. The activities developed specially for debugging help us troubleshoot the issues we encountered quickly.

Using the Modbus protocol for the communication between the phone and the controller removes a lot of burden in both the Android app and the PLC code compare with using serial port communication directly.

If I had a chance to develop a similar app, I would consider developing a DSL (Domain Specific Language) for defining the sequences: defining how the states should be changed depending on the sensor values and the object detection result. This would allow non-Java developers to define and debug the sequences. I would also enhance the object detection by utilizing more OpenCV functionality.

We often use ‘simple’ and ‘easy’ interchangeably. This presentation given by Rich Hickey makes it clear about the difference between the two words. Simple is objective. Easy is relative. Some thing may be very easy to someone, but very hard to others. When we say something is easy, it might be because we are familiar with it. It doesn’t necessarily means it is simple.

## BarModel Script

I’ve written an article introducing the syntax, the semantic model and the graphical model of the BarModel script I’ve designed for “drawing” bar models by writing scripts.

https://wuxuesong.files.wordpress.com/2015/04/barmodel-script.pdf