Recently I’ve become addicted to solving math problems at Project Euler. Yes, I know this is incredibly dorky, but I am a computer science grad student, and it is probably a good sign that I am doing math problems in my spare time.
Project Euler keeps a list of math problems to which there is a numeric solution. You register on the web site, and then you can submit an answer for a problem. If your answer is correct, then you are given access to an official solution and also a forum where others have posted their solutions.
The problems get increasingly difficult, from (relatively) simple questions like “What is the largest prime factor of the number 600851475143 ?” (solved by brute-force factorization) to much more difficult problems.
I got hooked on this by a post at a programming forum I frequent. The poster could not find a solution to problem 185 and was looking for suggestions. His initial idea was to basically try guess-and-check with some hill climbing to look for local solutions. I didn’t think that would work because the search space is too large (10^16). My idea was to use the hints to construct the number.
Let’s look at the hints. Given the hint with 0 digits correct, you can eliminate each of those digits from the possible answers. Now look at a hint with 1 digit correct. We don’t know which digit is correct, so let’s assume it’s the first. Then we know the first digit and can eliminate another possible digit for the remaining digits. Now look at the next hing. Again, assume the first digit is correct. If it is the same as the first one, then this is an OK guess and we can continue. If not, then we assume the second digit is the correct one and continue our search.
So basically we want to construct a search tree using all the hints, looking for a consistent set of assumptions about which digits in each hint are correct. The depth of the tree is the number of hints given, and the fan-out depends on the number correct in each hint — if n is the number correct, then the fan out for that level is 16 choose n. We short circuit a branch if we encounter an inconsistent assumption. If we ever reach a leaf node and have a fully constrained assumption, then that should be our answer.
The worst-case running time of this algorithm is horrendous because of the fan out. The fan-out for the sample problem can be as bad as 16 choose 3 = 560, so if you actually have to explore every path, you’re looking at a running time of at worst 560^22 steps. In reality it’s not nearly that bad, partly because not every hint causes a fan-out of 560, but mostly because you can skip large parts of the tree because they lead to inconsistent assumptions early on.
I coded this algorithm up in Java, but not without some difficulty. Specifically, I don’t think I chose good representations for my guesses and for my the combinations of possible correct digits. Regardless, my program chugged away for 4 hours and finally spit out the correct answer. Success!
There’s a lot of optimization I could do. One thing I didn’t exploit was ordering the hints to reduce the search space. I tried to do this by ordering the hints from least to most digits correct, but I think a better strategy would be to choose the hint that constrains the problem the most. That way you will have to explore less of the lower part of the tree.
I’ve been thinking about this problem for several days now, and I’m very pleased to have solved it. I’ll be working on more Project Euler problems, and if I come across any particularly interesting ones, I will post my solution here.
