## Random number Generation with RNG

I would like to mention a question that posed on stackoverflow a year back, with a slight change.

Given a function which produces a random integer in the range 0 to 4, write a function which produces a random integer in the range 0 to 6.

Simply, we have let ran5() = new Random().Next(5), we would like to write ran7 using ran5, and without any other random number generator
The answers are rather interesting for this question, as it is important to have a uniformly distributed random number generator.
The first attempt, is a naive way to generate the random number by defining the sample set small.

//random number generator with 6 numbers let ran = new Random() let random5() = ran.Next(5)   //naive let rantbl = [| 0 .. 6 |]   let rec random7() = let i,j = random5(), random5() let sum = i + j if sum < rantbl.Length then rantbl.[sum] else random7()

Now, if you run the sample, it will generate the random numbers to 7 just fine, but it won’t be uniformly distributed, and will converge to a number as we run infinite times.
However, if we define our initial set uniformly to match out number generator, in this case we can generate 5 numbers, so a set of 25, we can hit each element by the multiplication of those two generators

//based on let randomTable = [|for i in 0 .. 24 do if i / 7<3 then yield i % 7 else yield -1 |] let rec random7_2() = let i,j = random5(), random5() let index = i * 5 + j if randomTable.[index] <> -1 then randomTable.[index] else random7_2()   let sampler sample = seq { for i in 0 .. 100000 do yield sample() }
val ran : Random
val random5 : unit -> int
val rantbl : int array
val it : int array = [|0; 1; 2; 3; 4; 5; 6|]
val randomTable : int array
val it : int array = [|0; 1; 2; 3; 4; 5; 6; 0; 1; 2; 3; 4; 5; 6; 0; 1; 2; 3; 4; 5; 6; -1; -1; -1;
-1|]
val random7 : unit -> int
val random7_2 : unit -> int
val sampler : (unit -> ‘a) -> seq<'a>

We can estimate of the value of a random variable and predict the error, which is proportional to the iterations. Since we have 2 sets, we can analyse and compare their statistical properties.

let variance sample N = let mean = sample |> Seq.average_by (fun i-> float i) (sample |> Seq.sum_by (fun i->(float i - mean) * (float i - mean) )) / N let standardDeviation varian= sqrt (varian)   let standardError sample = let N = float (Seq.length sample) let vari = variance sample N let stDev = standardDeviation vari stDev / (sqrt N)   let sample = sampler random7 standardError(sampler random7 ) standardError (sampler random7_2)   // uniform distribution let errorSet mySet = let N = Seq.length mySet |> float mySet |> Seq.count_by (fun e-> e) |> Seq.map (fun (i,j) -> i, (float j)/N * 100.0) |> Map.of_seq   errorSet (sampler random7) errorSet (sampler random7_2)
val variance : seq -> float -> float
val standardDeviation : float -> float
val standardError : seq -> float
val sample : seq
val errorSet : seq<'a> -> Map<'a,float>

.

## Happy Pi Day and Monte Carlo Method

### Pi Calculation

Today is the $\pi$ day, 03/14 2010. Happy $\pi$day to all!

The Monte Carlo method generates multiple trials to determine the expected value of a random variable.

Calculating Pi is generally the hello world of Monte Carlo Method in Stochastic Calculus. So for today, I will try to give a sample calculation of pi as monte carlo in F#. There are very good articles on the Monte carlo and how the pi calculation is formulated.

Generally these are the steps to follow, before running the simulation

1. Define the input set
2. Generate randomly the input set
3. Filter the random set using some computations
4. Fold the result to the final result

Pi calculation formula :
$\frac{Hitting inside the circle} {Hitting Outside the circle} = \frac { 1/4 \pi r^2} { r^2} = \frac {1}{4}\pi$

open System let calcPi() = let ran = new Random() let distances = seq { for i in 0 .. 100000 do let x,y = ran.NextDouble(), ran.NextDouble() yield sqrt (x * x + y * y) }   let count = distances |> Seq.filter (fun distance -> distance <= 1.0) |> Seq.length 4.0 * (float count) / (float (Seq.length distances))   let errorRate() = (1.0 - (calcPi() / Math.PI)) * 100.0   let print5 value = for i in 0 .. 5 do printf "%f\n" (value()) print5 (errorRate)
val calcPi : unit -> float
val errorRate : unit -> float
val print5 : (unit -> float) -> unit
Error rates:
-0.024698
-0.093453
-0.013239
-0.094726
-0.373563
0.308887
>

.

## Book Review – Real World Functional Programming

Real-World functional programming has been written by Tomas Petricek and Jon Skeet.
Tomasz’s and Jon’s book is built around how to think functionally when programming and how to make best use of functional paradigm for real world scenerios. The book is written  mainly for the C# programmers who would like to switch/learn more of the functional world. It also features snippets with some technical background of the ideas involved.
As the title suggests the book is not focussed on one language, instead a mix of C# and F#, and it does a great job in bringing these worlds together,which is to me best of both worlds. Although, samples are all in functional style, when the problem needs the functional beauty to express, F# takes place. This gives any .NET developer to see when to use the necessary language for a particular problem.

The book starts slowly with the functional structures, and goes to monads, and to reactive libraries.  I found the language of the book clear to understand, and easy to follow. The samples in the beginning of a chapter starts with some really simple constructs, but at the end of a chapter they become more complicated, and a nice programs to reflect the idea of the chapter.

Applied functional programming is probably the most sophisticated part of the book. Some ideas mainly inspired from research papers (cited at the end) blended with modern languages and libraries and applied somewhat differently. Especially composable functional libraries and reactive functional programs were insightful and open the mind with new possibilities.

Finally, I would recommend this book whoever wants to switch to functional programming and also learn new techniques in general. Each sample is crafted well, and represent real value with its tutorial writing style.

## Pex, Unit Test but Better, Parameterized Unit Testing

Finally I had a chance to play with the Pex (Program EXploration) , I heard it on lang.net for the very first time and I was quite impressed, but it took a while to explore it.

I downloaded the latest commercial evaluation package 0.22.50128.1 from Pex web site.

It is about 12 MB, it comes with different installation options with the support of VS 2008 and 2010. It installed without any problems on my VS2010 beta 2.

Here is what you get from the installation :

• Pex command line (Visual Studio not required)
• Pex Visual Studio Add-in, for Visual Studio 2008 and Visual Studio 2010 Beta2
• Moles (which includes Stubs), lightweight test stubs and detours for .NET
• API reference, tutorials and documentation
• Samples

The documentation is really detailed, and the samples are worth investigating. I quite liked the Pex Tutorial document, which explains in detail what Pex is all about.

The good thing is it supports many different testing frameworks, including .NET’s own, nunit, xunit etc. By the way, I have to say VS2010 is awesome!

Pex is pretty much like a unit test but better in many ways. I’m quite surprised by the dynamic coverage window of a test method that you execute. This way, it is clear to see if the code is fully covered by the Pex test.

Pex is more like test method that takes inputs. In general, unit tests are not taking any inputs, they are isolated from each other and from external access, other than calling them parameterless.

Input generation in Pex based on the static analysis of the methods. It generates inputs such that, the code will be covered in full, however for some special types, the inputs might need to be explicitely told to test framework.  The tools it brings to Visual Studio is extremely simple and easy to use. It does a very good job on incorporating those results.

Here is a very simple function that I generated my first Pex tests from

 public static int Compare(int i, string s) { if (i > 500) { i *= 2; } else { return Compare2(i); } return i * i; }

When you run Pex, it generates potential inputs to cover all the code. According to the documentation, it uses static analysis to figure the potential values. So it is not a random number generated test, or a brute force test, which is quite interesting. Pex can cover some obscure side of the code, which fully supports many Unicode string inputs or regular expressions.

However, when I converted this very simple code, from System.Int32 to System.Numeric.BigInteger (a new type in .NET 4), the test only generated for a null value. Unless I’m missing something, it doesn’t support all the types as yet, but it looks like a promising and valuable product to be added to your toolset

## TouchJSON conflicts with AdMob and Cocos2d

If you happen to use Admob and cocos2d in the same project, the compilation will fail with some linking errors. Although it is not mentioned on Admod SDK documentation, apparently Admob borrows TouchJSON from touch code, so does Cocos2d.

The duplicated links could be resolved by removing it from one of the sources. Since we don’t have Admob source code, the workaround is actually to remove the TouchJSON directories from your project which are located in the cocos2d source code.

Directory and Files to be Removed as they are statically linked through admob
+TouchJSON
-CDataScanner.h
-CDataScanner.m
+Extensions
-CDataScanner_Extensions.h
-CDataScanner_Extensions.m
-NSCharacterSet_Extensions.h
-NSCharacterSet_Extensions.m
-NSDictionary_JSONExtensions.h
-NSDictionary_JSONExtensions.m
-NSScanner_Extensions.h
-NSScanner_Extensions.m
+JSON
-CJSONDeserializer.h
-CJSONDeserializer.m
-CJSONScanner.h
-CJSONScanner.m
-CJSONSerializer.h
-CJSONSerializer.m

## Poker : Programming Problem

Although it has been a while since Brian posted the poker problem in his blog, I haven’t got the chance to look at it until I came across in ProjectEuler Problem 54. It is not the elegant or best solution at all, but just wanted to join the crew and can confirm it works with the problem’s 1000 games’ dataset.

Hope this helps.

#light (* Problem 54 *) type suit = |Spades |Hearts |Clubs |Diamonds type card= |Ace = 14 |Two = 2 |Three =3 |Four = 4 |Five = 5 |Six = 6 |Seven =7 |Eight = 8 |Nine = 9 |Ten = 10 |Jack = 11 |Queen =12 |King =13 type acard = (card * suit)   let carder x:card= enum x   let card_value = function | 'A' -> card.Ace | 'K' -> card.King | 'Q' -> card.Queen | 'J' -> card.Jack | 'T' -> card.Ten | c -> carder(System.Int32.Parse(c.ToString()))   let suit_value = function | 'S' -> Spades | 'H' -> Hearts | 'C' -> Clubs | 'D' -> Diamonds | a -> invalid_arg (a.ToString())   let Create (str: string) :acard = (card_value str.[0],suit_value str.[1])   let isstraigh (mycards:acard list) = let mycards = List.sort_by (fun (a,b) -> a,b) mycards let rec isstr previouscard mycards (straightlist : acard list) = if straightlist.Length >= 5 then straightlist else match mycards with | cur :: rest -> if int (fst cur) = int ((fst previouscard)) + 1 then isstr cur rest (cur::straightlist) else isstr cur rest [] | _ -> [] let head = List.hd mycards isstr head (List.tl mycards) [head]   let pairl (mycards : acard list) groupfunction minelementCount = mycards |> Seq.group_by groupfunction |> Seq.filter (fun a -> Seq.length (snd a) >= minelementCount) |> Seq.to_list |> List.unzip     type Ranks = | Highest of card | Pair of card | TwoPair of card*card | Three of card | Straight of card | Flush of card | FullHouse of card*card | Four of card | StraightFlush of card   type Player = |One |Two |Noone   let rank (mycards : acard list) = let traverseL (l :'a list) = if not l.IsEmpty then l |> List.hd |> Seq.to_list else [] let isflush mycards = snd (pairl mycards snd 5) |> traverseL   let FofF l = traverseL l |> List.hd |> fst   let flush = isflush mycards let straight = isstraigh mycards   let ispair count= pairl mycards fst count   let four,fours = let f,s = ispair 4 f,s|> traverseL let three,threes = ispair 3 let two,twos = ispair 2   let maxcard c = fst (List.max c)   if not flush.IsEmpty && not straight.IsEmpty then StraightFlush(maxcard flush),flush elif not fours.IsEmpty then Four(four.Head),fours elif not threes.IsEmpty && not twos.IsEmpty && FofF twos <> FofF threes then FullHouse(two.Head, three.Head), List.append (threes |> traverseL) (traverseL twos) elif not flush.IsEmpty then Flush(maxcard flush),flush elif not straight.IsEmpty then Straight(maxcard straight),straight elif not three.IsEmpty then Three( three.Head), threes |> traverseL elif List.length two = 2 then TwoPair(two.Head,two.Tail.Head),Seq.append (twos.Head) (twos.Tail.Head) |> Seq.to_list elif not (twos |> traverseL).IsEmpty then Pair(two.Head), twos |> traverseL else Highest(maxcard mycards), [List.max mycards]   let play input = let convert (line: string) = let l = line.Split([|' '|]) [|[for j in 0 .. 4 do yield Create( l.[j])]; [for j in 5 .. 9 do yield Create( l.[j])]|] let playercrds = convert input let rec iswinner pcards= let ranks,rankcards = pcards |> Array.map (rank) |> Array.unzip   let removecards (mainlist) (toberemoved) = mainlist |> Array.map2 (fun rem main-> main |> List.filter (fun c-> List.fold_left(fun ac x-> if x = c then ac && false else ac && true) true rem)) toberemoved   if ranks.[0]>ranks.[1] then One elif ranks.[0]<ranks.[1] then Two else iswinner (removecards pcards rankcards)   iswinner playercrds     play "5H 5C 6S 7S KD 2C 3S 8S 8D TD" play "5D 8C 9S JS AC 2C 5C 7D 8S QH" play "2D 9C AS AH AC 3D 6D 7D TD QD" play "4D 6S 9H QH QC 3D 6D 7H QD QS" // prob pair queens look at the highes play "2H 2D 4C 4D 4S 3C 3D 3S 9S 9D"   play "2H 2D 4C 4D 4S 2H 2D 4C 4D 4S"   play "TH 8D 6C 4D 3S TH 8D 6C 4D 4S"       let rdinput = use file = System.IO.File.OpenText("poker.txt") let p1count = ref 0   while not file.EndOfStream do if play (file.ReadLine()) = One then p1count := !p1count+1   file.Close() !p1count