Project Euler

0_ProjectEuler.md

Project Euler

My attempt at weekly project euler solution

Problem001.js

/**
 * https://projecteuler.net/problem=1
 *  If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
 *  Find the sum of all the multiples of 3 or 5 below 1000.
 * 
 *  @param  {Number}    n       When to stop summing multiples, 1000 for the answer
 */
Problem1(1000) === 233168;
function Problem1(n) {
    
    var sum = 0;
    
    for (var i = 0; i < n; i++) {
        if (i % 3 === 0 || i % 5 === 0) {
            sum += i;
        }
    }
    
    return sum;
    
}

Problem002.js

/**
 * https://projecteuler.net/problem=2
 *  Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
 *  1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
 *  By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
 *  
 *  @param  {Number}    max         When to stop summing
 *  @param  {Number}    fib1        The first fibonacci number, by default 1
 *  @param  {Number}    fib2        The second fibonacci number, by default 1
 */
Problem2(4000000, 1, 2) === 4613732;
function Problem2(max, fib1, fib2) {
    
    var sum = 0;
    var f = Fibonacci(fib1, fib2);
    
    for (var n = 0; n < max; n = f.next().value) {
        if (n % 2 === 0) sum += n;
    }
    
    return sum;
    
}
 
/**
 * The Fibonacci sequence, in an ES6 Generator
 *  
 *  @param  {Number}    seed1       The first fibonacci number, by default 1
 *  @param  {Number}    seed2       The second fibonacci number, by default 1
 */
function *Fibonacci(seed1, seed2) {
    
    if (seed1 == null) seed1 = 1;
    if (seed2 == null) seed2 = 1;
    
    var fib1 = seed2;
    var fib2 = seed1;
    
    while (true) {
        var current = fib2;
        fib2 = fib1;
        fib1 = fib1 + current;
        yield current;
    }
    
}

Problem004.js

/**
 * https://projecteuler.net/problem=4
 *  A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
 *  Find the largest palindrome made from the product of two 3-digit numbers.
 *  
 *  @param  {Number}    max         Where to start {a} and {b}
 */
Problem4(999) === 906609;
function Problem4(max) {
    
    // Initialise the largest palindrome to zero
    var largestPalindrome = 0;
    
    // Loop through {a} and {b} from {max} to 0
    for (var a = max; a > 0; a--) {
        for (var b = max; b > 0; b--) {
            
            // Calculate the product from {a} and {b}
            var n = a * b;
            
            // Check if the product is a palindrome
            if (isPalindrome(n.toString())) {
                
                // Overwrite the largest palindrome if {n} is larger
                if (n > largestPalindrome) {
                    largestPalindrome = n;
                }
                
                // Break from the loop
                break;
                
            }
            
        }
    }
    
    return largestPalindrome;
    
}

/**
 * Check if a string is the same in reverse
 *  
 *  @param  {String}    string  String to check for palindrome-ness
 */
function isPalindrome(string) {
    
    // Check the string matches the reverse of itself
    return  string === string.split('').reverse().join('');
    
}

Problem005.js

/**
 * https://projecteuler.net/problem=5
 *  2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
 *  What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
 *  
 *  @param  {Number}    max         Length of range to test numbers, 20 for test
 */
Problem5(10) === 2520;
function Problem5(max) {
    
    // Get a range of numbers from 1 through {max}
    // (simplest way to do it in Vanilla ECMAScript)
    var range = Array.apply(null, Array(max)).map(function(_, i) {
        return i + 1;
    });
    
    // Remove the numbers from the range we don't need to test
    range = range.filter(function(i) {
        
        // Keep the last element
        if (i === max) return true;
        
        // Remove if it is divisble by the max
        return (max % i !== 0);
        
    });
    
    // We know the answer can't be less than {max}
    var n = max;
    
    // Increment {n} by {max} until we find {n} that is divisible by
    // every {i} in {range}
    while (!range.every(function(i) {
        return n % i === 0;
    })) n += max;
    
    // Then return {n}
    return n;
    
}

Problem006.js

/**
 * https://projecteuler.net/problem=6
 *  The sum of the squares of the first ten natural numbers is,
 *  12 + 22 + ... + 102 = 385
 *  The square of the sum of the first ten natural numbers is,
 *  (1 + 2 + ... + 10)2 = 552 = 3025
 *  Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
 *  Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
 *  
 *  @param  {Number}    max         When to stop adding squares
 */
Problem6(100) === 25164150;
function Problem6(max) {
    
    // let {a} = the square of the sum of {1..max}
    var a = Math.pow((max * (max + 1)) / 2, 2);
    
    // let {b} = the sum of the squares from {1..max}
    var b = 0;
    for (var i = 1; i <= max; i++) b += Math.pow(i, 2);
    
    return a - b;
    
}

Problem008.js

/** The 1000-digit number **/
var n = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450';

/**
 * https://projecteuler.net/problem=8
 *  The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
 *  Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
 *  
 *  @param  {Number}    length          The amount of adjacent digits to find the product for
 *  @param  {String}    n               The 1000-digit number to search
 */
Problem8(4, n) === 5832;
function Problem8(length, n) {
    
    // Turn the string into an array
    n = n.split('');
    
    // Reduce the array to find the largest product
    return n.reduce(function(largestProduct, _, i) {
        
        // Get the next {length} numbers
        var a = n.slice(i, i + length);
        
        // Ignore any with 0
        if (a.indexOf(0) !== -1) return largestProduct;
        
        // Calculate the product of the numbers
        var product = a.reduce(function(product, i) {
            return product *= parseInt(i, 10);
        }, 1);
        
        // Overwrite the largest product if this is larger
        if (product > largestProduct) {
            largestProduct = product;
        }
        
        return largestProduct;
        
    }, 0);
    
}

Problem011.js

/** The 20x20 grid **/
var n = '08022297381500400075040507785212507791084949994017811857608717409843694804566200814931735579142993714067538830034913366552709523046011426924685601325671370236912231167151676389419236542240402866331380244732609903450244753353783684203517125032988128642367102638406759547066183864706726206802621220956394396308409166499421245558056673992697177878968314883489637221362309750076442045351400613397343133957817532822753167159403800462161409535692163905429635314755588824001754243629855786560048357189070544443744602158515417581980816805944769287392138652177704895540045208839735991607975732162626793327986688366887576220720346336746551232639353690442167338253911249472180846293240627636206936417230238834629969826759857404361620733529783190017431497148868116235705540170547183515469169233486143520189196748';

/**
 * https://projecteuler.net/problem=11
 *  In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
 *  The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
 *  What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
 *  
 *  @param  {Number}    arrayLength         The amount of adjacent digits to find the product for
 *  @param  {Number}    numberLength        The size of the numbers
 *  @param  {Number}    rowLength           The amount of numbers in a row
 *  @param  {Number}    n                   The grid
 */
Problem11(4, 2, 20, n) === 70600674;
function Problem11(arrayLength, numberLength, rowLength, n) {
    
    // Convert n into an array
    n = n.split('');
    
    // Convert it to a grid
    n = n.reduce(function(grid, _, index) {
        
        if (index % numberLength === 0) {
            grid.push(parseInt(n.slice(index, index + numberLength).join(''), 10));
        }
        
        return grid;
        
    }, []);
    
    // Reduce the grid to get the largest product
    return n.reduce(function(largestProduct, _, index) {
        
        // Get the column and row
        var column = index % rowLength;
        var row = Math.floor(index / rowLength);
        var lastRow = Math.floor(n.length / rowLength);
        
        // Check the left->right adjacent numbers
        if (rowLength - column >= arrayLength) {
            
            var a = n.slice(index, index + arrayLength);
            largestProduct = largest(largestProduct, findProduct(a));
            
        }
        
        // Check the up->down numbers
        if (lastRow - row >= arrayLength) {
            
            var a = [];
            for (var i = 0; i < arrayLength; i++) {
                a.push(n[index + (rowLength * i)]);
            }
            
            largestProduct = largest(largestProduct, findProduct(a));
            
        }
        
        // Check the left->right diagonal numbers
        if (rowLength - column >= arrayLength && lastRow - row >= arrayLength) {
            
            var a = [];
            for (var i = 0; i < arrayLength; i++) {
                a.push(n[index + (rowLength * i) + (1 * i)]);
            }
            
            largestProduct = largest(largestProduct, findProduct(a));
            
        }
        
        // Check the right->left diagonal numbers
        if (column >= arrayLength && lastRow - row >= arrayLength) {
            
            var a = [];
            for (var i = 0; i < arrayLength; i++) {
                a.push(n[index + (rowLength * i) - (1 * i)]);
            }
            
            largestProduct = largest(largestProduct, findProduct(a));
            
        }
        
        return largestProduct;
        
    }, 0);
    
}

// Function to return largest argument
function largest() {
    return [].reduce.call(arguments, function(largest, n) {
        return n > largest? n : largest;
    }, 0);
}

// Function to get the product of an array
function findProduct(array) {
    return array.reduce(function(product, n) {
        return product * n;
    }, 1);
}

Problem013.py

#!/usr/bin/env python
# https://projecteuler.net/problem=13
#    Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

with open('large-numbers.txt', 'r') as numbers:
    str(sum(map(int, numbers.readlines())))[:10]

Problem014.js

/**
 * https://projecteuler.net/problem=14
 *  
 *  The following iterative sequence is defined for the set of positive integers:
 *  n → n/2 (n is even)
 *  n → 3n + 1 (n is odd)
 *  
 *  Using the rule above and starting with 13, we generate the following sequence:
 *  13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
 *  
 *  It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
 *  Which starting number, under one million, produces the longest chain?
 *  
 *  @param  {Number}    max         The largest starting number
 */
Problem14(1000000) === 837799;
function Problem14(max) {
    
    var longestChain = 0;
    var longestChainStart = 0;
    
    for (var n = 2; n < max; n++) {
        
        var length = collatzLength(n);
        if (length > longestChain) {
            longestChain = length;
            longestChainStart = n;
        }
        
    }
    
    return longestChainStart;
    
}

function largest() {
    return [].reduce.call(arguments, function(largest, n) {
        return n > largest? n : largest;
    }, 0);
}

function collatzLength(n) {
    
    var length = 0;
    var chain = Collatz(n);
    
    while (!chain.next().done) length++;
    
    return length;
    
}

function *Collatz(n) {
    
    yield n;
    
    while (n !== 1) {
        
        if (n % 2 === 0) {
            n = n / 2;
        } else {
            n = 3 * n + 1;
        }
        
        yield n;
        
    }
    
}

Problem016.js

/** 2^1000, ECMAScript can't handle >2^53 natively so I quickly ran pow(2, 1000) through python **/
var n = '10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376';

/**
 * https://projecteuler.net/problem=16
 *  2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
 *  What is the sum of the digits of the number 2^1000?
 *  
 *  @param  {Number}    n           Number to sum digits of
 */
Problem16(n);
function Problem16(n) {
    
    return n.split('').reduce(function(sum, digit) {
        
        return sum + parseInt(digit, 10);
        
    }, 0)
    
}

Problem017.sh

#!/bin/sh

strip_leading_zeros() {
    echo "$1" | sed 's/^0*\(.*\)/\1/';
}

first_digit() {
    echo "$1" | sed 's/^\(.\).*/\1/';
}

nth_last_digits() {
    echo "$1" | sed 's/.*\(.\{'"$2"'\}\)$/\1/';
}

nth_last_digit() {
    echo "$1" | nth_last_digits "$2" | first_digit;
}

last_digit() {
    echo "$1" | sed 's/.*\(.\)$/\1/';
}

number_to_word() {
    NUMBER="$(strip_leading_zeros "$1")";
    case $NUMBER in
        1) printf 'one'; ;;
        2) printf 'two'; ;;
        3) printf 'three'; ;;
        4) printf 'four'; ;;
        5) printf 'five'; ;;
        6) printf 'six'; ;;
        7) printf 'seven'; ;;
        8) printf 'eight'; ;;
        9) printf 'nine'; ;;
        10) printf 'ten'; ;;
        11) printf 'eleven'; ;;
        12) printf 'twelve'; ;;
        13) printf 'thirteen'; ;;
        15) printf 'fifteen'; ;;
        18) printf 'eighteen'; ;;
        1[4-9])
            printf $(number_to_word $(last_digit $NUMBER));
            printf 'teen';
            ;;
        
        [2-9][0-9])
            case $(first_digit $NUMBER) in
                2) printf 'twenty'; ;;
                3) printf 'thirty'; ;;
                4) printf 'forty'; ;;
                5) printf 'fifty'; ;;
                6) printf 'sixty'; ;;
                7) printf 'seventy'; ;;
                8) printf 'eighty'; ;;
                9) printf 'ninety'; ;;
            esac;
            case $(last_digit $NUMBER) in
                [1-9]) printf ' '; printf "$(number_to_word $(last_digit $NUMBER))"; ;;
            esac;
            ;;
        
        [1-9]00)
            printf "$(number_to_word $(first_digit $NUMBER))";
            printf ' hundred';
            ;;
        
        [1-9][0-9][0-9])
            printf "$(number_to_word $(first_digit $NUMBER))";
            printf ' hundred and ';
            printf "$(number_to_word $(strip_leading_zeros $(nth_last_digits $NUMBER 2)))";
            ;;
        
        [1-9]000)
            printf "$(number_to_word $(first_digit $NUMBER))";
            printf ' thousand';
            ;;
        
        [1-9][0-9][0-9][0-9])
            printf "$(number_to_word $(first_digit $NUMBER))"; 
            printf ' thousand and ';
            printf "$(number_to_word $(strip_leading_zeros $(nth_last_digits $NUMBER 3)))";
            ;;
        
        *)
            printf 'Unsupported number: '"$NUMBER" >&2;
            ;;
    esac;
    printf '\n';
}

strip_space() {
    echo "$*" | tr -cd '[[:alnum:]]';
}

word_length() {
    printf "$1" | wc -c;
}

number_word_length() {
    word_length "$(strip_space $(number_to_word "$1"))";
}

LENGTH=0;
for I in $(seq 1 1000); do
    LENGTH=$(( $LENGTH + $(number_word_length "$I")))
done;
echo "$LENGTH";

Problem018.js

/** The triangle **/
var triangle = '759564174782183587102004824765190123750334880277730763679965042806167092414126568340807033414872334732371694295371446525439152975114701133287773177839681757917152381714914358502729486366046889536730731669874031046298272309709873933853600423'

/**
 * https://projecteuler.net/problem=18
 *  By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
 *     3
 *    7 4
 *   2 4 6
 *  8 5 9 3
 *  That is, 3 + 7 + 4 + 9 = 23.
 *  Find the maximum total from top to bottom of the triangle below:
 *  
 *  @param  {Number}    numberLength        The size of the numbers
 *  @param  {String}    triangle            The triangle
 */
Problem18(2, triangle) === 1074;
function Problem18(numberLength, triangle) {
    
    // Convert the triangle to an array
    triangle = triangle.split('');
    
    // Parse the triangle
    var row = 0;
    triangle = triangle.reduce(function(rows, _, index) {
        
        if (index % numberLength === 0) {
            
            // Get the current number
            var n = parseInt(triangle.slice(index, index + numberLength).join(''), 10);
            
            // Get the current row
            if ((rows[row] || []).length === row + 1) row++;
            rows[row] = rows[row] || [];
            
            // Add the number to the row
            rows[row].push(n);
            
        }
        
        return rows;
        
    }, []);
    
    // Reduce the triangle
    return triangle.reverse().reduce(function(triangle, _, index) {
        
        // Skip the first row
        if (index === 0) return triangle;
        
        // Calculate the row
        var row = (triangle.length - 1) - index;
        
        // Reduce the row
        triangle[row] = triangle[row].map(function(n, i) {
            
            // Add the largest from the row below
            return n + largest(triangle[row + 1][i], triangle[row + 1][i + 1]);
            
        });
        
        return triangle;
        
    }, triangle.reverse())[0][0];
    
}

function largest() {
    return [].reduce.call(arguments, function(largest, n) {
        return n > largest? n : largest;
    }, 0);
}

Problem034.js

/**
 * https://projecteuler.net/problem=34
 *  145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
 *  Find the sum of all numbers which are equal to the sum of the factorial of their digits.
 *  Note: as 1! = 1 and 2! = 2 are not sums they are not included.
 */
Problem34() === 40730;
function Problem34() {
    
    var sum = 0;
    var factorials = nFactorials(9);
    
    for (var n = 3; n < 2540161; n++) {
        
        if (n === n.toString().split('').reduce(function(sum, digit) {
            
            return sum + factorials[digit];
            
        }, 0)) sum += n;
        
    }
    
    return sum;
    
}

/**
 * Get the first {n} factorials
 *  
 *  @param  {Number}    n       The amount of factorials to calculate
 */
function nFactorials(n) {
    
    return Array.apply(null, new Array(n + 1)).reduce(function(factorials, _, i) {
        
        if (i <= 1) {
            factorials.push(1);
        } else {
            factorials.push(i * factorials[i - 1]);
        }
        
        return factorials;
        
    }, []);   
    
}

Problem036.js

/**
 * https://projecteuler.net/problem=36
 *  The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.
 *  Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
 *  (Please note that the palindromic number, in either base, may not include leading zeros.)
 *  
 *  @param  {Number}    max         When to stop counting palindromes
 */
Problem4(999999) === 872187;
function Problem4(max) {
    
    var sum = 0;
    
    for (var n = 0; n < max; n++) {
        
        if (isPalindrome(n.toString()) && isPalindrome(n.toString(2))) sum += n;
        
    }
    
    return sum;
    
}

/**
 * Check if a string is the same in reverse
 *  
 *  @param  {String}    string  String to check for palindrome-ness
 */
function isPalindrome(string) {
    
    // Check the string matches the reverse of itself
    return  string === string.split('').reverse().join('');
    
}