Project Euler #41 - pandigital prime

Question

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');

Answer 1

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.