Skip to content

Instantly share code, notes, and snippets.

@djacobs djacobs/euler24.js
Created Nov 30, 2011

Embed
What would you like to do?
Euler 24 solution
#!/usr/local/bin/node
// basic problem setup
// the answer we want for the millionth iteration is 2783915460
var iteration = 999999;
var size = 2;
// figure out the size of the largest factorial smaller than our target iteration
var tempi = iteration;
while (tempi/size > 1) {
size++;
tempi = tempi/size;
}
// the arrays we'll use
var permutation = new Array();
var answer = new Array();
var f = new Array();
for (i=0; i <= size; i++) {
permutation[i] = i;
}
// I wrote a slightly slower factorial function, I took this one from http://stackoverflow.com/questions/3959211/fast-factorial-function-in-javascript
function factorial(n) {
if (n<=1) { return 1; }
else if (f[n]>0) { return f[n]; }
else { return f[n]=factorial(n-1)*n; }
}
// pull out the next value for the iterator by taking the floor of the divisor of the remainder and the next smallest factorial
function findTumbler(rem, b) {
var f = Math.floor(rem/factorial(b));
if (rem == 0) {
// fill in the rest of the answers array, we're done!
l = permutation.length;
for (j=0; j <= l; j++) {
answer[size-b+j] = permutation.splice(0,1);
}
} else {
answer[size-b] = permutation.splice(f,1);
findTumbler(rem % factorial(b), b-1);
}
}
findTumbler(iteration, size);
console.log ("final answer:", answer.join(''));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.