Repository: keon/algorithms
Pull request #647 (2020-04-05 16:27:14)

Update flatten.py
Avoid strings being recursing forever


Patch:
diff --git a/README.md b/README.md
index 06fb2d4..79c1d08 100644
--- a/README.md
+++ b/README.md
@@ -158,6 +158,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [markov_chain](algorithms/graph/markov_chain.py)
     - [minimum_spanning_tree](algorithms/graph/minimum_spanning_tree.py)
     - [satisfiability](algorithms/graph/satisfiability.py)
+    - [minimum_spanning_tree_prims](algorithms/graph/prims_minimum_spanning.py)
     - [tarjan](algorithms/graph/tarjan.py)
     - [traversal](algorithms/graph/traversal.py)
 	  - [maximum_flow](algorithms/graph/maximum_flow.py)
@@ -328,9 +329,10 @@ If you want to uninstall algorithms, it is as simple as:
     - [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)     
-	- [atbash_cipher](algorithms/strings/atbash_cipher.py)
-	- [knuth_morris_pratt](algorithms/strings/knuth_morris_pratt.py)
+    - [repeat_substring](algorithms/strings/repeat_substring.py)
+	  - [atbash_cipher](algorithms/strings/atbash_cipher.py)
+    - [longest_palindromic_substring](algorithms/strings/longest_palindromic_substring.py)
+  	- [knuth_morris_pratt](algorithms/strings/knuth_morris_pratt.py)
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/bst)
         - [array_to_bst](algorithms/tree/bst/array_to_bst.py)
diff --git a/algorithms/arrays/flatten.py b/algorithms/arrays/flatten.py
index f19156a..52f4ec5 100644
--- a/algorithms/arrays/flatten.py
+++ b/algorithms/arrays/flatten.py
@@ -11,7 +11,7 @@ def flatten(input_arr, output_arr=None):
     if output_arr is None:
         output_arr = []
     for ele in input_arr:
-        if isinstance(ele, Iterable):
+        if not isinstance(ele, str) and isinstance(ele, Iterable):
             flatten(ele, output_arr)    #tail-recursion
         else:
             output_arr.append(ele)      #produce the result
@@ -25,7 +25,7 @@ def flatten_iter(iterable):
     returns generator which produces one dimensional output.
     """
     for element in iterable:
-        if isinstance(element, Iterable):
+        if not isinstance(element, str) and isinstance(element, Iterable):
             yield from flatten_iter(element)    
         else:
             yield element
diff --git a/algorithms/dp/fib.py b/algorithms/dp/fib.py
index 6762e90..7a6fd71 100644
--- a/algorithms/dp/fib.py
+++ b/algorithms/dp/fib.py
@@ -1,3 +1,17 @@
+'''
+In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, called the Fibonacci sequence, 
+such that each number is the sum of the two preceding ones, starting from 0 and 1. 
+That is,
+    F0=0 , F1=1
+and
+    Fn= F(n-1) + F(n-2)
+The Fibonacci numbers are the numbers in the following integer sequence.
+    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….
+
+In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
+
+Here, given a number n, print n-th Fibonacci Number.
+'''
 def fib_recursive(n):
     """[summary]
     Computes the n-th fibonacci number recursive.
diff --git a/algorithms/graph/__init__.py b/algorithms/graph/__init__.py
index 6675e63..3bf3a1c 100644
--- a/algorithms/graph/__init__.py
+++ b/algorithms/graph/__init__.py
@@ -5,3 +5,4 @@ from .maximum_flow_bfs import *
 from .maximum_flow_dfs import *
 from .all_pairs_shortest_path import *
 from .bellman_ford import *
+from .prims_minimum_spanning import *
diff --git a/algorithms/graph/prims_minimum_spanning.py b/algorithms/graph/prims_minimum_spanning.py
new file mode 100644
index 0000000..02295c4
--- /dev/null
+++ b/algorithms/graph/prims_minimum_spanning.py
@@ -0,0 +1,42 @@
+'''
+This Prim's Algorithm Code is for finding weight of minimum spanning tree
+of a connected graph.
+For argument graph, it should be a dictionary type
+such as
+graph = {
+    'a': [ [3, 'b'], [8,'c'] ],
+    'b': [ [3, 'a'], [5, 'd'] ],
+    'c': [ [8, 'a'], [2, 'd'], [4, 'e'] ],
+    'd': [ [5, 'b'], [2, 'c'], [6, 'e'] ],
+    'e': [ [4, 'c'], [6, 'd'] ]
+}
+
+where 'a','b','c','d','e' are nodes (these can be 1,2,3,4,5 as well)
+'''
+
+
+import heapq  # for priority queue
+
+# prim's algo. to find weight of minimum spanning tree
+def prims_minimum_spanning(graph_used):
+    vis=[]
+    s=[[0,1]]
+    prim = []
+    mincost=0
+    
+    while(len(s)>0):
+        v=heapq.heappop(s)
+        x=v[1]
+        if(x in vis):
+            continue
+
+        mincost += v[0]
+        prim.append(x)
+        vis.append(x)
+
+        for j in graph_used[x]:
+            i=j[-1]
+            if(i not in vis):
+                heapq.heappush(s,j)
+
+    return mincost
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
index 3e6bc19..72ea7d7 100644
--- a/algorithms/strings/__init__.py
+++ b/algorithms/strings/__init__.py
@@ -35,5 +35,5 @@ from .rotate import *
 from .first_unique_char import *
 from .repeat_substring import *
 from .atbash_cipher import *
+from .longest_palindromic_substring import *
 from .knuth_morris_pratt import *
-
diff --git a/algorithms/strings/longest_palindromic_substring.py b/algorithms/strings/longest_palindromic_substring.py
new file mode 100644
index 0000000..ad0c831
--- /dev/null
+++ b/algorithms/strings/longest_palindromic_substring.py
@@ -0,0 +1,44 @@
+'''
+Given string s, find the longest palindromic substring.
+
+Example1:
+
+* input: "dasdasdasdasdasdadsa"
+* output: "asdadsa"
+
+Example2:
+
+* input: "acdbbdaa"
+* output: "dbbd"
+
+Manacher's algorithm
+
+'''
+
+def longest_palindrome(s):
+    if len(s) < 2:
+        return s
+
+    n_str = '#' + '#'.join(s) + '#'
+    p = [0] * len(n_str)
+    mx, loc = 0, 0
+    index, maxlen = 0, 0
+    for i in range(len(n_str)):
+        if i < mx and 2 * loc - i < len(n_str):
+            p[i] = min(mx - i, p[2 * loc - i])
+        else:
+            p[i] = 1
+
+        while p[i] + i < len(n_str) and i - p[i] >= 0 and n_str[
+                i - p[i]] == n_str[i + p[i]]:
+            p[i] += 1
+
+        if i + p[i] > mx:
+            mx = i + p[i]
+            loc = i
+
+        if p[i] > maxlen:
+            index = i
+            maxlen = p[i]
+    s = n_str[index - p[index] + 1:index + p[index]]
+    return s.replace('#', '')


Test patch:
diff --git a/tests/test_graph.py b/tests/test_graph.py
index 83d3529..325b5d8 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -10,6 +10,7 @@ from algorithms.graph import all_pairs_shortest_path
 from algorithms.graph import bellman_ford
 from algorithms.graph import bellman_ford
 from algorithms.graph import count_connected_number_of_component
+from algorithms.graph import prims_minimum_spanning
 
 import unittest
 
@@ -264,3 +265,23 @@ class TestConnectedComponentInGraph(unittest.TestCase):
         expected_result = 4
         result = count_connected_number_of_component.count_components(l,size)
         self.assertEqual(result,expected_result)
+
+        
+class PrimsMinimumSpanning(unittest.TestCase):
+    def test_prim_spanning(self):
+        graph1 = {
+            1 : [ [3, 2], [8, 3] ],
+            2 : [ [3, 1], [5, 4] ],
+            3 : [ [8, 1], [2, 4], [4, 5] ],
+            4 : [ [5, 2], [2, 3], [6, 5] ],
+            5 : [ [4, 3], [6, 4] ]
+        }
+        self.assertEqual(14, prims_minimum_spanning(graph1))
+        
+        graph2 = {
+            1 : [ [7, 2], [6, 4] ],
+            2 : [ [7, 1], [9, 4], [6, 3] ],
+            3 : [ [8, 4], [6, 2] ],
+            4 : [ [6, 1], [9, 2], [8, 3] ]
+        }
+        self.assertEqual(19, prims_minimum_spanning(graph2))
diff --git a/tests/test_strings.py b/tests/test_strings.py
index 48fafd2..b8750b1 100644
--- a/tests/test_strings.py
+++ b/tests/test_strings.py
@@ -38,6 +38,7 @@ from algorithms.strings import (
     first_unique_char,
     repeat_substring,
     atbash,
+    longest_palindrome,
     knuth_morris_pratt
 )
 
@@ -527,24 +528,44 @@ class TestAtbashCipher(unittest.TestCase):
     Arguments:
         unittest {[type]} -- [description]
     """
-    
+
     def test_atbash_cipher(self):
         self.assertEqual("zyxwvutsrqponml", atbash("abcdefghijklmno"))
         self.assertEqual("KbgslM", atbash("PythoN"))
         self.assertEqual("AttaCK at DawN", atbash("ZggzXP zg WzdM"))
         self.assertEqual("ZggzXP zg WzdM", atbash("AttaCK at DawN"))
+
+
+
+class TestLongestPalindromicSubstring(unittest.TestCase):
+    """[summary]
+    Test for the file longest_palindromic_substring.py
+    
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    
+    def test_longest_palindromic_substring(self):
+        self.assertEqual("bb", longest_palindrome("cbbd"))
+        self.assertEqual("abba", longest_palindrome("abba"))
+        self.assertEqual("asdadsa", longest_palindrome("dasdasdasdasdasdadsa"))
+        self.assertEqual("abba", longest_palindrome("cabba"))
+
         
 class TestKnuthMorrisPratt(unittest.TestCase):
     """[summary]
     Test for the file knuth_morris_pratt.py
 
+
     Arguments:
         unittest {[type]} -- [description]
     """
+
     def test_knuth_morris_pratt(self):
         self.assertEqual([0, 1, 2, 3, 4], knuth_morris_pratt("aaaaaaa", "aaa"))
         self.assertEqual([0, 4], knuth_morris_pratt("abcdabc", "abc"))
         self.assertEqual([], knuth_morris_pratt("aabcdaab", "aba"))
 
+
 if __name__ == "__main__":
     unittest.main()