I had already solved Project Euler 23 in F# but wanted to translate my solution to C# for a friend. Those translations always tend to become very functional.

This time around I needed a MapWhile method. This method should take a list and map a function over all elements as long as the while condition is true. This is actually very simple to implement, if you know how.

public static class Extensions
{
    public static IEnumerable<T> MapWhile<T>(this IEnumerable<T> list, Func<T, T> mapFunction, Func<T, bool> whilePredicate)
    {
        return MapWhile(list, (i, item) => mapFunction(item), (i, item) => whilePredicate(item));
    }

    public static IEnumerable<T> MapWhile<T>(this IEnumerable<T> list, Func<int, T, T> mapFunction, Func<int, T, bool> whilePredicate)
    {
        var enumerator = list.GetEnumerator();
        var index = 0;

        while (enumerator.MoveNext())
        {
            if (!whilePredicate(index, enumerator.Current))
            {
                break;
            }

            yield return mapFunction(index, enumerator.Current);
            index++;
        }
    }
}

And some unit tests on usage.

[TestFixture]
public class MapWhileShould
{
    [Test]
    public void ReturnAtEndOfList()
    {
        /* Setup */
        var list = new[] { 1, 2, 3, 4 };

        /* Test */
        var result = list.MapWhile(x => x * 2, x => true);

        /* Assert */
        Assert.That(result.Sum(), Is.EqualTo(20));
    }

    [Test]
    public void BreakWhenWhileConditionIsFalse()
    {
        /* Setup */
        var list = new[] { 1, 2, 3, 4 };

        /* Test */
        var result = list.MapWhile(x => x * 2, x => x < 3);

        /* Assert */
        Assert.That(result.Sum(), Is.EqualTo(6));
    }

    [Test]
    public void ReturnEmptyListWhenWhileConditionIsFalseByDefault()
    {
        /* Setup */
        var list = new[] { 1, 2, 3, 4 };

        /* Test */
        var result = list.MapWhile(x => x * 2, x => false);

        /* Assert */
        Assert.That(result.Count(), Is.EqualTo(0));
    }

    [Test]
    public void WorkWithStrings()
    {
        /* Setup */
        var list = new[] { "Hello", "World", "Santa", "Claudius" };

        /* Test */
        var result = list.MapWhile((i, s) => i % 2 == 0 ? s.ToUpper() : s, (i, s) => true);

        /* Assert */
        Assert.That(string.Join(string.Empty, result), Is.EqualTo("HELLOWorldSANTAClaudius"));
    }
}

Usage in Project Euler 23

This is how I solved Project Euler 23 with the MapWhile function. This is not the most effective solution imaginable, but it is short and readable.

private const int AbundantSumMax = 28123;

public static void Main(string[] args)
{
    // Just create this once
    var defaultRange = Enumerable.Range(1, AbundantSumMax);

    // Returns true if n is abundant
    Func<int, bool> isAbundant = n => Enumerable.Range(1, n / 2).Where(x => n % x == 0).Sum() > n;

    // Get all abundants up to 28123
    var abundants = defaultRange.Where(isAbundant).ToList();

    // Get abundant sums
    var abundantSums = GetAbundantSums(abundants);

    // Invert abundant sums
    var result = defaultRange.Except(abundantSums).Sum();

    // Print
    Console.WriteLine("Result: {0}", result);
}

private static IEnumerable<int> GetAbundantSums(IList<int> abundants)
{
    // Unique set of numbers
    var result = new HashSet<int>();

    // The Tortoise and the Hare
    foreach (var abundant in abundants)
    foreach (var abundantSum in abundants.MapWhile(x => x + abundant, x => x <= abundant))
    {
        result.Add(abundantSum);
    }

    return result;
}

You can find my F# solution at bitbucket.

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.

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

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below

type BinaryTree =
    | Node of int * BinaryTree * BinaryTree
    | Empty

let rec calculate tree =
    match tree with
    | Node (n, left, right) -> n + List.max [(calculate left); (calculate right)]
    | Empty -> 0

let s_data =
    [
    "75";
    "95 64";
    "17 47 82";
    "18 35 87 10";
    "20 04 82 47 65";
    "19 01 23 75 03 34";
    "88 02 77 73 07 63 67";
    "99 65 04 28 06 16 70 92";
    "41 41 26 56 83 40 80 70 33";
    "41 48 72 33 47 32 37 16 94 29";
    "53 71 44 65 25 43 91 52 97 51 14";
    "70 11 33 28 77 73 17 78 39 68 17 57";
    "91 71 52 38 17 14 91 43 58 50 27 29 48";
    "63 66 04 68 89 53 67 30 73 16 69 87 40 31";
    "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23";
    ]

let rec data_tree (data : string list) row i =
    let data_row row_number = data.[row_number].Split(' ') |> Seq.map (fun s -> System.Int32.Parse(s)) |> Seq.toList
    let length = data.Length
    match row with
    | 15 -> Empty
    | _ -> Node ((data_row row).[i], data_tree data (row + 1) i, data_tree data (row + 1) (i + 1))

data_tree s_data 0 0 |> calculate;;