What is your favorite Project Euler question?

Question

I was searching around for questions related to Project Euler on Stack Overflow, and it seems that there were plenty of people asking about it, and even more people recommending it, whether for fun, to learn a new language, or to practice for interview questions. All this seems to imply to me that there are lots of people on SO that solve Project Euler problems now and then. I just started, so I was wondering:

What was your favorite Project Euler question? Why? Did you think of a clever trick, or did you learn some new math, or did you discover a feature of a new programming language?

(If possible, please include the actual question in your answer.)

Answer 1

I've only gotten up to Problem 43. Most of them have been pretty straightforward.

This one was fun, especially seeing people's more and more efficient solutions on the forums once I completed it.

Answer 2

Problem 229. Before that I was not aware just how fast and powerful sieving is.

Answer 3

My least favorite question is #54 about the poker hands, it's not mathematical and doesn't seem to lead to an elegant solution.

Answer 4

Problem 58 taught me once again that optimization should be done only after profiling. Naive method to check primes was working couple of times faster than finding them with sieve before hand and then check for them with the hash. Makes you think sometimes.

Problem 230 showed me once again how much C++ faster than Ruby. Makes you wonder every time.

BTW as much as I love solving those problems, it takes intensive amount of time, so much, that not only my side projects got abandoned but it really affects efficiency at my day-to-day job. So I just make myself stop after couple of weeks of solving them.

Answer 5

Two that I had a lot of fun doing were Question 59 which was about cracking a piece of (weakly) encrypted text and Question 96 which was a sudoku solver.

I have to admit, though, that they're questions that probably appeal more to programmers with weaker math backgrounds (such as myself).

Answer 6

I liked the one with where you had to cross every path through a matrix only once. It's how I learned the importance of caching!

Answer 7

My favorite is number 227, because there is a funny story about it. In our university network, there is one quad-core computer that everyone can use for high-performance computations. My friend was complaining that it had been kind of laggy lately. We saw that there was a process named "prob-227-e" running, which had used already three weeks(!) of CPU time.

I immediately guessed that it must be Project Euler problem. I took a look at the problem, and within 20 minutes I had written a ten-line Octave-script that just solves a 100x100-system of equations and runs in a blink of an eye (and produces the correct answer). I then emailed that to the user, and the next day, he answered to thank me and explain what he had been doing, which was some kind of brute-force simulation.

Elegance always pays off : )

---

The question

The players sit around a table; the game begins with two opposite players having one die each. On each turn, the two players with a die roll it. If a player rolls a 1, he passes the die to his neighbour on the left; if he rolls a 6, he passes the die to his neighbour on the right; otherwise, he keeps the die for the next turn. The game ends when one player has both dice after they have been rolled and passed, that player has then lost.

In a game with 100 players, what is the expected number of turns the game lasts?

Answer 8

One of my faves is Problem 164.

It says:

How many 20 digit numbers n (without any leading zero) exist such that no three consecutive digits of n have a sum greater than 9?

You can't solve it by brute force (in a reasonable time, at least), but you can using concepts as Dynamic Programming and Memoization.

Answer 9

I really like the problem about the Heighway Dragon. I made a simple program, which made the moves, but then I realized how many steps does it have to make (using two recursive functions)... I haven't solved it yet, well I think, there must be some simplier way to solve it.