Archive for the ‘C#’ Category

Coin Flips with Go

Thursday, September 15th, 2016

Following on from my little experiment with flipping coins millions of times, I thought that it would be interesting to write the same program in Go for comparison.

func main() {
    rand.Seed(time.Now().UTC().UnixNano())
 
    var competitionSize, runs int
    flag.IntVar(&competitionSize, "competitionSize", 10, "The size of each coin tossing competition.")
    flag.IntVar(&runs, "runs", 10, "The number of runs of the competition")
 
    flag.Parse()
 
    fmt.Println("heads, tails, flips")
    for i := 0; i < runs; i++ {
        countHeads := 0
        for j := 0; j < competitionSize; j++ {
            countHeads += rand.Intn(2)
        }
 
        fmt.Printf("%d, %d, %d\n", countHeads, competitionSize-countHeads, competitionSize)
    }
}

The basic idea of how to write the program is unchanged in this language. The output showed a similar distribution to the C# program.

However, Go has straightforward command line arguments parsing built into the standard library (like Python or Perl). In C#, there are a number of third party libraries that do this that can be installed via NuGet. I went with Command Line Parser.

To use this, I needed to add a class with properties with attributes to describe my expected options:

class Options
{
    // Taken from http://www.bbc.co.uk/news/politics/eu_referendum/results
    [Option('s', "competitionSize", DefaultValue = 33551983, HelpText = "The size of each coin tossing competition.")]
    public int CompetitionSize { get; set; }
 
    [Option('r', "runs", DefaultValue = 1000, HelpText = "The number of runs of the competition")]
    public int Runs { get; set; }
}

The command line arguments are then parsed in the main method:

var commandLineArgs = new Options();
if (Parser.Default.ParseArguments(args, commandLineArgs))
{
    var runs = commandLineArgs.Runs;
    var flips = commandLineArgs.CompetitionSize;
    ...
}
else
{
    WriteLine("Unable to parse the command line arguments!");
}

While this is not difficult to understand, it is more complicated than it needs to be and requires quite a bit more typing than in the Go program.

10 runs of the referendum simulation in both programs on Windows 10 with an Intel i7 4500U running at 1.8GHz took 7 seconds for the C# program and 13 seconds for the Go program. I wouldn’t take such simple programs very seriously for drawing conclusions about the relative speed of these languages.

The updated C# program and the complete Go program are on GitHub:
https://github.com/robert-impey/CodingExperiments/blob/master/C-Sharp/CoinFlipsAreRandom/CoinFlipsAreRandom/Program.cs
https://github.com/robert-impey/CodingExperiments/blob/master/Go/coinToss.go

Was the EU Referendum Random?

Monday, September 5th, 2016

One of the claims that I saw on social media in the aftermath of the recent EU referendum here in the UK was that the result (52% to 48%) was so close that it was little different from tossing a coin.

Without getting bogged down in the politics of that referendum, or the various campaigns that led up to it; I want to consider whether this claim holds any water. How similar to millions people each tossing a coin and voting accordingly was the result?

According to the BBC, there were 17,410,742 votes to leave and 16,141,241 votes to remain, giving a total of 33,551,983 votes. If we were to make each of these people toss a coin and count up the results, the ratio of heads/tails or remains/leaves could be anywhere between all heads and all tails. However, we would expect the counts to be about equal if the coins were all fair. Of course, any ratio is possible, but if we were to run the coin tossing game repeatedly, we would expect to mean ratio to converge on 1:1. How likely would a 52:48 ratio be?

The leave side got a share of the vote equal to 0.51891842. Therefore, their absolute deviation from the expectation (the mean, or 0.5) is 0.01891842. The difference between the two counts is 1,269,501. Would we expect to see a deviation of this magnitude in a coin tossing competition?

Being a computer programmer rather than a mathematician, I’m going to look at this using a simple program.

WriteLine("heads, tails, flips, heads share");
 
var runs = 1000;
 
// Taken from http://www.bbc.co.uk/news/politics/eu_referendum/results
var flips = 33551983;
 
var randomNumberGenerator = new Random();
 
for (var run = 0; run < runs; run++)
{
    var heads = 0;
 
    for (var coinToss = 0; coinToss < flips; coinToss++)
    {
        var toss = randomNumberGenerator.Next(2);
 
        if (toss > 0)
        {
            heads++;
        }
    }
 
    WriteLine($"{heads}, {flips - heads}, {flips}, {(0.0 + heads) / flips}");
}

This program simulates 1,000 coin tossing competitions with 33,551,983 players and writes the counts as comma separated values.

Putting the output into Excel, the largest deviation was 0.000275081 (or a difference between counts of 18,459) and the smallest was 1.49022E-08 (which was 16,775,992 heads and 16,775,991 tails. This happened twice in 1,000 runs!) The largest difference between heads and tails was 69 times smaller than the result from the referendum.

Plotting the shares in decreasing order, we see how quickly larger deviations fall off:

deviation

Putting the deviations into bins and counting the competitions by deviation from the expectation, we see that smaller deviations are more common:

bins

Whatever else we might say about the result, we cannot seriously claim that the result was random.

The full program can be found here:

https://github.com/robert-impey/CodingExperiments/blob/master/C-Sharp/CoinFlipsAreRandom/CoinFlipsAreRandom/Program.cs

The Excel file can be found here:
http://www.reversing-entropy.com/wp-content/uploads/2016/09/EuRef.xlsx

Does Declarative Programming generally help?

Sunday, April 17th, 2016

A recent post compared different ways of approaching the same problem in Scala and Go:

https://www.quora.com/Scala-vs-Go-Could-people-help-compare-contrast-these-on-relative-merits-demerits/answer/Nick-Snyder-1?srid=dsGW&share=191eaf13

The Go approach is longer than the one in Scala, but every line is dead simple to understand. We might dismiss it as repetitive, boiler plate code rather than abstract, business logic. However, setting break points for debugging or changing the behaviour of the code when the new requirements arrive, six months down the line, is trivial. This can be a mixed blessing, as there’s really nothing to stop code like that ballooning in size as new conditional statements get added to cope with the changing needs of the software. Every 5 kLoC ball of mud that any programmer ever wrestled with started out as something dead simple like that.

The following article investigates how non-programmers approach programming problems and whether programming languages make the task harder because they do not match how an untrained mind thinks.

http://alumni.cs.ucr.edu/~ratana/PaneRatanamahatanaMyers00.pdf

More children developed rules to describe the behaviour of Pacman than instructions for the sprites to follow. People apparently start out thinking in a more declarative style and then develop the habit of thinking in the imperative style.

Is this an argument for using more declarative languages? If declarative programming is more natural, surely it would be easier. However, many programmers start out with imperative code and perhaps only try declarative code later. Is this just a historical or social accident caused by the greater availability of imperative languages compared to declarative ones? It is possible that this is a greater issue for novice programmers than for experienced ones.

Often, we cannot move between languages at whim. Few programmers have the privilege of being able to write part of their system in Go in the morning, then head over to Scala land after lunch. However, .Net has Linq, which affords a C# developer, like your author, greater freedom to move freely back and forth between imperative and declarative styles of programming.

Imagine a book stall in a market. There is a table with books with different numbers of pages with covers that are red or blue.

The types in this world are an enum for the colours and a class for the book:

enum Colour
{
    Red,
    Blue
}
 
class Book
{
    internal Book(string name, int numberOfPages, Colour colour)
    {
        Name = name;
        NumberOfPages = numberOfPages;
        Colour = colour;
    }
 
    internal string Name { get; }
    internal int NumberOfPages { get; }
    internal Colour Colour { get; }
}

We can model our bookstall with a list:

var books = new List<Book>
{
    new Book ("War and Peace", 1123, Colour.Red),
    new Book ("Doctor Zhivago", 803, Colour.Blue),
    new Book ("Jeeves and the Feudal Spirit", 154, Colour.Red),
    new Book ("Shogun", 1213, Colour.Red)
};

You want to write down the names of the books that are more than 500 pages long and have red covers. Here are three ways to solve this problem.

The imperative approach:

foreach (var book in books)
{
    if (book.Colour == Colour.Red && book.NumberOfPages > 500)
    {
        WriteLine(book.Name);
    }
}

This way, we are putting ourselves in the role of the person actually sifting through the books one by one and writing the names of the books that meet our criteria as we go. However, the presentation code (the WriteLine) is mixed up with the filtering logic in the loop.

Linq makes use of the Where extension method to allow the so-called fluent syntax:

var longRedBooks = books.Where(b => b.Colour == Colour.Red && b.NumberOfPages > 500);
 
foreach (var longRedBook in longRedBooks)
{
    WriteLine(longRedBook.Name);
}

Here, we first ask for the books that match our criteria, defined in the lambda expression passed to the Where method. Then, we print the books that matched. The filtering logic and presentation logic are now separate.

Using Linq’s query syntax below, the code looks quite different from the fluent syntax used above, but the meaning is the same. This approach is perhaps more familiar to developers with a background in SQL.

var longRedBooks = from book in books
                   where book.Colour == Colour.Red && book.NumberOfPages > 500
                   select book;
 
foreach (var longRedBook in longRedBooks)
{
    WriteLine(longRedBook.Name);
}

The complete source can be found on GitHub:
https://github.com/robert-impey/CodingExperiments/blob/master/C-Sharp/BookFinding/Program.cs

Which is easiest to understand? If the requirements change, let’s say that we now only want one book, which should be the longest book, shorter than 500 pages, with a blue cover, which approach will be easiest to update and understand with the new logic? With the Linq approach, we can take advantage of the type system to see that the query now returns a Book (which may be null) rather than an IEnumerable<Book> and handle the object appropriately. Will the change in meaning be as obvious in the imperative code?

For what it’s worth, I’ve experienced plenty of resistance in code reviews to Linq queries, but almost none to writing the same thing in a for loop. Sometimes the reasoning is to do with performance, but I doubt there’s much in that. Anyway, a read-only code review is a terrible place to make assumptions about relative performance. However, it’s very easy to reason about the performance of the for loop, but more advanced knowledge of lazy evaluation, the iterator pattern and its implementation is needed to understand what gets executed where and how many times for the linq approaches.

I would be very interested to see an analysis of open source projects that compared the frequency on these approaches to see what is the approach that people tend to settle on. Do pull request with Linq get accepted more or less often? Is code generally refactored from one to the other? In which direction?

How should this influence job interviews and hiring? If we want to hire experienced programmers, we could check for signs that their thinking has been moulded to the structures of industrial programming languages. Perhaps we should pity such creatures. Should we look for signs of skills in imperative programming in hands-on programmers and for a declarative approach in tech leads and more senior roles, where coordinating the efforts of several developers is the required skill?

Finding Reversed Words

Sunday, November 23rd, 2014

Following on from coding experiments with using the decorator pattern to reverse strings in Java and with palindromes and string reversal in C#, I decided to search for the words in the English language that are the reverse of other words. The Devil lived, but Black Sabbath gave us Live Evil. To beat Sega takes ages. You’re upping the ante living near Etna.

I had a copy of a dictionary file from Ubuntu on my hard drive. To make life a little simpler, I used some PowerShell magic to remove the many words that end in “‘s” (there are no words that start “s'”) and to make the list all lower case:

PS M:data> Get-Content .\british-english.csv | ?{ $_ -NotMatch "'s$" } | %{ $_.ToLower() } | Sort-Object | Get-Unique | Set-Content british-english-without-apostrophe-s.txt

The simplest algorithm for finding words that are the reverse of other words is to simply go through the whole list and then check whether any of the other words are the reverse of that word. To do this, we need a method to test if two strings are a reversed pair. Pushing the characters of the first string onto a stack and then popping them off as you check them against each character of the second string can achieve this:

public bool AreReversedPair(string firstString, string secondString)
{
    if (firstString.Length != secondString.Length)
    {
        return false;
    }
 
    var firstStringStack = new Stack<char>();
 
    foreach (var c in firstString)
    {
        firstStringStack.Push(c);
    }
 
    foreach (var currentCharFromSecond in secondString)
    {
        var currentCharFromFirst = firstStringStack.Pop();
 
        if (currentCharFromFirst != currentCharFromSecond)
        {
            return false;
        }
    }
 
    return true;
}

Next, the code for finding the pairs:

public IEnumerable<ReversedWordPair> FindReversedWords(IQueryable<string> allWords)
{
    var reversedWords = new LinkedList<ReversedWordPair>();
    var reversedStringChecker = new StackReversedStringChecker();
 
    foreach (var firstWord in allWords)
    {
        foreach (var secondWord in allWords)
        {
            if (reversedStringChecker.AreReversedPair(firstWord, secondWord))
            {
                reversedWords.AddLast(new ReversedWordPair(firstWord, secondWord));
            }
        }
    }
 
    return reversedWords;
}

This code is very straightforward, but not fast at all. The time complexity of the algorithm is O(n^2) because for each word, we need to check every other word. For a list with almost 73,000 words, this takes a long time. In spite of this, it does finish. I left the program running, went to dinner and found a list waiting for me when I came back.

reversed-word-pairs.txt

As the list of words is not going to change very often and I only need to run the algorithm once, I could just leave the program as it is. However, it would be nice to reduce the time complexity of the algorithm. The simplest way to do this would be to reverse each word and then check whether the list of all the words contains the reversed word (readers who are familiar with .Net may have noticed that I passed the list of words as an IQueryable rather than an IEnumerable for the list of words). Depending on the data structure, checking whether the reversed string is a member of the set of words should be less than O(n). For example, retrieval from a Trie takes O(m) where m is the length of the string. This would leave us with O(nm) time. As with all optimisations, you’ve got to time the code to see whether you get a boost or not.

My next task is to come up with a meaningful sentence with all words the reverse of the corresponding word at the other end of the sentence, with a palindrome at the centre. There must be something that can be made of Dennis, who sinned in the straw, only to get warts to stun his nuts.

See if you can make a mirror sentence of your own.

The complete code, along with some tests, can be found at:

https://github.com/robert-impey/CodingExperiments/tree/master/C-Sharp/FindReversedWords

Fizz Buzz with Functional Programming

Saturday, October 11th, 2014

Fizz Buzz is a counting game where players count upwards saying either the number, “Fizz!” if the number is a multiple of 3, “Buzz!” if a multiple of 5, or “Fizz! Buzz!” if the a multiple of 3 and 5.

It’s also a simple programming problem that can be solved in a number of ways.

In C#, the solution could be as simple as:

var max = 30;
 
Console.WriteLine("With a for loop:");
 
for (var i = 1; i <= max; i++)
{
    Console.Write(i + ": ");
 
    if (i % 3 == 0)
    {
        Console.Write("Fizz! ");
    }
 
    if (i % 5 == 0)
    {
        Console.Write("Bang!");
    }
 
    Console.WriteLine();
}

href=”https://github.com/robert-impey/CodingExperiments/blob/master/C-Sharp/FizzBang/FizzBang/Program.cs

I’m going to show a way of solving this problem using F#. This is not the simplest way to solve this problem. However, the F# solution below does demonstrate the use of higher order functions, an important concept in functional programming.

F# is a strongly typed language. This means that the compiler checks that the values that we bind and pass to and return from functions conform to its expectations. This catches a huge number of programmer errors almost as soon as they are made. It also allow the programmer to state his or her intentions by defining types. In this program, we are dealing with checking numbers that may or may not have the special property of causing us to say a message. We are going to need a function that can check numbers, so we define a type that describes such functions:

type NumberChecker = int -> string option

An example of such a function is

let isEven x = 
    if x % 2 = 0 then Some "That number's even!"
    else None

This takes x and checks whether the remainder after dividing by 2 is 0. If so, it returns something (the message). Otherwise, it returns nothing.

We can test this function using a match statement. We call isEven with a number. If the function returns a message (the case where there is Some message) we can print it. If the function returned None, then we’ll just print the number.

let number = 4
match isEven number with
| Some message -> printfn "%s" message
| None -> printfn "%d" number

This code is fine if we only want to check one number with one number checker. We want to be able to check numbers with different checker functions.

For example, we might also define:

let isOdd x =
    if x % 2 = 1 then Some "That number's odd!"
    else None

To test this, we could duplicate our code:

match isOdd number with
| Some message -> printfn "%s" message
| None -> printfn "%d" number

Nobody likes duplicated effort. The only difference between these lines of code and the isEven printing code is the checker function. This is where a higher order functions come in. A higher order function takes a function as an input or returns a function as the output.

let numberCheckerPrinter (numberChecker : NumberChecker) number =
    match numberChecker number with
    | Some message -> printfn "%s" message
    | None -> printfn "%d" number

The first argument to this function is annotated as a NumberChecker, which we defined at the top of our program. We can pass into this function any number checker function we like and it will either print the message (if one is returned) or the number on its own.

numberCheckerPrinter isEven 2
numberCheckerPrinter isEven 3
numberCheckerPrinter isOdd 2
numberCheckerPrinter isOdd 3

This has this output:

That number's even!
3
2
That number's odd!

Note that the first argument (which happens to be a function) is passed to the function in the same way as the second argument (which happens to be an integer).

We could go on defining number functions in the way, but we’re already beginning to repeat ourselves. The definition of the higher order function was a function that took a function as an input or returned a function. It would nice if the programming language could some of the work for us and make number checkers. All that stays the same from number checker to number checker is that they all must accept an integer and return either a message or nothing.

We might have a number of number checkers that vary only in that they check a different divisor and have a different message.

let divisorNumberChecker (divisor, message) number = 
    if number % divisor = 0 then
        Some message
    else    
        None

Note that this function does not conform to the NumberChecker type that is defined at the top as it takes two arguments: a tuple of the divisor and the message and the number. We can use this function to make new number checkers by fixing the first input with partial function application.

let fizz = divisorNumberChecker (3, "Fizz!")

Even though divisorNumberChecker takes two arguments, we only supplied the first. This causes F# to return a new function which accepts the remaining argument and has fixed the first argument.

Running this in F# interactive gives the type of fizz, which matches NumberChecker.

> 

val fizz : (int -> string option)

Making the “Buzz!” checker is simply:

let buzz = divisorNumberChecker (5, "Buzz!")

We have functions for the “Fizz!” and the “Buzz!” part of the game, we now need to deal with the case when the number is divisible by 3 and 5. We could define a function to do this, but this a duplicated effort that we want to avoid. After all we have fizz and buzz, we want to reuse them.

let andNumberChecker (f : NumberChecker, g : NumberChecker) x  = 
    match f x, g x with
    | Some messageF, Some messageG -> messageF + " " + messageG |> Some
    | _ -> None

The andNumberChecker lets us combine two number checker functions into one. If both functions return a message for the given number, then it joins the messages together and returns them. Otherwise, it returns None.

Again, I’ve use partial function application to fix the fizz and buzz functions to make fizzBuzz.

let fizzBuzz = andNumberChecker (fizz, buzz)

So far, I’ve been passing single functions as arguments to other functions. Functions can be treated as other objects in F#. Therefore, we can put them into a list and pass that list to a function. This way we can keep checking the same number with different checkers and use the message from the first one that returns something rather than nothing:

let doManyChecks (numberCheckers : NumberChecker list) number =
    let message = 
        List.fold (fun message numberChecker ->
            match message with 
            | Some _ -> message
            | None -> numberChecker number
        ) None numberCheckers
    match message with
    | Some message' -> printfn "%s" message'
    | None -> printfn "%d" number   
 
let doFizzBuzzChecks = doManyChecks [ fizzBuzz; fizz; buzz ]

We can use this to play the game:

doFizzBuzzChecks 3
doFizzBuzzChecks 4
doFizzBuzzChecks 5
doFizzBuzzChecks 15

In FSI:

Fizz!
4
Buzz!
Fizz! Buzz!

Or to play the game with many numbers:

[ 1 .. 30 ] |> List.iter doFizzBuzzChecks

The complete code for this can be found here:

https://github.com/robert-impey/CodingExperiments/blob/master/F-Sharp/Loose/FizzBuzz.fsx

Functional programming has been described as a non-solution to a non-problem. Compared to the for loop in C#, this looks like a lot of work. If you have a problem as simple as Fizz! Buzz!, then it’s best to stick to the simplest solution. However, many interesting problems are much more complicated.

Higher order functions allow for abstracting away the details and generalising code. We might add a rule of saying “Boom!” for primes. The code such a checker might be complicated and require extensive testing. The code that makes use of the checkers does not need to change in order to use this new checker, we simply add the function to the list of checkers. We can also combine it with other checkers, enabling code reuse. Functional programming is getting increasing attention because it allows programmers to closely focus their attention on just their problem and decouple that code from the part of the program that will make use of it.

Finding the Nearest Tube Station with LINQ

Tuesday, August 20th, 2013

I recently wrote a little command line program in C# that can tell you the name of the nearest tube station. I’ve put the program on GitHub in my Coding Experiments repository:

https://github.com/robert-impey/CodingExperiments/tree/master/C%23/NearestTube

The interface is very simple- this more of an experiment than something that I intend for mass consumption! You enter a location via the command line as the latitude and longitude:

Nearest Tube CLI

The starting point of the program was to calculate the distances between points. To do this I adapted some JavaScript code that John D. Cook wrote:

http://www.johndcook.com/lat_long_distance.html

Mathematical code looks very similar in many languages, and the translation from JavaScript to C# was trivially simple as the languages are very similar in this case. This code is part of the Point class:

        /// <summary>
        /// Porting JavaScript code from
        /// http://www.johndcook.com/lat_long_distance.html
        /// </summary>
        /// <param name="that"></param>
        /// <returns></returns>
        public double Distance(Point that)
        {
            // Compute spherical coordinates
 
            double rho = 6373;
 
            // convert latitude and longitude to spherical coordinates in radians
            // phi = 90 - latitude
            double phi1 = (90.0 - this.Latitude) * Math.PI / 180.0;
            double phi2 = (90.0 - that.Latitude) * Math.PI / 180.0;
            // theta = longitude
            double theta1 = this.Longitude * Math.PI / 180.0;
            double theta2 = that.Longitude * Math.PI / 180.0;
 
            // compute spherical distance from spherical coordinates
            // arc length = \arccos(\sin\phi\sin\phi'\cos(\theta-\theta') + \cos\phi\cos\phi')
            // distance = rho times arc length
            return rho * Math.Acos(
                    Math.Sin(phi1) * Math.Sin(phi2) * Math.Cos(theta1 - theta2)
                    + Math.Cos(phi1) * Math.Cos(phi2)) * 1000;
        }

Once I was able to calculate the distances between points on the map, I needed to be able to sort the tube stations of London by distance from the given point. This is the sort of code that LINQ to objects handles very naturally. In the SequentialTubeStationFinder class, I have the following method:

        public TubeStation FindNearestTubeStation(Point point)
        {
            return (from tubeStation in tubeStations
                    orderby tubeStation.Point.Distance(point)
                    select tubeStation).First();
        }

tubeStations is a generic list of TubeStation objects. Each has a Point property that is used to sort the tube stations and find the nearest one to our location.

The declarative style of programming that LINQ uses is much easier to read (and therefore maintain) than the equivalent code written with a for loop.