Project Euler Problem #38

May 3, 2010

Read the details of the problem here

Summary

What is the largest 1 to 9 pandigital that can be formed by multiplying a fixed number by 1, 2, 3, … ?

Solution

As with a lot of Project Euler problems it’s worth having a bit of a think about the problem before jumping into coding a solution in order to understand the potential search space.

In the second part of the question it states that (9*1)…(9*5) is going to give 918273645 so, as that’s most probably not the actual answer, any solution has to exceed that value. This means that the seed number must begin with a “9”.

This therefore forces additional constraints on the range. A two-digit seed number (90-98) won’t work as, the concatenated sequence would either be 8 digits long (for 3 multipliers) or 11 digits long (for 4 multipliers) and so could not be pandigital. Also, it can’t be a three-digit seed number (901-987) as the length would be either 7 or 11 digits for multipliers of 2 and 3 respectively. As at least two numbers have to be concatenated, this means that it has to be a four-digit seed number, using only multipliers of 1 & 2, between the range of 9182 and 9876. As we’re looking for the highest number, it would probably make sense to code a descending search so the first item satisfying criteria will be the solution, but I’ll use Groovy listops unless performance is horrible.

The code itself is then very straightforward to write and declarative of the problem.

def answer =
    (9876..9182).collect { it.toString() + (it*2).toString() }
                .findAll { it.toList().sort().join() == "123456789" }
                .max()

This runs in 16 ms. So quite quick even with Groovy listops! A non-listop approach using a descending search, as mentioned above and coded as below, runs in 6 ms.

def answer = 0

for (i in 9876..9182) {
    def s = i.toString() + (i*2).toString()
    if (s.toList().sort().join() == "123456789") {
        answer = s
        break
   }
}

Conclusion

Groovy made it simple to code the pandigital test and performed quite adequately for the scope of the problem. I’m not sure that I like the for-loop’s capability to infer direction of the loop. It’s great in this case, where the bounds are hardcoded, but might cause some confusion with variable values.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: