Project Euler 008 – TSQL

24 03 2011

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution

declare @digits varchar(MAX)

set @digits =

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450′

 

declare @returnpattern varchar(2);

set @returnpattern = char(13) + char(10)

 

set @digits = replace(@digits, @returnpattern, )

 

declare @currentDigit int

set @currentDigit = 1

declare @sql varchar(max)

 

while(@currentDigit <= len(@digits))

begin

       set @sql = ‘insert into Problem_008 (ordinal, digit) values (‘ + str(@currentdigit) + ‘, ‘ + substring(@digits, @currentDigit, 1) + ‘)’

       exec(@sql)

       set @currentDigit = @currentDigit + 1

end

 

GO

 

select max(product) from

(select

       digit

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 1)

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 2)

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 3)

       * (select digit from Problem_008 a where a.ordinal = Problem_008.ordinal + 4) as product

from Problem_008

where ordinal < (select count(*) from Problem_008) 3) Products

 

 

Discussion

This one is going to take a bit of explanation.  I parse the thousand digit number for it’s component digits and insert them into a database table with their ordinals.  After the digits are in a table it’s a simple query.

Clearly, I didn’t need to insert the digits into a table to get the result, but as with all of the TSQL solutions I want to solve it as if the information exists in the database if possible.

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

Advertisements




Phone Vision 18 – Erosion and Dilation

23 03 2011

Our exploration of set theory last time was a precursor to discussing dilation and erosion.  Simply put, dilation makes things bigger and erosion makes things smaller.  Seems obvious right?  Let’s see if the mathematicians can muck it up.

Translation

This is not necessarily a fundamental set operation, but it is critical for what we will be doing. Translation can be described as shifting the pixels in the image. We can move it in both the x and y directions and we will represent the amount of movement using a point. To translate the set then, we simply add that point to every element of the set. For instance, using the point (20, 20) the puzzle is moved down 20 pixels and right 20 pixels like this:

image

The light blue area marks the original location.

Dilation

Dilation is an extension of translation from a point to a set of points. If you union the sets created by each translation you end up with dilation.  In the following diagram, the black pixels represent the original puzzle piece.  The light blue halo represents several translations of the original.  Each translation is translucent so I have tried to make the image large enough so you can see the overlap.  Notice how the hole is missing?

image

The set of points that were used to create the translated sets is called the structuring element.  A common structuring element is

{ (-1,-1), (0,-1), (1,-1),(-1,0), (0,0), (1,0),(-1,1), (0,1), (1,1) }

This will expand the image by one pixel in every direction.  If we think about this as a binary image, it might be represented by this:

image

Kinda reminds me of one of our convolution kernels.  Structuring elements are often called “probes”.  This one is centered at (0,0).

Using the PixelSet we created last time, the code is pretty straightforward.

public void Dilate(PixelSet structuringElem)

{

    PixelSet dilatedSet = new PixelSet();

    foreach(int translateY in structuringElem._pixels.Keys)

    {

        foreach(int translateX in structuringElem._pixels[translateY])

        {

            PixelSet translatedSet = new PixelSet();

            foreach (int y in _pixels.Keys)

            {

                foreach(int x in _pixels[y])

                {

                    translatedSet.Add(x + translateX, y + translateY);

                }

            }

            dilatedSet.Union(translatedSet);

        }

    }

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

}

Here is the puzzle piece dilated by one pixel in all directions.  The hole is gone.

image

Erosion

Erosion is similar to dilation except that our translation is subtraction instead of addition and we are finding the intersection instead of the union.  Here is an image that has been eroded by 10 pixels in all directions.  The light blue area is the original puzzle.

 

image

 

public void Erode(PixelSet structuringElem)

{

    PixelSet erodedSet = new PixelSet(this);

    foreach (int translateY in structuringElem._pixels.Keys)

    {

        foreach (int translateX in structuringElem._pixels[translateY])

        {

            PixelSet translatedSet = new PixelSet();

            foreach (int y in _pixels.Keys)

            {

                foreach (int x in _pixels[y])

                {

                    translatedSet.Add(x – translateX, y – translateY);

                }

            }

            erodedSet.Intersect(translatedSet);

        }

    }

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

}

 

Here is the puzzle eroded by one pixel in all directions.  That hole is a little bigger.

image

Summary

Like I said at the beginning, dilation makes things bigger and erosion makes things smaller.  Interestingly, erosion is simply the dilation of the background and dilation is the erosion of the background.

Download Code

http://cid-88e82fb27d609ced.office.live.com/embedicon.aspx/Blog%20Files/PhoneVision/PhoneVision%2018%20-%20Erosion%20and%20Dilation.zip

Up Next: Opening and Closing





Project Euler 008–IronRuby

23 03 2011

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution

digits = "73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450"

 

#remove the line breaks again

digits = digits.delete("\r\n");

 

answer = 0

 

for i in 0..digits.length 5 do

        product = Integer(digits[i]) * Integer(digits[i+1]) * Integer(digits[i+2]) * Integer(digits[i+3]) * Integer(digits[i+4])

        if answer < product

                answer = product

        end

end

 

puts answer

Discussion

Here I used delete to get rid of the line breaks.  Maybe instead of Integer I should have tried the “-‘0’” method described yesterday.

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





Project Euler 008 – C#

22 03 2011

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution

namespace ProjectEulerCSharp_008

{

    class Program

    {

        static void Main(string[] args)

        {

            string digits = @"

                73167176531330624919225119674426574742355349194934

                96983520312774506326239578318016984801869478851843

                85861560789112949495459501737958331952853208805511

                12540698747158523863050715693290963295227443043557

                66896648950445244523161731856403098711121722383113

                62229893423380308135336276614282806444486645238749

                30358907296290491560440772390713810515859307960866

                70172427121883998797908792274921901699720888093776

                65727333001053367881220235421809751254540594752243

                52584907711670556013604839586446706324415722155397

                53697817977846174064955149290862569321978468622482

                83972241375657056057490261407972968652414535100474

                82166370484403199890008895243450658541227588666881

                16427171479924442928230863465674813919123162824586

                17866458359124566529476545682848912883142607690042

                24219022671055626321111109370544217506941658960408

                07198403850962455444362981230987879927244284909188

                84580156166097919133875499200524063689912560717606

                05886116467109405077541002256983155200055935729725

                71636269561882670428252483600823257530420752963450"

            .Replace(" ", "").Replace("\r\n", "");

           

            int answer = 0;

            for(int i = 0; i < digits.Length – 5; i++)

            {

                int digit1 = int.Parse(digits.Substring(i+0, 1));

                int digit2 = int.Parse(digits.Substring(i+1, 1));

                int digit3 = int.Parse(digits.Substring(i+2, 1));

                int digit4 = int.Parse(digits.Substring(i+3, 1));

                int digit5 = int.Parse(digits.Substring(i+4, 1));

                int product = digit1*digit2*digit3*digit4*digit5;

                if(product > answer) { answer = product; }

            }

            System.Console.WriteLine(answer);

        }

    }

}

Discussion

I’m not sure what the ‘trick’ with this problem was supposed to be.  Even when this problem was posted (a little over 9 years ago) it probably only took a fraction of a second.  I suppose converting a character digit to an integer used to be a bit of a novelty.  Something like int digit = chardigit – ‘0’ would give you the results you want. 

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





Project Euler 008 – F#

21 03 2011

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution

(*

Find the greatest product of five consecutive digits in the 1000-digit number.

*)

 

(* needed for Int32.Parse *)

open System

 

(* need to remove the line breaks *)

let digits = "73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450".Replace("\r\n","")

 

let products (str:string) =

    let indices = [0..str.Length-5]

    [for i in indices do

        yield Int32.Parse(str.Chars(i).ToString())

            * Int32.Parse(str.Chars(i+1).ToString())

            * Int32.Parse(str.Chars(i+2).ToString())

            * Int32.Parse(str.Chars(i+3).ToString())

            * Int32.Parse(str.Chars(i+4).ToString())]

 

let answer = products digits

             |> List.max

 

printfn "%A" (answer)

 

Discussion

This problem is almost trivial.  I’m not sure there is more to say on it. 

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





Project Euler 007 – JavaScript

18 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

<!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;

<!–

 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?

–>

<head>

    <title>Project Euler 007</title>

</head>

<body>

    <script type="text/javascript">

        maxPrime = 10001;

        primes = new Array(maxPrime);

 

        primes[0] = 2;

        primes[1] = 3;

 

        primeCount = 2;

        while (primeCount < maxPrime) {

            isPrime = false;

            candidate = primes[primeCount – 1] + 2;

            while (!isPrime) {

                isPrime = true;

                for (pindex = 0; pindex < primeCount; pindex++) {

                    prime = primes[pindex];

                    if (candidate % prime == 0) {

                        isPrime = false;

                        break;

                    }

                }

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

                else {

                    primes[primeCount] = candidate;

                    primeCount++;

                }

            }

        }

 

        document.write("<b>" + primes[maxPrime-1] + "</b>");

    </script>

</body>

</html>

Discussion

Happy JavaScript nth prime finder.

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





Project Euler 007 – TSQL

17 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?

 

SELECT number FROM

       (SELECT row_number() OVER (ORDER BY number) as primeindex, number

              FROM Number

              WHERE isprime = 1) Primes

WHERE Primes.primeindex = 10001

Discussion

On the surface this solution might seem pretty ‘meh’, but I’m a big fan.  It’s obviously going to be my fastest solution because it’s a simple look up – very common in real life scenarios.  I also got to use row_number() and a subquery as a data source which always delight me.

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