Project Euler 007 – IronRuby

16 03 2011

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution

#By listing the first six prime numbers:

#2, 3, 5, 7, 11, and 13, we can see that

#the 6th prime is 13.

#What is the 10001st prime number?

 

primes = [2,3]

 

while primes.length < 10001 do

    candidate = primes[primes.length 1] + 2;

    isPrime = false

    while !isPrime do

        isPrime = true

        for prime in primes

            if candidate % prime == 0 then

                isPrime = false

                break

            end

        end

        if !isPrime then

            candidate += 2

        else

            primes.push(candidate)

        end

    end

end

 

puts primes[primes.length1]

 

Discussion

This is pretty much a straight port of the C# solution.  It turns out to be about an order of magnitude slower than the C# version (IronRuby ~11 seconds, C# ~ 1 second).  It still comes up with the correct answer, and it’s well within the 1 minute rule.

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

Advertisements




Phone Vision 17–Sets

16 03 2011

Last time we were able to get a pretty decent binary image.  The question is, what do we do with it?  Before we can answer that, we need to make sure you’ve got a basic understanding of set theory.

Sets

In a binary image we can think of the objects of interest as a set of points.  Here is our binary image from last time:

image

I am going to focus on just the top puzzle piece so let’s extract it.  (The code for extracting this is not important for this lesson, but it is included in the code as GetPuzzleImage).

image

We are going to be working with this image for a while.  In this case, the black pixels will represent members of our set.

Universe

The universe is the set of all possibilities.  In the case of image processing this is typically the set of all of the pixels.  I have seen this referred to as E2 (for 2-dimensional Euclidean space).  In our case, the universe is…

image

As expected, the set of every possibility is all black.  This is important some operations rely on this set.

Empty Set

The empty set is, well, empty.

image

Since the boundary for our image is not a specified size, this is just an empty image. If the universe was a specified size then the empty set would often be represented by a completely white image.

Complement

The complement is everything in the universe that is not in the set.  The complement of our puzzle piece:

image

The puzzle piece is now a hole in the black image.

Union (⋃)

The union is the set of all elements in either of two sets.  If you have been playing along, this is very similar to the | (binary OR) operation mentioned in lesson three. Below we union the puzzle set with the set of its complement.  The output is the universe.

image

image

image

Intersection (⋂)

Finally, the intersection is the set of all shared members of two sets.  Below we intersect the puzzle set with its complement.  This is similar to the & (binary AND) operations mentioned way back in lesson 2.  Since the complement of a set  doesn’t share any elements with the original set the output is going to be the empty set.

imageimageimage

Pixel Set

In order to demonstrate these concepts (and a few in the future) I created a class called PixelSet that behaves similar to a mathematical set. 

Caution: This set is not optimized for use in actual applications.  You’ve been warned.

Elements

The elements of the set are represented by a Dictionary.

Dictionary<int, List<int>> _pixels = new Dictionary<int, List<int>>();

The key is the y-value for the pixel and the List<int> represents all x-values in that row.

 

Add

 

public void Add(int x, int y)

{

    List<int> columns = new List<int>();

    if (!_pixels.ContainsKey(y))

    {

        _pixels.Add(y, columns);

    }

    else

    {

        columns = _pixels[y];

    }

 

    if (!columns.Contains(x))

    {

        columns.Add(x);

    }

}

 

The add function is a little tricky because if the row (y-value) doesn’t have a representative in the set yet then we need to create a new list to contain them. If it does, then we need to use the existing list.

 

Remove

 

public void Remove(int x, int y)

{

    if (_pixels.ContainsKey(y))

    {

        if (_pixels[y].Contains(x))

        {

            _pixels[y].Remove(x);

            if (_pixels[y].Count == 0)

            {

                _pixels.Remove(y);

            }

        }

    }

}

 

Remove is included for completeness, but I’m not calling it from any location in the code.

 

Union

 

public void Union(PixelSet otherSet)

{

    foreach (int key in otherSet._pixels.Keys)

    {

        foreach (int col in otherSet._pixels[key])

        {

            Add(col, key);

        }

    }

}

 

A possible optimization here is to loop through the smallest set.  You would need to maintain a count, but since new members are added through Add that should be easy.

 

Intersect

 

public void Intersect(PixelSet otherSet)

{

    PixelSet intersection = new PixelSet();

    foreach (int key in otherSet._pixels.Keys)

    {

        if (_pixels.ContainsKey(key))

        {

            foreach (int col in otherSet._pixels[key])

            {

                if (_pixels[key].Contains(col))

                {

                    intersection.Add(col, key);

                }

            }

        }

    }

    _pixels = new Dictionary<int, List<int>>(intersection._pixels);

}

 

Once again you could change this to loop through the smallest set to speed this up.

 

Summary
 

I expect this will have been a review for many readers, but it’s important to have a grasp of this information before we head into the next lesson regarding erosion and dilation.  I’d also like to reiterate that this is not optimized for image processing.  My HD7 takes almost 8 times longer to execute some of these tight loops.

 

Download Code

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2017%20-%20Set%20Operations.zip

Up Next: Erosion and Dilation





Project Euler 007 – C#

15 03 2011

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution

//By listing the first six prime numbers:

//2, 3, 5, 7, 11, and 13, we can see that

//the 6th prime is 13.

 

//What is the 10001st prime number?

 

 

using System.Collections.Generic;

namespace ProjectEulerCSharp_007

{

    class Program

    {

        static void Main(string[] args)

        {

            List<long> primes = new List<long>(10) { 2, 3 };

            while (primes.Count < 10001)

            {

                bool isPrime = false;

                long candidate = primes[primes.Count – 1] + 2;

                while (!isPrime)

                {

                    isPrime = true;

                    foreach (long prime in primes)

                    {

                        if (candidate % prime == 0)

                        {

                            isPrime = false;

                            break;

                        }

                    }

                    if (!isPrime) { candidate += 2; }

                    else { primes.Add(candidate); }

                }

            }

            System.Console.WriteLine(primes[primes.Count-1]);

        }

    }

}

 

Discussion

Getting back to my imperative roots, this problem was pretty easy to solve.

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





Project Euler 007 – F#

14 03 2011

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution

(*

 By listing the first six prime numbers:

 2, 3, 5, 7, 11, and 13, we can see that

 the 6th prime is 13.

 

 What is the 10001st prime number?

*)

 

let primes =

  let rec prim n (sofar: list<int>) =

      seq { if (sofar |> List.forall (fun i -> n%i <> 0)) then

                yield n

                yield! prim (n+1) (n :: sofar)

            else

                yield! prim (n+1) sofar }

  prim 2 []

 

let tenthousandfirst = primes

                       |> Seq.take 10001

                       |> Seq.max

 

printfn "%A" tenthousandfirst

 

Discussion

The primes function was posted on a forum by Don Syme.  The use of the infinite sequence is just awesome – again.  20+ years of imperative programming has taken it’s toll so it’s going to take a lot more effort on my part to wrap my mind around this functional stuff.  I’ll keep plugging away.

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





Project Euler 006 – JavaScript

11 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

(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.

–>

 

<head>

    <title>Project Euler 006</title>

</head>

<body >

  <script type="text/javascript">

    n = 100;

    answer=.25*Math.pow(n,4)+1/6*Math.pow(n,3)-.25*Math.pow(n,2)-1/6*n;

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

  </script>

</body>

</html>

 

Discussion

You’ll notice that this is fast, but different from the IronRuby solution given a couple of days ago. if you know that this is a 4th order polynomial then you can solve for the coefficients using simple linear algebra techniques.  That is, assume the solution is in the form of

ax4 + bx3 + cx2 + dx + e

Then you just need to solve for a, b, c, d, and e. This is a pretty trivial tasks if you have the right tools at your disposal.   Since there are 5 unknowns here we need 5 equations. Let’s plug 0 in first.

a*0 + b*0 + c * 0 + d * 0 + e = 0

This means that e = 0 so now we actually only have 4 unknowns a, b, c, and d.  If you repeat this process by replacing x with your number (1,2,3,4) and setting the right side of the equation to the square(sums) – sum(squares) then you will get this matrix:

n4 n3 n2 n s
1 1 1 1 0
16 8 4 2 4
81 27 9 3 22
256 64 16 4 70

Where s is the solution to sum(n)2 – sum(n2). If you plug this into a solver you will get:

(1/4, 1/6, –1/4, –1/6)

The only real trick is determining that a 4th order polynomial will be adequate to solve the problem.  If you are really curious how to do that, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).





Project Euler 006 – TSQL

10 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.

 

select power(sum(number),2) sum([square])

from Number

where number <= 100

 

Discussion

Just like the other solutions, this one is quite simple.  It is aided by the fact that when I populated my database I included all of the squares in the number table as well.

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





Phone Vision 16 – Binary Images

9 03 2011

When we are creating a binary image we are defining objects of interest.  Defining these objects is very specific to the task at hand.  In some cases a simple threshold will work while others require a more complex approach such as color segmentation, edge detection, or something even more sinister.

Thresholding

The most common way to create a binary image from a grayscale image is to pick an intensity threshold (also known as gray-level segmentation).  Everything below the threshold becomes a pixel of interest (black).  Everything else is not (white).  Let’s explore a few methods for picking that threshold.

The Image

Interestingly, this picture is a white piece of poster board (not blue) with some dark puzzle pieces on it.  If you look closely you can see the famous HD7 pink tint.  The image on the right is simply converted to grayscale using the average of the RGB values.

imageimage

Mean Threshold

Almost every time an image processing problem arises and a simple average is a possible answer my gut tells me to go for it.  In this case, my gut is going to lead me astray, but first some code:

WriteableBitmap ToAverageBinary(WriteableBitmap grayscale)

{

    WriteableBitmap binary =

        new WriteableBitmap(grayscale.PixelWidth,

            grayscale.PixelHeight);

 

 

    int[] histogramData = new int[256];

    int maxCount = 0;

 

    //first we will determine the histogram

    //for the grayscale image

    for (int pixelIndex = 0;

        pixelIndex < grayscale.Pixels.Length;

        pixelIndex++)

    {

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

 

        //simply add another to the count

        //for that intensity

        histogramData[intensity]++;

 

        if (histogramData[intensity] > maxCount)

        {

            maxCount = histogramData[intensity];

        }

    }

 

    //now we need to figure out the average intensity

    long average = 0;

    for (int intensity = 0; intensity < 256; intensity++)

    {

        average += intensity * histogramData[intensity];

    }

 

    //this is our threshold

    average /= grayscale.Pixels.Length;

 

    for (int pixelIndex = 0;

        pixelIndex < grayscale.Pixels.Length;

        pixelIndex++)

    {

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

 

        //now we’re going to set the pixels

        //greater than or equal to the average

        //to white and everything else to black

        if (intensity >= average)

        {

            intensity = 255;

            unchecked { binary.Pixels[pixelIndex] = (int)0xFFFFFFFF; }

        }

        else

        {

            intensity = 0;

            unchecked { binary.Pixels[pixelIndex] = (int)0xFF000000; }

        }

    }

 

    //note that this is the ORIGINAL histogram

    //not the histogram for the binary image

    PlotHistogram(histogramData, maxCount);

 

    //this is a line to show where the

    //average is relative to the rest of

    //the histogram

    Line averageLine = new Line();

    averageLine.X1 = HistogramPlot.Width * average / 255;

    averageLine.X2 = HistogramPlot.Width * average / 255;

    averageLine.Y1 = 0;

    averageLine.Y2 = HistogramPlot.Height;

    averageLine.Stroke = new SolidColorBrush(Colors.Magenta);

    averageLine.StrokeThickness = 2;

    averageLine.StrokeDashArray = new DoubleCollection() { 5, 2.5 };

    HistogramPlot.Children.Add(averageLine);

    return binary;

}

image

 

While the puzzle pieces came through loud and clear so did a lot of garbage.  Notice how the average line (magenta) splits the peak?  This is going to lead to a large number of false black pixels.  What we want is an automated technique for shifting the threshold left.

 

Two Peak

 

If you look at the original grayscale image you’ll notice that the puzzle pieces seem to be close to the same intensity while the background is another. This is represented in the histogram by the large peak (the background) and an almost imperceptible peak toward the dark end of the spectrum (the puzzle pieces).

 

Finding the large peak is trivial.  It’s just the highest occurring intensity.  The small peak on the other hand is a little trickier.  It’s not the second most frequent intensity – that’s right next to the largest peak.  A little trick is to give a higher weight to intensities that are far from the highest peak.  To do this we multiply the intensity count at each point by the square of its distance to the peak.  That’s a mouthful, but it’s pretty easy.  Here’s the code:

 

int secondPeak = 0;

long secondPeakCount = 0;

for (int intensity = 0; intensity < 256; intensity++)

{

    long adjustedPeakCount =

        (long)(histogramData[intensity]*Math.Pow(intensity-maxPeak, 2));

    if (adjustedPeakCount > secondPeakCount)

    {

        secondPeak = intensity;

        secondPeakCount = adjustedPeakCount;

    }

}

So we calculate an adjusted count for each intensity.  By multiplying it by the square of the distance we give higher counts to those further from the first peak.  Amazingly, this works even in this case where the second peak is so small.

image

Wow!  Those results are so much better.  Notice I marked the two peaks with green and the new threshold is in magenta.

Summary

Don’t use the mean.  You might get lucky in a few cases, but in general you’ll end up in a messy situation.  That said, the two-peak solution will work well in cases where your objects are of a consistent color and that color is separate from the background.  I created this photo because I knew it would have good results.  I highly recommend you try these techniques out on your own photos so you can get a feel for when they will work and when they won’t.

We will most likely revisit different thresholding techniques for different situations when they arise, but for now we have a binary image so we’re going to see what we can do with it.

Download Code

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2016%20-%20Binary%20Images.zip

Up Next: Sets