From 9fbac923132ffca69d796358afc4ff8516f08308 Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Mon, 30 May 2016 16:32:16 -0400 Subject: [PATCH] Merging in 6 year old repo of project euler files --- {project-euler => euler/clj}/20.clj | 0 {project-euler => euler/clj}/21.clj | 0 project-euler/14.py => euler/py/0014.py | 0 euler/py/euler-0001.py | 11 ++ euler/py/euler-0002.py | 7 ++ euler/py/euler-0003.py | 7 ++ euler/py/euler-0004.py | 12 ++ euler/py/euler-0005.py | 7 ++ euler/py/euler-0006.py | 14 +++ euler/py/euler-0007.py | 7 ++ euler/py/euler-0008.py | 14 +++ euler/py/euler-0009.py | 10 ++ euler/py/euler-0010.py | 7 ++ euler/py/euler.py | 159 ++++++++++++++++++++++++ 14 files changed, 255 insertions(+) rename {project-euler => euler/clj}/20.clj (100%) rename {project-euler => euler/clj}/21.clj (100%) rename project-euler/14.py => euler/py/0014.py (100%) create mode 100644 euler/py/euler-0001.py create mode 100644 euler/py/euler-0002.py create mode 100644 euler/py/euler-0003.py create mode 100644 euler/py/euler-0004.py create mode 100644 euler/py/euler-0005.py create mode 100644 euler/py/euler-0006.py create mode 100644 euler/py/euler-0007.py create mode 100644 euler/py/euler-0008.py create mode 100644 euler/py/euler-0009.py create mode 100644 euler/py/euler-0010.py create mode 100644 euler/py/euler.py diff --git a/project-euler/20.clj b/euler/clj/20.clj similarity index 100% rename from project-euler/20.clj rename to euler/clj/20.clj diff --git a/project-euler/21.clj b/euler/clj/21.clj similarity index 100% rename from project-euler/21.clj rename to euler/clj/21.clj diff --git a/project-euler/14.py b/euler/py/0014.py similarity index 100% rename from project-euler/14.py rename to euler/py/0014.py 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() -- 2.20.1