Project Euler

Can you get a more geeky hobby than one which combines maths and computer programming?

A friend of mine recently introduced me to Project Euler. What is it? To quote the about page:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

In other words, you write short computer programs to solve mathematical puzzles. Here’s the very first problem:

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.

You may recognise that as being the FizzBuzz question that I’ve discussed before, except adding the numbers for a total instead of printing out Fizz and/or Buzz. It’s a simple algorithm. If you sign up to Project Euler you get to check your answer, and, if you’re right, gain access to the forum discussing solutions in a variety of different programming languages.

Sometimes – often, in fact – you’ll discover that there’s a mathematical formula that provides the answer. That’s certainly the case for the first problem. In the spirit of the site I’ll avoid spoilers. There’s also an element of gamification as you can earn awards and increase your level as you progress through the problems:

The problems generally get progressively harder and also rely on techniques and ideas from earlier problems, so it’s worth tackling them roughly in order. Some of the problems are very easy to state and understand, but can tricky to solve. Problem 31 is a good example:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

It took me a while to get that one, and my solution is a horribly messy and inelegant set of loops. I seem to have something of a blind spot when it comes to writing recursive functions, and that’s definitely something I need to overcome.

As well as being a fun intellectual challenge, it’s a great way to get to know a programming language. I’m using Python, and my previous experience with it was limited to making minor changes to existing code and short scripts. I could have used Perl, as I feel I’m more fluent in Perl, but I wanted to brush up on my Python. If you want to be able to throw data structures such as lists and dictionaries around with abandon, then Project Euler is a good way to get confident with them.

Some of the problems also make use of data files, so there’s an opportunity to get used to reading data and converting it into a data structure. You can also investigate the various libraries of your language of choice. For example, some of the problems require you to calculate or iterate over the permutations of a set of numbers. The purist approach might be to figure out an algorithm from scratch, but Python has the itertools library – it’s your choice, but I’m happy with using existing libraries where they help.

Problem 54 is a great example of one that covers many of the basics, from file I/O to data structures. The idea is to score poker hands to determine how many are won by player 1, from a list of 1000 random hands dealt to two players.

The hands are represented by a file containing 1000 lines of cards represented as follows:

5C AD 5D AC 9C 7C 5H 8D TD KS

Player 1 has the first 5 cards, player 2 has the second. The challenge is to read the file into a suitable data structure and then analyse the structure to determine who wins each hand.

Later problems have you decoding encrypted text and even writing a general Sudoku solver.

As the problems go on, the need to know the maths behind the questions becomes more important. Sometimes it’s simply a case of googling the concept and trying to interpret the resulting Wikipedia page, but you can take if further if you’re interested in a more rigorous understanding. I may have gone a bit too far…

You have to be a bit careful with your googling. As the site puts it:

I solved it by using a search engine, does that matter?

Making use of the internet to research a problem is to be encouraged as there could be hidden treasures of mathematics to be discovered beneath the surface of many of these problems. However, there is a fine line between researching ideas and using the answer you found on another website. If you photocopy a crossword solution then what have you achieved?

If you’re thinking of joining it’s probably worth scanning the first couple of pages of problems to see whether you’ll be able to stick with it. The site shows how many users have solved each problem, and those numbers drop off quickly – from nearly 900,000 for problem 1 to less than 10,000 for some of the first 100 problems and down to a few hundred for the later problems. Be aware that, as they go on, the problems become much more about the maths than the programming.

And you don’t have to go as far as buying an undergraduate level number theory textbook… but it helps 🙂

in Random Musings

Related Posts