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);
}
}
}


Using URL Rewriting For More Friendly Links

As part of an application we're developing at work, I recently did some research on whether it was possible to make the links to items, categories, etc., more friendly to search engines. The links we currently have are something like this: /website/productdetails.aspx?productid=123456. Basically, we pass in a product ID to the productdetails.aspx page. However, it would be nicer to have something more like /website/item/123456/rewritten-item-description.aspx.

I did some research and came up with some code that will work, and not be too intrusive to the rest of the code, or require any changes in IIS. First, we'll add a property to the items that returns a link in the correct format, so that we don't have to duplicate that code in the various places we show the link. To convert the item description to something that looks like a filename, I came up with the following method:

private string CreateLink(string prefix, string id, string description)
{
String format = "{0}/{1}/{2}.aspx";
String fixedDescription = "";
fixedDescription = description.Trim().Replace(" ", "-").Replace("&", "and").Replace("/", "-");

Regex nonWord = new Regex(@"[^\w\-]", RegexOptions.IgnoreCase);
fixedDescription = nonWord.Replace(fixedDescription, "");

fixedDescription = DeAccentCharacters(fixedDescription);

return String.Format(format, prefix, id, fixedDescription);
}

This strips out any non-word characters, replaces spaces and slashes with dashes, ampersands with the word "and" and converts accented characters to their non-accented counterparts (that part is done in DeAccentCharacters(), which I won't post, since it just uses a pre-made lookup table, and isn't that interesting). It then prefixes the name with the prefix and id, basically coming up with what I showed above.

Now that we have links in the correct format, we need to interpret them. Note that it looks like we have a couple of directories there ("item" and "123456") that don't actually exist. We need to intercept the request for this page before ASP.NET has a chance to complain about it not existing. To do that, we add some code in the Global.cs class in the App_Code directory. First, in the Application_Start() method, add this, anywhere in the method:

SetupRewriteRules();

This will set up a list of URL rewriting rules, using regular expressions. Then, in Application_BeginRequest(), add this as the first line, before anything else you may be doing:

RewriteURL();

This calls a new method that interprets the rules created in SetupRewriteRules() and rewrites the URL in the request accordingly.

Next, add this class to the file (at the end is preferable):

private class RewriteRule
{
private Regex rule;
private String rewrite;

public RewriteRule(String ruleRegex, String rewriteText)
{
rule = new Regex(ruleRegex, RegexOptions.Compiled | RegexOptions.IgnoreCase);
rewrite = rewriteText;
}

public String Process(String path)
{
Match match = rule.Match(path);

if (match.Success)
{
return rule.Replace(path, rewrite);
}

return string.Empty;
}
}

Next, add a static list to hold these and the SetupRewriteRules() method:

private static List<RewriteRule> rules = new List<RewriteRule>();

private void SetupRewriteRules()
{
rules.Add(new RewriteRule("Item/([^/]*)/(.*).aspx", "/ProductDetails.aspx?productID=$1"));
}

We have more rules, but I'll just show this one. Note that the first parameter is a regular expression that matches "Item/item ID/filename.aspx". The second parameter is what to replace that with. In this case, it takes the first match (the item ID, enclosed in the first set of parentheses), and puts it where the "$1" is in the URL.

Finally, add the RewriteURL() method:

private void RewriteURL()
{
foreach (RewriteRule rule in rules)
{
String subst = rule.Process(HttpContext.Current.Request.Path);
if (subst.Length > 0)
{
HttpContext.Current.RewritePath(subst);
break;
}
}
}

This code iterates through each rule, and if it finds one that matches, it calls RewritePath() using the rewritten URL. This is what actually translates the "friendly" URL into something that works with our application. The great part is that it is totally transparent to the user; they never see the rewritten URL. Postbacks still work fine as well.

I realize there are other ways to do this, like ASP.NET MVC, but our application is pretty much already written, and I'm not wild about going back and redoing it in a totally new technology. This can be retrofitted onto the app without too much pain, and could even be turned off or on with a config file setting if needed.

Debugging ASP.Net AJAX Pages

If you've done any ASP.Net AJAX development, you've probably run into the following error message while debugging (Sys.WebForms.PageRequestManagerTimeoutException: The server request timed out):

This happens because the default timeout for asynchronous processing is 90 seconds. This is a reasonable default, and really, nothing in an asynchronous request should take that long. However, if you're stepping through code of any complexity, you can easily exceed that limit. You can fix this by setting the timeout on your script manager, like this:

<asp:ScriptManager ID="MainScriptManager" runat="server" EnablePartialRendering="true" AsyncPostBackTimeout="3600" />

However, you probably don't want that in production. There is also a way to set this in your code-behind, and do it conditionally, based on whether your pages are running in debug mode or not. If you've been doing ASP.Net development for any amount of time you are probably aware that you shouldn't run your production site in with debug enabled in the web.config file. So, how do you tell if that is enabled? In that link, Scott Guthrie mentions that you can use HttpContext.Current.IsDebuggingEnabled to tell. So, the code to set this would look like this:

// if we're running debug mode, increase the async timeout to 1 hour.
// this allows stepping through code without timing out on the front end.
if (HttpContext.Current.IsDebuggingEnabled)
{
MainScriptManager.AsyncPostBackTimeout = 3600;
}

This only increases the timeout if you're running in debug mode. I've implemented this in one of our products, and it has worked great.

Windows Forms Standards

At work, we develop for both the web and for Windows. One of the things that we've had issues with over the years as developers come and go from our team, is keeping the Windows forms (written C#) consistent as far as usability goes. These are simple things to do, but sometimes hard to remember. I'm posting them here partly for me to remember and partly for others to maybe learn from. This list isn't meant to be exhaustive; just a few things seem to consistently pop up.

• Escape key should trigger the Cancel or Close button on the form. A lot people (me included) use the keyboard as much as possible, and this allows quickly closing the form you were using. To do this, just set the CancelButton property on the form to the ID of the appropriate button.
• If your form has an obvious default button, set that as well. This is done by setting the AcceptButton property. This allows the Enter key to trigger that button even when it doesn't have focus.
  
• Tab order should be set. Our internal standard is left to right, top to bottom on the form, unless otherwise specified by requirements. It doesn't matter what standard you use, as long as you have one and stick to it on every form you write. Visual Studio has a great visual way of doing this. With the form selected, click on View, then "Tab Order". This will put little numbers beside each form element. Just click on each element in the order you want them to be tabbed through. When you're done, the Escape key will exit out of this mode.
• Groupboxes should be used to separate functional areas on a form. For example, on a search form, the criteria would be in one groupbox, and the results grid would be in another. We use the Infragistics NetAdvantage suite, so we always use their UltraGroupBox control, but the standard Windows one works well too.
• Going back to keyboard usage: Menu items should have an accelerator key, where possible. To do this, just put an ampersand ("&") before the letter in the menu caption that you want to be the accelerator. This allows those of use who prefer using the keyboard to more quickly navigate around the application.
• Buttons on a form should also have accelerator keys when possible. This is done the same way it is for menus: just put “&” before the letter you want to be the accelerator. The “Cancel” button does not need this done, since it will always use Escape as its accelerator.
• For internationalization, we also always put field labels above the textbox or other control they refer to. This normally allows for more space to put in foreign languages, since they can end up being much longer than the original English equivalent.