Mark Grealish

the life and code of a crazy cat man


Project Euler Problem #16

in code

Ruby this time, and a wee bit shorter too.

(2**1000).to_s.split(//).map(&:to_i).reduce(:+)

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;
    }
}

Project Euler Problem #22

in code

Again, better. :)

#!/usr/bin/env node

const fs = require('fs');
const add = previous, current) => previous + current;

const toNumbers = string => {
    return string.split('').map((_, index) => string.charCodeAt(index) % 64);
}

fs.readFile('./p022_names.txt', 'utf8', (_, data) => {
    const names = JSON.parse(['[', data, ']'].join('')).sort();

    const reduced = names.map((name, index) => {
        return toNumbers(name).reduce(add) * (index + 1);
    }).reduce(add);

    console.log(reduced);
});

Project Euler Problem #12

in code

Once again, it’s more readable than my last solution. I used a generator to get the next triangle.

function divisorCount(number) {
    let end = Math.ceil(Math.sqrt(number));
    let divisorCount = 0;

    for (let i = 1; i < = end; i++) {
        if (!(number % i)) {
            divisorCount += 2;
        }
    }

    return divisorCount;
}

function* triangleGenerator(number) {
    let current = 0;

    while (true) {
        current += 1;
        yield (current + 1) * current >> 1;
    }
}

function solver(goal, generator) {
    const triangle = generator.next().value;

    if (divisorCount(triangle) > goal) {
        return triangle;
    } else {
        return solver(goal, generator);
    }
}

console.log(solver(500, triangleGenerator()));

A karmic ditty for developers everywhere

in random

Whenever you start to complain
First take the time to git blame!


Project Euler Problem #8

in code

Functional JavaScript is cleaner than my C# solution, for sure!

const raw = '731..450'; // Snipped for clarity.
const chunkSize = 13;
const multiply = (previous, current) => previous * current;
const largest = (previous, current) => current > previous ? current : previous;

function chop(string, size, chunks) {
    chunks = chunks || [];

    if (!string || string.length < size) {
        return chunks;
    }

    return chunks.concat(string.slice(0, size), chop(string.slice(1), size, chunks));
}

chop(rawString, chunkSize).map(str => str.split('').reduce(multiply)).reduce(largest);