Euler 14

When I read Dustin Campbell’s latest post, I couldn’t help but feel a bit like Steve Carrell in this clip from the Office. While his solution is an admirably close port of the original F# solution, it makes me feel a little bit yucky.

Of course, it’s completely hypocritical of me to say so, since I’ve abused C# to make it exhibit F#-like behavior in the past.

But Project Euler invites elegantly simple solutions (like the original F#). Different languages have different idioms, and a literal port typically doesn’t exhibit the same beauty as the original.

If I was solving project Euler 14 in C# (with “elegance and brevity in mind”), my code would look more like:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Euler14
{
    class Program
    {
        static void Main(string[] args)
        {
            var iterativeSequences = from start in 1.To(1000000L)
                select new
                {
                    Start = start,
                    Length = SequenceUtility.Generate(start,
                        n => n % 2 == 0 ? n / 2 : 3 * n + 1,
                        n => n == 1).Count()
                };

            Stopwatch sw = Stopwatch.StartNew();

            var longestSequence = iterativeSequences.Aggregate(
                (longest, current) => current.Length > longest.Length ? current : longest
            );

            sw.Stop();

            Console.WriteLine("Longest sequence starts with {0:#,#} (found in {1:#,#.000} seconds)",
                longestSequence.Start, (float) sw.ElapsedTicks / (float) Stopwatch.Frequency);
        }
    }

    public static class SequenceUtility
    {
        // Can also overload To by changing the end value's type;
        // example: "int excludedEnd" returns "IEnumerable<int>"
        public static IEnumerable<long> To(this int start, long excludedEnd)
        {
            for (long i = start; i < excludedEnd; i++)
                yield return i;
        }

        public static IEnumerable<T> Generate<T>(T first, Func<T, T> getNext, Func<T, bool> isLast)
        {
            T value = first;
            yield return value;

            while (!isLast(value))
            {
                value = getNext(value);
                yield return value;
            }
        }
    }
}

Which runs in an acceptable ~5 seconds on my machine.

…

[Okay. You caught me: I stole the idea for that To extension method from Ruby's upto. I'm a huge hypocrite and take back everything I said before.

Do invest time learning the idoms of other programming languages, and try applying them to your native language. You may discover something beautiful, after all.]

LINQ to prime numbers

Having last Friday off, and finding myself in want of something to do, I decided to learn F#. Once I installed F#, though, I learned that desire and motivation are different things.

So I started killing time by solving Project Euler problems. In LINQPad.

(Which you really should download, if you haven’t already.)

People more eloquent than me can explain how embracing constraints helps creativity flourish. I’m not going to try.

Instead, I’ll share a prime number generator inspired by Euler problem 10 and implemented with LINQ:

var odds =
	from n in Enumerable.Range(0, int.MaxValue)
	select 3 + (long) n * 2;

var primes = (new[] { 2L }).Concat(
	from p in odds
	where ! odds.TakeWhile(odd => odd * odd <= p).Any(odd => p % odd == 0)
	select p);

This certainly isn’t the most efficient prime number generator in the world. But the full query to solve the problem (left as a exercise to the reader) runs in a perfectly acceptable less than six seconds on my machine. And it uses no intermediate storage for the primes!

Now that you’ve downloaded LINQPad—you have downloaded LINQPad, haven’t you?—you can start solving Project Euler problems in a blissfully constrained environment, too!

I’ve got Problem 1 down to 54 characters.