5
\$\begingroup\$

I've written a solution to Euler 41:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

But it feels like I could compress the code down instead of having 30 lines of for loops. To briefly explain how it works:

I generate all pandigital numbers through the generate function which features 9 nested for loops which continue if their value is equal to a higher loop or if they would make a number longer than what is required. The generated numbers are then prime checked. This is a bruteforce method.

var time = new Date;
var buffer = [];
var greatest = 0;

function isPrime(number) {
var s = Math.sqrt(number);
for (var b = 2; b <= s; b++) {
    if (number % b === 0) {
        return false;
    }
}
return true;
}

function push(array) {
buffer.push(array.join(''));
}

function generate(length) {
var max = length;
for (var u = 1; u <= max; u++) {
    if (max === 1) {
        push([u]);
    }
    for (var i = 1; i <= max; i++) {
        if (i === u || max < 2) {
            continue;
        }
        if (max === 2) {
            push([u, i]);
        }
        for (var o = 1; o <= max; o++) {
            if (o === i || o === u || max < 3) {
                continue;
            }
            if (max === 3) {
                push([u, i, o]);
            }
            for (var p = 1; p <= max; p++) {
                if (p === i || p === o || p === u || max < 4) {
                    continue;
                }
                if (max === 4) {
                    push([u, i, o, p]);
                }
                for (var a = 1; a <= max; a++) {
                    if (a === i || a === o || a === p || a === u || max < 5) {
                        continue;
                    }
                    if (max === 5) {
                        push([u, i, o, p, a]);
                    }
                    for (var s = 1; s <= max; s++) {
                        if (s === a || s === p || s === o || s === i || s === u || max < 6) {
                            continue;
                        }
                        if (max === 6) {
                            push([u, i, o, p, a, s]);
                        }
                        for (var d = 1; d <= max; d++) {
                            if (d === s || d === a || d === p || d === o || d === i || d === u || max < 7) {
                                continue;
                            }
                            if (max === 7) {
                                push([u, i, o, p, a, s, d]);
                            }
                            for (var f = 1; f <= max; f++) {
                                if (f === d || f === s || f === a || f === p || f === o || f === i || f === u || max < 8) {
                                    continue;
                                }
                                if (max === 8) {
                                    push([u, i, o, p, a, s, d, f]);
                                }
                                for (var g = 1; g <= max; g++) {
                                    if (g === f || g === d || g === s || g === a || g === p || g === o || g === i || g === u || max < 9) {
                                        continue;
                                    }
                                    push([u, i, o, p, a, s, d, f, g]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
}

for (var i = 1; i <= 8; i++) {
generate(i);
}

for (var i = buffer.length - 1; i >= 0; i--) {
if (isPrime(buffer[i])) {
    greatest = buffer[i];
    break;
}
}

var time1 = new Date;
console.log(greatest, 'took:', time1 - time, 'ms');
\$\endgroup\$
3
\$\begingroup\$

I think this is a bit over engineered. Let's talk our way through the problem.

  • By definition we know the highest pandigital number is 987654321.
  • We need to loop through each odd number between 1 and 987654321.
  • We need to test each number as a prime. Here's a nice optimised isPrime function from here.

    function isPrime(number) {
      var start = 2;
      while (start <= Math.sqrt(number)) {
        if (number % start++ < 1) return false;
      }
      return number > 1;
    }
    
  • If it is prime we need to test each number is pandigital. We should only need to loop once. If we make a set of the digits in a number, then the length of the set will be equal to the total count of digits in the number.

    function isPandigital(number) {
       var numStr = number.toString(),
         digits = [];
    
       for (var digit in numStr) {
    
         if (numStr.hasOwnProperty(digit) && digits.indexOf(digit) === -1) 
            digits.push(digit);
       }
    
       return digits.length === numStr.length;
    }
    
  • Then you just need to write the loop:

    var pandigitalPrimes = [];
    
    for (var n = 1; n <= 987654321; n+=2) {
      if (isPrime(n) && isPandigital(n)) pandigitalPrimes.push(n);
    }
    
  • Now it's your job to optimise these ideas so that this process doesn't take absolutely forever.

\$\endgroup\$
  • 2
    \$\begingroup\$ Maybe it's a bit under-engineered. :) "Optimise these ideas" means "Use the Sieve of Erastothene" which is a bit different than simply looping over all numbers. \$\endgroup\$ – Quentin Pradet Feb 6 '14 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.