Project Euler Problem #24

in code


#24 defeated the fuck out of me first time through:

My solution to this was basically stolen elsewhere, and it took me a whole year to come back, sit down, and work through my own solution. The poor wording (I’ve since edited it) of the Wikipedia article didn’t help me.

The specific piece of information that defeated me so badly was the mathematical description of lexicographic permutation on Wikipedia. I just could not wrap my head around it, and even this attempt took a serious effort for me to mentally rephrase:

  1. Find the last index in an array where a number is smaller than the number to its right.
  2. Find the last_index in an array which is bigger than step #1, but smaller or equal to Number to the Right.
  3. Swap Number To the Right with Smaller Or Equal Number.
  4. Return the array with everything from Number To The Right reversed.

I first used Lodash’s findLastIndex method, but I wrote my own implementation because I didn’t like the external dependency.

/**
 * Find the last element in an array where predicate returns true.
 *
 * @param {array} array - Array to test.
 * @param {function} predicate - Callback function to execute.
 * @param {number=} [index=array.length - 1] - Starting index.
 * @return {number} First index matching predicate, -1 if not matched.
 */

function findLastIndex(array, predicate, index) {
    if (!Number.isInteger(index)) {
        index = array.length - 1;
    }

    if (index < 0 || predicate(array[index], index, array)) {
        return index;
    } else {
        return findLastIndex(array, predicate, index - 1);
    }
}

/**
 * Generator which performs lexicographic permutations on an array, more-or-less
 * endlessly.
 *
 * @see https://projecteuler.net/problem=24
 * @see https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
 * @see https://www.nayuki.io/res/next-lexicographical-permutation-algorithm/next-permutation-algorithm.png
 * @require findLastIndex
 * @param {array} array - Array to permute. Strings should be split and joined outside.
 * @return {object} - Iterator object.
 */

function* lexicographer(array) {
    let pivot, largest, successor;

    while (true) {
        // Yield first to ensure the proper first iteration (the unchanged collection) is output.
        yield array;

        pivot = findLastIndex(array, (number, index) => number < array[index + 1]);
        // Largest such element in an array.
        largest = pivot + 1;
        // Last element such that it is bigger than the pivot, and smaller or equal to the largest.
        successor = findLastIndex(array, (number, index) => array[pivot] < number && number <= array[largest]);
        // Swap the pivot and successor.
        [array[pivot], array[successor]] = [array[successor], array[pivot]];
        // Return the rest of the array with the end reversed.
        array = array.slice(0, largest).concat(array.slice(largest).reverse());
    }
}

const breakpoint = 1000000;
let permutations = 0;

for (let value of lexicographer([...Array(10).keys()])) {
    permutations++;

    if (permutations === breakpoint) {
        console.log(value.join(''));
        break;
    }
}


A Summer of Running

in running

Achill Half Marathon

in running


Your email address will not be published. Required fields are marked *