December 2008 - Posts

Project Euler #14

I had so much fun doing #13 I thought I'd tackle #14 as well.

This problem wasn't too bad.  I started by defining some extension methods on long:

   1: static class Extensions
   2: {
   3:     public static long NextInSequence(this long number)
   4:     {
   5:         if (number % 2 == 0)
   6:         {
   7:             return number / 2;
   8:         }
   9:         else
  10:         {
  11:             return 3 * number + 1;
  12:         }
  13:     }
  14:  
  15:     public static IList<long> GenerateSequence(this long number)
  16:     {
  17:         List<long> seq = new List<long>();
  18:  
  19:         long next = 0;
  20:         do
  21:         {
  22:             next = number.NextInSequence();
  23:             seq.Add(next);
  24:             number = next;
  25:         } while (next != 1);
  26:  
  27:         return seq;
  28:     }
  29: }

While I don't necessarily need the full list of terms (GenerateSequence), I used the list in testing to make sure my sequence logic was correct.

Now, the only thing left to do was to find the longest sequence.  I used a LINQ query to order the list of sequence counts in descending order so the longest would be at the top:

   1: var range = Enumerable.Range(1, 1000000);
   2:  
   3: var biggest = (from n in range
   4:                let size = ((long)n).GenerateSequence().Count
   5:                orderby size descending
   6:                select new { Number = n, Length = size }).ToArray();
   7:  
   8: Console.WriteLine("{0} has a sequence of {1}", biggest[0].Number, biggest[0].Length);
Technorati Tags: ,,
Posted by PSteele | with no comments
Filed under: ,

Project Euler #13

It's been a while since I did one of the Project Euler problems.  And since a lot of my work recently has been fixing bugs and working on some design documents, I was itching to do some "real" coding.  So it's on to problem #13.

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

It would be nice if I could have stuck all of those numbers in an integer and simply added them up, but they were too big for that.  The solution I came up with kind of feels like I cheated a bit, but it gives me the correct answer!  What I did was take the list of 50-digit numbers and stick a decimal point in the middle (at the 25th character).  This gives me a number that .NET's double data type can handle.  I just had to make sure I removed the decimal point before grabbing my answer.

So my final solution was:

   1: string[] numbers = {
   2:     // giant list of numbers from website clipped
   3:                    };
   4:  
   5: var list = from num in numbers
   6:            select double.Parse(num.Insert(25, "."));
   7:  
   8: var sum = list.Sum();
   9: string answer = sum.ToString().Replace(".", "").Substring(0, 10);
Technorati Tags: ,,
Posted by PSteele | 3 comment(s)
Filed under: ,

Loops, Conversions and Lambdas

I ran across some old code today while fixing a bug and was able to simplify it quite a bit using the latest version of C# – 3.5 (as well as fix the bug!).  Changing the code reminded me of where we (.NET developers) came from and how we've gotten to where we are today.

Data Conversion

For the sake of argument, let's say I have a double array.  I need to use this double array in a UI routine that expects a string[] (a representation of my doubles).  Back in .NET 1.x, converting this to a string[] was pretty simple (and we're ignoring culture issues in the interest of simplicity):

   1: // convert double[] to string[]
   2: string[] sa = new string[data.Length];
   3: for (int i = 0; i < data.Length; i++)
   4: {
   5:     sa[i] = data[i].ToString();
   6: }

.NET 2.0

When .NET 2.0 hit the scene, we got generics.  Since converting an array of data from one type to another was so common, Microsoft took advantage of generics and gave us Array.ConvertAll():

   1: public static TOutput[] ConvertAll<TInput, TOutput>(TInput[] array, Converter<TInput, TOutput> converter);

This takes an array of some type (TInput[]) and produces an array of a different type (TOutput).  The second parameter is a delegate that does the conversion routine.  Array.ConvertAll creates your output array and loops through your input array, calling the method pointed to by your delegate for each member to do the conversion.  A simple example would be:

   1: string[] genericSA = Array.ConvertAll(data, new Converter<double, string>(DoubleToStringConverter));
   2:  
   3: private static string DoubleToStringConverter(double d)
   4: {
   5:     return d.ToString();
   6: }

Anonymous Methods

So if we consider our first example, we took lines 2-6 and trimmed them down to one line of code (Array.ConvertAll).  But, in the process, we had to create that conversion method that contained the logic from line 5.  Microsoft decided that it would be nice to just sort of "inline" your method logic right in the code.  That's where anonymous methods come in.

The second parameter to Array.ConvertAll has to be a delegate of type Converter<TInput,TOutput> – or more specifically in our case, Converter<double,string>.  Since the compiler knows this, why require the developer to type in a whole separate method along with a delegate creation statement?  With anonymous methods, we can put our conversion code right in the call to Array.ConvertAll:

   1: string[] sa2 = Array.ConvertAll(data, delegate(double d) { return d.ToString(); });

Now we're getting some pretty clean code!  Our conversion code is right there inside our call to ConvertAll (easier for reading and code reviews).  This code will compile to almost the exact same code as earlier (where we had our own method and delegate conversion) because internally, the C# compiler will actually create a separate method (anonymously!) with our "return d.ToString()" code and will also generate a new Converter<double, string> delegate to pass to the ConvertAll method.  Nice!

Lambdas

The final icing on the cake for this conversion is the introduction of lambdas.  Lambdas seem a little scary at first, but if you've followed along with this example, you'll see how the lambda syntax has been implemented.

Like the introduction of anonymous methods, lambdas help us reduce the amount of code we write by inferring details that exist in your code.  Like our anonymous method example where the compiler will create the anonymous method and delegate call, a lambda will do the same thing.  So if we look at our conversion code above:

   1: delegate(double d) { return d.ToString(); }

The C# compiler knows we need a delegate that takes a double (since we're passing in a double[]) and returns a string (the returning of a string is inferred because the anonymous method returns a string).  If it knows all that, why make the developer type in "delegate" and the type of data ("double")?  Enter lambdas.  The above code can now be reduced to the following lambda expression:

   1: (d) => d.ToString()

If you only have a single argument, you can skip the parenthesis and simply enter:

   1: d => d.ToString()

The "return" is implied.  Microsoft says the "=>" operator is read as "goes to".  So our example reads "d goes to d.ToString()".  As before, this code will compile to almost exactly the same code as our first Array.ConvertAll example using a separate method and delegate creation (and exactly the same code as when we used anonymous methods).  But this time, we let the compiler to most of the plumbing.

End Result

We've taken our original 1.x code of:

   1: string[] sa = new string[data.Length];
   2: for (int i = 0; i < data.Length; i++)
   3: {
   4:     sa[i] = data[i].ToString();
   5: }

And have been able to reduce it down to the following C# 3.5 code:

   1: string[] lambdaSA = Array.ConvertAll(data, d => d.ToString());

I hope this little history has given you a good overview of how we moved from delegates, to anonymous methods and finally to lambdas.  Lambda expressions provide a lot of power to us and you should at least work on being able to read them as you'll see them more and more as .NET 3.5 becomes mainstream.

Technorati Tags: ,,
Posted by PSteele | 7 comment(s)
Filed under:

GANG Holiday Party

As always is the case in December, GANG doesn't hold a regular user group meeting.  Instead, we invite all supporting members to our Holiday Party.  Like last year, we'll be having a nice get together at Microsoft's Southfield, Michigan offices from 6:00pm – 9:00pm EST.  We'll provide pizza and other snacks, beverages, some XBOX 360's all wired up for play and a few Texas Hold 'Em games running.

Please note that this event is for supporting members only.  If you'd like to become a supporting member (it's only $20!), we'll be accepting payment at the door.  Bring yourself and a guest and have a great time!

And thanks to Brooksource for sponsoring this event!

Posted by PSteele | with no comments
Filed under:

Synchronization in WinForms with Lambdas

In a recent thread in the ADVANCED-DOTNET mailing list, the topic of multiple threads and WinForms came up.  As you probably know, Windows Forms controls can only be accessed/manipulated from the thread on which they were created.  The topic of Control.Invoke came up and Richard Blewett made the following comment:

As an aside, I generally find the programming model introduced with SynchronizationContext in v2.0 to be simpler than using the Control.InvokeRequired/Control.BeginInvoke pair

I had never even heard of this object so I did some research.  There's a WindowsFormsSynchronizationContext that handles executing code on the main UI thread.  Matt Dotson has an example of using the synchronization context to update a Textbox from a background thread.  The code is pretty simple:

   1: context.Send(new SendOrPostCallback(
   2:       delegate(object state)
   3:       {
   4:           //This executes on the ui thread
   5:           textBox1.Text = DateTime.Now.ToLongTimeString();
   6:       }
   7:    ), null);

But it becomes even simpler with C# 3.5's lambda syntax:

   1: context.Send(s => textBox1.Text = DateTime.Now.ToLongTimeString(), null);

Nice!

Technorati Tags: ,,
Posted by PSteele | 1 comment(s)
Filed under:
More Posts