Skip to content

Instantly share code, notes, and snippets.

@Syrup-tan

Syrup-tan/0_ProjectEuler.md

Last active September 30, 2016 08:52
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Syrup-tan/4e5c9c097fe4a4578e6c to your computer and use it in GitHub Desktop.
Save Syrup-tan/4e5c9c097fe4a4578e6c to your computer and use it in GitHub Desktop.
Download ZIP
Project Euler
Raw
0_ProjectEuler.md

Project Euler

My attempt at weekly project euler solution

Raw
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;
}
Raw
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;
}
}
Raw
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('');
}
Raw
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;
}
Raw
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;
}
Raw
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);
}
Raw
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);
}
Raw
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]
Raw
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;
}
}
Raw
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)
}
Raw
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";
Raw
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);
}
Raw
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;
}, []);
}
Raw
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('');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment