Project Euler resources

Question

I'm a student with an interest in computer science and a lot of time on my hands. I've started solving Project Euler problems in PHP and Python, and most of the early problems are pretty easy to solve with either brute-force or common-sense solutions. However, when compared to the elegant solutions I see on some of the forums, my solutions are downright cumbersome, utilizing mathematical formualas I've had little experience with.

My question is, what resources do you recommend (books, websites, etc) so that I can improve the ways I solve these problems? Math books, theory websites, anything will do. I have a background in calculus, trig, all the high school math subjects, plus a decent knowledge of PHP and Python. I know I can't brute-force everything forever, and summer break means a lot of problems to solve!

Answer 1

I recommend any standard book on algorithms. Many are the same, and they teach you about simple techniques and program flow control that can solve a problem in milliseconds that was previously taking minutes!

Answer 2

In Python - http://pyeuler.wikidot.com/ Project Euler website itself has a host of solutions by users - you may want to take a look at those if you want.

Answer 3

Project Euler is more about teaching a combination of number theory and programming than just about teaching programming :).

If you know nifty things about the numbers, you can approach a problem obliquely and come up with 'elegant' solutions.

For instance the amicable pair problem is fun to solve once you read up on the properties of Amicable Pairs

The other thing to consider is that you want to also take into account some programming shortcuts, like properties of numbers when represented in binary.

For example to check for an odd number compare:

 int isOdd1(int x) { return (x % 2); } 

vs.

 int isOdd2(int x) { return x & 1; }

Here is the x86_64 disassembly of the two

0000000000000000 <isOdd1>:
   0:   89 fa                   mov    %edi,%edx
   2:   c1 ea 1f                shr    $0x1f,%edx
   5:   8d 04 17                lea    (%rdi,%rdx,1),%eax
   8:   83 e0 01                and    $0x1,%eax
   b:   29 d0                   sub    %edx,%eax
   d:   c3                      retq   
   e:   66 90                   xchg   %ax,%ax

0000000000000010 <isOdd2>:
  10:   89 f8                   mov    %edi,%eax
  12:   83 e0 01                and    $0x1,%eax
  15:   c3                      retq  

Which one would you use ? :-)

So there are a lot of things to consider, and it's good to read up on other solutions to get hints, and to really think differently.

I hope this will get you more excited about programming :-)

Cheers,

Code for above:

isodd.c

int isOdd1(int x) {
        return x % 2;
}


int isOdd2(int x) {
        return x & 1;
}

To compile with gcc:

gcc -O99 -c -o isodd.o isodd.c

To see the disassembly with objdump:

objdump -d isodd.o

Output from objdump on an x86-64 platform

isodd.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <isOdd1>:
   0:   89 fa                   mov    %edi,%edx
   2:   c1 ea 1f                shr    $0x1f,%edx
   5:   8d 04 17                lea    (%rdi,%rdx,1),%eax
   8:   83 e0 01                and    $0x1,%eax
   b:   29 d0                   sub    %edx,%eax
   d:   c3                      retq   
   e:   66 90                   xchg   %ax,%ax

0000000000000010 <isOdd2>:
  10:   89 f8                   mov    %edi,%eax
  12:   83 e0 01                and    $0x1,%eax
  15:   c3                      retq