Project Euler programming challenges: Am I missing something?

[Jamin2112]

I recently was looking for programming challenges and it was suggested to me that I check out Project Euler. http://projecteuler.net/problems

These all seem straight-forward to me. Or there's something I'm not understanding about them.

For instance, problem 1:

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.

Is there supposed to be some fancy way of doing that?

 

[SixNein]

I recently was looking for programming challenges and it was suggested to me that I check out Project Euler. http://projecteuler.net/problems

These all seem straight-forward to me. Or there's something I'm not understanding about them.

For instance, problem 1:



Is there supposed to be some fancy way of doing that?

Well there is always the dumb method aka brute force. But I think the goal here is to avoid brute force algorithms for algorithms with much less complexity.

So think about it for a second:

Uncle Gauss the mathematician came up with this cute little trick to sum up numbers:
∑(i) = (n(n+1)) / 2

So how could we use that little trick to come up with a smarter algorithm?

 

[Jamin2112]

Well there is always the dumb method aka brute force. But I think the goal here is to avoid brute force algorithms for algorithms with much less complexity.

So think about it for a second:

Uncle Gauss the mathematician came up with this cute little trick to sum up numbers:
∑(i) = (n(n+1)) / 2

So how could we use that little trick to come up with a smarter algorithm?

Let me think about that for a minute.

 

[Jamin2112]

Uncle Gauss the mathematician came up with this cute little trick to sum up numbers:
∑(i) = (n(n+1)) / 2

So how could we use that little trick to come up with a smarter algorithm?

Oh, okay.

We know that we're summing up

3 + 6 + 9 + ... + 996 + 999 = 3(1 + 2 + 3 + ... + 332 + 333)

and

5 + 10 + 15 + ... + 990 + 995 = 5(1 + 2 + 3 + ... + 198 + 199)

So that's

3*(333*334/2) + 5*(199*200/2)

For some reason, though, it's not working ...

Output:

Answer using brute force algorithm: 233168 (17 ns)
Answer using Gauss's Sum of Integers Formula: 266333 (2 ns)

Source code:

// Prompt: http://projecteuler.net/problem=1

#include <iostream>
#include <time.h>

int main (int argc, char* const argv[]) {
	
	time_t start, end;
	
	// Brute force:
	start = clock();
	int sumBrute = 0;
	for (int k = 1; k < 1000; ++k) { 
		if (k % 3 == 0) { 
			sumBrute += k;
		} else {
			if (k % 5 == 0)
				sumBrute += k;
		}
	} 
	end = clock();
	std::cout << "Answer using brute force algorithm: " 
	          << sumBrute << " ("<< (double)(end - start) << " ns)" << std::endl;
	
	// Improved, using the fact that 1 + 2 + ... + n = n(n+1)/2:
	start = clock();
	int sumOptimized = 3*(333*334/2) + 5*(199*200/2); 
	end = clock();
	std::cout << "Answer using Gauss's Sum of Integers Formula: " 
	          << sumOptimized << " ("<< (double)(end - start) << " ns)" << std::endl;
	
    return 0;
}

 

[D H]

So that's

3*(333*334/2) + 5*(199*200/2)

For some reason, though, it's not working ...

That is not working because your algorithm isn't correct.

You can sanity check your algorithm with some smaller number N (as opposed to 1000). For example, suppose N is 20. The multiples of 3 less than or equal to 20 are 3, 6, 9, 12, 15, and 18, which sum to 63. The multiples of 5 less than or equal to 20 are 5, 10, 15, 20, which sum to 50. The multiples of 3 or 5 that are less than or equal to 20 are 3, 5, 6, 9, 10, 12, 15, 18, and 20. These sum to 98, not 63+50=113. Do you see why they don't sum to 113, and how can you fix your algorithm?

 

[D H]

BTW, here's an "interesting" perl script to calculate the sum in Euler problem #1. This also works for other integral powers of 10 between 10² to 10¹⁸, inclusive.

my $N = 1000;  # Or any integral power of 10 between 10^2 and 10^18, inclusive
(my $p = ($N-1)/3) =~ s/.(.*)./2${1}4/;
(my $q = 2*$p) =~ s/./1/;
$sum = "$p$q";  # Add zero if you want a number.
print "N=$N sum=$sum\n";

I doubt this would garner any points with the project Euler crowd. It's more suitable for an obfuscated Perl contest.

 

[SixNein]

Oh, okay.

We know that we're summing up

3 + 6 + 9 + ... + 996 + 999 = 3(1 + 2 + 3 + ... + 332 + 333)

and

5 + 10 + 15 + ... + 990 + 995 = 5(1 + 2 + 3 + ... + 198 + 199)

So that's

3*(333*334/2) + 5*(199*200/2)

For some reason, though, it's not working ...

Output:

Answer using brute force algorithm: 233168 (17 ns)
Answer using Gauss's Sum of Integers Formula: 266333 (2 ns)

Source code:

// Prompt: http://projecteuler.net/problem=1

#include <iostream>
#include <time.h>

int main (int argc, char* const argv[]) {
	
	time_t start, end;
	
	// Brute force:
	start = clock();
	int sumBrute = 0;
	for (int k = 1; k < 1000; ++k) { 
		if (k % 3 == 0) { 
			sumBrute += k;
		} else {
			if (k % 5 == 0)
				sumBrute += k;
		}
	} 
	end = clock();
	std::cout << "Answer using brute force algorithm: " 
	          << sumBrute << " ("<< (double)(end - start) << " ns)" << std::endl;
	
	// Improved, using the fact that 1 + 2 + ... + n = n(n+1)/2:
	start = clock();
	int sumOptimized = 3*(333*334/2) + 5*(199*200/2); 
	end = clock();
	std::cout << "Answer using Gauss's Sum of Integers Formula: " 
	          << sumOptimized << " ("<< (double)(end - start) << " ns)" << std::endl;
	
    return 0;
}

So we started out with ∑i = (n(n+1))/2

so how did you end up with 3*(333*334/2) + 5*(199*200/2)?

∑3i = 3∑i = 3 ((n(n+1))/2)
∑5i = 5∑i = 5 ((n(n+1))/2)


So 3 ((n(n+1))/2) + 5 ((n(n+1))/2)
where n is equal to 1000.

BUT WAIT!

There is an intersection when 3 and 5 are factors of some number. For example, 3*5 = 15. So if we just use the above two formulas, we'll be computing 15 twice. But we only want to calculate it once!

So now we have to start thinking about this in terms of set theory.

Any ideas?

 

[JorisL]

if they are multiples of 3 and 5 how can you write them?

 

[Borek]

While some of the problems can be solved by brute force, others will take way too long.

Besides, brute force is for weenies.

 

[AlephZero]

Besides, brute force is for weenies.

The sad thing is, given a 4 GHz 8-core CPU, and a 16 Gb of RAM, the weenies can still do a lot of "kool" stuff by brute force, before they get bored waiting for the answer.

And some of them even get to be "professional programmers" before they stop being weenies...

IMO computer professionals should be forced to figure out how to do something "kool" on an 8 MHz (not GHz) CPU and 512 kb (note, kb, not Mb) of RAM, before they are let loose on modern hardware

 

[Borek]

IMO computer professionals should be forced to figure out how to do something "kool" on an 8 MHz (not GHz) CPU and 512 kb (note, kb, not Mb) of RAM, before they are let loose on modern hardware

Agreed. And I think you are way too generous.

256 bytes were enough for these demos (http://en.wikipedia.org/wiki/Demoscene):

 

[Jamin2112]

So we started out with ∑i = (n(n+1))/2

so how did you end up with 3*(333*334/2) + 5*(199*200/2)?

∑3i = 3∑i = 3 ((n(n+1))/2)
∑5i = 5∑i = 5 ((n(n+1))/2)


So 3 ((n(n+1))/2) + 5 ((n(n+1))/2)
where n is equal to 1000.

BUT WAIT!

There is an intersection when 3 and 5 are factors of some number. For example, 3*5 = 15. So if we just use the above two formulas, we'll be computing 15 twice. But we only want to calculate it once!

So now we have to start thinking about this in terms of set theory.

Any ideas?

Yea, my bad. Now it's right.

Answer using brute force algorithm: 233168 (21 ns)
Answer using Gauss's Sum of Integers Formula: 233168 (1 ns)

from

// Prompt: http://projecteuler.net/problem=1

#include <iostream>
#include <time.h>

int main (int argc, char* const argv[]) {
	
	time_t start, end;
	
	// Brute force:
	start = clock();
	int sumBrute = 0;
	for (int k = 1; k < 1000; ++k) { 
		if (k % 3 == 0) { 
			sumBrute += k;
		} else {
			if (k % 5 == 0)
				sumBrute += k;
		}
	} 
	end = clock();
	std::cout << "Answer using brute force algorithm: " 
	          << sumBrute << " ("<< (double)(end - start) << " ns)" << std::endl;
	
	/* Improved, using the fact that 1 + 2 + ... + n = n(n+1)/2. 
	 
	   sumOptimized = 3 + 5 + 6 + 9 + ... + 995 + 999
	                = (3 + 6 + ... + 999) + (5 + 10 + ... + 995) - (15 + 30 + ... + 990)
	                = 3(1 + 2 + ... + 333) + 5(1 + 2 + ... + 199) - 15(1 + 2 + ... + 66)
	                = 3(333*334/2) + 5(199*200/2) - 15(66*67/2)
	 
	*/
	start = clock();
	int sumOptimized = 3*(333*334/2) + 5*(199*200/2) - 15*(66*67/2); 
	end = clock();
	std::cout << "Answer using Gauss's Sum of Integers Formula: " 
	          << sumOptimized << " ("<< (double)(end - start) << " ns)" << std::endl;
	
    return 0;
}

 

[JorisL]

This is correct but now do it so you can use any range.
Because this is pretty useless as is.

 

[Jamin2112]

This is correct but now do it so you can use any range.
Because this is pretty useless as is.

I think the point of these problems is that they be useless. Anyhow, I'll make it slightly less useless. Or do you want no magic numbers at all? We could make a program that finds the sum of all multiples of numbers in the set S={s₁, s₂, ..., s_n} between 0 and N exclusive, but then you'd have to find all the pairwise products of numbers in S and it would be a really messy procedure.

// Prompt: http://projecteuler.net/problem=1

#include <iostream>
#include <time.h>

int main (int argc, char* const argv[]) {
	
	time_t start, end;
	
	const int N = 1000;
	
	// Brute force
	start = clock();
	int sumBrute = 0;
	for (int k = 1; k < N; ++k) { 
		if (k % 3 == 0) { 
			sumBrute += k;
		} else {
			if (k % 5 == 0)
				sumBrute += k;
		}
	} 
	end = clock();
	std::cout << "Answer using brute force algorithm: " 
	          << sumBrute << " ("<< (double)(end - start) << " ns)" << std::endl;
	
	/* Improved, using the fact that 1 + 2 + ... + n = n(n+1)/2 
	 
	   e.g.
	 
	   sumOptimized = 3 + 5 + 6 + 9 + ... + 995 + 999
	                = (3 + 6 + ... + 999) + (5 + 10 + ... + 995) - (15 + 30 + ... + 990)
	                = 3(1 + 2 + ... + 333) + 5(1 + 2 + ... + 199) - 15(1 + 2 + ... + 66)
	                = 3(333*334/2) + 5(199*200/2) - 15(66*67/2)
	 
	  for N = 1000
	 
	*/
	start = clock();
	int sumOptimized = 3*(((N-1)/3)*((N-1)/3+1)/2) + 5*(((N-1)/5)*((N-1)/5+1)/2) - 15*(((N-1)/15)*((N-1)/15+1)/2); 
	end = clock();
	std::cout << "Answer using Gauss's Sum of Integers Formula: " 
	          << sumOptimized << " ("<< (double)(end - start) << " ns)" << std::endl;
	
    return 0;
}

 

[Jamin2112]

I mean, if we're really going to try and make this proper, we should change all the ints to unsigned ints, check that we're not getting overflow when the sum is too big, etc.

 

[JorisL]

nope that's what I meant. ofcourse you can expand for other numbers (say 3 and 7).
Regardless the same procedure can be used.

 

[Jamin2112]

nope that's what I meant. ofcourse you can expand for other numbers (say 3 and 7).
Regardless the same procedure can be used.

// Prompt: http://projecteuler.net/problem=1

#include <iostream>
#include <time.h>

int main (int argc, char* const argv[]) {
	
	time_t start, end;
	
	int a(3), b(5), N(1000);
	
	// Brute force
	start = clock();
	int sumBrute = 0;
	for (int k = 1; k < N; ++k) { 
		if (k % a == 0) { 
			sumBrute += k;
		} else {
			if (k % b == 0)
				sumBrute += k;
		}
	} 
	end = clock();
	std::cout << "Answer using brute force algorithm: " 
	          << sumBrute << " ("<< (double)(end - start) << " ns)" << std::endl;
	
	/* Improved, using the fact that 1 + 2 + ... + n = n(n+1)/2 
	 
	   e.g.
	 
	   sumOptimized = 3 + 5 + 6 + 9 + ... + 995 + 999
	                = (3 + 6 + ... + 999) + (5 + 10 + ... + 995) - (15 + 30 + ... + 990)
	                = 3(1 + 2 + ... + 333) + 5(1 + 2 + ... + 199) - 15(1 + 2 + ... + 66)
	                = 3(333*334/2) + 5(199*200/2) - 15(66*67/2)
	 
	  for N = 1000
	 
	*/
	start = clock();
	int sumOptimized = a*(((N-1)/a)*((N-1)/a+1)/2) + b*(((N-1)/b)*((N-1)/b+1)/2) - (a*b)*(((N-1)/(a*b))*((N-1)/(a*b)+1)/2); 
	end = clock();
	std::cout << "Answer using Gauss's Sum of Integers Formula: " 
	          << sumOptimized << " ("<< (double)(end - start) << " ns)" << std::endl;
	
    return 0;
}

 

[Jamin2112]

On to the next problem:

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Can anyone think of a non-brute-force way of doing this?

 

[D H]

Don't go overboard. Those Project Euler problems are small numerical problems. Integer programming, in particular. You are not going to run into many of these problems in real life. With a few exceptions, they are not going to make you a better programmer. The key exception is that these problems might teach you to recognize up front rather than after the fact why your initial cut at the non-summed solution was wrong.

 

[Jamin2112]

Don't go overboard. Those Project Euler problems are small numerical problems. Integer programming, in particular. You are not going to run into many of these problems in real life. With a few exceptions, they are not going to make you a better programmer. The key exception is that these problems might teach you to recognize up front rather than after the fact why your initial cut at the non-summed solution was wrong.

Do you know any site where I can find a list of problems that would make me a better programmer?

 

[DavidSnider]

Not all of Project Euler is small numerical problems. DH is right though, these sorts of problems will make you fairly good at writing algorithms but teach you nothing about constructing and maintaining large real world applications.

The only way I know of to do that is to get real world experience. Contributing to open source projects is a good way to do this before you start your career.

 

[SixNein]

Do you know any site where I can find a list of problems that would make me a better programmer?

Being a good programmer is being good at algorithms and data structures. So take the first problem as an example, bad programmers would go with the dumb method of brute force. Good programmers try to find algorithms with less complexity. The reason is due to the simple fact that algorithms with less complexity run faster and often use less resources.

The method I was leading you towards has a complexity of O(1) which means it will do the same amount of work regardless of the size of input. A brute force method on the other hand has a complexity of o(n). So it has to do more and more work as n grows.

Doing smart algorithms is paramount to being a good programmer. Suppose we had a lot of problems similar to these and selected brute force for them. In a real application, it will bog down resources very fast.

 

[SixNein]

Not all of Project Euler is small numerical problems. DH is right though, these sorts of problems will make you fairly good at writing algorithms but teach you nothing about constructing and maintaining large real world applications.

The only way I know of to do that is to get real world experience. Contributing to open source projects is a good way to do this before you start your career.

If the goal is to be a better software engineer, I would recommend learning UML. Take a project from a use case diagram to production following UML rigorously. Learn how to write a SRS, SDD, and do some V&V testing. And most importantly, don't write it for yourself.

Open source doesn't necessarily help one become a better software engineer. The real challenge to software engineering is to develop software according to customer requirements instead of your own. Open source isn't geared to creating business value. It's more about a few developers (often times just one) who want to write software their way and HOPE its useful.

 

[D H]

Being a good programmer is being good at algorithms and data structures. So take the first problem as an example, bad programmers would go with the dumb method of brute force. Good programmers try to find algorithms with less complexity. The reason is due to the simple fact that algorithms with less complexity run faster and often use less resources.

That's a good programmer. Even better programmers realize that someone has to maintain the code. If you want to be a top-notch programmer, you will write code that is maintainable so that you can attack other interesting problems. If you make your code so overly optimized that only you can understand it, you are the one who will be stuck maintaining it.

The second Project Euler problem is a good example. There are only eleven terms to be summed. A brute force algorithm will work quite fine here. A slight tweak that recognizes that the even elements of the Fibonacci sequence are separated by two odd elements is something that a maintenance programmer could understand. On the other hand, recognizing that the desired sum is itself closely related to the Fibonacci sequence and optimizing for that is something that a maintenance programmer will foul up.

The desired sum of the even Fibonacci terms up to and including N can be expressed rather compactly as

 (1+Fibonacci(2+3*floor(floor(log(N*sqrt(5))/log((1+sqrt(5))/2))/3)))/2

For example, with N=4000000,
http://www.wolframalpha.com/input/?...))/Log((1+sqrt(5))/2)]/3]])/2+where+N=4000000

Do you really want to do that?

 

[Jamin2112]

This look right?

#include <iostream>

// Prompt: http://projecteuler.net/problem=2

int main (int argc, char* const argv[]) {
   
	int N = 4000000;
	int previousFib(1), thisFib(2); 
	int sum = 0;
	while (thisFib <= N) { 
		if (thisFib & 1 == 0)
			sum += thisFib;
		int temp = thisFib;
		thisFib += previousFib;
		previousFib = temp;
	}
	std::cout << "Sum of even Fibonacci terms up to " << N << " equals " << sum << std::endl;
	
    return 0;
}

----------------------------------------------------------------------------------------------------------------------------

Sum of even Fibonacci terms up to 4000000 equals 4613732

 

[SixNein]

That's a good programmer. Even better programmers realize that someone has to maintain the code. If you want to be a top-notch programmer, you will write code that is maintainable so that you can attack other interesting problems. If you make your code so overly optimized that only you can understand it, you are the one who will be stuck maintaining it.

The second Project Euler problem is a good example. There are only eleven terms to be summed. A brute force algorithm will work quite fine here. A slight tweak that recognizes that the even elements of the Fibonacci sequence are separated by two odd elements is something that a maintenance programmer could understand. On the other hand, recognizing that the desired sum is itself closely related to the Fibonacci sequence and optimizing for that is something that a maintenance programmer will foul up.

The desired sum of the even Fibonacci terms up to and including N can be expressed rather compactly as

 (1+Fibonacci(2+3*floor(floor(log(N*sqrt(5))/log((1+sqrt(5))/2))/3)))/2

For example, with N=4000000,
http://www.wolframalpha.com/input/?...))/Log((1+sqrt(5))/2)]/3]])/2+where+N=4000000

Do you really want to do that?

Code optimization and algorithm selection are two separate things. Code optimization is the next stage after algorithmic selection and its more machine specific. For example, suppose we select the following algorithm to find a null in a string:

while (strPtr[location] != 0)
{
location++;
}

The above algorithm is O(n) and that's about as good as your going to get; however, the algorithm itself can be optimized for the machine itself.

Here is an example of the above algorithm optimized for SSE2:
http://www.strchr.com/sse2_optimised_strlen

Sometimes code optimization is necessary like in some embedded systems; however, good algorithm selection is always desired. Suppose, for example, we need to sort an array of a million randomly generated integers. There is a really big difference in using an insertion sort and a heap sort. An insertion sort has O(n^2) complexity whereas the heap sort has O(nlgn) complexity. In other words, the selection sort algorithm will require 1,000,000^2 = 1,000,000,000,000 or 1 trillion operations. But the heap sort can do it in 1,000,000 ln1,000,000 = 13,815,511 operations.

Also there is a lemma here... A highly optimized o(n^2) algorithm will never ever out perform a regular old non-optimized o(nlgn) algorithm.

 

[.Scott]

"What makes a good programmer?"
I'll put my 2 cents in.

Here are some candidate rules:
1) Find the optimal algorithm.
2) Code for maintenance.
3) Write modular code.
4) Unit test.
5) Document requirements.
6) Document how you got the algorithms.
7) ...

Every programmer can add lots more to this list.
Not every rule is useful in every condition.

Perhaps you're writing a program to search a database looking for a particular type of typo that a temp worker tended to make during his 3-week contract period. You're starting with similar code you've used before and changing it for this particular task. The total life span of that code might be 4 hours. If you're a good programmer, you're not going to spend a lot of time worrying about efficiency or maintainability.

Perhaps you're contributing code that will operate a subway system in a major US city. The lifetime of the code will be measured in decades. You're working with a team of programmers. It isn't good enough that you know it works correctly, your work and your testing needs to be fully auditable so that corporate management and government agencies have evidence to believe in its reliability.

Or perhaps your doing something that isn't at these extremes.

Here are some points in deciding what rules to follow:
1) The most important step in programming is the last of these develop steps: learning and understanding the requirements; developing the overall strategy for meeting those requirements; writing the code and working out the algorithms; testing; documenting; forgetting everything.
2) What you will remember is all the things that gave you trouble. The stuff that took 12 minutes and worked on the third try will be forgotten before the weekend.
3) If your code does a good job at something useful, it's lifetime is likely to be much longer than you expect it to be.
4) When documenting a module, the most important question to answer is why that module exists. Does it address certain product or contract requirements? Did it need to be separated out from another module? Why?
5) The most likely person to be reading the in-code documentation is you - about 9 months from now - and you will remember nothing.

 

[D H]

Perhaps you're writing a program to search a database looking for a particular type of typo that a temp worker tended to make during his 3-week contract period. You're starting with similar code you've used before and changing it for this particular task. The total life span of that code might be 4 hours. If you're a good programmer, you're not going to spend a lot of time worrying about efficiency or maintainability.

That's true, but with a caveat. I too have written short little programs or scripts to do a one-time job. I've written lot's of them. Efficiency? Maintainability? Who cares? Just get the job done. But there's one little problem, which you already noted:

If your code does a good job at something useful, it's lifetime is likely to be much longer than you expect it to be.

 

[Jamin2112]

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Right now I'm figuring out a non-brute-force way. Here's pure brute:

#include <iostream>
#include <vector>

// Prompt: http://projecteuler.net/problem=4

bool isPalindrome(int);

int main (int argc, char * const argv[]) {

	//  ---------------- Brute force -------------------
	int k = 111 * 111; // smallest product of two 3-digit numbers
	int n = 999 * 999; // largest product of two 3-digit numbers
	int largestPalindrome;
	bool foundPalindrome = false;
	while (k != n) { 
		if (isPalindrome(k)) { 
			largestPalindrome = k;
			foundPalindrome = true;
		}
		++k;
	}
	if (foundPalindrome) { 
		std::cout << "Largest palindrome that's a sum of two 3-digits numbers is " << largestPalindrome << std::endl;
	} else { 
		std::cout << "Didn't find palindrome in range." << std::endl;
	}
	
    return 0;
}

bool isPalindrome(int i) { 
	std::vector<int> digits;
	while (i != 0) { 
		digits.push_back(i % 10);
		i /= 10;
	}
	std::vector<int>::size_type sz = digits.size();
	for (std::vector<int>::size_type j(0), k(sz - 1); j < k; ++j, --k) 
		if (digits[j] != digits[k])
			return false;
	return true;

}

 

[Jamin2112]

There's probably a formula to find the next palindrome number from the previous one. Or a formula to find the nth one. Let me try to find a pattern.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, ..., 999, 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, ...