Project Euler 006 – IronRuby

9 03 2011

Problem 6

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution

#The sum of the squares of

 #the first ten natural numbers is,

 #

 #1^2 + 2^2 + … + 10^2 = 385

 #The square of the sum of the

 #first ten natural numbers is,

 #

 #(1 + 2 + … + 10)^2 = 55^2 = 3025

 #Hence the difference between the sum

 #of the squares of the first ten natural

 #numbers and the square of the sum is

 #3025 – 385 = 2640.

 #

 #Find the difference between the sum of

 #the squares of the first one hundred natural

 #numbers and the square of the sum.

 

n = 100

answer = (n*(n+1) / 2)**2 (n*(n+1)*(2*n+1)) / 6

puts answer

 

Discussion

And there’s your trick.  Incidentally, I need to create a cheat sheet for the math functions in all of these languages.  ** is not in my vocabulary.  It’s nice though.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).





Project Euler 006 – C#

8 03 2011

Problem 6

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution

//The sum of the squares of

 //the first ten natural numbers is,

 

 //1^2 + 2^2 + … + 10^2 = 385

 //The square of the sum of the

 //first ten natural numbers is,

 

 //(1 + 2 + … + 10)^2 = 55^2 = 3025

 //Hence the difference between the sum

 //of the squares of the first ten natural

 //numbers and the square of the sum is

 //3025 – 385 = 2640.

 

 //Find the difference between the sum of

 //the squares of the first one hundred natural

 //numbers and the square of the sum.

 

 

namespace ProjectEulerCSharp_006

{

    class Program

    {

        static void Main(string[] args)

        {

            int sumsqrs = 0;

            int sqrsums = 0;

            for (int i = 0; i <= 100; i++)

            {

                sumsqrs += i * i;

                sqrsums += i;

            }

            sqrsums *= sqrsums;

            System.Console.WriteLine(sqrsums – sumsqrs);

        }

    }

}

 

Discussion

No trick today. 

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).





Project Euler 006 – F#

7 03 2011

Problem 6

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution

(*

 The sum of the squares of

 the first ten natural numbers is,

 

 1^2 + 2^2 + … + 10^2 = 385

 The square of the sum of the

 first ten natural numbers is,

 

 (1 + 2 + … + 10)^2 = 55^2 = 3025

 Hence the difference between the sum

 of the squares of the first ten natural

 numbers and the square of the sum is

 3025 – 385 = 2640.

 

 Find the difference between the sum of

 the squares of the first one hundred natural

 numbers and the square of the sum.

*)

 

let sqr x = x*x

let numbers = [1..100]

 

let sumofsqrs x = x

                  |> List.map sqr

                  |> List.sum

 

let sqrofsum x = x

                 |> List.sum

                 |> sqr

 

let answer x = sqrofsum x – sumofsqrs x

 

printfn "%A" (answer numbers)

Discussion

The F# solution is rather elegant once again.  There is a common math ‘trick’, but for only 100 elements there is no reason to shy away from the brute force solution.  Later this week we’ll see the trick.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).





Project Euler 005 – JavaScript

4 03 2011

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&gt;

<html xmlns="http://www.w3.org/1999/xhtml"&gt;

 

<!–

 2520 is the smallest number that can be

 divided by each of the numbers from 1 to 10

 without any remainder.

 

 What is the smallest positive number

 that is evenly divisible by all of the

 numbers from 1 to 20?

–>

 

<head>

    <title>Project Euler 005</title>

</head>

<body >

    <script type="text/javascript">

 

        factors = [16, 9, 5, 7, 11, 13, 17, 19];

        answer = 1;

        for (i = 0; i < factors.length; i++) {

            answer *= factors[i];

        }

        document.write("<b>" + answer + "</b>");

    </script>

</body>

</html>

 

Discussion

I looked into a reduce function for JavaScript but it seemed more difficult than a simple loop in this case.  So that’s what you got – a simple loop.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).





Project Euler 005 – TSQL

3 03 2011

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

— 2520 is the smallest number that can be

— divided by each of the numbers from 1 to 10

— without any remainder.

 

— What is the smallest positive number

— that is evenly divisible by all of the

— numbers from 1 to 20?

 

SELECT EXP(SUM(LOG(POWER(number, FLOOR(LOG(20) / log(number))))))

FROM Number WHERE isprime = 1

AND number < 20

Discussion

I’ll admit it.  I am pretty proud of this solution.  Assuming that we have a list of primes already (which we do) there are two problems that we need to solve.  The first is, what is the proper exponent for each prime?

If you remember from Monday’s solution (F#), I mentioned that 25 was too big (32 > 20) so 24 was the number we needed to use?  So how do you figure that out?  Well, we want to find the maximum k such that

2k ≤ 20

Right?  Let’s solve for k.  Here’s the “trick”:

log(2k) ≤ log(20)

k*log(2) ≤ log(20)

k ≤ log(20)/log(2)

k ≤ 4.32

Since k is an integer, we can set it to 4.  That’s pretty easy.

The next problem I ran into was that SQL doesn’t natively support a “product” aggregate and doesn’t appear to have a convenient fold mechanism.  I was able to solve it with COALESCE, but that required a separate variable to accumulate the results.  I really wanted to solve this with a simple query.  Then I found another trick…

log(a*b) = log(a)+log(b)

So I could use the built in sum aggregator to find the product.  That is

a*b*c… = exp(log(a) + log(b) + log(c)…)

When you couple this trick with the original you find your answer.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).





Project Euler 005 – IronRuby

2 03 2011

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

# 2520 is the smallest number that can be

# divided by each of the numbers from 1 to 10

# without any remainder.

 

# What is the smallest positive number

# that is evenly divisible by all of the

# numbers from 1 to 20?

 

#I had to shorten this to fit on the blog

#correctly so

#r = result

#e = element

answer = [16,9,5,7,11,13,17,19].inject(1) {|r, e| r * e }

puts answer

 

Discussion

Well, that was easy.  I really enjoy inject style methods for operating on arrays..

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).





Phone Vision 15 – Median Filters

1 03 2011

Filters, filters, filters… Tired of them yet?  Me too.  After this we’ll leave them alone for a while.  I promise.  Until then, we have work to do.

What is a median filter?  If you understand the average filter (or mean filter) then the median filter should give you no troubles at all – assuming you know what the median is.  We’ll start there.

What is the Median?

The median is the middle number of a sample.  To find it, you sort your list and pick the middle item.  Yes, it really is that simple.

Here is a random set of 9 numbers:

image

Sort them:

image

Pick the middle value:

image

Like I said, it’s simple.

Why use median instead of mean?

The median is particularly effective against certain types of noise – specifically “salt and pepper” noise (black and white specks).  Let’s assume this is the neighborhood we’re dealing with:

image

Performing the mean gives:

image

image

While the median returns:

image

image

If we expect that the 0 values are noise then the median is probably a much closer estimate.

Code

private WriteableBitmap MedianFilter(WriteableBitmap grayscale, int radius)

{

    // we are still going to create a new image

    // because we don’t want to modify the

    // old image as we are processing it

    WriteableBitmap filtered =

        new WriteableBitmap(

            grayscale.PixelWidth,

            grayscale.PixelHeight);

 

    // boiler plate code for our

    // histogram stuff

    int[] histogram = new int[256];

    int maxIntensity = 0;

 

    // the math is still easier if we create two loops

    // instead of one

    for (int y = 0; y < grayscale.PixelHeight; y++)

    {

        for (int x = 0; x < grayscale.PixelWidth; x++)

        {

            //here’s the pixel we’re centered on

            int pixel = x + y * grayscale.PixelWidth;

            byte intensity = (byte)grayscale.Pixels[pixel];

 

            // if we are on an edge we are going to leave it

            // as the original intensity.  you will see the

            // edges increasingly unsmoothed as the window

            // size increases.  here we are using the radius

            // to determine our bounds

            if (y <= radius – 1 ||

                x <= radius – 1 ||

                y >= grayscale.PixelHeight – radius ||

                x >= grayscale.PixelWidth – radius)

            {

 

                histogram[intensity]++;

                if (histogram[intensity] > maxIntensity)

                {

                    maxIntensity = histogram[intensity];

                }

                continue;

            }

 

            /////////////////////////////////////////////////////////

            // IMPORTANT PART ///////////////////////////////////////

            /////////////////////////////////////////////////////////

            // this list is the key

            // it contains all of the neighboring pixels

            List<byte> localIntensities = new List<byte>();

            for (int yoffset = -radius; yoffset <= radius; yoffset++)

            {

                for (int xoffset = -radius;

                    xoffset <= radius;

                    xoffset++)

                {

                    localIntensities.Add((

                        (byte)grayscale.Pixels[(x + xoffset)

                        + (y + yoffset) * grayscale.PixelWidth]));

                }

            }

            //sort the intensities

            localIntensities.Sort();

            //pick the middle value

            int medianLocalIntensity =

             localIntensities[(int)(localIntensities.Count/2.0+.5)];

            /////////////////////////////////////////////////////////

            // END IMPORTANT PART ///////////////////////////////////

            /////////////////////////////////////////////////////////

                   

            // and now just set the color

            filtered.Pixels[pixel] = (255 << 24)

                | (byte)medianLocalIntensity << 16

                | (byte)medianLocalIntensity << 8

                | (byte)medianLocalIntensity;

 

            histogram[(byte)medianLocalIntensity]++;

            if (histogram[(byte)medianLocalIntensity] > maxIntensity)

            {

                maxIntensity = histogram[(byte)medianLocalIntensity];

            }

        }

    }

 

    PlotHistogram(histogram, maxIntensity);

    return filtered;

}

 

Results

Taking a simple gray image I added salt and pepper noise to the image then performed a median filter and an average filter to it.  The results are stunning.

imageimage

                flat gray image                              10% salt and pepper noise

imageimage

           after median filtering                      after mean filtering

There are a few specks after applying the median filter, but the noise is removed pretty well.  The average filter performed dismally to say the list.

Summary

If you expect salt and pepper noise then the median filter is great tool to have in your toolbox.  If you want you can explore max, min, and mode filters.  I don’t think we’ll cover them here unless we have a specific application for it.

Download Code

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2015%20-%20Median%20Filter.zip

(code includes salt and pepper noise generation)

Up Next: Binary Images

Feel free to leave a comment or follow @azzlsoft on Twitter if you have any questions.





Project Euler 005 – C#

1 03 2011

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

// 2520 is the smallest number that can be

// divided by each of the numbers from 1 to 10

// without any remainder.

 

// What is the smallest positive number

// that is evenly divisible by all of the

// numbers from 1 to 20? 

 

namespace ProjectEulerCSharp_005

{

    class Program

    {

        static void Main(string[] args)

        {

            //have we found the answer yet?

            //let’s start off by saying "no"

            bool notFound = true;

            //20 seems like as good of a

            //starting spot as any

            long candidate = 20;

            while(notFound)

            {

                //I am incrementing up front

                //so that my loop exits elegantly

                candidate++;

 

                //here I am assuming that this candidate

                //is the answer.  I set it back when I

                //find a divisor that it doesn’t work for

                notFound = false;

 

                //this is not too important, but it’s a good

                //idea to start with the small numbers first because

                //they are more likely to fail

                for (int divisor = 2; divisor <= 20; divisor++)

                {

                    if (candidate % divisor != 0)

                    {

                        notFound = true;

                        break;

                    }

                }

            }

 

            System.Console.WriteLine(candidate);

        }

    }

}

Discussion

The brute force approach is pretty silly, but it does work and within the 1 minute rule.  It takes about 7.5 seconds on my 6 month old laptop.  When this problem was announced (November 2001) the same code would have probably taken over 10 minutes to complete – at least according to my back of the napkin estimation of Moore’s law.  🙂

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).