I like to go back and re-solve Project Euler problems in different languages. Lately, I’ve been solving them in Javascript for fun. When I do this, I don’t look at previous solutions and try to do it from scratch. When I was finished, I was surprised by the performance of my solution to 43 compared to my previous attempts in other languages.
Problem 43 is as follows:
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
- d2d3d4=406 is divisible by 2
- d3d4d5=063 is divisible by 3
- d4d5d6=635 is divisible by 5
- d5d6d7=357 is divisible by 7
- d6d7d8=572 is divisible by 11
- d7d8d9=728 is divisible by 13
- d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
When I first solved this problem, I solved it in C. This was in 2014, and I was still fairly green. My solution at the time was to iterate through every 10-digit number and see if it was pandigital and then if it was, check if it met the sub-divisibility requirement.
This solution is what you would call “brute-force”. It’s inelegant, and slow. However, it does work. It took 33.948 seconds to compute.
A few years later I was doing more with Rust and Python. Both of these solutions I created used the same method. This probably happened because I wrote both solutions close together. At any case, this time I thought myself more clever and took a pandigital number, 1234567890, and discovered every permutation, and then checked for the sub-divisibility requirement of each.
This is better than brute force, but still time consuming. Python can accomplish this in 18.724 seconds and Rust in 4.621. Better, but still not great.
The general rule of thumb with Project Euler is that if a solution takes more than a second, you haven’t found the intended method of solving it.
Looking at it this time around, it seemed like a very straightforward problem with an obvious path for a solution. Instead of finding pandigital numbers and checking if they meet the sub-string divisibility requirement, this time I would build up the pandigital numbers using the sub-strings.
First I created arrays for the multiples of the first 7 primes with 2 and 3 digits. I then used a recursive function to build up a number using valid combinations of these sub-strings (since each one overlaps the next with 2 digits). This creates a much smaller group of numbers to check.
Once I have all my potential pandigital numbers, I check to make sure they are in fact pandigital. (Note that at this stage, they should be missing the first digit). When checking for pandigitality, I’m actually looking for 9 different digits, and if so, I prepend the missing 10th digit and voila, it’s a valid pandigital number!
This solution is much, much faster at .237 seconds.
I’m very pleased with that result, but a little shocked I didn’t see this method when I have solved it previously. It’s nice to know that since I first started solving these problems years ago, I can see measurable improvement in my ability to find and create solutions to these fun little puzzles.