Repository: keon/algorithms
Pull request #220 (2018-04-12 20:31:47)

Test maths
* I added a file ```test_maths.py``` which tests the files in this module. 
* Small changes on certain files.  
* I fixed a bug in the file ```rsa.py```. Decryption has always failed and returns 1. Now it works.  
* I fixed bugs in other files, too.  


Patch:
diff --git a/README.md b/README.md
index 96fded2..8097c4d 100644
--- a/README.md
+++ b/README.md
@@ -1,6 +1,7 @@
 English | [简体中文](https://github.com/yunshuipiao/algorithms/blob/master/README_CN.md)
 
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
+[![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
 
 Pythonic Data Structures and Algorithms
 =========================================
diff --git a/maths/extended_gcd.py b/maths/extended_gcd.py
index 69ecfa3..96c31ac 100644
--- a/maths/extended_gcd.py
+++ b/maths/extended_gcd.py
@@ -17,4 +17,4 @@ def extended_gcd(a,b):
         old_s, s = s, old_s - quotient * s
         old_t, t = t, old_t - quotient * t
     
-    return old_s, old_t, old_r
\ No newline at end of file
+    return old_s, old_t, old_r
diff --git a/maths/gcd.py b/maths/gcd.py
index 9792d8f..1f80fc9 100644
--- a/maths/gcd.py
+++ b/maths/gcd.py
@@ -2,10 +2,9 @@ def gcd(a, b):
     """Computes the greatest common divisor of integers a and b using
     Euclid's Algorithm.
     """
-    while True:
-        if b == 0:
-            return a
+    while b != 0:
         a, b = b, a % b
+    return a
 
 
 def lcm(a, b):
diff --git a/maths/generate_strobogrammtic.py b/maths/generate_strobogrammtic.py
index f5589ac..2311dcf 100644
--- a/maths/generate_strobogrammtic.py
+++ b/maths/generate_strobogrammtic.py
@@ -14,8 +14,7 @@ def gen_strobogrammatic(n):
     :type n: int
     :rtype: List[str]
     """
-    result = helper(n, n)
-    return result
+    return helper(n, n)
 
 
 def helper(n, length):
@@ -43,19 +42,21 @@ def strobogrammaticInRange(low, high):
     """
     res = []
     count = 0
-    for i in range(len(low), len(high)+1):
+    low_len = len(low)
+    high_len = len(high)
+    for i in range(low_len, high_len + 1):
         res.extend(helper2(i, i))
     for perm in res:
-        if len(perm) == len(low) and int(perm) < int(low):
+        if len(perm) == low_len and int(perm) < int(low):
             continue
-        elif len(perm) == len(high) and int(perm) > int(high):
+        elif len(perm) == high_len and int(perm) > int(high):
             continue
         else:
             count += 1
     return count
 
 
-def helper2(self, n, length):
+def helper2(n, length):
     if n == 0:
         return [""]
     if n == 1:
diff --git a/maths/next_perfect_square.py b/maths/next_perfect_square.py
index dc52ddc..7e6e6b9 100644
--- a/maths/next_perfect_square.py
+++ b/maths/next_perfect_square.py
@@ -13,6 +13,7 @@ def find_next_square(sq):
     
 # Another way:
 
-def find_next_square(sq):
+def find_next_square2(sq):
     x = sq**0.5    
     return -1 if x % 1 else (x+1)**2
+
diff --git a/maths/primes_sieve_of_eratosthenes.py b/maths/primes_sieve_of_eratosthenes.py
index 34289da..1677b25 100644
--- a/maths/primes_sieve_of_eratosthenes.py
+++ b/maths/primes_sieve_of_eratosthenes.py
@@ -31,7 +31,7 @@ def primes(x):
     primes = []                              # List of Primes
     if x >= 2:
         primes.append(2)                     # Add 2 by default
-    for i in range(0, sieve_size):
+    for i in range(sieve_size):
         if sieve[i] == 1:
             value_at_i = i*2 + 3
             primes.append(value_at_i)
diff --git a/maths/pythagoras.py b/maths/pythagoras.py
index 8effe13..d896260 100644
--- a/maths/pythagoras.py
+++ b/maths/pythagoras.py
@@ -13,4 +13,4 @@ def pythagoras(opposite,adjacent,hypotenuse):
         else:
             return "You already know the answer!"
     except:
-        print ("Error, check your input. You must know 2 of the 3 variables.")
+        raise ValueError("invalid argument were given.")
diff --git a/maths/rabin_miller.py b/maths/rabin_miller.py
index b06db5c..c8e2921 100644
--- a/maths/rabin_miller.py
+++ b/maths/rabin_miller.py
@@ -8,6 +8,12 @@ def pow2_factor(n):
         power += 1
     return power, n
 
+def pow_3(a, b, c):
+    """ 
+        helper function for a, b and c integers. 
+    """
+    return a**b % c
+
 """
 Rabin-Miller primality test
 returning False implies that n is guarenteed composite
@@ -15,6 +21,9 @@ returning True means that n is probably prime
 with a 4 ** -k chance of being wrong
 """
 def is_prime(n, k):
+    #precondition
+    assert n >= 5, "the to tested number must been >= 5"
+
     r, d = pow2_factor(n - 1)
     
     """
@@ -23,13 +32,13 @@ def is_prime(n, k):
     an invalid witness guarentees n is composite
     """
     def valid_witness(a):
-        x = pow(a, d, n)
+        x = pow(int(a), int(d), int(n))
         
         if x == 1 or x == n - 1:
             return False
         
         for _ in range(r - 1):
-            x = pow(x, 2, n)
+            x = pow(int(x), int(2), int(n))
             
             if x == 1:
                 return True
diff --git a/maths/rsa.py b/maths/rsa.py
index f3b0f68..5ec1ccc 100644
--- a/maths/rsa.py
+++ b/maths/rsa.py
@@ -30,18 +30,22 @@ from extended_gcd import * # extended_gcd
 generate a prime with k bits
 """
 def genprime(k):
+    random.seed()
     while True:
-        n = random.randrange(2 ** (k - 1),2 ** k)
+        n = random.randrange(int(2 ** (k - 1)),int(2 ** k))
         if is_prime(n,128):
             return n
 
+
 """
 calculate the inverse of a mod m
 that is, find b such that (a * b) % m == 1
 """
 def modinv(a, m):
-        x, y, g = extended_gcd(a,m)
-        return x % m
+        b = 1
+        while ((a*b) % m != 1):
+            b += 1
+        return b
 
 """
 the RSA key generating algorithm
@@ -68,13 +72,20 @@ def generate_key(k):
     l = (p - 1) * (q - 1) # calculate totient function
     d = modinv(e,l)
     
-    return n, e, d
+    return int(n), int(e), int(d)
+
+def encrypt(data, e, n):
+    return pow(int(data), int(e), int(n))
+
+def decrypt(data, d, n):
+    return pow(int(data), int(d), int(n))
+
+
+
+#sample usage:
+# n,e,d = generate_key(16)
+# data = 20
+# encrypted = pow(data,e,n)
+# decrypted = pow(encrypted,d,n)
+# assert decrypted == data
 
-"""
-sample usage:
-n,e,d = generate_key(1024)
-data = 1337
-encrypted = pow(data,e,n)
-decrypted = pow(encrypted,d,n)
-assert decrypted == data
-"""
diff --git a/matrix/sudoku_validator.py b/matrix/sudoku_validator.py
index b3a6adf..ad2faeb 100644
--- a/matrix/sudoku_validator.py
+++ b/matrix/sudoku_validator.py
@@ -33,7 +33,7 @@ def valid_solution_hashtable(board):
                 for l in range(3):
                     grid_add += board[i*3+k][j*3+l]
             if grid_add != 45:
-                return False    
+                return False
     return True
 
 
@@ -44,22 +44,22 @@ def valid_solution(board):
     for row in board:
         if sorted(row) != correct:
             return False
-    
+
     # check columns
     for column in zip(*board):
         if sorted(column) != correct:
             return False
-    
+
     # check regions
     for i in range(3):
         for j in range(3):
             region = []
             for line in board[i*3:(i+1)*3]:
                 region += line[j*3:(j+1)*3]
-            
+
             if sorted(region) != correct:
                 return False
-    
+
     # if everything correct
     return True
 
@@ -67,20 +67,20 @@ def valid_solution(board):
 # Using set
 def valid_solution_set (board):
     valid = set(range(1, 10))
-    
+
     for row in board:
-        if set(row) != valid: 
+        if set(row) != valid:
             return False
-    
+
     for col in [[row[i] for row in board] for i in range(9)]:
-        if set(col) != valid: 
+        if set(col) != valid:
             return False
-    
+
     for x in range(3):
         for y in range(3):
             if set(sum([row[x*3:(x+1)*3] for row in board[y*3:(y+1)*3]], [])) != valid:
                 return False
-    
+
     return True
 
 # test cases
@@ -88,7 +88,7 @@ def valid_solution_set (board):
 import unittest
 class TestSuite(unittest.TestCase):
     def test_valid(self):
-        self.assertTrue(valid_solution([[5, 3, 4, 6, 7, 8, 9, 1, 2], 
+        self.assertTrue(valid_solution([[5, 3, 4, 6, 7, 8, 9, 1, 2],
                          [6, 7, 2, 1, 9, 5, 3, 4, 8],
                          [1, 9, 8, 3, 4, 2, 5, 6, 7],
                          [8, 5, 9, 7, 6, 1, 4, 2, 3],
@@ -96,10 +96,10 @@ class TestSuite(unittest.TestCase):
                          [7, 1, 3, 9, 2, 4, 8, 5, 6],
                          [9, 6, 1, 5, 3, 7, 2, 8, 4],
                          [2, 8, 7, 4, 1, 9, 6, 3, 5],
-                         [3, 4, 5, 2, 8, 6, 1, 7, 9]])
-        
+                         [3, 4, 5, 2, 8, 6, 1, 7, 9]]))
+
     def test_invalid(self):
-        self.assertFalse(valid_solution([[5, 3, 4, 6, 7, 8, 9, 1, 2], 
+        self.assertFalse(valid_solution([[5, 3, 4, 6, 7, 8, 9, 1, 2],
                          [6, 7, 2, 1, 9, 0, 3, 4, 9],
                          [1, 0, 0, 3, 4, 2, 5, 6, 0],
                          [8, 5, 9, 7, 6, 1, 0, 2, 0],
@@ -107,7 +107,7 @@ class TestSuite(unittest.TestCase):
                          [7, 1, 3, 9, 2, 4, 8, 5, 6],
                          [9, 0, 1, 5, 3, 7, 2, 1, 4],
                          [2, 8, 7, 4, 1, 9, 6, 3, 5],
-                         [3, 0, 0, 4, 8, 1, 1, 7, 9]])
-                             
+                         [3, 0, 0, 4, 8, 1, 1, 7, 9]]))
+
 if __name__ == "__main__":
     unittest.main()
diff --git a/search/first_occurance.py b/search/first_occurance.py
index 63d77b8..f4d8c75 100644
--- a/search/first_occurance.py
+++ b/search/first_occurance.py
@@ -4,42 +4,37 @@
 # T(n)- O(log n)
 #
 
+import unittest
 
 def firstOccurance(array, query):
     lo, hi = 0, len(array) - 1
     while lo <= hi:
-        mid = (hi + lo) // 2
-        print("lo: ", lo, " hi: ", hi, " mid: ", mid)
-        if (mid == 0 and array[mid] == query) or \
-           (array[mid] == query and array[mid-1] < query):
-            return mid
-        elif array[mid] <= query:
+        mid = (lo + hi) // 2
+        #print("lo: ", lo, " hi: ", hi, " mid: ", mid)
+        if lo == hi:
+            break
+        if array[mid] < query:
             lo = mid + 1
         else:
-            hi = mid - 1
+            hi = mid
+    if array[lo] == query:
+      return lo
 
+class TestSuite(unittest.TestCase):
 
-def main():
-    array = [1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6]
-    print(array)
-    print("-----SEARCH-----")
-    query = 3
-    print("found first: ", query, " in index:", firstOccurance(array, query))
-    print("-----SEARCH-----")
-    query = 5
-    print("found first: ", query, " in index:", firstOccurance(array, query))
-    print("-----SEARCH-----")
-    query = 7
-    print("found first: ", query, " in index:", firstOccurance(array, query))
-    print("-----SEARCH-----")
-    query = 1
-    print("found first: ", query, " in index:", firstOccurance(array, query))
-    print("-----SEARCH-----")
-    query = -1
-    print("found first: ", query, " in index:", firstOccurance(array, query))
-    print("-----SEARCH-----")
-    query = 9
-    print("found first: ", query, " in index:", firstOccurance(array, query))
+    def test_firstOccurance(self):
+        def helper(array, query):
+            idx = array.index(query) if query in array else None
+            return idx
+        array = [1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6]
+        self.assertEqual(firstOccurance(array, 1), helper(array, 1))
+        self.assertEqual(firstOccurance(array, 3), helper(array, 3))
+        self.assertEqual(firstOccurance(array, 5), helper(array, 5))
+        self.assertEqual(firstOccurance(array, 6), helper(array, 6))
+        self.assertEqual(firstOccurance(array, 7), helper(array, 7))
+        self.assertEqual(firstOccurance(array, -1), helper(array, -1))
 
-if __name__ == "__main__":
-    main()
+
+if __name__ == '__main__':
+
+    unittest.main()


Test patch:
diff --git a/maths/prime_test.py b/maths/prime_test.py
index 05a069f..ba67071 100644
--- a/maths/prime_test.py
+++ b/maths/prime_test.py
@@ -1,7 +1,6 @@
 """
 prime_test(n) returns a True if n is a prime number else it returns False
 """
-import unittest
 
 def prime_test(n):
     if n <= 1:
@@ -34,30 +33,4 @@ def prime_test2(n):
     # if input number is less than
     # or equal to 1, it is not prime
     else:
-        return False
-
-
-class TestSuite (unittest.TestCase):
-    def test_prime_test(self):
-        """
-            checks all prime numbers between 2 up to 100.
-            Between 2 up to 100 exists 25 prime numbers!
-        """
-        counter = 0
-        for i in range(2,101):
-            if prime_test(i):
-                counter += 1
-        self.assertEqual(25,counter)
-    def test_prime_test2(self):
-        """
-            checks all prime numbers between 2 up to 100.
-            Between 2 up to 100 exists 25 prime numbers!
-        """
-        counter = 0
-        for i in range(2,101):
-            if prime_test(i):
-                counter += 1
-        self.assertEqual(25,counter)
-        
-if __name__ == "__main__":
-    unittest.main()
\ No newline at end of file
+        return False
\ No newline at end of file
diff --git a/maths/test_maths.py b/maths/test_maths.py
new file mode 100644
index 0000000..ff6cda0
--- /dev/null
+++ b/maths/test_maths.py
@@ -0,0 +1,193 @@
+from base_conversion import int2base,base2int
+from extended_gcd import extended_gcd
+from gcd import gcd,lcm
+from generate_strobogrammtic import gen_strobogrammatic,strobogrammaticInRange
+from is_strobogrammatic import is_strobogrammatic,is_strobogrammatic2
+from next_perfect_square import find_next_square,find_next_square2
+from primes_sieve_of_eratosthenes import primes
+from prime_test import prime_test, prime_test2
+from pythagoras import pythagoras
+from rabin_miller import is_prime 
+from rsa import encrypt, decrypt, generate_key
+
+import unittest
+
+
+class TestBaseConversion(unittest.TestCase):
+    """
+    Test for the file base_conversion.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_int2base(self):
+        self.assertEqual("101",int2base(5,2))
+        self.assertEqual("0",int2base(0,2))
+        self.assertEqual("FF",int2base(255,16))
+    def test_base2int(self):
+        self.assertEqual(5,base2int("101",2))
+        self.assertEqual(0,base2int("0",2))
+        self.assertEqual(255,base2int("FF",16))
+
+
+class TestExtendedGcd(unittest.TestCase):
+    """[summary]
+    Test for the file extended_gcd.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_extended_gcd(self):
+        self.assertEqual((0,1,2),extended_gcd(8,2))
+        self.assertEqual((0,1,17),extended_gcd(13,17))
+
+
+class TestGcd(unittest.TestCase):
+    """[summary]
+    Test for the file gcd.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_gcd(self):
+        self.assertEqual(4,gcd(8,12))
+        self.assertEqual(1,gcd(13,17))
+    def test_lcm(self):
+        self.assertEqual(24,lcm(8,12))
+
+
+class TestGenerateStroboGrammatic(unittest.TestCase):
+    """[summary]
+    Test for the file generate_strobogrammatic.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_gen_strobomatic(self):
+        self.assertEqual(['88', '11', '96', '69'],gen_strobogrammatic(2))
+    def test_strobogrammaticInRange(self):
+        self.assertEqual(4,strobogrammaticInRange("10","100"))
+
+
+class TestIsStrobogrammatic(unittest.TestCase):
+    """[summary]
+    Test for the file is_strobogrammatic.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_is_strobogrammatic(self):
+        self.assertTrue(is_strobogrammatic("69"))
+        self.assertFalse(is_strobogrammatic("14"))
+    def test_is_strobogrammatic2(self):
+        self.assertTrue(is_strobogrammatic2("69"))
+        self.assertFalse(is_strobogrammatic2("14"))
+
+
+class TestNextPerfectSquare(unittest.TestCase):
+    """[summary]
+    Test for the file next_perfect_square.py
+    
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_find_next_square(self):
+        self.assertEqual(36,find_next_square(25))
+        self.assertEqual(1,find_next_square(0))
+    def test_find_next_square2(self):
+        self.assertEqual(36,find_next_square2(25))
+        self.assertEqual(1,find_next_square2(0))
+
+
+class TestPrimesSieveOfEratosthenes(unittest.TestCase):
+    """[summary]
+    Test for the file primes_sieve_of_eratosthenes.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_primes(self):
+        self.assertEqual([2, 3, 5, 7],primes(7))
+
+
+class TestPrimeTest (unittest.TestCase):
+    """[summary]
+    Test for the file prime_test.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_prime_test(self):
+        """
+            checks all prime numbers between 2 up to 100.
+            Between 2 up to 100 exists 25 prime numbers!
+        """
+        counter = 0
+        for i in range(2,101):
+            if prime_test(i):
+                counter += 1
+        self.assertEqual(25,counter)
+    def test_prime_test2(self):
+        """
+            checks all prime numbers between 2 up to 100.
+            Between 2 up to 100 exists 25 prime numbers!
+        """
+        counter = 0
+        for i in range(2,101):
+            if prime_test(i):
+                counter += 1
+        self.assertEqual(25,counter)
+        
+
+class TestPythagoras(unittest.TestCase):
+    """[summary]
+    Test for the file pythagoras.py 
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_pythagoras(self):
+        self.assertEqual("Hypotenuse = 3.605551275463989",pythagoras(3, 2, "?"))
+
+
+class TestRabinMiller(unittest.TestCase):
+    """[summary]
+    Test for the file rabin_miller.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_is_prime(self):
+        self.assertTrue(is_prime(7,2))
+        self.assertTrue(is_prime(13,11))
+        self.assertFalse(is_prime(6,2))
+
+
+class TestRSA(unittest.TestCase):
+    """[summary]
+    Test for the file rsa.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_encrypt_decrypt(self):
+        self.assertEqual(7,decrypt(encrypt(7, 23, 143), 47, 143))
+    def test_key_generator(self):
+        n, e, d = generate_key(8)
+        data = 2
+        en = encrypt(data, e, n)
+        dec = decrypt(en, d, n)
+        self.assertEqual(data,dec)
+
+if __name__ == "__main__":
+    unittest.main()
\ No newline at end of file