Project Euler programming challenges: Am I missing something?

  • Thread starter Jamin2112
  • Start date
  • #26
SixNein
Gold Member
42
16
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

Code:
 (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.
 
Last edited:
  • #27
.Scott
Homework Helper
2,636
962
"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.
 
  • #28
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
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.
 
  • #29
986
9
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:

Code:
#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;

}
 
  • #30
986
9
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, ...
 
  • #31
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
685
Right now I'm figuring out a non-brute-force way. Here's pure brute:
When you apply brute force you need to ensure that you are apply that brute force to the right problem. Here you are applying brute force to solve the wrong problem. Your algorithm finds the largest palindrome that is smaller than 999*999=998001. You are not finding the largest palindrome that is the product of two three digit numbers, which is 993*913=906609.

Your program's output is 997799. This has a rather easy factorization: It is product of two primes, 11 and 90709. Since both are prime and neither is a three digit number, this does not qualify as the answer to the problem. Here are two different approaches to the problem:
  • Use a double loop that walks through all pairs of three digit numbers. Compute their product. Save the product as the largest palindromic product if the product is larger than your largest palindromic product and if it's a palindrome.

  • Walk downward through the palindromic numbers, starting at 999999 (or 997799 to be a bit smarter). (You'll need an algorithm to form the next smallest palindromic number.) Compute the prime factorization (including repetitions) of the current palindromic number. Stop when the prime factorization can be recombined to form a pair of three digit numbers.

The first approach is a bit more brute forcish, but it's probably going to be faster than the second because factorization is a slow algorithm, as is the recombination of these prime factors.
 
Last edited:
  • #32
986
9
When you apply brute force you need to ensure that you are apply that brute force to the right problem. Here you are applying brute force to solve the wrong problem. Your algorithm finds the largest palindrome that is smaller than 999*999=998001. You are not finding the largest palindrome that is the product of two three digit numbers, which is 993*913=906609.

Your program's output is 997799. This has a rather easy factorization: It is product of two primes, 11 and 90709. Since both are prime and neither is a three digit number, this does not qualify as the answer to the problem. Here are two different approaches to the problem:
  • Use a double loop that walks through all pairs of three digit numbers. Compute their product. Save the product as the largest palindromic product if the product is larger than your largest palindromic product and if it's a palindrome.

  • Walk downward through the palindromic numbers, starting at 999999 (or 997799 to be a bit smarter). (You'll need an algorithm to form the next smallest palindromic number.) Compute the prime factorization (including repetitions) of the current palindromic number. Stop when the prime factorization can be recombined to form a pair of three digit numbers.

The first approach is a bit more brute forcish, but it's probably going to be faster than the second because factorization is a slow algorithm, as is the recombination of these prime factors.
Whoops. I can't believe how much of an idiot I am sometimes.
 

Related Threads on Project Euler programming challenges: Am I missing something?

  • Last Post
Replies
22
Views
4K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
5
Views
505
Replies
20
Views
1K
  • Last Post
Replies
4
Views
808
Replies
2
Views
1K
Replies
6
Views
4K
Replies
13
Views
1K
  • Last Post
Replies
14
Views
848
  • Last Post
Replies
5
Views
2K
Top