/* Extensions */
/**
 * Find the sum of all the entries in this array
 */
Array.prototype.sum = function() {
	var x = 0;
	for (var i=0; i<this.length; i++) {
		x += this[i];
	}
	return x;
};

function isPrime(x) {
	if (x == 1) {
		return false;
	} else if (x < 4) {
		return true;
	} else if (x % 2 == 0) {
		return false;
	} else if (x < 9) {
		return true;
	} else if (x % 3 == 0) {
		return false;
	} else {
		var r = Math.floor(Math.sqrt(x));
		var f = 5;
		while (f <= r) {
			if (x % f == 0) {
				return false;
			} else if (x % (f+2) == 0) {
				return false;
			}
			f += 6;
		}
		return true;
	}
}

function problem1() {
	/**
	 * 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.
	 **/
	var multiples = [];
	for (var i=3; i<1000; i++) {
		if (i % 3 == 0 || i % 5 == 0) {
			multiples.push(i);
		}
	}
	var sum = multiples.sum();
	
	return new Answer(sum, {
		Multiples: multiples.join(' ')
	});
}

function problem2() {
	/**
	 * 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, ...
     *       
     * Find the sum of all the even-valued terms in the sequence which do
     *   not exceed four million.
	 */
	var hash = {
		1: 1,
		2: 2
	};
	function fibonacci(x) {
		var y = hash[x];
		if (!y) {
			y = hash[x] = (fibonacci(x-1) + fibonacci(x-2));
		}
		return y;
	}
	
	var seq = [];
	
	var i = 1;
	while (true) {
		var v = fibonacci(i++);
		if (v >= 4000000) {
			break;
		} else {
			if (v % 2 == 0) {
				seq.push(v);
			}
		}
	}
	
	var sum = seq.sum();
	
	return new Answer(sum, {
		'Even Fibonacci': seq.join(' ')
	});
}

function problem3() {
	/**
	 * The prime factors of 13195 are 5, 7, 13 and 29.
	 *
	 * What is the largest prime factor of the number 600851475143?
	 */
	function getFactors(n) {
		var factors = [];
		// Keep track of the next number to factorize
		var next = n;
		var toCheck = 2;
		
		while (toCheck <= next) {
			// is a factor
			if (next % toCheck == 0) {
				factors.push(toCheck);
				next = next / toCheck;
			// not a factor, check the next number
			} else {
				toCheck++;
			}
		}
		return factors;
	}
	
	var n = 600851475143;
	var factors = getFactors(n);	
	var largest = factors[factors.length-1] || n;
	
	return new Answer(largest,{
		'Factors': factors.join(' ')
	});
}

function problem4() {
	/**
	 * 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.
	 */
	function isPalindrome(n) {
		n = n + "";
		var rev = n.split('');
		rev.reverse();
		rev = rev.join("");
		return n == rev;
	}
	var palindromes = [];
	
	for (var i=100; i<1000; i++) {
		for (var j=100; j<1000; j++) {
			var n = i*j;
			if (isPalindrome(n)) {
				palindromes.push(n);
			}
		}
	}
	
	var largest = Math.max.apply(null, palindromes);
	return new Answer(largest,{
		'Palindromes': palindromes.join(' ')
	});
}

function problem5() {
	/**
	 * 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 number that is evenly divisible by all of the
	 * numbers from 1 to 20?
	 **/
	
	var n = 1;
	var to = 20;
	
	wLoop:
	while(true) {
		for (var i=to; i>1; i--) {
			if (n % i != 0) {
				n++;
				continue wLoop;
			}
		}
		break;
	}
	return new Answer(n);
}

function problem6() {
	/**
	 * The sum of the squares of the first ten natural numbers is,
	 * 
	 *    1^(2) + 2^(2) + ... + 10^(2) = 385
	 *    
	 * The square of the sum of the first ten natural numbers is,
	 * 
	 *    (1 + 2 + ... + 10)^(2) = 55^(2) = 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.
	 *
	 **/
	
	function sumOfSquares(j) {
		var sum = 0;
		for (var i=1; i<=j; i++) {
			sum += (i*i);
		}
		return sum;
	}
	
	function squareOfSums(j) {
		var sum = 0;
		for (var i=1; i<=j; i++) {
			sum += i;
		}
		return sum * sum;
	}
	
	function diff(j) {
		return squareOfSums(j) - sumOfSquares(j);
	}
	
	return new Answer(diff(100), {});
}

function problem7() {
	var limit = 10001;
	var cnt = 1;
	var candidate = 1;
	
	do {
		candidate += 2;
		if (isPrime(candidate)) {
			cnt++;
		}
	} while(cnt < limit);
	
	return new Answer(candidate);
}

function problem8() {
	/**
	 * Find the greatest product of five consecutive digits in the 1000-digit number.
	 */
	var data = [
		"73167176531330624919225119674426574742355349194934",
		"96983520312774506326239578318016984801869478851843",
		"85861560789112949495459501737958331952853208805511",
		"12540698747158523863050715693290963295227443043557",
		"66896648950445244523161731856403098711121722383113",
		"62229893423380308135336276614282806444486645238749",
		"30358907296290491560440772390713810515859307960866",
		"70172427121883998797908792274921901699720888093776",
		"65727333001053367881220235421809751254540594752243",
		"52584907711670556013604839586446706324415722155397",
		"53697817977846174064955149290862569321978468622482",
		"83972241375657056057490261407972968652414535100474",
		"82166370484403199890008895243450658541227588666881",
		"16427171479924442928230863465674813919123162824586",
		"17866458359124566529476545682848912883142607690042",
		"24219022671055626321111109370544217506941658960408",
		"07198403850962455444362981230987879927244284909188",
		"84580156166097919133875499200524063689912560717606",
		"05886116467109405077541002256983155200055935729725",
		"71636269561882670428252483600823257530420752963450"
	].join("");
	
	var largest = 0;
	var largestPos;
	for (var i=0; i<data.length-5; i++) {
		var x = 1;
		for (var j=i; j<i+5; j++) {
			x *= parseInt(data.charAt(j));
		}
		x = Math.max(largest, x);
		if (x != largest) {
			largest = x;
			largestPos = i;
		}
	}
	
	return new Answer(largest, {
		Position: largestPos
	});
}

function problem9() {
	/**
	 * A Pythagorean triplet is a set of three natural numbers,
	 * a < b < c, for which,
	 *
	 *    a^(2) + b^(2) = c^(2)
	 *
	 * For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).
	 *
	 * There exists exactly one Pythagorean triplet for which a + b + c = 1000.
	 *
	 * Find the product abc.
	 **/
	
	function findTripleSum(a,b) {
		var c = Math.sqrt(a*a + b*b);
		if (b < c) {
			return a + b + c;
		} else {
			return NaN;
		}
	}
	
	function findTripleProduct(a,b) {
		var c = Math.sqrt(a*a + b*b);
		if (b < c) {
			return a * b * c;
		} else {
			return NaN;
		}
	}
	
	var a = 1;
	var b = 2;
	var x;
		
	while (true) {
		x = findTripleSum(a,b);
		if (x == 1000) {
			break;
		} else if (x > 1000) {
			a++;
			b = a+1;
		} else {
			b++;
		}
	}
	
	return new Answer(findTripleProduct(a,b), {
		a: a,
		b: b
	});
}

function problem10() {
	/**
	 * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
	 * Find the sum of all the primes below two million.
	 **/
	var sum = 0;
	for (var i=2; i<2000000; i++) {
		if (isPrime(i)) {
			sum += i;
		}
	}
	return new Answer(sum);
}

function problem11() {
	/**
	 * 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 any
	 * direction (up, down, left, right, or diagonally) in the 20×20 grid?
	 **/
	var data = [
		"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08",
		"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00",
		"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65",
		"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91",
		"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80",
		"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50",
		"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70",
		"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21",
		"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72",
		"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95",
		"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92",
		"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57",
		"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58",
		"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40",
		"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66",
		"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69",
		"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36",
		"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16",
		"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54",
		"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"
	];
	for (var i=0; i<data.length; i++) {
		data[i] = data[i].split(' ');
		for (var j=0; j<data[i].length; j++) {
			data[i][j] = parseInt(data[i][j], 10);
		}
	}
	
	var max = 0;
	var positions = [];
	// Up
	// Down
	for (var i=0; i<data.length-4; i++) {
		for (var j=0; j<data[i].length; j++) {
			var p = 1;
			for (var k=i; k<i+4; k++) {
				p *= data[k][j];
			}
			if (p > max) {
				max = p;
				positions = [[i,j],[i+1,j],[i+2,j],[i+3,j]];
			}
		}
	}
	// Left
	// Right
	for (var i=0; i<data.length; i++) {
		for (var j=0; j<data[i].length-4; j++) {
			var p = 1;
			for (var k=j; k<j+4; k++) {
				p *= data[i][k];
			}
			if (p > max) {
				max = p;
				positions = [[i,j],[i,j+1],[i,j+2],[i,j+3]];
			}
		}
	}
	
	// Diagonal-down
	for (var i=0; i<data.length-4; i++) {
		for (var j=0; j<data[i].length-4; j++) {
			var p = 1;
			for (var k=0; k<4; k++) {
				p *= data[i+k][j+k];	
			}
			if (p > max) {
				max = p;
				positions = [[i,j],[i+1,j+1],[i+2,j+2],[i+3,j+3]];
			}
		}
	}
	// Diagonal-up
	for (var i=3; i<data.length; i++) {
		for (var j=0; j<data[i].length-4; j++) {
			var p = 1;
			for (var k=0; k<4; k++) {
				p *= data[i-k][j+k];
			}
			if (p > max) {
				max = p;
				positions = [[i,j],[i-1,j+1],[i-2,j+2],[i-3,j+3]];
			}
		}
	}
	
	var tbl = ['<table>'];
	
	for (var i=0; i<data.length; i++) {
		tbl.push('<tr>');
		for (var j=0; j<data[i].length; j++) {
			var found = false;
			for (var k=0; k<positions.length; k++) {
				if (positions[k][0] == i && positions[k][1] == j) {
					found =true;
				}
			}
			
			tbl.push('<td style="text-align: center; ',(found ? 'background: #CCC;' : ""),'">', data[i][j], '</td>');
		}
		tbl.push('</tr>');
	}
	
	tbl.push('</table>');
	
	return new Answer(max, {
		Table: tbl.join('')
	});
}