add atbash, crout, hosoya triangle algorithms (keon#470)

Notheryne · keon · commit d31ec0a453b6 · 2019-01-24T00:51:46.000-08:00
* add atbash, crout, hosoya triangle algorithms

* add tests, update readmes
diff --git a/README.md b/README.md
@@ -140,6 +140,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [rod_cut](algorithms/dp/rod_cut.py)
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
+	- [hosoya triangle](algorithms/dp/hosoya_triangle.py)
 - [graph](algorithms/graph)
     - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/check_digraph_strongly_connected.py)
@@ -216,6 +217,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [sparse_dot_vector](algorithms/matrix/sparse_dot_vector.py)
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
+	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py
 - [queues](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
@@ -306,6 +308,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [rotate](algorithms/strings/rotate.py)
     - [first_unique_char](algorithms/strings/first_unique_char.py)
     - [repeat_substring](algorithms/strings/repeat_substring.py)     
+	- [atbash_cipher](algorithms/strings/atbash_cipher.py)
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/bst)
         - [array_to_bst](algorithms/tree/bst/array_to_bst.py)
diff --git a/README_ES.md b/README_ES.md
@@ -140,6 +140,7 @@ Si desea desinstalar algorithms, es tan simple como:
     - [rod_cut](algorithms/dp/rod_cut.py)
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
+	- [hosoya triangle](algorithms/dp/hosoya_triangle.py)
 - [graph](algorithms/graph)
     - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/check_digraph_strongly_connected.py)
@@ -214,6 +215,7 @@ Si desea desinstalar algorithms, es tan simple como:
     - [sparse_dot_vector](algorithms/matrix/sparse_dot_vector.py)
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
+	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py
 - [queues](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
@@ -303,7 +305,8 @@ Si desea desinstalar algorithms, es tan simple como:
     - [longest_common_prefix](algorithms/strings/longest_common_prefix.py)
     - [rotate](algorithms/strings/rotate.py)
     - [first_unique_char](algorithms/strings/first_unique_char.py)
-    - [repeat_substring](algorithms/strings/repeat_substring.py)     
+    - [repeat_substring](algorithms/strings/repeat_substring.py) 
+	- [atbash_cipher](algorithms/strings/atbash_cipher.py)    
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/bst)
         - [array_to_bst](algorithms/tree/bst/array_to_bst.py)
diff --git a/README_FR.md b/README_FR.md
@@ -139,6 +139,7 @@ Si vous voulez désinstaller le paquet algorithms, il suffit de procéder comme
     - [rod_cut](algorithms/dp/rod_cut.py)
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
+	- [hosoya triangle](algorithms/dp/hosoya_triangle.py)
 - [graph](algorithms/graph)
     - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
@@ -212,6 +213,7 @@ Si vous voulez désinstaller le paquet algorithms, il suffit de procéder comme
     - [sparse_dot_vector](algorithms/matrix/sparse_dot_vector.py)
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
+	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py
 - [queues](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
@@ -301,7 +303,8 @@ Si vous voulez désinstaller le paquet algorithms, il suffit de procéder comme
     - [longest_common_prefix](algorithms/strings/longest_common_prefix.py)
     - [rotate](algorithms/strings/rotate.py)
     - [first_unique_char](algorithms/strings/first_unique_char.py)
-    - [repeat_substring](algorithms/strings/repeat_substring.py)     
+    - [repeat_substring](algorithms/strings/repeat_substring.py)   
+	- [atbash_cipher](algorithms/strings/atbash_cipher.py)	
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
diff --git a/README_GE.md b/README_GE.md
@@ -146,6 +146,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [rod_cut](algorithms/dp/rod_cut.py)
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
+	- [hosoya triangle](algorithms/dp/hosoya_triangle.py)
 - [graph](algorithms/graph)
     - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
@@ -215,6 +216,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [sparse_dot_vector](algorithms/matrix/sparse_dot_vector.py)
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
+	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py
 - [queues](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
@@ -291,6 +293,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [reverse_words](algorithms/strings/reverse_words.py)
     - [roman_to_int](algorithms/strings/roman_to_int.py)
     - [word_squares](algorithms/strings/word_squares.py)
+	- [atbash_cipher](algorithms/strings/atbash_cipher.py)
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
diff --git a/README_JP.md b/README_JP.md
@@ -140,6 +140,7 @@ if __name__ == "__main__":
     - [rod_cut](algorithms/dp/rod_cut.py)
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
+	- [hosoya triangle](algorithms/dp/hosoya_triangle.py)
 - [graph : グラフ](algorithms/graph)
     - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
@@ -209,6 +210,7 @@ if __name__ == "__main__":
     - [sparse_dot_vector](algorithms/matrix/sparse_dot_vector.py)
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
+	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py
 - [queues : キュー](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
@@ -285,6 +287,7 @@ if __name__ == "__main__":
     - [reverse_words](algorithms/strings/reverse_words.py)
     - [roman_to_int](algorithms/strings/roman_to_int.py)
     - [word_squares](algorithms/strings/word_squares.py)
+	- [atbash_cipher](algorithms/strings/atbash_cipher.py)
 - [tree : 木構造](algorithms/tree)
     - [bst](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
diff --git a/README_KR.md b/README_KR.md
@@ -136,6 +136,7 @@ if __name__ == "__main__":
     - [rod_cut](algorithms/dp/rod_cut.py)
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
+	- [hosoya triangle](algorithms/dp/hosoya_triangle.py)
 - [graph : 그래프](algorithms/graph)
     - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
@@ -205,6 +206,7 @@ if __name__ == "__main__":
     - [sparse_dot_vector](algorithms/matrix/sparse_dot_vector.py)
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
+	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py
 - [queues : 큐](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
@@ -279,6 +281,7 @@ if __name__ == "__main__":
     - [reverse_words](algorithms/strings/reverse_words.py)
     - [roman_to_int](algorithms/strings/roman_to_int.py)
     - [word_squares](algorithms/strings/word_squares.py)
+	- [atbash_cipher](algorithms/strings/atbash_cipher.py)
 - [tree : 트리](algorithms/tree)
     - [bst : 이진 탐색 트리](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
diff --git a/README_PTBR.md b/README_PTBR.md
@@ -138,6 +138,7 @@ Se você deseja desinstalar os algoritmos, é tão simples quanto:
     - [rod_cut](algorithms/dp/rod_cut.py)
     - [word_break](algorithms/dp/word_break.py)
     - [fibonacci](algorithms/dp/fib.py)
+	- [hosoya triangle](algorithms/dp/hosoya_triangle.py)
 - [graph](algorithms/graph)
     - [check_bipartite](algorithms/graph/check_bipartite.py)
     - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
@@ -207,6 +208,7 @@ Se você deseja desinstalar os algoritmos, é tão simples quanto:
     - [sparse_dot_vector](algorithms/matrix/sparse_dot_vector.py)
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
+	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py
 - [queues](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
@@ -289,6 +291,7 @@ Se você deseja desinstalar os algoritmos, é tão simples quanto:
     - [caesar_cipher](algorithms/strings/caesar_cipher.py)
     - [contain_string](algorithms/strings/contain_string.py)
     - [count_binary_substring](algorithms/strings/count_binary_substring.py)
+	- [atbash_cipher](algorithms/strings/atbash_cipher.py)
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/tree/bst)
         - [array2bst](algorithms/tree/bst/array2bst.py)
diff --git a/algorithms/dp/hosoya_triangle.py b/algorithms/dp/hosoya_triangle.py
@@ -0,0 +1,45 @@
+"""
+Hosoya triangle (originally Fibonacci triangle) is a triangular arrangement
+of numbers, where if you take any number it is the sum of 2 numbers above.
+First line is always 1, and second line is always {1     1}.
+
+This printHosoya function takes argument n which is the height of the triangle
+(number of lines).
+
+For example:
+printHosoya( 6 ) would return:
+1 
+1 1 
+2 1 2 
+3 2 2 3 
+5 3 4 3 5 
+8 5 6 6 5 8
+
+The complexity is O(n^3).
+
+"""
+
+
+def hosoya(n, m): 
+    if ((n == 0 and m == 0) or (n == 1 and m == 0) or
+        (n == 1 and m == 1) or (n == 2 and m == 1)): 
+        return 1
+    if n > m: 
+        return hosoya(n - 1, m) + hosoya(n - 2, m) 
+    elif m == n: 
+        return hosoya(n - 1, m - 1) + hosoya(n - 2, m - 2) 
+    else: 
+        return 0
+          
+def print_hosoya(n): 
+    for i in range(n): 
+        for j in range(i + 1): 
+            print(hosoya(i, j) , end = " ") 
+        print ("\n", end = "")
+
+def hosoya_testing(n):
+    x = []
+    for i in range(n): 
+        for j in range(i + 1): 
+            x.append(hosoya(i, j))
+    return x
diff --git a/algorithms/matrix/crout_matrix_decomposition.py b/algorithms/matrix/crout_matrix_decomposition.py
@@ -0,0 +1,47 @@
+"""
+Crout matrix decomposition is used to find two matrices that, when multiplied
+give our input matrix, so L * U = A.
+L stands for lower and L has non-zero elements only on diagonal and below.
+U stands for upper and U has non-zero elements only on diagonal and above.
+
+This can for example be used to solve systems of linear equations.
+The last if is used  if  to avoid dividing by zero.
+
+Example:
+We input the A matrix:
+[[1,2,3],
+[3,4,5],
+[6,7,8]]
+
+We get:
+L = [1.0,  0.0, 0.0]
+    [3.0, -2.0, 0.0]
+    [6.0, -5.0, 0.0]
+U = [1.0,  2.0, 3.0]
+    [0.0,  1.0, 2.0]
+    [0.0,  0.0, 1.0]
+
+We can check that L * U = A.
+
+I think the complexity should be O(n^3).
+"""
+
+def crout_matrix_decomposition(A):
+    n = len(A)
+    L = [[0.0] * n for i in range(n)]
+    U = [[0.0] * n for i in range(n)]
+    for j in range(n):
+        U[j][j] = 1.0
+        for i in range(j, n):
+            alpha = float(A[i][j])
+            for k in range(j):
+                alpha -= L[i][k]*U[k][j]
+            L[i][j] = float(alpha)
+        for i in range(j+1, n):
+            tempU = float(A[j][i])
+            for k in range(j):
+                tempU -= float(L[j][k]*U[k][i])
+            if int(L[j][j]) == 0:
+                L[j][j] = float(0.1**40)
+            U[j][i] = float(tempU/L[j][j])
+    return (L,U)
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
@@ -34,3 +34,4 @@
 from .rotate import *
 from .first_unique_char import *
 from .repeat_substring import *
+from .atbash_cipher import *
diff --git a/algorithms/strings/atbash_cipher.py b/algorithms/strings/atbash_cipher.py
@@ -0,0 +1,27 @@
+"""
+Atbash cipher is mapping the alphabet to it's reverse.
+So if we take "a" as it is the first letter, we change it to the last - z.
+
+Example:
+Attack at dawn --> Zggzxp zg wzdm
+
+Complexity: O(n)
+"""
+
+def atbash(s):
+    translated = ""
+    for i in range(len(s)):
+        n = ord(s[i])
+        
+        if s[i].isalpha():
+            
+            if s[i].isupper():
+                x = n - ord('A')
+                translated += chr(ord('Z') - x)
+            
+            if s[i].islower():
+                x = n - ord('a')
+                translated += chr(ord('z') - x)
+        else:
+            translated += s[i]
+    return translated
diff --git a/tests/test_dp.py b/tests/test_dp.py
@@ -1,5 +1,6 @@
 from algorithms.dp import (
-    edit_distance
+    edit_distance,
+    hosoya_triangle
 )
 
 
@@ -11,6 +12,35 @@ def test_edit_distance(self):
         self.assertEqual(edit_distance('food', 'money'), 4)
         self.assertEqual(edit_distance('horse', 'ros'), 3)
 
+class TestHosoyaTriangle(unittest.TestCase):
+    """[summary]
+    Test for the file hosoya_triangle
+    
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    
+    def test_hosoya(self):
+        self.assertEqual([1], hosoya_testing(1))
+        self.assertEqual([1,
+                         1, 1,
+                         2, 1, 2,
+                         3, 2, 2, 3,
+                         5, 3, 4, 3, 5,
+                         8, 5, 6, 6, 5, 8],
+                         hosoya_testing(6))
+        self.assertEqual([1,
+                          1, 1,
+                          2, 1, 2,
+                          3, 2, 2, 3,
+                          5, 3, 4, 3, 5,
+                          8, 5, 6, 6, 5, 8,
+                          13, 8, 10, 9, 10, 8, 13,
+                          21, 13, 16, 15, 15, 16, 13, 21,
+                          34, 21, 26, 24, 25, 24, 26, 21, 34,
+                          55, 34, 42, 39, 40, 40, 39, 42, 34, 55],
+                          hosoya_testing(10))
+
 
 if __name__ == '__main__':
     unittest.main()
diff --git a/tests/test_matrix.py b/tests/test_matrix.py
@@ -0,0 +1,46 @@
+from algorithms.matrix import (
+    crout_matrix_decomposition
+    )
+
+
+import unittest
+
+
+class TestCroutMatrixDecomposition(unittest.TestCase):
+    """[summary]
+    Test for the file crout_matrix_decomposition.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    
+    def test_crout_matrix_decomposition(self):
+        self.assertEqual(([[9.0, 0.0], [7.0, 0.0]],
+                          [[1.0, 1.0], [0.0, 1.0]]),
+                         crout_matrix_decomposition([[9,9], [7,7]]))
+                         
+        self.assertEqual(([[1.0, 0.0, 0.0],
+                           [3.0, -2.0, 0.0],
+                           [6.0, -5.0, 0.0]],
+                           [[1.0, 2.0, 3.0],
+                            [0.0, 1.0, 2.0],
+                            [0.0, 0.0, 1.0]]),
+                         crout_matrix_decomposition([[1,2,3],[3,4,5],[6,7,8]]))
+                         
+        self.assertEqual(([[2.0, 0, 0, 0],
+                           [4.0, -1.0, 0, 0],
+                           [6.0, -2.0, 2.0, 0],
+                           [8.0, -3.0, 3.0, 0.0]],
+                          [[1.0, 0.5, 1.5, 0.5],
+                           [0, 1.0, 2.0, 1.0],
+                           [0, 0, 1.0, 0.0],
+                           [0, 0, 0, 1.0]]),
+                         crout_matrix_decomposition([[2,1,3,1],
+                                                     [4,1,4,1],
+                                                     [6,1,7,1],
+                                                     [8,1,9,1]]))
+                           
+    
+        
+if __name__ == "__main__":
+    unittest.main()
diff --git a/tests/test_strings.py b/tests/test_strings.py
