Project Euler Problem 3

For Problem 3, the goal is to find the largest prime factor of the number 600851475143. For this, I created a prime number generator in my NumberGenerator class, called Primes(), which takes a single parameter indicating the largest prime number we want returned. It uses the "yield return" operator to return the primes.

public static IEnumerable Primes(long max)
{
var nonPrimes = new bool[max + 1];

for (long i = 2; i <= max; i++)
{
if (nonPrimes[i] == false)
{
for (var j = i * i; j <= max; j += i)
{
nonPrimes[j] = true;
}
yield return i;
}
}
}

I then call that generator using the square root of the target number as the maximum prime number to return. I use a Linq where clause to only return prime numbers that are factors of the target number, then use the Last() method to just return the last of these. This gives me my answer.

public void Run()
{
const long target = 600851475143L;
int sqrt = (int)Math.Sqrt(target);

long answer = NumberGenerator.Primes(sqrt).Where(x => target % x == 0).Last();

Console.WriteLine("answer = {0}", answer);
}

I was pretty happy with how short the code for this turned out, once the prime number generator was written. I've since used the prime number generator quite a bit in other Euler problems, so making it separate was a good decision.

Project Euler Problem 1

For Problem 1, we are asked to "Find the sum of all the multiples of 3 or 5 below 1000." To do this, I created a helper function called Integers(), contained in a class called NumberGenerator. This method uses the "yield return" operator to return integers, starting at 1. It is as follows:

public static IEnumerable Integers()
{
long currentValue = 1;
while (true)
{
yield return currentValue++;
}
}

Then, the main method of the Problem001 class uses the "Integers()" method along with LINQ expressions, as follows:

public class Problem001
{
public void Run()
{
var expression = new Func(
p => p.IsMultipleOf(3) || p.IsMultipleOf(5));
Console.WriteLine("Sum using Linq expression: {0}", NumberGenerator.Integers().Take(999).Where(expression).Sum());
}
}

I also added an extension method to the long type called "IsMultipleOf()", which is implemented as follows:

public static bool IsMultipleOf(this long x, int m)
{
return (x % m == 0);
}

This was my first real exposure to LINQ and enumerators, and I was pretty impressed with it. Note that this code was very similar to that of Steve Smith, as I noted in my previous post that he was the inspiration for me getting into Project Euler in the first place.

Project Euler

I realize I've been neglecting this blog for awhile, but I think I finally have something interesting to write about, so I'm going to try keeping this updated again.

After a recent post by Steve Smith, I got started doing some of the Project Euler problems. Like Steve, I've been using this as an opportunity to get more familiar with some of the .NET 2.0/3.5 features that I haven't used much in my daily coding, including Linq, iterators and extension methods.

Over the next few posts, I'll be writing about some of the problems, and posting my solutions to them. I won't post code for every problem, just some of the ones I've found more interesting, or that I came up with a cool solution for.

For today, I will post the class launcher (i.e., the main program). The way I structured things, I created a solution in Visual Studio called ProjectEuler. I then create a class for each problem, called "ProblemNNN" where "NNN" is the problem number. The launcher takes the class name on the command line, then uses reflection to load the class, instantiate an instance of it then run it. It also times the execution and displays the elapsed time at the end. Below is the code for the Launcher class.

using System;
using System.Linq;
using System.Reflection;
using System.Diagnostics;

namespace ProjectEuler
{
public class Launcher
{
public static void Main(string[] args)
{
Assembly myAssembly = Assembly.GetExecutingAssembly();
try
{
if (args.Length != 1)
{
Usage(myAssembly, false);
}

if (args[0] == "/?")
{
Usage(myAssembly, true);
}

Type type = myAssembly.GetType("ProjectEuler." + args[0]);

if (type == null)
{
Console.WriteLine("Class {0} not found\r\n", args[0]);
Usage(myAssembly, true);
return;
}

var obj = Activator.CreateInstance(type);

Console.WriteLine("\nEuler {0}", args[0]);
Console.WriteLine("================\n");

FieldInfo summary = type.GetField("summary");
Console.WriteLine("{0}\r\n", summary.GetValue(obj));

Stopwatch sw = new Stopwatch();
sw.Start();

type.InvokeMember("Run", BindingFlags.Default | BindingFlags.InvokeMethod, null, obj, null);

sw.Stop();
Console.WriteLine("\r\nElapsed time: {0} ({1} ms)", sw.Elapsed, sw.ElapsedMilliseconds);

if (Debugger.IsAttached)
{
Console.WriteLine("\nPress return to quit.");
Console.ReadLine();
}
}
catch (Exception ex)
{
if (args.Length > 0)
{
Console.WriteLine("Exception trying to execute method on {0}: {1}\r\n", args[0], ex.Message);
if (ex.InnerException != null)
{
Console.WriteLine(" Inner exception: {0}", ex.InnerException);
}
}
else
{
Console.WriteLine("Exception in problem runner methods: {0}\r\n", ex.Message);
}
Usage(myAssembly, false);
}
}

private static void Usage(Assembly myAssembly, bool showClasses)
{
Console.WriteLine("Usage: ProjectEuler.exe ");

if (showClasses)
{
Console.WriteLine("\r\nPossible classnames:");

myAssembly.GetTypes().Where(t => t.Name.StartsWith("Problem")).OrderBy(t => t.Name).ToList().ForEach(
t => Console.WriteLine(" {0}", t.Name));
}
else
{
Console.Out.WriteLine(" add /? to show list of classes");
}

Environment.Exit(1);
}
}
}


.NET and PHP Encryption

For a project I'm currently researching at work, we are going to be doing some encrypted communication with a third-party.  Normally, if both companies were using .NET, that would be simple; however, this company uses PHP on Linux, which complicates things a bit.

I talked with their developer, and he was planning on using the PHP functions openssl_public_encrypt() and openssl_private_decrypt() for the encryption and decryption. I did some research, and found this page that described the .NET equivalents. That got me started, but the next problem was that he sent his public key in PEM format, which looks like this:

-----BEGIN PUBLIC KEY-----
(base-64 encoded data here)
-----END PUBLIC KEY-----

From what I could gather, .NET can't read this format, at least not with the built-in classes. I did more research and found this tool which converts between PEM and .NET (and other) formats. When run on the PEM-format public key, this generates a file that looks like this:


<rsakeyvalue>
<modulus>(base-64 encoded data)</modulus>
<exponent>(data)</exponent>
</rsakeyvalue>


This is directly usable by the .NET class RSACryptoServiceProvider using the FromXmlString() method. The same tool can be used to convert the private key to an Xml file, which can be read in using the same class and method.  Once the keys are read in, you can use the Encrypt() and Decrypt() methods on your data.

Are Certifications Worth It?

For our training this year, because of budget limitations, we were restricted from traveling, and ended up all getting CBTs that should enable us to get some Microsoft certifications. I'm about to start my training, and I've started wondering if it will be worth it.

On the one hand, doing the study necessary to earn it will definitely expose me to more of the .NET framework and the C# language than I may have been in by day-to-day programming. Of course, a lot of it may be things that I don't really have a need to know, since certification exams tend to ask about such a wide range of topics.

On the other hand, it's been my experience in the past that getting a certification doesn't usually buy you anything at your current employer; they're more useful when looking for something new. I'm not currently looking for a job, nor am I expecting to (though you never know, especially with the economy going the way it is).

I'm not going to turn down the chance to take a week and study, and I'll definitely take the exams and get the certifications, but I'm still not sure exactly how much benefit I will gain from this.

ORMs and Generated Code

At my job, we've been using a code generator for our main applications since we originally started writing them over 5 years ago. It implements Object-Relational Mapping (ORM) and generates most of the code necessary to read and write objects from the database, even includig some rudimentary business logic. Since we started, we've also extended this to include generating some things that I didn't think could even be generated, like Windows dropdowns with enumerations and a custom stored procedure for keeping a permission table up to date.

Overall, it has been a good system, and it has certainly saved us a lot of time over the years. It is very nice to be able to put a bunch of XML into a file, run the code generator, and get virtually everything we need to work with a new table or set of tables.

Still, it has some limitations, and some other issues that have made me reconsider whether using it has been a good idea 100% of the time.

First, the tool we use to generate the code was written by a consulting company that our company used for many years before the IT department became as fully staffed as it is now. Unfortunately, a couple of years ago we severed ties with that company, which means we no longer get updated versions of the tool. It was written in .NET 1.1, and the C# parser still only understands 1.1 constructs. That means if we use anything introduced in 2.0 or later, like generics, LINQ, etc., we get errors when we run the tool. We have source for most of the tool, but we are missing it for the C# parser, which is exactly what we would need to modify to fix this.

Next, I feel like in some ways, it has kept me from learning everything I could about ADO.NET. Unless we have some custom stuff we need to do in the database that the tool can't generate, we just end up calling generated methods to read and write from the database. Now, I do understand how it works, and in fact, I extended it to include the .NET 2.0 transaction model, but I still wonder if I would know more about ADO.NET if it weren't for this tool.

Finally, it has introduced somewhat of a learning curve as we have brought new developers onto the project, especially if they are not really experienced developers. Since it generates so much of the business logic and data access layers, developers have to be trained to not just jump in and start writing or changing code that touches those areas. They need to understand that some of their changes may be wiped out by the tool if they don't do them correctly. So far, most have been positive about this, and have caught on quickly, but it is still something different than most people are used to.

So, looking back, would I have done anything differently if I could have? It's hard to say. Probably the biggest change I would have liked to have made would be to somehow keep the generated code separate from any custom code we wrote. If we had had .NET 2.0 back then, we could have used partial classes (and in fact, if I had the source to the C# parser, that would be the first thing I would add). As it is, the code is all mixed together, and it can sometimes be hard to tell what is getting generated and what is hand-coded. I definitely would not have chosen to write everything by hand. I definitely believe generating code like this is beneficial.

ASP.NET MVC First Impressions

There's been a lot of discussion online lately about Microsoft's new ASP.NET MVC framework. If you don't know what it is, it is a new, alternative framework for web development. It isn't meant to replace ASP.NET web forms, but instead be another choice.

I've been reading about it and playing with the preview releases a bit, so I thought I would write up my brief first impressions. Later on, after I've had a chance to work with it a bit more, and maybe build something useful with it, I'll come back and write something else.

Things I like:

• The separation of logic. I like how it breaks up the presentation (View), logic (Controller) and data (Model) into separate files. It would make it easy to have alternate views of the same data. For example, if you were writing a blog enginge, you could have one view be the normal text view, and another view be the RSS feed.


• URL handling. I wrote recently about URL rewriting using ASP.NET web forms. If we were using ASP.NET MVC, we would have been able to have more friendly URLs with no "tricky" code to intercept the calls and rewrite them to what we already had.


• Cleaner HTML. One of the things I've run into with web forms that has bugged me is the way it renames form elements to things like "ctl00$Leftnavigation1$productSearch". Since you're now responsible for generating form elements yourself, you no longer get this.


• Testing. Since the model and controller logic are separated from the view, you can now write unit tests against them.


• Lots of community support. As I mentioned above, a lot of people are using this and talking about it, so before long, there will be plenty of places to go for answers to questions.

Things I'm not wild about:

• Tag soup. I think there are more ways to do this, but most of the examples I've seen involve putting C# or VB code right in the .aspx file. It's like a return to bad old ASP days.


• Lack of view state. Again, I'm not sure if this is the only way, but so far everything I've seen indicates that you have to manually repopulate form fields, just like in ASP. And this is actually getting better. I noticed in Scott Guthrie's recent post that Preview 5 now automatically repopulates fields in an error condition.


• It is a completely different model from what I (and the other devs on my team) are used to. This is obviously not a huge complaint, since I enjoy learning new things, but if we decide to use this, it will take some time to get everyone up to speed.


• Sparse official documentation. I realize it is still in preview stage, so hopefully this will get better over time.

Overall, this is an interesting framework, and it will be nice to have a choice when developing new projects. Having said that, I don't think we will be rushing to rewrite all our existing code into MVC. We just have far too much time and knowledge invested in what we already have.