Repository: keon/algorithms
Pull request #549 (2019-10-11 05:45:39)

Add_Integer_Divide Algorithms
- [X] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?




Patch:
diff --git a/.travis.yml b/.travis.yml
index 37013bd..94607d4 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -6,8 +6,6 @@ cache:
     - $HOME/.cache/pip
 matrix:
     include:
-        - python: 3.5
-          env: TOX_ENV=py35
         - python: 3.6
           env: TOX_ENV=py36
         - python: 3.7
@@ -15,6 +13,8 @@ matrix:
 install:
     - pip install -r test_requirements.txt
 before_script:
+    # run black to check if some files would need reformatting
+    - black --check . || true
     # stop the build if there are Python syntax errors or undefined names
     - flake8 . --count --select=E9,F63,F7,F82 --show-source --statistics
     # exit-zero treats all errors as warnings.  The GitHub editor is 127 chars wide
diff --git a/README.md b/README.md
index f30d452..06446e6 100644
--- a/README.md
+++ b/README.md
@@ -116,6 +116,7 @@ If you want to uninstall algorithms, it is as simple as:
 - [compression](algorithms/compression)
     - [huffman_coding](algorithms/compression/huffman_coding.py)
     - [rle_compression](algorithms/compression/rle_compression.py)
+    - [elias](algorithms/compression/elias.py)
 - [dfs](algorithms/dfs)
     - [all_factors](algorithms/dfs/all_factors.py)
     - [count_islands](algorithms/dfs/count_islands.py)
@@ -129,6 +130,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [combination_sum](algorithms/dp/combination_sum.py)
     - [egg_drop](algorithms/dp/egg_drop.py)
     - [house_robber](algorithms/dp/house_robber.py)
+    - [int_divide](algorithms/dp/int_divide.py)
     - [job_scheduling](algorithms/dp/job_scheduling.py)
     - [knapsack](algorithms/dp/knapsack.py)
     - [longest_increasing](algorithms/dp/longest_increasing.py)
@@ -150,6 +152,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [find_all_cliques](algorithms/graph/find_all_cliques.py)
     - [find_path](algorithms/graph/find_path.py)
     - [graph](algorithms/graph/graph.py)
+    - [dijkstra](algorithms/graph/dijkstra.py)
     - [markov_chain](algorithms/graph/markov_chain.py)
     - [minimum_spanning_tree](algorithms/graph/minimum_spanning_tree.py)
     - [satisfiability](algorithms/graph/satisfiability.py)
@@ -223,6 +226,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
 	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py)
+	- [cholesky_matrix_decomposition](algorithms/matrix/cholesky_matrix_decomposition.py)
 - [queues](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
diff --git a/algorithms/arrays/flatten.py b/algorithms/arrays/flatten.py
index 4133c34..f19156a 100644
--- a/algorithms/arrays/flatten.py
+++ b/algorithms/arrays/flatten.py
@@ -3,7 +3,7 @@ Implement Flatten Arrays.
 Given an array that may contain nested arrays,
 produce a single resultant array.
 """
-from collections import Iterable
+from collections.abc import Iterable
 
 
 # return list
diff --git a/algorithms/arrays/limit.py b/algorithms/arrays/limit.py
index 33468a0..c6100da 100644
--- a/algorithms/arrays/limit.py
+++ b/algorithms/arrays/limit.py
@@ -14,10 +14,7 @@ Complexity = O(n)
 
 # tl:dr -- array slicing by value
 def limit(arr, min_lim=None, max_lim=None):
-    if min_lim is None and max_lim is not None:
-        return [x for x in arr if x <= max_lim]
-    if max_lim is None and min_lim is not None:
-        return [x for x in arr if x >= min_lim]
-    if max_lim is not None and min_lim is not None:
-        return [x for x in arr if min_lim <= x <= max_lim]
-    return arr
+    min_check = lambda val: True if min_lim is None else (min_lim <= val)
+    max_check = lambda val: True if max_lim is None else (val <= max_lim)
+    
+    return [val for val in arr if min_check(val) and max_check(val)]
diff --git a/algorithms/bfs/maze_search.py b/algorithms/bfs/maze_search.py
index 436b3ef..f7410d4 100644
--- a/algorithms/bfs/maze_search.py
+++ b/algorithms/bfs/maze_search.py
@@ -1,6 +1,8 @@
+from collections import deque
+
 '''
-BFS time complexity : O(|E|)
-BFS space complexity : O(|V|)
+BFS time complexity : O(|E| + |V|)
+BFS space complexity : O(|E| + |V|)
 
 do BFS from (0,0) of the grid and get the minimum number of steps needed to get to the lower right column
 
@@ -24,25 +26,42 @@ If grid is
 the answer is: -1
 '''
 
-def maze_search(grid):
-    dx = [0,0,-1,1]
-    dy = [-1,1,0,0]
-    n = len(grid)
-    m = len(grid[0])
-    q = [(0,0,0)]
-    visit = [[0]*m for _ in range(n)]
-    if grid[0][0] == 0:
+def maze_search(maze):
+    BLOCKED, ALLOWED = 0, 1
+    UNVISITED, VISITED = 0, 1
+
+    initial_x, initial_y = 0, 0
+
+    if maze[initial_x][initial_y] == BLOCKED:
         return -1
-    visit[0][0] = 1
-    while q:
-        i, j, step = q.pop(0)
-        if i == n-1 and j == m-1:
-            return step
-        for k in range(4):
-            x = i + dx[k]
-            y = j + dy[k]
-            if x>=0 and x<n and y>=0 and y<m:
-                if grid[x][y] ==1 and visit[x][y] == 0:
-                    visit[x][y] = 1
-                    q.append((x,y,step+1))
-    return -1
+    
+    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
+
+    height, width = len(maze), len(maze[0])
+
+    target_x, target_y = height - 1, width - 1
+
+    queue = deque([(initial_x, initial_y, 0)])
+
+    is_visited = [[UNVISITED for w in range(width)] for h in range(height)]
+    is_visited[initial_x][initial_y] = VISITED
+
+    while queue:
+        x, y, steps = queue.popleft()
+
+        if x == target_x and y == target_y:
+            return steps
+
+        for dx, dy in directions:
+            new_x = x + dx
+            new_y = y + dy
+
+            if not (0 <= new_x < height and 0 <= new_y < width):
+                continue
+
+            if maze[new_x][new_y] == ALLOWED and is_visited[new_x][new_y] == UNVISITED:
+                queue.append((new_x, new_y, steps + 1))
+                is_visited[new_x][new_y] = VISITED
+
+    return -1 
+
diff --git a/algorithms/compression/elias.py b/algorithms/compression/elias.py
new file mode 100644
index 0000000..bdeb7fd
--- /dev/null
+++ b/algorithms/compression/elias.py
@@ -0,0 +1,49 @@
+"""
+Elias γ code or Elias gamma code is a universal code encoding positive integers.
+It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.
+Elias δ code or Elias delta code is a universal code encoding the positive integers,
+that includes Elias γ code when calculating.
+Both were developed by Peter Elias.
+
+"""
+from math import log,ceil
+
+log2 = lambda x: log(x,2)
+
+# Calculates the binary number
+def binary(x,l=1):
+	fmt = '{0:0%db}' % l
+	return fmt.format(x)
+
+# Calculates the unary number
+def unary(x):
+	return (x-1)*'1'+'0'
+
+def elias_generic(lencoding, x):
+	"""
+	The compressed data is calculated in two parts. 
+	The first part is the unary number of 1 + ⌊log2(x)⌋. 
+	The second part is the binary number of x - 2^(⌊log2(x)⌋).
+	For the final result we add these two parts.
+	"""
+	if x == 0: return '0'
+	
+	first_part = 1 + int(log2(x))
+	
+	a = x - 2**(int(log2(x)))
+	
+	k = int(log2(x))
+
+	return lencoding(first_part) + binary(a,k)
+
+def elias_gamma(x):
+	"""
+	For the first part we put the unary number of x.
+	"""
+	return elias_generic(unary, x)
+
+def elias_delta(x):
+	"""
+	For the first part we put the elias_g of the number.
+	"""
+	return elias_generic(elias_gamma,x)
diff --git a/algorithms/dp/__init__.py b/algorithms/dp/__init__.py
index 8925409..c96a9b3 100644
--- a/algorithms/dp/__init__.py
+++ b/algorithms/dp/__init__.py
@@ -18,3 +18,4 @@ from .num_decodings import *
 from .regex_matching import *
 from .rod_cut import *
 from .word_break import *
+from .int_divide import *
diff --git a/algorithms/dp/int_divide.py b/algorithms/dp/int_divide.py
new file mode 100644
index 0000000..86ba8cb
--- /dev/null
+++ b/algorithms/dp/int_divide.py
@@ -0,0 +1,50 @@
+"""
+Given positive integer n, find an algorithm to find the number of non-negative number division, or descomposition.
+
+The complexity is O(n^2).
+
+Example 1:
+Input: 4
+Output: 5
+Explaination:
+4=4
+4=3+1
+4=2+2
+4=2+1+1
+4=1+1+1+1
+
+Example :
+Input: 7
+Output: 15
+Explaination:
+7=7
+7=6+1
+7=5+2
+7=5+1+1
+7=4+3
+7=4+2+1
+7=4+1+1+1
+7=3+3+1
+7=3+2+2
+7=3+2+1+1
+7=3+1+1+1+1
+7=2+2+2+1
+7=2+2+1+1+1
+7=2+1+1+1+1+1
+7=1+1+1+1+1+1+1
+
+"""
+
+
+def int_divide(n):
+    arr = [[0 for i in range(n + 1)] for j in range(n + 1)]
+    arr[1][1] = 1
+    for i in range(1, n + 1):
+        for j in range(1, n + 1):
+            if i < j:
+                arr[i][j] = arr[i][i]
+            elif i == j:
+                arr[i][j] = 1 + arr[i][j - 1]
+            else:
+                arr[i][j] = arr[i][j - 1] + arr[i - j][j]
+    return arr[n][n]
diff --git a/algorithms/dp/longest_common_subsequence.py b/algorithms/dp/longest_common_subsequence.py
new file mode 100644
index 0000000..cdbba95
--- /dev/null
+++ b/algorithms/dp/longest_common_subsequence.py
@@ -0,0 +1,48 @@
+"""
+A subsequence is a sequence that can be derived from another
+sequence by deleting some or no elements without changing the
+order of the remaining elements.
+
+For example, 'abd' is a subsequence of 'abcd' whereas 'adc' is not
+
+Given 2 strings containing lowercase english alphabets, find the length
+of the Longest Common Subsequence (L.C.S.).
+
+Example:
+    Input:  'abcdgh'
+            'aedfhr'
+    Output: 3
+
+    Explanation: The longest subsequence common to both the string is "adh"
+
+Time Complexity : O(M*N)
+Space Complexity : O(M*N), where M and N are the lengths of the 1st and 2nd string
+respectively.
+
+"""
+
+
+def longest_common_subsequence(s1, s2):
+    """
+    :param s1: string
+    :param s2: string
+    :return: int
+    """
+    m = len(s1)
+    n = len(s2)
+
+    dp = [[0] * (n + 1) for i in range(m + 1)]
+    """
+    dp[i][j] : contains length of LCS of s1[0..i-1] and s2[0..j-1]
+    """
+
+    for i in range(m + 1):
+        for j in range(n + 1):
+            if i == 0 or j == 0:
+                dp[i][j] = 0
+            elif s1[i - 1] == s2[j - 1]:
+                dp[i][j] = dp[i - 1][j - 1] + 1
+            else:
+                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
+
+    return dp[m][n]
diff --git a/algorithms/graph/dijkstra.py b/algorithms/graph/dijkstra.py
index fe5772e..2cf0430 100644
--- a/algorithms/graph/dijkstra.py
+++ b/algorithms/graph/dijkstra.py
@@ -1,6 +1,6 @@
 #Dijkstra's single source shortest path algorithm
 
-class Graph():
+class Dijkstra():
 
     def __init__(self, vertices):
         self.vertices = vertices
diff --git a/algorithms/graph/find_path.py b/algorithms/graph/find_path.py
index d1716c0..a188005 100644
--- a/algorithms/graph/find_path.py
+++ b/algorithms/graph/find_path.py
@@ -21,7 +21,6 @@ def find_path(graph, start, end, path=[]):
 # find all path
 def find_all_path(graph, start, end, path=[]):
     path = path + [start]
-    print(path)
     if (start == end):
         return [path]
     if not start in graph:
diff --git a/algorithms/matrix/cholesky_matrix_decomposition.py b/algorithms/matrix/cholesky_matrix_decomposition.py
new file mode 100644
index 0000000..4b5e24e
--- /dev/null
+++ b/algorithms/matrix/cholesky_matrix_decomposition.py
@@ -0,0 +1,48 @@
+"""
+Cholesky matrix decomposition is used to find the decomposition of a Hermitian positive-definite matrix A
+into matrix V, so that V * V* = A, where V* denotes the conjugate transpose of L.
+The dimensions of the matrix A must match.
+
+This method is mainly used for numeric solution of linear equations Ax = b.
+
+example:
+Input matrix A:
+[[  4,  12, -16],
+ [ 12,  37, -43],
+ [-16, -43,  98]]
+
+Result:
+[[2.0, 0.0, 0.0],
+[6.0, 1.0, 0.0],
+[-8.0, 5.0, 3.0]]
+
+Time complexity of this algorithm is O(n^3), specifically about (n^3)/3
+
+"""
+import math
+
+
+def cholesky_decomposition(A):
+    """
+    :param A: Hermitian positive-definite matrix of type List[List[float]]
+    :return: matrix of type List[List[float]] if A can be decomposed, otherwise None
+    """
+    n = len(A)
+    for ai in A:
+        if len(ai) != n:
+            return None
+    V = [[0.0] * n for _ in range(n)]
+    for j in range(n):
+        sum_diagonal_element = 0
+        for k in range(j):
+            sum_diagonal_element = sum_diagonal_element + math.pow(V[j][k], 2)
+        sum_diagonal_element = A[j][j] - sum_diagonal_element
+        if sum_diagonal_element <= 0:
+            return None
+        V[j][j] = math.pow(sum_diagonal_element, 0.5)
+        for i in range(j+1, n):
+            sum_other_element = 0
+            for k in range(j):
+                sum_other_element += V[i][k]*V[j][k]
+            V[i][j] = (A[i][j] - sum_other_element)/V[j][j]
+    return V


Test patch:
diff --git a/test_requirements.txt b/test_requirements.txt
index 7a3e47c..f0afad0 100644
--- a/test_requirements.txt
+++ b/test_requirements.txt
@@ -4,3 +4,4 @@ coverage
 nose
 pytest
 tox
+black
diff --git a/tests/test_compression.py b/tests/test_compression.py
index 144d944..cd41283 100644
--- a/tests/test_compression.py
+++ b/tests/test_compression.py
@@ -1,5 +1,6 @@
 from algorithms.compression.huffman_coding import HuffmanCoding
 from algorithms.compression.rle_compression import (decode_rle, encode_rle)
+from algorithms.compression.elias import (elias_gamma, elias_delta)
 
 import unittest
 
@@ -44,6 +45,25 @@ class TestRLECompression(unittest.TestCase):
         self.assertEqual('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW', 
             decode_rle('12W1B12W3B24W1B14W'))
 
+class TestEliasCoding(unittest.TestCase):
+
+    def test_elias_gamma(self):
+        correct_result = ['0', '00', '100', '101', '11000', '11001', '11010', '11011', '1110000', '1110001', '1110010']
+        
+        result = []
+        for i in range(11):	
+            result.append(elias_gamma(i))
+
+        self.assertEqual(correct_result, result)
+
+    def test_elias_delta(self):
+        correct_result = ['0', '000', '1000', '1001', '10100', '10101', '10110', '10111', '11000000', '11000001', '11000010']
+
+        result = []
+        for i in range(11):	
+            result.append(elias_delta(i))
+
+        self.assertEqual(correct_result, result)        
 
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_dp.py b/tests/test_dp.py
index 08f6bd0..cd1dde2 100644
--- a/tests/test_dp.py
+++ b/tests/test_dp.py
@@ -10,7 +10,8 @@ from algorithms.dp import (
     house_robber,
     Job, schedule,
     Item, get_maximum_value,
-    longest_increasing_subsequence
+    longest_increasing_subsequence,
+    int_divide
 )
 
 
@@ -31,7 +32,7 @@ class TestClimbingStairs(unittest.TestCase):
     def test_climb_stairs(self):
         self.assertEqual(climb_stairs(2), 2)
         self.assertEqual(climb_stairs(10), 89)
-    
+
     def test_climb_stairs_optimized(self):
         self.assertEqual(climb_stairs_optimized(2), 2)
         self.assertEqual(climb_stairs_optimized(10), 89)
@@ -46,7 +47,7 @@ class TestCoinChange(unittest.TestCase):
 class TestCombinationSum(unittest.TestCase):
     def test_combination_sum_topdown(self):
         self.assertEqual(combination_sum_topdown([1, 2, 3], 4), 7)
-    
+
     def test_combination_sum_bottom_up(self):
         self.assertEqual(combination_sum_bottom_up([1, 2, 3], 4), 7)
 
@@ -68,11 +69,11 @@ class TestFib(unittest.TestCase):
     def test_fib_recursive(self):
         self.assertEqual(fib_recursive(10), 55)
         self.assertEqual(fib_recursive(30), 832040)
-    
+
     def test_fib_list(self):
         self.assertEqual(fib_list(10), 55)
         self.assertEqual(fib_list(30), 832040)
-    
+
     def test_fib_iter(self):
         self.assertEqual(fib_iter(10), 55)
         self.assertEqual(fib_iter(30), 832040)
@@ -85,7 +86,7 @@ class TestHosoyaTriangle(unittest.TestCase):
     Arguments:
         unittest {[type]} -- [description]
     """
-    
+
     def test_hosoya(self):
         self.assertEqual([1], hosoya_testing(1))
         self.assertEqual([1,
@@ -108,7 +109,7 @@ class TestHosoyaTriangle(unittest.TestCase):
                           hosoya_testing(10))
 
 
-class TestHouseRobber(unittest.TestCase):    
+class TestHouseRobber(unittest.TestCase):
     def test_house_robber(self):
         self.assertEqual(44, house_robber([1, 2, 16, 3, 15, 3, 12, 1]))
 
@@ -134,5 +135,12 @@ class TestLongestIncreasingSubsequence(unittest.TestCase):
         self.assertEqual(5, longest_increasing_subsequence(sequence))
 
 
+class TestIntDivide(unittest.TestCase):
+    def test_int_divide(self):
+        self.assertEqual(5, int_divide(4))
+        self.assertEqual(42, int_divide(10))
+        self.assertEqual(204226, int_divide(50))
+
+
 if __name__ == '__main__':
     unittest.main()
diff --git a/tests/test_graph.py b/tests/test_graph.py
index d402b86..893ea77 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -1,5 +1,6 @@
 from algorithms.graph import Tarjan
 from algorithms.graph import check_bipartite
+from algorithms.graph.dijkstra import Dijkstra
 
 import unittest
 
@@ -57,3 +58,20 @@ class TestCheckBipartite(unittest.TestCase):
         
         adj_list_3 = [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]]
         self.assertEqual(False, check_bipartite(adj_list_3))
+
+class TestDijkstra(unittest.TestCase):
+    
+    def test_dijkstra(self):
+        g = Dijkstra(9) 
+        g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], 
+           [4, 0, 8, 0, 0, 0, 0, 11, 0], 
+           [0, 8, 0, 7, 0, 4, 0, 0, 2], 
+           [0, 0, 7, 0, 9, 14, 0, 0, 0], 
+           [0, 0, 0, 9, 0, 10, 0, 0, 0], 
+           [0, 0, 4, 14, 10, 0, 2, 0, 0], 
+           [0, 0, 0, 0, 0, 2, 0, 1, 6], 
+           [8, 11, 0, 0, 0, 0, 1, 0, 7], 
+           [0, 0, 2, 0, 0, 0, 6, 7, 0] 
+          ]; 
+
+        self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14]);
\ No newline at end of file
diff --git a/tests/test_matrix.py b/tests/test_matrix.py
index 4d7e129..3522d7d 100644
--- a/tests/test_matrix.py
+++ b/tests/test_matrix.py
@@ -2,6 +2,7 @@ from algorithms.matrix import (
     bomb_enemy,
     copy_transform,
     crout_matrix_decomposition,
+    cholesky_matrix_decomposition,
     multiply,
     rotate_image,
     sparse_dot_vector,
@@ -93,6 +94,39 @@ class TestCroutMatrixDecomposition(unittest.TestCase):
                              [[2, 1, 3, 1], [4, 1, 4, 1], [6, 1, 7, 1], [8, 1, 9, 1]]))
 
 
+class TestCholeskyMatrixDecomposition(unittest.TestCase):
+    """[summary]
+    Test for the file cholesky_matrix_decomposition.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_cholesky_matrix_decomposition(self):
+        self.assertEqual([[2.0, 0.0, 0.0],
+                          [6.0, 1.0, 0.0],
+                          [-8.0, 5.0, 3.0]],
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[4, 12, -16], [12, 37, -43], [-16, -43, 98]]))
+
+        self.assertEqual( None,
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[4, 12, -8], [12, 4, -43], [-16, -1, 32]]))
+
+        self.assertEqual(None,
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[4, 12, -16], [12, 37, -43], [-16, -43, 98], [1, 2, 3]]))
+
+        # example taken from https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/04LinearAlgebra/cholesky/
+        self.assertEqual([[2.23606797749979, 0.0, 0.0, 0.0],
+                          [0.5366563145999494, 2.389979079406345, 0.0, 0.0],
+                          [0.13416407864998736, -0.19749126846635062, 2.818332343581848, 0.0],
+                          [-0.2683281572999747, 0.43682390737048743, 0.64657701271919, 3.052723872310221]],
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[5, 1.2, 0.3, -0.6], [1.2, 6, -0.4, 0.9],
+                              [0.3, -0.4, 8, 1.7], [-0.6, 0.9, 1.7, 10]]))
+
+
 class TestMultiply(unittest.TestCase):
     """[summary]
     Test for the file multiply.py