Euler 9 in C | ~robteix

So I recently wrote an ugly solution to Project Euler’s problem #9. It was written in Python and even though every other Project Euler solution I wrote ran in less than one second, this one took over 18 seconds to get to the answer. Obviously it’s my fault for using a purely brute force algorithm.

Anyway, boredom is a great motivator and I just rewrote the exact same algorithm in C, just to see how much faster it would be.

#include 

int is_triplet(int a, int b, int c)
{
        return (((a < b) && (b < c)) && ((a * a + b * b) == (c * c)));
}

int main(void)
{
        for (int a = 0; a < 1000; a++)
                for (int b = a + 1; b < 1000; b++)
                        for (int c = b + 1; c < 1000; c++)
                                if ((a + b + c == 1000) && is_triplet(a, b, c)) {
                                        printf("%d %d %d = %d\n", a, b, c,
                                               a * b * c);
                                        return 0;
                                }
}

It's the exact same algorithm, but instead of 18 seconds, it ran in 0.072s.

Update: And here's the version suggested by Gustavo Niemeyer:

#include 

int is_triplet(int a, int b, int c)
{
        return ((a * a + b * b) == (c * c));
}

int main(void)
{
        for (int a = 1; a < 1000; a++)
                for (int b = a + 1; b < (1000 - a) / 2; b++) {
                        int c = 1000 - a - b;
                        if (is_triplet(a, b, c)) {
                                printf("%d %d %d = %d\n", a, b, c,
                                       a * b * c);
                                return 0;
                        }
                }
}

It now runs in 0.002s :-)

import psyco psyco.full() from sys import exit def is_triplet(a, b, c): if a < b and b < c: return a ** 2 + b ** 2 == c ** 2 def doit(): for a in range(0, 1000): for b in range(a + 1, 1000): for c in range(b + 1, 1000): if a + b + c == 1000 and is_triplet(a, b, c): return a*b*c print doit()

http://raisama.net/ Eduardo Habkost

On my machine, the original Python code took more than 40 seconds to run.

Then I changed it to use Psyco (I just moved the main code into its own function to make life easier for Psyco) and it took only 0.773 seconds!

This is the Python code I ran:

http://robteix.com Roberto Teixeira
Wow, big difference. Didn’t think of trying Psyco. Anyway, the algorithm is still pretty damn stupid. One of this days I’ll try to figure a math-based solution.

http://robteix.com Roberto Teixeira
Also, stupid me, just realized the test for a < b and b > c isn’t at all needed since the fors already take care of that. Shouldn’t make too much of a difference though.

http://niemeyer.net Gustavo Niemeyer
When brute forcing, the innermost loop isn’t necessary, since there’s only one possible working value, and the second loop can be restricted based on the value of a.
Here is a faster version incorporating these changes:
#include
int is_triplet(int a, int b, int c)
{
return (((a < b) && (b < c)) && ((a * a + b * b) == (c * c)));
}
int main(void)
{
for (int a = 0; a < 1000; a++) {
for (int b = a + 1; b < 1000 – a; b++) {
int c = 1000 – a – b;
if (is_triplet(a, b, c)) {
printf("%d %d %d = %d\n", a, b, c,
a * b * c);
return 0;
}
}
}
}
http://niemeyer.net Gustavo Niemeyer
Here is a Python version, with a final optimization in the b loop. b must necessarily be under (1000 – a)/2, because c is greater than b. This removes the need for the comparison entirely.
def doit():
for a in range(1, 1000):
for b in range(a + 1, (1000 – a) // 2 + 1):
c = 1000 – a – b
if a ** 2 + b ** 2 == c ** 2:
return (a, b, c), a*b*c
print doit()