Jacob Carpenter’s Weblog

April 4, 2008

Euler 14

Filed under: csharp, Euler, extension methods, LINQ, Ruby — Jacob @ 12:41 pm

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.]

Advertisements

November 24, 2007

Another set of extension methods

Filed under: csharp, extension methods, Ruby — Jacob @ 3:16 pm

In addition to the interesting diversions we’ve taken, I do want to continue presenting potentially useful code samples too. So here’s a fresh set of ruby inspired extensions:

public static IEnumerable<IndexValuePair<T>> WithIndex<T>(this IEnumerable<T> source)
{
    int position = 0;
    foreach (T value in source)
        yield return new IndexValuePair<T>(position++, value);
}    

public static void Each<T>(this IEnumerable<T> source, Action<T> action)
{
    foreach (T item in source)
        action(item);
}

public static void EachWithIndex<T>(this IEnumerable<T> source, Action<T, int> action)
{
    Each(WithIndex(source), pair => action(pair.Value, pair.Index));
}

I’ll include the mundane definition of IndexValuePair<T> (along with parameter validation) at the end of this post. But spend some time looking at these very simple methods.

diagram 1

Notice how once we’ve defined WithIndex and Each, we can combine them to define EachWithIndex. When we chain Each to the result of WithIndex, the type of the Action must be converted accordingly:

diagram 2

This is easily accomplished by the statement:

pair => action(pair.Value, pair.Index)

So with the added definition of IndexValuePair<T> and parameter validation, we add to our collection extensions the following:

using System;
using System.Collections.Generic;

public static class CollectionEx
{
    public static void Each<T>(this IEnumerable<T> source, Action<T> action)
    {
        if (source == null)
            throw new ArgumentNullException("source");
        if (action == null)
            throw new ArgumentNullException("action");

        foreach (T item in source)
            action(item);
    }

    public static void EachWithIndex<T>(this IEnumerable<T> source, Action<T, int> action)
    {
        if (source == null)
            throw new ArgumentNullException("source");
        if (action == null)
            throw new ArgumentNullException("action");

        Each(WithIndexIterator(source), pair => action(pair.Value, pair.Index));
    }

    public static IEnumerable<IndexValuePair<T>> WithIndex<T>(this IEnumerable<T> source)
    {
        if (source == null)
            throw new ArgumentNullException("source");

        return WithIndexIterator(source);
    }

    private static IEnumerable<IndexValuePair<T>> WithIndexIterator<T>(IEnumerable<T> source)
    {
        int position = 0;
        foreach (T value in source)
            yield return new IndexValuePair<T>(position++, value);
    }
}

public struct IndexValuePair<T>
{
    public IndexValuePair(int index, T value)
    {
        m_index = index;
        m_value = value;
    }

    public int Index
    {
        get { return m_index; }
    }
    public T Value
    {
        get { return m_value; }
    }

    readonly int m_index;
    readonly T m_value;
}

November 16, 2007

Ruby inspired extension method

Filed under: csharp, extension methods, Ruby — Jacob @ 12:00 am

Reading Dustin Campbell‘s latest post reminded me that I really like Ruby’s Enumerable mixin.

One of the compelling methods in that type is each_slice (and the related enum_slice). The each/enum distinction to a C# developer can be understood as the distinction between a void method that takes a delegate, and an iterator method (a method that uses yield return) that returns an IEnumerable.

With the advent of C# 3.0 and the built-in Enumerable extension methods, returning an IEnumerable is a pretty powerful construct—developers aren’t limited to just foreach-ing over the results anymore.

So here’s a C# Slice extension method that is roughly the equivalent of Ruby’s enum_slice method:

using System;
using System.Collections.Generic;

namespace RubyInspiredExtensions
{
    public static class CollectionEx
    {
        /// <summary>
        /// Iterates the specified sequence returning arrays of each slice of <paramref name="size"/> elements.
        /// The last array may contain fewer that <paramref name="size"/> elements.
        /// </summary>
        /// <typeparam name="T">The sequence element type.</typeparam>
        /// <param name="sequence">The source sequence.</param>
        /// <param name="size">The desired slice size.</param>
        /// <returns>A sequence of arrays containing the elements from the specified sequence.</returns>
        public static IEnumerable<T[]> Slice<T>(this IEnumerable<T> sequence, int size)
        {
            // validate arguments
            if (sequence == null)
                throw new ArgumentNullException("sequence");
            if (size <= 0)
                throw new ArgumentOutOfRangeException("size");

            // return lazily evaluated iterator
            return SliceIterator(sequence, size);
        }

        // SliceIterator: iterator implementation of Slice
        private static IEnumerable<T[]> SliceIterator<T>(IEnumerable<T> sequence, int size)
        {
            // prepare the result array
            int position = 0;
            T[] resultArr = new T[size];

            foreach (T item in sequence)
            {
                // NOTE: performing the following test at the beginning of the loop ensures that we do not needlessly
                // create empty result arrays for sequences with even numbers of elements [(sequence.Count() % size) == 0]
                if (position == size)
                {
                    // full result array; return to caller
                    yield return resultArr;

                    // create a new result array and reset position
                    resultArr = new T[size];
                    position = 0;
                }

                // store the current element in the result array
                resultArr[position++] = item;
            }

            // no elements in source sequence
            if (position == 0)
                yield break;

            // resize partial final slice
            if (position < size)
                Array.Resize(ref resultArr, position);

            // return final slice
            yield return resultArr;
        }
    }
}

Blog at WordPress.com.