If you want to release software often, as scrum advises, you need to take special care about those releases. I had recently a problem where releasing changes to an ASP.NET website would cause it to generate new machine key and invalidating ViewState for all visitors that were using some sort of form on the website.

The solution to that is of course specifying the machine key in web.config to make sure that it doesn’t change when the application pool refreshes.

let gen len =
    let provider = new System.Security.Cryptography.RNGCryptoServiceProvider()
    let out : byte array = Array.zeroCreate (len / 2)
    provider.GetBytes(out)
    out |> Seq.map (fun b -> System.String.Format("{0:X2}", b)) |> System.String.Concat

This is how I use F# to generate the keys.

type MachineKey = { sha1 : string; aes : string; _3des : string }
let machineKey = { sha1 = (gen 128); aes = (gen 64); _3des = (gen 48) } 

printfn "<machineKey validationKey=\"%s\" decryptionKey=\"%s\" validation=\"SHA1\" decryption=\"AES\" />"
    machineKey.sha1
    machineKey.aes

And the result is…

<machineKey
	validationKey="E2063661CB8652441A7B687309A5F688C95CFC71513334CBE4CE8AE7F73404C468B784EA7A1BFDECD514572D4330383879A4AE418119B65C9755A30D0208FC8A"
	decryptionKey="1047AF920BE7770803DF9ECBDC1FDB73F3AF0C8D9F71C1C8E0D7B8260AFE607D"
	validation="SHA1"
	decryption="AES" />

Dump this in your web.config and you’re good to go. Just don’t forget to encrypt the configuration file before deployment to avoid the keys getting in the wrong hands.

I did know that the F# compiler pulls some magic tricks with recursion, but I didn’t know that it could affect performance like I’ve recently discovered. Me and my friend where discussing Project Euler #16, and where he did an iterative C# solution manipulating strings, I went for a recursive list mangling solution in F#.

Project Euler #16

2^¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^¹⁰⁰⁰?

Iterative string manipulating solution by Whettingstone

public static void Run()
{
	/*2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
	  What is the sum of the digits of the number 2^1000?*/

	StringBuilder allDigits = new StringBuilder("1");
	int carryOver = 0;
	int temp;

	for (int i = 0; i < 1000; i++)
	{
		for (int index = 0; index < allDigits.Length; index++)
		{
			//Multiply the digit by two
			temp = int.Parse(allDigits[index].ToString()) * 2;

			if (temp > 9)
			{
				//The result is 10 or larger so add digit and set carryOver
				allDigits.Remove(index, 1);
				allDigits.Insert(index, (temp % 10) + carryOver);
				carryOver = 1;
			}

			if (temp <= 9)
			{
				//The result is less than 10 so add digit and reset carryOver
				allDigits.Remove(index, 1);
				allDigits.Insert(index, temp + carryOver);
				carryOver = 0;
			}

			if ((index == allDigits.Length - 1) && carryOver == 1)
			{
				//This is the last index so add the carryOver to the StringBuilder and break the loop
				allDigits.Append(carryOver);
				carryOver = 0;
				break;
			}
		}
	}

	//Calculation is done, let's sum it up
	int sum = 0;

	for (int i = 0; i < allDigits.Length; i++)
	{
		sum += int.Parse(allDigits[i].ToString());
	}

	Console.WriteLine("Sum of 2^1000: {0}", sum);
}

This solution is pretty straight forward. Put the result in a string, double all the digits and span out overflowing number to next number in the string. At the end he sums it all up to an int.

Mean execution time: 127 ms

Recursive F# solution by me

let rec calc list exp =
    let rec evenOut overhead l =
        match (l, overhead) with
        | [], 0 -> []
        | [], _ -> [overhead]
        | head :: tail, _ -> ((overhead + head) % 10) :: (evenOut ((overhead + head) / 10) tail)

    match exp with
    | 1 -> list
    | _ -> calc (list |> List.map (fun x -> x * 2) |> evenOut 0) (exp - 1)

calc [2] 1000 |> List.sum

This is two recursive loops where the outer loop doubles every list item and the inner loop evens out the list with moving any number larger than 9 up the stack.

Mean execution time: 5 ms

Recursive C# translation of the F# version

private List<int> EvenOut(IEnumerable<int> numbers, int overflow)
{
    Func<IEnumerable<int>, bool> empty = list =>
        {
            var enumerator = list.GetEnumerator();
            return !enumerator.MoveNext();
        };

    if (empty(numbers))
    {
        if (overflow > 0)
            return new List<int> { overflow };

        return new List<int>();
    }

    var head = numbers.First();
    var n = (overflow + head) % 10;
    var newOverflow = (overflow + head) / 10;

    var result = EvenOut(numbers.Skip(1), newOverflow);
    result.Insert(0, n);
    return result;
}

private IEnumerable<int> Calc(IEnumerable<int> numbers, int exp)
{
    if (exp == 1)
        return numbers;

    return Calc(EvenOut(numbers.Select(n => n * 2), 0), exp - 1);
}

[Test]
public void Pe16()
{
    Assert.That(this.Calc(new[] { 2 }, 1000).Sum(), Is.EqualTo(1366));
}

In order to explain to my friend whettingstone what I do with my F# code I translated it to C#. I was really suprised when I noticed that it took so much longer to execute.

Mean execution time: 87235 ms

Conclusion

The F# compiler does some heavy optimizations to our recursion and going from F# to C# one must watch out, and not write pure functional constructs without thinking about the consequences. You could problably rewrite the C# recursive solution to be much faster, but an iterative solution is probably the preferred one here.

Thycotic presented a code challenge where you could win a gyroball here. Since I live in Sweden, I’m not eligible to win this challenge but I thought it would be fun to solve the problem.

// We have designed a new magical number system called "alpha-end".  This number system is
// similar to hexadecimal but has the following characters:  0 1 2 3 4 5 6 7 8 9 x y z
// (basically the decimal number system plus the 3 characters x, y and z)
// Therefore converting from decimal to alpha-end gives the following:
//    5   =>   5
//    10  =>   x
//    13  =>   10
//    20  =>   17
// Your task is to implement the Converter.Convert method for this new number system to get all the
// unit tests passing.  Feel free to add more unit tests as you work if it helps you test drive to the goal.
// You will be judged based on the accuracy and design of your code.
//
// Extra challenge:
// Try extending from your Converter to support other number systems such as binary, octal and hexadecimal.
// Is there an easy way to refactor your code/algorithm to support this?

Simply, write a method that will convert from decimal to any number system. Lucky for us all their examples contains only positive discrete numbers.

type Converter(alphabet:list<string>) =
    let alphabet = alphabet

    new () = Converter(["0"; "1"; "2"; "3"; "4"; "5"; "6"; "7"; "8"; "9"; "x"; "y"; "z"])

    member this.Convert (n:int) =
        let division = (n |> float) / (alphabet.Length |> float) |> System.Math.Truncate |> int
        match division with
        | 0 -> alphabet.Item(n)
        | _ -> this.Convert division + alphabet.Item(n % alphabet.Length)

type BinaryConverter() =
    inherit Converter(["0"; "1"])

type OctalConverter() =
    inherit Converter(["0"; "1"; "2"; "3"; "4"; "5"; "6"; "7"])

type HexConverter() =
    inherit Converter(["0"; "1"; "2"; "3"; "4"; "5"; "6"; "7"; "8"; "9"; "a"; "b"; "c"; "d"; "e"; "f"])

Here’s the same thing in C#.

public class Converter2
{
    private readonly string[] alphabet;
    private static string[] AlphaEnd = new[] { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "x", "y", "z" };

    public Converter2()
        : this(AlphaEnd)
    {
    }

    public Converter2(string[] alphabet)
    {
        this.alphabet = alphabet;
    }

    public string Convert(int number)
    {
        int division = (int) Math.Truncate(((double)number) / alphabet.Length);

        if (division == 0)
        {
            return alphabet[number];
        }

        return Convert(division) + alphabet[number % alphabet.Length];
    }
}

Personally I think F# looks much better.

n! means n (n 1)  …  3  2  1

Find the sum of the digits in the number 100!

let factorial n : bigint = List.fold (*) 1I [1I .. n]

let sum (n:bigint) =
    n |> string |> Seq.fold (fun acc x -> acc + System.Int32.Parse(x.ToString())) 0

sum (factorial 100I)

If you consider using bigint to be cheating, here’s a solution that will calculate it with the use of lists instead.

let rec plan overflow l =
    match l with
    | head :: tail ->
        let column = head + overflow
        if column > 9 then
            let next_overflow = column / 10 |> float |> System.Math.Truncate |> int
            (column - next_overflow * 10) :: plan next_overflow tail
        else
            column :: plan 0 tail
    | _ -> if overflow > 0 then
              (overflow % 10) :: plan ((overflow - (overflow % 10)) / 10) []
           else
              []

let add (l1 : int list) (l2 : int list) =
    l1 |> List.map2 (fun i1 i2 -> i1 + i2) l2 

let prod (l1 : int list) (l2 : int list) =
    let tenths i = 10.0 ** (i |> float) |> int
    l2 |> List.mapi (fun i x -> l1 |> List.map (fun y -> x * y * tenths (-1 + l2.Length - i)))
    |> List.fold (fun acc l -> add acc l) (List.init l1.Length (fun i -> 0))
    |> List.rev
    |> plan 0 // from outer space
    |> List.rev

let to_list n =
    let rec calc x =
        if x > 0 then
            (x % 10) :: calc ((x - (x % 10)) / 10)
        else
            []
    calc n |> List.rev

[2..100] |> List.map (fun x -> to_list x) |> List.fold (fun acc y -> prod acc y) [1] |> List.sum

You are given the following information, but you may prefer to do some research for yourself.

• 1 Jan 1900 was a Monday.
• Thirty days has September,
  April, June and November.
  All the rest have thirty-one,
  Saving February alone,
  Which has twenty-eight, rain or shine.
  And on leap years, twenty-nine.
• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

let months = [31; 28; 31; 30; 31; 30; 31; 31; 30; 31; 30; 31]

[0..99]
    |> List.map (fun x -> months) |> List.concat // all months consecutive
    |> List.mapi (fun i x -> if i = 1 && ((i - 1) / 12) % 4 = 0 then x + 1 else x) // leap year
    |> List.fold (fun (acc, result) x -> if (acc + x) % 7 = 6 then (acc + x, result + 1) else (acc + x, result)) (0,0) // Sunday bloody sunday