code.kerkeslager.com Git - sandbox/blob - euler/py/euler.py

   1 #!/usr/bin/env python
   2
   3 import itertools
   4 import math
   5 import unittest
   6
   7 def divisible_by(dividend, divisor):
   8     return dividend % divisor == 0
   9
  10 def is_even(n):
  11     return divisible_by(n, 2)
  12
  13 def take_while_less_than(n, xs):
  14     def less_than_n(x):
  15         return x < n
  16     return itertools.takewhile(less_than_n, xs)
  17
  18 def take_while_less_than_or_equal(n, xs):
  19     def less_than_or_equal_to_n(x):
  20         return x <= n
  21
  22     return itertools.takewhile(less_than_or_equal_to_n, xs)
  23
  24 def fibonacci():
  25     previous = 1
  26     current = 1
  27
  28     while True:
  29         yield current
  30         temporary = previous + current
  31         previous = current
  32         current = temporary
  33
  34 def fibonacci_less_than(n):
  35     return take_while_less_than(n, fibonacci())
  36
  37 class FibonacciTestCase(unittest.TestCase):
  38     def test_fibonacci_less_than_ten(self):
  39         expected = [1, 2, 3, 5, 8]
  40         actual = list(fibonacci_less_than(10))
  41         self.assertEqual(expected, actual)
  42
  43 def evens(xs):
  44     return itertools.ifilter(is_even, xs)
  45
  46 class EvensTestCase(unittest.TestCase):
  47     def test_evens(self):
  48         expected = [0, 2, 4, 6, 8]
  49         actual = list(evens(range(10)))
  50         self.assertEqual(expected, actual)
  51
  52 def any(predicate, xs):
  53     for x in xs:
  54         if predicate(x):
  55             return True
  56
  57     return False
  58
  59 def primes():
  60     composites_to_witnesses = {}
  61
  62     for n in itertools.count(2):
  63         if n in composites_to_witnesses:
  64             for witness in composites_to_witnesses[n]:
  65                 composites_to_witnesses.setdefault(n + witness, []).append(witness)
  66         else:
  67             yield n
  68             composites_to_witnesses[n * n] = [n]
  69
  70 def primes_less_than(n):
  71     return take_while_less_than(n, primes())
  72
  73 def n_primes(n):
  74     return itertools.islice(primes(), n)
  75
  76 def factors(n):
  77     remaining = n
  78
  79     for prime in primes():
  80         while divisible_by(remaining, prime):
  81             yield prime
  82             remaining = remaining / prime
  83
  84         if remaining == 1:
  85             break
  86
  87 def product(xs):
  88     result = 1
  89
  90     for x in xs:
  91         result = result * x
  92
  93     return result
  94
  95 class PrimesTestCase(unittest.TestCase):
  96     def test_primes(self):
  97         expected = [2, 3, 5, 7, 11, 13, 17, 19]
  98         actual = list(primes_less_than(20))
  99         self.assertEqual(expected, actual)
 100
 101     def test_factors(self):
 102         expected = [2, 3, 7, 19, 31]
 103         actual = list(factors(product(expected)))
 104         self.assertEqual(expected, actual)
 105
 106 def first(xs, predicate = lambda x : True):
 107     for x in xs:
 108         if predicate(x):
 109             return x
 110
 111 def last(xs):
 112     return list(xs)[-1]
 113
 114 def is_palindromic(n):
 115     n = str(n)
 116     return n[:] == n[::-1]
 117
 118 class PalindromicTestCase(unittest.TestCase):
 119     def test_is_palindromic(self):
 120         self.assertTrue(is_palindromic(505))
 121         self.assertTrue(is_palindromic(2002))
 122         self.assertFalse(is_palindromic(8675309))
 123
 124 def numbers_with_digits(digits, radix = 10):
 125     start = pow(radix, digits - 1)
 126     end = pow(radix, digits)
 127     return range(start, end)
 128
 129 def gcd(a, b):
 130     while b:
 131         a, b = b, a % b
 132     return a
 133
 134 def lcm(a, b):
 135     return a * b / gcd(a, b)
 136
 137 def count_to(n):
 138     return range(1, n + 1)
 139
 140 def square(n):
 141     return n * n
 142
 143 def squares(start = 0):
 144     return itertools.imap(square, itertools.count(start))
 145
 146 def is_perfect_square(n):
 147     root = math.sqrt(n)
 148     return root == int(root)
 149
 150 def pythagorean_triplets():
 151     for square in squares(5):
 152         for i in range(9, square / 2):
 153             if is_perfect_square(i):
 154                 j = square - i
 155                 if is_perfect_square(j):
 156                     yield (int(math.sqrt(i)), int(math.sqrt(j)), int(math.sqrt(square)))
 157
 158 if __name__ == '__main__':
 159     unittest.main()