Project Euler #3

Here’s the next one. I’m not happy with the way I determine if it’s a prime number (checking the modulo of every possible number), but it works.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

def find_largest_prime_factor(n)
  if n % 2 == 0
    find_largest_prime_factor(n/2)
  else
    x = find_divisor(n, 3)
  end
  puts x
end

def find_divisor(number, divisor)
  return divisor if divisor >= number
  if number % divisor == 0
    find_divisor(number/divisor, divisor)
  else
    find_divisor(number, divisor+2)
  end
end

find_largest_prime_factor(600851475143)

And the golf…

# Score: 98
def a n;p n%2==0?a(n/2):b(n,3);end;def b(n, d);d>=n ?d:n%d==0?b(n/d,d):b(n,d+2);end;a 600851475143

Project Euler #2

Here we go, Project Euler #2!

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

one_back, two_back, current_fib, total = 1, 1, 0, 0</code>

while current_fib &lt; 4_000_000 do
two_back = one_back
one_back = current_fib
current_fib = one_back + two_back
total += current_fib if current_fib % 2 == 0
end

puts total

And the golf…

# Score: 69
a,b,c,t=1,0,0,0;while(c<4000000):b=a;a=c;c=a+b;t+=c if c%2==0;end;p t

EDIT!

I knew there was a way to do it without that stupid current_fib variable, but I couldn’t get it to work at first. Then, as soon as I post, I realised what I was doing wrong.

one_back, two_back, total = 1, 1, 0

while one_back < 4_000_000 do
  total += one_back if one_back % 2 == 0
  current = one_back
  one_back += two_back
  two_back = current
end

puts total

And, even better, it improved my golf score!

# Score: 63
a,b,t=1,1,0;while a<4000000:t+=a if a%2==0;c=a;a+=b;b=c;end;p t

Jim Weirich on Connascence

I was recently at RailsConf in Las Vegas. For me, the stand-out best talk was Jim Weirich’s session on Connascence, “Writing Modular Applications.” I, unfortunately, couldn’t find a video of the talk he gave at RailsConf, but he gave the same talk at Mountain West Ruby Conf 2009, and you can watch a video of that here. I truly believe that this is one of those things that every programmer should watch. What are you doing still reading this? Go watch.

Project Euler #1

I recently signed up for Project Euler. I’ve decided to see how far I can get, both just solving the problems and “golfing” them. If you’re not familiar with programming golf, it’s when you try to write as few lines of code and characters as possible.

So far, I’ve only solved the first problem, as I’ve just started. I’m looking forward to doing more in the future. If you’re interested, here’s my solution, along with my golf solution.

# If we list all the natural numbers below 10 that are
# multiples of 3 or 5, we get 3, 5, 6 and 9. The sum
# of these multiples is 23.
# Find the sum of all the multiples of 3 or 5 below 1000.

total = 0
1000.times do |i|
  if i % 3 == 0 or i % 5 == 0
    total += i
  end
end
puts total

# Score: 45
t=0;1000.times{|i|t+=i if i%3==0||i%5==0};p t

Last.fm Wallpaper

This has nothing to do with Ruby or .Net, but I thought it was pretty neat.

If you have a Last.fm account, you should check out the Last.fm Wallpaper Generator. It takes some of your top albums’ artwork and complies them into one big image. Pretty neat, and it’s not my background.

Finally, if you’re on Last.fm, please feel free to add me.

Happy coding.

Hashtables and .Net Web Services

If you’ve spent any time with .Net Webservices, you’ve probably seen this error:

System.NotSupportedException: The type System.Collections.Hashtable is not supported because it implements IDictionary.

Recently my co-worker Chelsea and I devised a way to get around this.  Hashtables are essentially collections of DictionaryEntrys with some extras to make certain functions.  So, all you have to do is convert from a Hashtable to a List<DictionaryEntry>.  Here’s how:

private static List<DictionaryEntry> ConvertHashToDictionaryEntryList(Hashtable source)
{
    var resultList = new List<DictionaryEntry>();

    foreach (DictionaryEntry item in source)
        resultList.Add(item);

    return resultList;
}

Hope this helps!  Happy coding.
Also posted to Fluid.Net, my employer’s blog about .Net development.

Solving Multiple Inheritance in C# 3.0

I recently came across a problem while trying to DRY my old code.  I had been two classes, one that inherits from DropDownList called DynamicDropDownList, and one that inherits from CheckBoxList called DynamicCheckBoxList.

Since both DropDownList and CheckBoxList inherit from ListControl, there was some duplicated code.  However, I was at a loss as to how to remove that since C# doesn’t support multiple inheritance.

I eventually came up with the following solution using Extensions Methods, which are new to C# 3.0.

First, create a new class to hold your duplicated methods.  Note that both the class and the method are declared static.

namespace YourNamespace
{
    public static class DynamicListControlExtension
    {
        public static void DoYourStuff(this ListControl listControl)
        {
            // Do your stuff here.
        }
    }
}

Then, in your soon-to-be-DRY classes include the following:

using YourNamespace;

namespace YourOtherNamespace
{
    public class DynamicDropDownList
    {
        public void RefactoredMethod()
        {
            this.DoYourStuff();
            // This method could also be written like this if you prefer:
            DynamicListControlExtension.DoYourStuff(this);
        }
    }
}

And there you have it!  You’ll notice that I’ve included the this qualifier.  It is necessary in this case.

As always, leave a comment if you have any questions.  Happy coding!

Ajax User Controls in ASP.Net MVC Preview 3

I was taking a look into how to ajax up my website using the new ASP.Net MVC stuff, and I came across some difficulties. After using Ruby on Rails for the better part of the last year, I expected to be able to call render_to_string or something similar on a UserControl, and replace a div with that string.

I’m writing a basic product page, and the product can come in many colours. I opted to ajaxify the colour pagination.

The first thing I did was get JQuery into my project. JQuery is a javascript library that makes a lot of the more common AJAX and DHTML tasks easier.

function ChangeColorwayPage(pageNumber) {
  // Hide the element with the id of colorway1
  $("#colorway1").hide("slow");
  // Generate the URL of the ajax call
  url = '/ColorWay/ChangeColorWayPage/<%= ViewData.Model.Style_Number %>/' + pageNumber;
  // Make a GET request to the URL.  The third parameter is the function that gets called after the ASP.Net code is run.
  $.get(url, null, function(data, status) {
    // Replace the HTML within the div 'colorway1'
    $("#colorway1").html(data);
    // Show the div again!
    $("#colorway1").show("slow");
  });
}

This was easy enough. The tricky part came when rendering a UserControl into a string. I opted to make a simple AjaxController that inherits from the base Controller object.

namespace YourApp.Controllers
{
    public class AjaxController : Controller
    {
        public string RenderToString(string UserControl, object model, Dictionary<string, object> ViewParameters)
        {
            // Replace the current context with a new context that writes to a string writer
            var existingContext = System.Web.HttpContext.Current;
            var writer = new StringWriter();
            var response = new HttpResponse(writer);
            var context = new HttpContext(existingContext.Request, response) {
                User = existingContext.User
            };
            System.Web.HttpContext.Current = context;

            // Add the ViewParameters to the ViewData hash
            foreach (string key in ViewParameters.Keys)
                ViewData[key] = ViewParameters[key];

            // Execute the action
            var viewResult = View(UserControl, model);

            // Execute the result
            viewResult.ExecuteResult(ControllerContext);

            // Restore the old context
            System.Web.HttpContext.Current = existingContext;

            return writer.ToString();
        }
    }
}

And now, in my ColorWay controller, all I have to do is this:

namespace YourApp.Controllers
{
    // Notice that it inherits from AjaxController
    public class ColorWayController : AjaxController
    {
        public string ChangeColorWayPage(string sellingStyleNumber, int pageNumber)
        {
            var productSpecs = new ProductSpec(sellingStyleNumber, false);
            var parameters = new Dictionary<string, object>();
            parameters["page"] = pageNumber;

            // Simply call RenderToString and you're good to go!
            return RenderToString("ProductSpecColorWay", productSpecs, parameters);
        }
    }
}

And with that, you should be good to go.

Happy coding!

Single Quotes or Double Quotes?

Josh Susser recently had an interesting article about Symbols. I had noticed that in many places where I thought I should be able to use symbols, I had to use strings (the routes file comes to mind).

Reading that post got me thinking about the differences between ’strings’ and “strings.” I knew that “strings” allowed you to do mid-string insertions:

puts "Your variable is #{my_var}."

On the other hand, with ’strings’ you had to use plus signs:

'Your variable is ' + my_var + '.'

I began to wonder if one was faster than the other. I had been told that single quotes were faster, but I had no idea if this was true, or by how much. I decided to run some benchmarks to see how quickly a string could be saved using the different methods.

require 'benchmark'
test_variable = 'a string'

Benchmark.bm do |x|
  x.report("Single Quotes, no insertion") {
    10000.times do
      str = 'Text without insertion'
    end
  }

  x.report("Double Quotes, no insertion") {
    10000.times do
      str = "Text without insertion"
    end
  }

  x.report("Single Quotes, with insertion") {
    10000.times do
      str = 'Inserting ' + test_variable + ' into a string.'
    end
  }

  x.report("Double Quotes, with insertion") {
    10000.times do
      str = "Inserting #{test_variable} into a string."
    end
  }
end

It turns out that single quotes are, in fact, slower than double quotes. Here’s my results:

                               user       system     total    real
Single Quotes, no insertion    0.000000   0.000000   0.000000 (  0.003485)
Double Quotes, no insertion    0.010000   0.000000   0.010000 (  0.002694)
Single Quotes, with insertion  0.010000   0.000000   0.010000 (  0.011286)
Double Quotes, with insertion  0.010000   0.000000   0.010000 (  0.009462)


Now keep in mind, my benchmarks were based on saving 10,000 strings. That means for every string using single quotes you have is wasting over 0.00000018 seconds. In other words, you would need to convert about 5.4 million single-quoted strings to double-quoted string to save one second of running time.

Happy coding!