From: David Kerkeslager Date: Mon, 30 May 2016 20:32:16 +0000 (-0400) Subject: Merging in 6 year old repo of project euler files X-Git-Url: https://code.kerkeslager.com/?p=sandbox;a=commitdiff_plain;h=9fbac923132ffca69d796358afc4ff8516f08308;hp=249411c080477350129b388cb544c1476c844f96 Merging in 6 year old repo of project euler files --- diff --git a/euler/clj/20.clj b/euler/clj/20.clj new file mode 100644 index 0000000..5501ee5 --- /dev/null +++ b/euler/clj/20.clj @@ -0,0 +1,12 @@ +(defn factorial [n] + (if (= n 1) + 1 + (* n (factorial (- n 1))))) + +(defn sum-digits [radix n] + (if (= n 0) + 0 + (+ (rem n radix) (sum-digits radix (quot n radix))))) + + +(println (sum-digits 10 (factorial 100))) diff --git a/euler/clj/21.clj b/euler/clj/21.clj new file mode 100644 index 0000000..aa337b8 --- /dev/null +++ b/euler/clj/21.clj @@ -0,0 +1,16 @@ +(defn factors [n] + (filter #(zero? (mod n %)) + (take (- n 1) (iterate inc 1)))) + +(defn d [n] + (reduce + (factors n))) + +(defn amicable? [a b] + (and + (= a (d b)) + (= (d a) b))) + +(defn list-length [a] + (if (= (first a) nil) + 0 + (+ 1 (list-length (rest a))))) diff --git a/euler/py/0014.py b/euler/py/0014.py new file mode 100644 index 0000000..75f3baf --- /dev/null +++ b/euler/py/0014.py @@ -0,0 +1,52 @@ +"""This code is the result of my attempt to solve Project Euler problem 14. It +takes a positive integer from the command line and finds the positive integer +less than the given integer which starts the longest hailstone sequence. For +more information on hailstone sequences, see +http://en.wikipedia.org/wiki/Collatz_conjecture . + +While solving this problem I came across a novel usage of a few different +advanced Python features for a very generalizeable and reusable way to implement +memoization. For more information on memoization, see +http://en.wikipedia.org/wiki/Memoization .""" + +class Memoize: + def __init__(self,function): + self.function = function + self.memo = {} + + def __call__(self,*arguments): + if arguments in self.memo: + return self.memo[arguments] + + result = self.function(*arguments) + self.memo[arguments] = result + return result + +@Memoize +def hailstone(start): + if start == 1: + return 1 + + if start % 2 == 0: + return hailstone(start / 2) + 1 + + return hailstone(start * 3 + 1) + 1 + +if __name__ == '__main__': + import sys + + # Needed in order to calculate the hailstone number of large numbers. + sys.setrecursionlimit(1000000) + + limit = int(sys.argv[1]) + max = 1 + max_start = 1 + + for i in xrange(1,limit): + chain = hailstone(i) + + if chain > max: + max = chain + max_start = i + + print max_start diff --git a/euler/py/euler-0001.py b/euler/py/euler-0001.py new file mode 100644 index 0000000..2506526 --- /dev/null +++ b/euler/py/euler-0001.py @@ -0,0 +1,11 @@ +#!/usr/bin/env python + +from euler import * + +def divisible_by_three_or_five(dividend): + return divisible_by(dividend, 3) or divisible_by(dividend, 5) + +result = sum([n for n in range(1000) if divisible_by_three_or_five(n)]) + +print result + diff --git a/euler/py/euler-0002.py b/euler/py/euler-0002.py new file mode 100644 index 0000000..dcd877c --- /dev/null +++ b/euler/py/euler-0002.py @@ -0,0 +1,7 @@ +#!/usr/bin/env python + +from euler import * + +result = sum(evens(fibonacci_less_than(4000000))) + +print result diff --git a/euler/py/euler-0003.py b/euler/py/euler-0003.py new file mode 100644 index 0000000..f652e02 --- /dev/null +++ b/euler/py/euler-0003.py @@ -0,0 +1,7 @@ +#!/usr/bin/env python + +from euler import * + +result = last(factors(600851475143)) + +print result diff --git a/euler/py/euler-0004.py b/euler/py/euler-0004.py new file mode 100644 index 0000000..7942f46 --- /dev/null +++ b/euler/py/euler-0004.py @@ -0,0 +1,12 @@ +#!/usr/bin/env python + +from euler import * +import itertools + +def products_of_three_digit_numbers(): + three_digit_pairs = itertools.combinations(numbers_with_digits(3),2) + return itertools.imap(product, three_digit_pairs) + +result = max(itertools.ifilter(is_palindromic, products_of_three_digit_numbers())) + +print result diff --git a/euler/py/euler-0005.py b/euler/py/euler-0005.py new file mode 100644 index 0000000..fa55cad --- /dev/null +++ b/euler/py/euler-0005.py @@ -0,0 +1,7 @@ +#!/usr/bin/env python + +from euler import * + +result = reduce(lcm, count_to(20)) + +print result diff --git a/euler/py/euler-0006.py b/euler/py/euler-0006.py new file mode 100644 index 0000000..0fdc286 --- /dev/null +++ b/euler/py/euler-0006.py @@ -0,0 +1,14 @@ +#!/usr/bin/env python + +from euler import * + +def sum_of_squares(n): + return sum(itertools.imap(square, count_to(n))) + +def square_of_sum(n): + return square(sum(count_to(n))) + +result = square_of_sum(100) - sum_of_squares(100) + +print result + diff --git a/euler/py/euler-0007.py b/euler/py/euler-0007.py new file mode 100644 index 0000000..10fe9ea --- /dev/null +++ b/euler/py/euler-0007.py @@ -0,0 +1,7 @@ +#!/usr/bin/env python + +from euler import * + +result = last(n_primes(10001)) + +print result diff --git a/euler/py/euler-0008.py b/euler/py/euler-0008.py new file mode 100644 index 0000000..b17706f --- /dev/null +++ b/euler/py/euler-0008.py @@ -0,0 +1,14 @@ +#!/usr/bin/env python + +from euler import * + +number = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450 +number = str(number) + +number_as_groups_of_five_digits = [number[i:i + 5] for i in range(len(number) - 5)] + +products = [product([int(d) for d in group]) for group in number_as_groups_of_five_digits] + +result = max(products) + +print result diff --git a/euler/py/euler-0009.py b/euler/py/euler-0009.py new file mode 100644 index 0000000..b213cb5 --- /dev/null +++ b/euler/py/euler-0009.py @@ -0,0 +1,10 @@ +#!/usr/bin/env python + +from euler import * + +def sum_is_one_thousand(xs): + return sum(xs) == 1000 + +result = product(first(pythagorean_triplets(), sum_is_one_thousand)) + +print result diff --git a/euler/py/euler-0010.py b/euler/py/euler-0010.py new file mode 100644 index 0000000..cc224ed --- /dev/null +++ b/euler/py/euler-0010.py @@ -0,0 +1,7 @@ +#!/usr/bin/env python + +from euler import * + +result = sum(primes_less_than(2000000)) + +print result diff --git a/euler/py/euler.py b/euler/py/euler.py new file mode 100644 index 0000000..719a2c2 --- /dev/null +++ b/euler/py/euler.py @@ -0,0 +1,159 @@ +#!/usr/bin/env python + +import itertools +import math +import unittest + +def divisible_by(dividend, divisor): + return dividend % divisor == 0 + +def is_even(n): + return divisible_by(n, 2) + +def take_while_less_than(n, xs): + def less_than_n(x): + return x < n + return itertools.takewhile(less_than_n, xs) + +def take_while_less_than_or_equal(n, xs): + def less_than_or_equal_to_n(x): + return x <= n + + return itertools.takewhile(less_than_or_equal_to_n, xs) + +def fibonacci(): + previous = 1 + current = 1 + + while True: + yield current + temporary = previous + current + previous = current + current = temporary + +def fibonacci_less_than(n): + return take_while_less_than(n, fibonacci()) + +class FibonacciTestCase(unittest.TestCase): + def test_fibonacci_less_than_ten(self): + expected = [1, 2, 3, 5, 8] + actual = list(fibonacci_less_than(10)) + self.assertEqual(expected, actual) + +def evens(xs): + return itertools.ifilter(is_even, xs) + +class EvensTestCase(unittest.TestCase): + def test_evens(self): + expected = [0, 2, 4, 6, 8] + actual = list(evens(range(10))) + self.assertEqual(expected, actual) + +def any(predicate, xs): + for x in xs: + if predicate(x): + return True + + return False + +def primes(): + composites_to_witnesses = {} + + for n in itertools.count(2): + if n in composites_to_witnesses: + for witness in composites_to_witnesses[n]: + composites_to_witnesses.setdefault(n + witness, []).append(witness) + else: + yield n + composites_to_witnesses[n * n] = [n] + +def primes_less_than(n): + return take_while_less_than(n, primes()) + +def n_primes(n): + return itertools.islice(primes(), n) + +def factors(n): + remaining = n + + for prime in primes(): + while divisible_by(remaining, prime): + yield prime + remaining = remaining / prime + + if remaining == 1: + break + +def product(xs): + result = 1 + + for x in xs: + result = result * x + + return result + +class PrimesTestCase(unittest.TestCase): + def test_primes(self): + expected = [2, 3, 5, 7, 11, 13, 17, 19] + actual = list(primes_less_than(20)) + self.assertEqual(expected, actual) + + def test_factors(self): + expected = [2, 3, 7, 19, 31] + actual = list(factors(product(expected))) + self.assertEqual(expected, actual) + +def first(xs, predicate = lambda x : True): + for x in xs: + if predicate(x): + return x + +def last(xs): + return list(xs)[-1] + +def is_palindromic(n): + n = str(n) + return n[:] == n[::-1] + +class PalindromicTestCase(unittest.TestCase): + def test_is_palindromic(self): + self.assertTrue(is_palindromic(505)) + self.assertTrue(is_palindromic(2002)) + self.assertFalse(is_palindromic(8675309)) + +def numbers_with_digits(digits, radix = 10): + start = pow(radix, digits - 1) + end = pow(radix, digits) + return range(start, end) + +def gcd(a, b): + while b: + a, b = b, a % b + return a + +def lcm(a, b): + return a * b / gcd(a, b) + +def count_to(n): + return range(1, n + 1) + +def square(n): + return n * n + +def squares(start = 0): + return itertools.imap(square, itertools.count(start)) + +def is_perfect_square(n): + root = math.sqrt(n) + return root == int(root) + +def pythagorean_triplets(): + for square in squares(5): + for i in range(9, square / 2): + if is_perfect_square(i): + j = square - i + if is_perfect_square(j): + yield (int(math.sqrt(i)), int(math.sqrt(j)), int(math.sqrt(square))) + +if __name__ == '__main__': + unittest.main() diff --git a/project-euler/14.py b/project-euler/14.py deleted file mode 100644 index 75f3baf..0000000 --- a/project-euler/14.py +++ /dev/null @@ -1,52 +0,0 @@ -"""This code is the result of my attempt to solve Project Euler problem 14. It -takes a positive integer from the command line and finds the positive integer -less than the given integer which starts the longest hailstone sequence. For -more information on hailstone sequences, see -http://en.wikipedia.org/wiki/Collatz_conjecture . - -While solving this problem I came across a novel usage of a few different -advanced Python features for a very generalizeable and reusable way to implement -memoization. For more information on memoization, see -http://en.wikipedia.org/wiki/Memoization .""" - -class Memoize: - def __init__(self,function): - self.function = function - self.memo = {} - - def __call__(self,*arguments): - if arguments in self.memo: - return self.memo[arguments] - - result = self.function(*arguments) - self.memo[arguments] = result - return result - -@Memoize -def hailstone(start): - if start == 1: - return 1 - - if start % 2 == 0: - return hailstone(start / 2) + 1 - - return hailstone(start * 3 + 1) + 1 - -if __name__ == '__main__': - import sys - - # Needed in order to calculate the hailstone number of large numbers. - sys.setrecursionlimit(1000000) - - limit = int(sys.argv[1]) - max = 1 - max_start = 1 - - for i in xrange(1,limit): - chain = hailstone(i) - - if chain > max: - max = chain - max_start = i - - print max_start diff --git a/project-euler/20.clj b/project-euler/20.clj deleted file mode 100644 index 5501ee5..0000000 --- a/project-euler/20.clj +++ /dev/null @@ -1,12 +0,0 @@ -(defn factorial [n] - (if (= n 1) - 1 - (* n (factorial (- n 1))))) - -(defn sum-digits [radix n] - (if (= n 0) - 0 - (+ (rem n radix) (sum-digits radix (quot n radix))))) - - -(println (sum-digits 10 (factorial 100))) diff --git a/project-euler/21.clj b/project-euler/21.clj deleted file mode 100644 index aa337b8..0000000 --- a/project-euler/21.clj +++ /dev/null @@ -1,16 +0,0 @@ -(defn factors [n] - (filter #(zero? (mod n %)) - (take (- n 1) (iterate inc 1)))) - -(defn d [n] - (reduce + (factors n))) - -(defn amicable? [a b] - (and - (= a (d b)) - (= (d a) b))) - -(defn list-length [a] - (if (= (first a) nil) - 0 - (+ 1 (list-length (rest a)))))