| Page 2

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

Comments : Leave a Comment »
Tags: C#, Project Euler
Categories : Project Euler

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

Comments : Leave a Comment »
Tags: F#, Project Euler
Categories : Project Euler

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">

<!–

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>

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

Comments : Leave a Comment »
Tags: Javascript, Project Euler
Categories : Project Euler

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

Comments : Leave a Comment »
Tags: Project Euler, TSQL
Categories : Project Euler

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

if !isPrime then

candidate += 2

else

primes.push(candidate)

end

puts primes[primes.length–1]

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

Comments : Leave a Comment »
Tags: IronRuby, Project Euler
Categories : Project Euler

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:

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

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 E² (for 2-dimensional Euclidean space). In our case, the universe is…

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.

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:

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.

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.

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

Comments : 1 Comment »
Tags: Azzl Software, Azzlsoft, Binary Image, Computer Vision, Phone Vision, Set Theory, Sets, Windows Phone, WP7
Categories : Phone Vision, Technology

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

Comments : Leave a Comment »
Tags: C#, Project Euler
Categories : Project Euler

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

Comments : Leave a Comment »
Tags: F#, Project Euler
Categories : Project Euler

Project Euler 006 – JavaScript

11 03 2011

Problem 6

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

1² + 2² + … + 10² = 385

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

(1 + 2 + … + 10)² = 55² = 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 >

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

ax⁴ + bx³ + cx² + 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:

n⁴	n³	n²	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)² – sum(n²). 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).

Comments : Leave a Comment »
Tags: Javascript, Project Euler
Categories : Project Euler

Project Euler 006 – TSQL

10 03 2011

Problem 6

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

1² + 2² + … + 10² = 385

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

(1 + 2 + … + 10)² = 55² = 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).

Comments : Leave a Comment »
Tags: Project Euler, TSQL
Categories : Project Euler

Project Euler 008 – C#

Project Euler 008 – F#

Project Euler 007 – JavaScript

Project Euler 007 – TSQL

Project Euler 007 – IronRuby

Phone Vision 17–Sets

Project Euler 007 – C#

Project Euler 007 – F#

Project Euler 006 – JavaScript

Project Euler 006 – TSQL

Top Posts

Archive