Formatting and comments.

jwasham · jwasham · commit 078f49b087d8 · 2016-10-28T16:39:28.000-07:00
diff --git a/dynamic_programming/maximum_increasing_subsequence.py b/dynamic_programming/maximum_increasing_subsequence.py
@@ -1,15 +1,20 @@
 
+
 def longest_increasing_subsequence(sequence):
-    sequence_length = len(sequence)
-    T = [1 for i in range(sequence_length)]
+    """
+    Returns the length of the longest increasing non-contiguous sequence
+    """
+    length = len(sequence)
+    counts = [1 for _ in range(length)]
+
+    for i in range(1, length):
+        for j in range(0, i):
+            if sequence[j] < sequence[i]:
+                counts[i] = max(counts[i], counts[j] + 1)
 
-    for index_i in range(1, sequence_length):
-        for index_j in range(0, index_i):
-            if sequence[index_j] < sequence[index_i]:
-                T[index_i] = max(T[index_i], T[index_j] + 1)
+    return max(counts)
 
-    return max(T)
 
 if __name__ == '__main__':
-    sequence = [1, 101, 10, 2, 3, 100, 4]
-    assert 4 == longest_increasing_subsequence(sequence)
+    sequence = [1, 101, 10, 2, 3, 100, 4, 6, 2]
+    assert 5 == longest_increasing_subsequence(sequence)
diff --git a/graphs/directed_graph_list.py b/graphs/directed_graph_list.py
@@ -181,7 +181,7 @@ def topological_sort(self):
     def strongly_connected_components(self):
         """
         Compute the vertices in the strongly connected components
-        :return list of lists, one for each components vertices:
+        :return list of lists, one for each component's vertices:
         """
         stack = self.scc_dfs_forward_pass()
         components = self.scc_dfs_reverse_pass(stack)
@@ -310,14 +310,14 @@ def test_dfs():
 def test_bfs():
     dg1 = get_test_graph_1()
     p1 = dg1.bfs()
-    assert(p1 == {1: 0, 2: 1, 4: 2, 5: 0, 6: 2, 8: 5})
+    assert (p1 == {1: 0, 2: 1, 4: 2, 5: 0, 6: 2, 8: 5})
 
 
 def test_contains_cycle():
-    assert(get_test_graph_1().contains_cycle() == False)
-    assert(get_test_graph_2().contains_cycle() == False)
-    assert(get_test_graph_3().contains_cycle() == False)
-    assert(get_test_graph_4().contains_cycle() == True)
+    assert (get_test_graph_1().contains_cycle() == False)
+    assert (get_test_graph_2().contains_cycle() == False)
+    assert (get_test_graph_3().contains_cycle() == False)
+    assert (get_test_graph_4().contains_cycle() == True)
 
 
 def test_topological_sort():
@@ -329,10 +329,10 @@ def test_topological_sort():
 def test_strongly_connected_components():
     dg = get_test_graph_5()
 
-    assert(dg.contains_cycle())
+    assert (dg.contains_cycle())
 
     components = dg.strongly_connected_components()
-    assert(components == [[10, 11, 9, 8], [7], [0], [1, 3, 2], [6, 4, 5]])
+    assert (components == [[10, 11, 9, 8], [7], [0], [1, 3, 2], [6, 4, 5]])
 
 
 def main():
@@ -344,5 +344,6 @@ def main():
 
     print("Tests complete.")
 
+
 if __name__ == "__main__":
     main()
diff --git a/hashes/hash-test.py b/hashes/hash-test.py
@@ -3,6 +3,7 @@
 import scipy
 import matplotlib.pyplot as plt
 
+
 # This script will test multiple hashes on strings to see if we get a uniform distribution
 
 
@@ -93,9 +94,7 @@ def polyhash_noprime(word, a, m):
     return abs(hash % m)
 
 
-
 def show_distribution(buckets, title):
-
     counts = {}
     for v in buckets:
         if v in counts.keys():
@@ -147,5 +146,6 @@ def main():
 
     show_distribution(buckets, "Bucket size distribution - PolyHash, no prime")
 
+
 if __name__ == "__main__":
     main()
diff --git a/puzzles/.gitignore b/puzzles/.gitignore
