Programming fun
Classic mashup: An FSharp coding dojo
Yesterday I attended the FSharp Dojo: Picasquez and Velasso at Skills Matter in London.
This dojo is all about manipulating images and creating mashups, like this:
Finding overlapping rectangles
This is a classic quick programming puzzle: write a function that, given two rectangles, will determine if the triangles overlap. I found this puzzle over on http://leetcode.com/2011/05/determine-if-two-rectangles-overlap.html, and thought it was worth talking about because the solution is wrong, and it was interesting to me because it shows how thinking about a domain can influence your implementation of behaviour.
The mistake made by the original author is with one of the assumptions / interpretations made during their reasoning process. They said “when two rectangles overlap, one rectangle’s corner point(s) must [be contained within] the other rectangle”. This appears reasonable, given the example below:
“The missing number” programming exercise
This is another entry in the brain teaser / programming exercise / interview question collection. It goes like this:
Imagine a list of consecutive numbers. The list is, however, unsorted and one number is missing. Write a function that finds which number is missing with the constraint that you may only allocate O(1) memory (i.e. the amount of memory you use cannot vary with the size of the list).
The fact that the list is unsorted means that you cannot step through in a pairwise fashion and compare each element of the list to the next to see if they are consecutive. Sure, we could sort the array first but the fact that you cannot allocate memory according to the size of the array means that you cannot create a helper array in the solution and certain sorting algorithms are ruled out. An in-place sorting algorithm such as quicksort would do it, but I don’t think that sorting the array is the best way to go.
What if we sum the list? We’re talking about a sequence of integers, after all. It turns out that there is a linear formula for calculating the sum of a sequence of consecutive integers: sum(1..n) = n(n+1) / 2.
This means that you can work out what the sum of the input list should be; all we must do it actually sum the list and the difference between the two will be the missing number. Our implementation then looks like this:
let findMissing (list : int array) =
let n = list.Length + 1
let expectedSum = n * (n + 1) / 2
let actualSum = Seq.sum list
expectedSum - actualSum
Note the let n = list.Length + 1. We have to add one to the length of the list to get the max element in the list because one element is missing. After that it’s pretty simple!
A functional Fizzbuzz
After reading Scott Wlashin’s post (http://fsharpforfunandprofit.com/posts/railway-oriented-programming-carbonated/) on writing FizzBuzz in a more functional style and with the ability to have more rules (other than 3 => fizz, 5 => buzz, etc) I decided to give it a go myself. This represents the most idiomatic F# I could come up with, and I think it reads pretty well. It uses partial application, list operations, shorthand match-expressions-as-functions and option types.
let carbonate rules i =
rules
|> List.choose (fun (divisor, replacement) ->
if i % divisor = 0 then Some replacement else None)
|> function [] -> string i | list -> String.concat "" list
let carbonateAll rules = List.map (carbonate rules)
let fizzbuzzbazz = carbonateAll [3, "fizz"; 5, "buzz"; 7, "bazz"]
fizzbuzzbazz [100..110] |> printfn "%A"
See if you can follow how it works.
Converting decimal integers to binary strings in different languages
This is a fun post, telling the tale of a simple programming challenge taken in a number of different languages to learn those languages. The challenge is simple: write a function that, given an integer input, will return the binary representation of that number. To start you can assume that the number you have been given is positive, but you can handle negative numbers for extra credit.
Let’s start with C#:
public static string IntToBinary(int i)
{
var resultBuilder = new StringBuilder();
do
{
var bit = i % 2;
resultBuilder.Insert(0, bit.ToString());
i = i / 2;
}
while (i > 0);
return resultBuilder.ToString();
}
As you can see, this is a very procedural way of thinking. It’s got a StringBuilder, a conventional loop… Not that pretty. We can do this much more succinctly, but it illustrates the basic procedure for converting a number to binary. You can find the final (right-most) bit of the binary representation by modding the number by 2. To find the right-most-but-one bit, you divide the number by 2 (discarding any result) and then mod the result by 2. Continue until you eventually end up with zero.
Let’s switch language. How about something more functional, like F#?
let rec intToBinary i = match i with | 0 | 1 -> string i | _ -> let bit = string (i % 2) (intToBinary (i / 2)) + bit
This looks better! What’s different here? First of all we have changed the function to a recursive one.
What about a language like CoffeeScript or, even better, Livescript?
int-to-binary = (i) ->
| i in [0, 1] => i
| _ => "#{int-to-binary i .>>. 1}#{i % 2}"
As usual Livescript produces the shortest code.
The Eight Queens problem
My colleague recently introduced me to the eight queens problem (you can read more about it over at Wikipedia). In summary, you have to be able to place eight queens down on a chess board without any of them attacking any other.
This sounds easy at first, but I found that taking a few guesses on a piece of paper yielded no results. Rather than simply solving the problem, I decided it would be more fun to write a program that would find all the solutions for me. I’d been looking for a nice little programming problem to teach myself F# for a while, so I thought I’d give this a go. Well, after a few false starts and a lot of F# Googling, here’s my solution:
Richiban 