Repository: keon/algorithms
Pull request #407 (2018-09-21 23:35:05)

Add edit distance DP problem
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [ ] **If creating a new file :**
  - [ ] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space compleixty, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


coveralls: ## Pull Request Test Coverage Report for [Build 745](https://coveralls.io/builds/19133542)

* **0** of **0**   changed or added relevant lines in **0** files are covered.
* **1** unchanged line in **1** file lost coverage.
* Overall coverage remained the same at **71.552%**

---


|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [algorithms/linkedlist/is_palindrome.py](https://coveralls.io/builds/19133542/source?filename=algorithms%2Flinkedlist%2Fis_palindrome.py#L88) | 1 | 93.33% |
<!-- | **Total:** | **1** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/19133542/badge)](https://coveralls.io/builds/19133542) |
| :-- | --: |
| Change from base [Build 742](https://coveralls.io/builds/18880653): |  0.0% |
| Covered Lines: | 4306 |
| Relevant Lines: | 6018 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/.vscode/settings.json b/.vscode/settings.json
new file mode 100644
index 0000000..9d17a27
--- /dev/null
+++ b/.vscode/settings.json
@@ -0,0 +1,3 @@
+{
+    "python.pythonPath": "C:\\Program Files (x86)\\Microsoft Visual Studio\\Shared\\Python36_64\\python.exe"
+}
\ No newline at end of file
diff --git a/README.md b/README.md
index 7ed8694..aecd53b 100644
--- a/README.md
+++ b/README.md
@@ -75,10 +75,10 @@ If you want to uninstall algorithms, it is as simple as:
     - [n_sum](algorithms/arrays/n_sum.py)
 - [backtrack](algorithms/backtrack)
     - [general_solution.md](algorithms/backtrack/)
+    - [add_operators](algorithms/backtrack/add_operators.py)
     - [anagram](algorithms/backtrack/anagram.py)
     - [array_sum_combinations](algorithms/backtrack/array_sum_combinations.py)
     - [combination_sum](algorithms/backtrack/combination_sum.py)
-    - [expression_add_operators](algorithms/backtrack/expression_add_operators.py)
     - [factor_combinations](algorithms/backtrack/factor_combinations.py)
     - [generate_abbreviations](algorithms/backtrack/generate_abbreviations.py)
     - [generate_parenthesis](algorithms/backtrack/generate_parenthesis.py)
@@ -142,7 +142,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [fibonacci](algorithms/dp/fib.py)
 - [graph](algorithms/graph)
     - [check_bipartite](algorithms/graph/check_bipartite.py)
-    - [strongly_connected](algorithms/graph/checkDiGraphStronglyConnected.py)
+    - [strongly_connected](algorithms/graph/check_digraph_strongly_connected.py)
     - [clone_graph](algorithms/graph/clone_graph.py)
     - [cycle_detection](algorithms/graph/cycle_detection.py)
     - [find_all_cliques](algorithms/graph/find_all_cliques.py)
@@ -186,6 +186,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [base_conversion](algorithms/maths/base_conversion.py)
     - [combination](algorithms/maths/combination.py)
     - [decimal_to_binary_ip](algorithms/maths/decimal_to_binary_ip.py)
+    - [euler_totient](algorithms/maths/euler_totient.py)
     - [extended_gcd](algorithms/maths/extended_gcd.py)
     - [factorial](algorithms/maths/factorial.py)    
     - [gcd/lcm](algorithms/maths/gcd.py)
@@ -221,8 +222,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [zigzagiterator](algorithms/queues/zigzagiterator.py)
 - [search](algorithms/search)
     - [binary_search](algorithms/search/binary_search.py)
-    - [first_occurance](algorithms/search/first_occurance.py)
-    - [last_occurance](algorithms/search/last_occurance.py)
+    - [first_occurrence](algorithms/search/first_occurrence.py)
+    - [last_occurrence](algorithms/search/last_occurrence.py)
     - [linear_search](algorithms/search/linear_search.py)
     - [search_insert](algorithms/search/search_insert.py)
     - [two_sum](algorithms/search/two_sum.py)
@@ -269,7 +270,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [is_sorted](algorithms/stack/is_sorted.py)
 - [strings](algorithms/strings)
     - [fizzbuzz](algorithms/strings/fizzbuzz.py)
-    - [delete_reoccurring_characters](algorithms/strings/delete_reoccurring_characters.py)
+    - [delete_reoccurring](algorithms/strings/delete_reoccurring.py)
     - [strip_url_params](algorithms/strings/strip_url_params.py)
     - [validate_coordinates](algorithms/strings/validate_coordinates.py)
     - [domain_extractor](algorithms/strings/domain_extractor.py)
@@ -304,8 +305,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [first_unique_char](algorithms/strings/first_unique_char.py)
     - [repeat_substring](algorithms/strings/repeat_substring.py)     
 - [tree](algorithms/tree)
-    - [bst](algorithms/tree/tree/bst)
-        - [array2bst](algorithms/tree/bst/array2bst.py)
+    - [bst](algorithms/tree/bst)
+        - [array_to_bst](algorithms/tree/bst/array_to_bst.py)
         - [bst_closest_value](algorithms/tree/bst/bst_closest_value.py)
         - [BSTIterator](algorithms/tree/bst/BSTIterator.py)
         - [delete_node](algorithms/tree/bst/delete_node.py)
@@ -334,7 +335,7 @@ If you want to uninstall algorithms, it is as simple as:
         - [add_and_search](algorithms/tree/trie/add_and_search.py)
         - [trie](algorithms/tree/trie/trie.py)
     - [binary_tree_paths](algorithms/tree/binary_tree_paths.py)
-    - [bintree2list](algorithms/tree/bintree2list.py)
+    - [bin_tree_to_list](algorithms/tree/bin_tree_to_list.py)
     - [deepest_left](algorithms/tree/deepest_left.py)
     - [invert_tree](algorithms/tree/invert_tree.py)
     - [is_balanced](algorithms/tree/is_balanced.py)
diff --git a/algorithms/arrays/flatten.py b/algorithms/arrays/flatten.py
index f2eba48..4133c34 100644
--- a/algorithms/arrays/flatten.py
+++ b/algorithms/arrays/flatten.py
@@ -12,9 +12,9 @@ def flatten(input_arr, output_arr=None):
         output_arr = []
     for ele in input_arr:
         if isinstance(ele, Iterable):
-            flatten(ele, output_arr)
+            flatten(ele, output_arr)    #tail-recursion
         else:
-            output_arr.append(ele)
+            output_arr.append(ele)      #produce the result
     return output_arr
 
 
@@ -26,6 +26,6 @@ def flatten_iter(iterable):
     """
     for element in iterable:
         if isinstance(element, Iterable):
-            yield from flatten_iter(element)
+            yield from flatten_iter(element)    
         else:
             yield element
diff --git a/algorithms/arrays/garage.py b/algorithms/arrays/garage.py
index d590343..474655a 100644
--- a/algorithms/arrays/garage.py
+++ b/algorithms/arrays/garage.py
@@ -34,14 +34,14 @@ Sequence :
 
 def garage(initial, final):
 
-    initial = initial[::]     # create a copy to prevent changes in original 'initial'.
+    initial = initial[::]      # prevent changes in original 'initial'
+    seq = []                   # list of each step in sequence
     steps = 0
-    seq = []                  # list of each step in sequence
     while initial != final:
         zero = initial.index(0)
-        if zero != final.index(0):
-            car_to_move = final[zero]
-            pos = initial.index(car_to_move)
+        if zero != final.index(0):  # if zero isn't where it should be,
+            car_to_move = final[zero]   # what should be where zero is,
+            pos = initial.index(car_to_move)         # and where is it?
             initial[zero], initial[pos] = initial[pos], initial[zero]
         else:
             for i in range(len(initial)):
@@ -51,4 +51,18 @@ def garage(initial, final):
         seq.append(initial[::])
         steps += 1
 
-    return steps, seq
+    return steps, seq       
+    # e.g.:  4, [{0, 2, 3, 1, 4}, {2, 0, 3, 1, 4}, 
+    #            {2, 3, 0, 1, 4}, {0, 3, 2, 1, 4}]
+
+"""
+thus:
+1 2 3 0 4 -- zero = 3, true, car_to_move = final[3] = 1,
+             pos = initial.index(1) = 0, switched [0], [3]
+0 2 3 1 4 -- zero = 0, f, initial[1] != final[1], switched 0,1
+2 0 3 1 4 -- zero = 1, t, car_to_move = final[1] = 3,
+             pos = initial.index(3) = 2, switched [1], [2]
+2 3 0 1 4 -- zero = 2, t, car_to_move = final[2] = 2, 
+             pos = initial.index(2) = 0, switched [0], [2]
+0 3 2 1 4 -- initial == final
+"""
\ No newline at end of file
diff --git a/algorithms/arrays/josephus.py b/algorithms/arrays/josephus.py
index f77c48a..3d0ad23 100644
--- a/algorithms/arrays/josephus.py
+++ b/algorithms/arrays/josephus.py
@@ -11,10 +11,10 @@ Output: 369485271
 
 
 def josephus(int_list, skip):
-    skip = skip - 1  # list starts with 0 index
+    skip = skip - 1                     # list starts with 0 index
     idx = 0
     len_list = (len(int_list))
     while len_list > 0:
-        idx = (skip+idx) % len_list  # hash index to every 3rd
+        idx = (skip + idx) % len_list   # hash index to every 3rd
         yield int_list.pop(idx)
         len_list -= 1
diff --git a/algorithms/arrays/limit.py b/algorithms/arrays/limit.py
index adcc577..131d16e 100644
--- a/algorithms/arrays/limit.py
+++ b/algorithms/arrays/limit.py
@@ -1,22 +1,23 @@
 """
-Sometimes you need to limit array result to use. Such as you only need the value over
-10 or, you need value under than 100. By use this algorithms, you can limit your array
-to specific value
+Sometimes you need to limit array result to use. Such as you only need the 
+ value over 10 or, you need value under than 100. By use this algorithms, you
+ can limit your array to specific value
 
-If array, Min, Max value was given, it returns array that contains values of given array
-which was larger than Min, and lower than Max. You need to give 'unlimit' to use only Min
-or Max.
+If array, Min, Max value was given, it returns array that contains values of 
+ given array which was larger than Min, and lower than Max. You need to give
+ 'unlimit' to use only Min or Max.
 
 ex) limit([1,2,3,4,5], None, 3) = [1,2,3]
 
 Complexity = O(n)
 """
 
+# tl:dr -- array slicing by value
 def limit(arr, min_lim = None, max_lim = None):
     result = []
     if min_lim == None:
         for i in arr:
-            if i<= max_lim:
+            if i <= max_lim:
                 result.append(i)
     elif max_lim == None:
         for i in arr:
diff --git a/algorithms/arrays/longest_non_repeat.py b/algorithms/arrays/longest_non_repeat.py
index 1d083fb..cad3d24 100644
--- a/algorithms/arrays/longest_non_repeat.py
+++ b/algorithms/arrays/longest_non_repeat.py
@@ -1,6 +1,7 @@
 """
 Given a string, find the length of the longest substring
 without repeating characters.
+
 Examples:
 Given "abcabcbb", the answer is "abc", which the length is 3.
 Given "bbbbb", the answer is "b", with the length of 1.
@@ -12,7 +13,8 @@ Note that the answer must be a substring,
 
 def longest_non_repeat_v1(string):
     """
-    Apply slide windown.
+    Find the length of the longest substring
+    without repeating characters.
     """
     dict = {}
     max_length = 0
@@ -24,10 +26,9 @@ def longest_non_repeat_v1(string):
         max_length = max(max_length, i - j + 1)
     return max_length
 
-
 def longest_non_repeat_v2(string):
     """
-    Finds the length of the longest substring
+    Find the length of the longest substring
     without repeating characters.
     Uses alternative algorithm.
     """
@@ -42,3 +43,40 @@ def longest_non_repeat_v2(string):
             max_len = max(max_len, index - start + 1)
         used_char[char] = index
     return max_len
+
+# get functions of above, returning the max_len and substring
+def get_longest_non_repeat_v1(string):
+    """
+    Find the length of the longest substring
+    without repeating characters.
+    Return max_len and the substring as a tuple
+    """
+    if string is None:
+        return 0
+    temp = []
+    max_len = 0
+    for i in string:
+        if i in temp:
+            temp = []
+        temp.append(i)
+        max_len = max(max_len, len(temp))
+    return max_len, temp
+
+def get_longest_non_repeat_v2(string):
+    """
+    Find the length of the longest substring
+    without repeating characters.
+    Uses alternative algorithm.
+    Return max_len and the substring as a tuple
+    """
+    if string is None:
+        return 0
+    start, max_len = 0, 0
+    used_char = {}
+    for index, char in enumerate(string):
+        if char in used_char and start <= used_char[char]:
+            start = used_char[char] + 1
+        else:
+            max_len = max(max_len, index - start + 1)
+        used_char[char] = index
+    return max_len, start
\ No newline at end of file
diff --git a/algorithms/arrays/merge_intervals.py b/algorithms/arrays/merge_intervals.py
index ee9ce60..fae4162 100644
--- a/algorithms/arrays/merge_intervals.py
+++ b/algorithms/arrays/merge_intervals.py
@@ -1,15 +1,16 @@
 """
-Given a collection of intervals, merge all overlapping intervals.
+In mathematics, a (real) interval is a set of real
+ numbers with the property that any number that lies
+ between two numbers in the set is also included in the set.
 """
 
 
 class Interval:
     """
-    In mathematics, a (real) interval is a set of real
-    numbers with the property that any number that lies
-    between two numbers in the set is also included in the set.
+    A set of real numbers with methods to determine if other
+     numbers are included in the set.
+    Includes related methods to merge and print interval sets.
     """
-
     def __init__(self, start=0, end=0):
         self.start = start
         self.end = end
@@ -44,7 +45,7 @@ class Interval:
 
     @staticmethod
     def merge(intervals):
-        """ Merges two intervals into one. """
+        """ Merge two intervals into one. """
         out = []
         for i in sorted(intervals, key=lambda i: i.start):
             if out and i.start <= out[-1].end:
@@ -55,9 +56,7 @@ class Interval:
 
     @staticmethod
     def print_intervals(intervals):
-        """
-        Prints out the intervals.
-        """
+        """ Print out the intervals. """
         res = []
         for i in intervals:
             res.append(repr(i))
@@ -65,7 +64,7 @@ class Interval:
 
 
 def merge_intervals(intervals):
-    """ Merges intervals in the form of list. """
+    """ Merge intervals in the form of a list. """
     if intervals is None:
         return None
     intervals.sort(key=lambda i: i[0])
diff --git a/algorithms/arrays/missing_ranges.py b/algorithms/arrays/missing_ranges.py
index 68fcc43..7f34bcd 100644
--- a/algorithms/arrays/missing_ranges.py
+++ b/algorithms/arrays/missing_ranges.py
@@ -3,7 +3,6 @@ Find missing ranges between low and high in the given array.
 Ex) [3, 5] lo=1 hi=10 => answer: [(1, 2), (4, 4), (6, 10)]
 """
 
-
 def missing_ranges(arr, lo, hi):
 
     res = []
@@ -17,7 +16,7 @@ def missing_ranges(arr, lo, hi):
             res.append((start, n-1))
             start = n + 1
 
-    if start <= hi:
-        res.append((start, hi))
+    if start <= hi:                 # after done iterating thru array,
+        res.append((start, hi))     # append remainder to list
 
     return res
diff --git a/algorithms/arrays/n_sum.py b/algorithms/arrays/n_sum.py
index a01348e..da7ee36 100644
--- a/algorithms/arrays/n_sum.py
+++ b/algorithms/arrays/n_sum.py
@@ -2,30 +2,32 @@
 Given an array of n integers, are there elements a, b, .. , n in nums
 such that a + b + .. + n = target?
 
-Find all unique triplets in the array which gives the sum of target.
+Find all unique n-tuplets in the array which gives the sum of target.
 
 Example:
     basic:
         Given:
-            n = 4, nums = [1, 0, -1, 0, -2, 2], target = 0,
+            n = 4
+            nums = [1, 0, -1, 0, -2, 2]
+            target = 0,
         return [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
 
     advanced:
         Given:
             n = 2
             nums = [[-3, 0], [-2, 1], [2, 2], [3, 3], [8, 4], [-9, 5]]
-            taget = -5
+            target = -5
             def sum(a, b):
                 return [a[0] + b[1], a[1] + b[0]]
-            def compare(num, taget):
-                if num[0] < taget:
+            def compare(num, target):
+                if num[0] < target:
                     return -1
-                elif if num[0] > taget:
+                elif if num[0] > target:
                     return 1
                 else:
                     return 0
         return [[-9, 5], [8, 4]]
-        because -9 + 4 = -5
+(TL:DR) because -9 + 4 = -5
 """
 
 
@@ -35,24 +37,26 @@ def n_sum(n, nums, target, **kv):
     nums: list[object]
     target: object
     sum_closure: function, optional
-                 Given two elements of nums, return sum of both.
+        Given two elements of nums, return sum of both.
     compare_closure: function, optional
-                     Given one object of nums and target, return one of -1, 1, or 0.
+        Given one object of nums and target, return -1, 1, or 0.
     same_closure: function, optional
-                  Given two object of nums, return bool.
+        Given two object of nums, return bool.
     return: list[list[object]]
 
     Note:
-    1. type of sum_closure's return should be same as type of compare_closure's first param
+    1. type of sum_closure's return should be same 
+       as type of compare_closure's first param
     """
 
     def sum_closure_default(a, b):
         return a + b
 
-    def compare_closure_default(num, taget):
-        if num < taget:
+    def compare_closure_default(num, target):
+        """ above, below, or right on? """
+        if num < target:
             return -1
-        elif num > taget:
+        elif num > target:
             return 1
         else:
             return 0
@@ -61,7 +65,7 @@ def n_sum(n, nums, target, **kv):
         return a == b
 
     def n_sum(n, nums, target):
-        if n == 2:
+        if n == 2:      # want answers with only 2 terms? easy!
             results = two_sum(nums, target)
         else:
             results = []
@@ -70,12 +74,19 @@ def n_sum(n, nums, target, **kv):
                 if prev_num is not None and \
                    same_closure(prev_num, num):
                     continue
+
                 prev_num = num
-                n_minus1_results = n_sum(n - 1,
-                                         nums[index + 1:],
-                                         target - num)
-                n_minus1_results = append_elem_to_each_list(num,
-                                                            n_minus1_results)
+                n_minus1_results = (
+                    n_sum(                      # recursive call
+                        n - 1,                  # a
+                        nums[index + 1:],       # b
+                        target - num            # c
+                        )   # x = n_sum( a, b, c )
+                    )   # n_minus1_results = x
+
+                n_minus1_results = (
+                    append_elem_to_each_list(num, n_minus1_results)
+                    )
                 results += n_minus1_results
         return union(results)
 
diff --git a/algorithms/arrays/plus_one.py b/algorithms/arrays/plus_one.py
index d5bf347..473b6c7 100644
--- a/algorithms/arrays/plus_one.py
+++ b/algorithms/arrays/plus_one.py
@@ -1,8 +1,8 @@
 """
 Given a non-negative number represented as an array of digits,
-plus one to the number.
+adding one to each numeral.
 
-The digits are stored such that the most significant
+The digits are stored big-endian, such that the most significant
 digit is at the head of the list.
 """
 
@@ -41,8 +41,8 @@ def plus_one_v2(digits):
 
 def plus_one_v3(num_arr):
 
-    for idx, digit in reversed(list(enumerate(num_arr))):
-        num_arr[idx] = (num_arr[idx] + 1) % 10
-        if num_arr[idx]:
+    for idx in reversed(list(enumerate(num_arr))):
+        num_arr[idx[0]] = (num_arr[idx[0]] + 1) % 10
+        if num_arr[idx[0]]:
             return num_arr
     return [1] + num_arr
diff --git a/algorithms/arrays/rotate.py b/algorithms/arrays/rotate.py
index d90035b..974b511 100644
--- a/algorithms/arrays/rotate.py
+++ b/algorithms/arrays/rotate.py
@@ -21,7 +21,7 @@ def rotate_v1(array, k):
     """
     array = array[:]
     n = len(array)
-    for i in range(k):
+    for i in range(k):      # unused variable is not a problem
         temp = array[n - 1]
         for j in range(n-1, 0, -1):
             array[j] = array[j - 1]
diff --git a/algorithms/arrays/three_sum.py b/algorithms/arrays/three_sum.py
index 524b83e..ccf3d26 100644
--- a/algorithms/arrays/three_sum.py
+++ b/algorithms/arrays/three_sum.py
@@ -1,6 +1,6 @@
 """
-Given an array S of n integers, are there elements a, b, c in S
-such that a + b + c = 0?
+Given an array S of n integers, are there three distinct elements
+a, b, c in S such that a + b + c = 0?
 Find all unique triplets in the array which gives the sum of zero.
 
 Note: The solution set must not contain duplicate triplets.
diff --git a/algorithms/arrays/top_1.py b/algorithms/arrays/top_1.py
index dea9aa2..71ac6b0 100644
--- a/algorithms/arrays/top_1.py
+++ b/algorithms/arrays/top_1.py
@@ -1,11 +1,15 @@
 """
-this algorithms receive array and check most_frequent_value(a.k.a mode). Also, sometimes it can be have numerous most_frequent_value,
-so this funtion returns list. This result can be used as finding representative value on array.
+This algorithm receives an array and returns most_frequent_value
+Also, sometimes it is possible to have multiple 'most_frequent_value's,
+so this function returns a list. This result can be used to find a 
+representative value in an array.
 
-This algorithms get array, and make dictionary of it, find most frequent count, and make result list.
+This algorithm gets an array, makes a dictionary of it,
+ finds the most frequent count, and makes the result list.
 
-For example) top_1([1, 1, 2, 2, 3, 4]) will return [1, 2]
+For example: top_1([1, 1, 2, 2, 3, 4]) will return [1, 2]
 
+(TL:DR) Get mathematical Mode
 Complexity: O(n)
 """
 def top_1(arr):
@@ -30,3 +34,4 @@ def top_1(arr):
             continue
     
     return result
+    
\ No newline at end of file
diff --git a/algorithms/arrays/trimmean.py b/algorithms/arrays/trimmean.py
index 4cea0db..3d330a0 100644
--- a/algorithms/arrays/trimmean.py
+++ b/algorithms/arrays/trimmean.py
@@ -1,9 +1,12 @@
 """
-When make reliable means, we need to neglect best and worst value. For example, when making average score on athletes we need this option.
-So, this algorithms, fix some percentage to neglect when making mean. For example, if you suggest 20%, it will neglect best 10% value, and
-worst 10% value.
+When make reliable means, we need to neglect best and worst values.
+For example, when making average score on athletes we need this option.
+So, this algorithm affixes some percentage to neglect when making mean.
+For example, if you suggest 20%, it will neglect the best 10% of values
+and the worst 10% of values.
 
-This algorithm gets array and percentage to neglect. After sorted, if index of array is larger or smaller or wanted ratio, we don't
+This algorithm takes an array and percentage to neglect. After sorted,
+if index of array is larger or smaller than desired ratio, we don't
 compute it.
 
 Compleity: O(n)
@@ -18,5 +21,4 @@ def trimmean(arr, per):
     arr = arr[neg_val:len(arr)-neg_val]
     for i in arr:
         cal_sum += i
-    #print(cal_sum, len(arr))
     return cal_sum/len(arr)
diff --git a/algorithms/dp/__init__.py b/algorithms/dp/__init__.py
new file mode 100644
index 0000000..174f524
--- /dev/null
+++ b/algorithms/dp/__init__.py
@@ -0,0 +1,1 @@
+from .edit_distance import *
diff --git a/algorithms/dp/edit_distance.py b/algorithms/dp/edit_distance.py
new file mode 100644
index 0000000..ecf6beb
--- /dev/null
+++ b/algorithms/dp/edit_distance.py
@@ -0,0 +1,54 @@
+"""The edit distance between two words is the minimum number of letter insertions,
+letter deletions, and letter substitutions required to transform one word into another.
+
+For example, the edit distance between FOOD and MONEY is at most four:
+
+FOOD -> MOOD -> MOND -> MONED -> MONEY
+
+Given two words A and B, find the minimum number of operations required to transform one string into the other.
+In other words, find the edit distance between A and B.
+
+Thought process:
+
+Let edit(i, j) denote the edit distance between the prefixes A[1..i] and B[1..j].
+
+Then, the function satifies the following recurrence:
+
+edit(i, j) = i if j = 0
+             j if i = 0
+             min(edit(i-1, j) + 1, 
+                 edit(i, j-1), + 1,
+                 edit(i-1, j-1) + cost) otherwise
+
+There are two base cases, both of which occur when one string is empty and the other is not.
+1. To convert an empty string A into a string B of length n, perform n insertions.
+2. To convert a string A of length m into an empty string B, perform m deletions.
+
+Here, the cost is 1 if a substitution is required,
+or 0 if both chars in words A and B are the same at indexes i and j, respectively.
+
+To find the edit distance between two words A and B,
+we need to find edit(m, n), where m is the length of A and n is the length of B.
+"""
+
+
+def edit_distance(A, B):
+    # Time: O(m*n)
+    # Space: O(m*n)
+
+    m, n = len(A) + 1, len(B) + 1
+
+    edit = [[0 for _ in range(n)] for _ in range(m)]
+
+    for i in range(1, m):
+        edit[i][0] = i
+
+    for j in range(1, n):
+        edit[0][j] = j
+
+    for i in range(1, m):
+        for j in range(1, n):
+            cost = 0 if A[i - 1] == B[j - 1] else 1
+            edit[i][j] = min(edit[i - 1][j] + 1, edit[i][j - 1] + 1, edit[i - 1][j - 1] + cost)
+
+    return edit[-1][-1]  # this is the same as edit[m][n]
diff --git a/algorithms/linkedlist/__init__.py b/algorithms/linkedlist/__init__.py
index 21263bf..1c9c3b9 100644
--- a/algorithms/linkedlist/__init__.py
+++ b/algorithms/linkedlist/__init__.py
@@ -6,3 +6,4 @@ from .rotate_list import *
 from .is_cyclic import *
 from .merge_two_list import *
 from .is_palindrome import *
+from .copy_random_pointer import *
diff --git a/algorithms/linkedlist/copy_random_pointer.py b/algorithms/linkedlist/copy_random_pointer.py
index 7653d49..b3ef462 100644
--- a/algorithms/linkedlist/copy_random_pointer.py
+++ b/algorithms/linkedlist/copy_random_pointer.py
@@ -4,35 +4,45 @@ pointer which could point to any node in the list or null.
 
 Return a deep copy of the list.
 """
-# from collections import defaultdict
+from collections import defaultdict
 
-# TODO: This requires to be rewritten -- commenting it out for now
-# class Solution0:
-  # @param head, a RandomListNode
-  # @return a RandomListNode
-  # def copyRandomList(self, head):
-  #   dic = dict()
-  #   m = n = head
-  #   while m:
-  #       dic[m] = RandomListNode(m.label)
-  #       m = m.next
-  #   while n:
-  #       dic[n].next = dic.get(n.next)
-  #       dic[n].random = dic.get(n.random)
-  #       n = n.next
-  #   return dic.get(head)
-#
-#
-# class Solution1:  # O(n)
-#   @param head, a RandomListNode
-#   @return a RandomListNode
-  # def copyRandomList(self, head):
-  #   copy = defaultdict(lambda: RandomListNode(0))
-  #   copy[None] = None
-  #   node = head
-  #   while node:
-  #       copy[node].label = node.label
-  #       copy[node].next = copy[node.next]
-  #       copy[node].random = copy[node.random]
-  #       node = node.next
-  #   return copy[head]
+
+class RandomListNode(object):
+    def __init__(self, label):
+        self.label = label
+        self.next = None
+        self.random = None
+
+
+def copy_random_pointer_v1(head):
+    """
+    :type head: RandomListNode
+    :rtype: RandomListNode
+    """
+    dic = dict()
+    m = n = head
+    while m:
+        dic[m] = RandomListNode(m.label)
+        m = m.next
+    while n:
+        dic[n].next = dic.get(n.next)
+        dic[n].random = dic.get(n.random)
+        n = n.next
+    return dic.get(head)
+
+
+# O(n)
+def copy_random_pointer_v2(head):
+    """
+    :type head: RandomListNode
+    :rtype: RandomListNode
+    """
+    copy = defaultdict(lambda: RandomListNode(0))
+    copy[None] = None
+    node = head
+    while node:
+        copy[node].label = node.label
+        copy[node].next = copy[node.next]
+        copy[node].random = copy[node.random]
+        node = node.next
+    return copy[head]
diff --git a/algorithms/maths/__init__.py b/algorithms/maths/__init__.py
index 177fed3..7a3fb7b 100644
--- a/algorithms/maths/__init__.py
+++ b/algorithms/maths/__init__.py
@@ -1,5 +1,6 @@
 from .base_conversion import *
 from .decimal_to_binary_ip import *
+from .euler_totient import *
 from .extended_gcd import *
 from .factorial import *
 from .gcd import *
diff --git a/algorithms/maths/euler_totient.py b/algorithms/maths/euler_totient.py
new file mode 100644
index 0000000..047b728
--- /dev/null
+++ b/algorithms/maths/euler_totient.py
@@ -0,0 +1,18 @@
+"""
+Euler's totient function, also known as phi-function ϕ(n),
+counts the number of integers between 1 and n inclusive,
+which are coprime to n.
+(Two numbers are coprime if their greatest common divisor (GCD) equals 1).
+"""
+def euler_totient(n):
+    """Euler's totient function or Phi function.
+    Time Complexity: O(sqrt(n))."""
+    result = n;
+    for i in range(2, int(n ** 0.5) + 1):
+        if n % i == 0:
+            while n % i == 0:
+                n //= i
+            result -= result // i
+    if n > 1:
+        result -= result // n;
+    return result;
diff --git a/algorithms/sort/bubble_sort.py b/algorithms/sort/bubble_sort.py
index 76c9816..84f4067 100644
--- a/algorithms/sort/bubble_sort.py
+++ b/algorithms/sort/bubble_sort.py
@@ -20,10 +20,11 @@ def bubble_sort(arr, simulation=False):
     iteration = 0
     if simulation:
         print("iteration",iteration,":",*arr)
-    
+    x = -1
     while swapped:
         swapped = False
-        for i in range(1, n):
+        x = x + 1
+        for i in range(1, n-x):
             if arr[i - 1] > arr[i]:
                 swap(i - 1, i)
                 swapped = True
diff --git a/algorithms/tree/is_symmetric.py b/algorithms/tree/is_symmetric.py
index 3aff3cf..0fd56b9 100644
--- a/algorithms/tree/is_symmetric.py
+++ b/algorithms/tree/is_symmetric.py
@@ -46,7 +46,7 @@ def is_symmetric_iterative(root):
             return False
         if left.val == right.val:
             stack.append([left.left, right.right])
-            stack.append([left.right, right.right])
+            stack.append([left.right, right.left])
         else:
             return False
     return True


Test patch:
diff --git a/tests/test_dp.py b/tests/test_dp.py
new file mode 100644
index 0000000..bbec085
--- /dev/null
+++ b/tests/test_dp.py
@@ -0,0 +1,16 @@
+from algorithms.dp import (
+    edit_distance
+)
+
+
+import unittest
+
+
+class TestEditDistance(unittest.TestCase):
+    def test_edit_distance(self):
+        self.assertEqual(edit_distance('food', 'money'), 4)
+        self.assertEqual(edit_distance('horse', 'ros'), 3)
+
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/tests/test_linkedlist.py b/tests/test_linkedlist.py
index 435ac72..6b7f1f4 100644
--- a/tests/test_linkedlist.py
+++ b/tests/test_linkedlist.py
@@ -1,3 +1,5 @@
+import unittest
+
 from algorithms.linkedlist import (
     reverse_list, reverse_list_recursive,
     is_sorted,
@@ -6,16 +8,17 @@ from algorithms.linkedlist import (
     rotate_right,
     is_cyclic,
     merge_two_list, merge_two_list_recur,
-    is_palindrome, is_palindrome_stack, is_palindrome_dict
+    is_palindrome, is_palindrome_stack, is_palindrome_dict,
+    RandomListNode, copy_random_pointer_v1, copy_random_pointer_v2
 )
 
-import unittest
 
 class Node(object):
     def __init__(self, x):
         self.val = x
         self.next = None
 
+
 # Convert from linked list Node to list for testing
 def convert(head):
     ret = []
@@ -26,6 +29,7 @@ def convert(head):
             current = current.next
     return ret
 
+
 class TestSuite(unittest.TestCase):
     def setUp(self):
         # list test for palindrome
@@ -69,7 +73,6 @@ class TestSuite(unittest.TestCase):
         self.assertFalse(is_sorted(head))
 
     def test_remove_range(self):
-
         # Test case: middle case.
         head = Node(0)
         head.next = Node(1)
@@ -163,12 +166,50 @@ class TestSuite(unittest.TestCase):
     def test_is_palindrome(self):
         self.assertTrue(is_palindrome(self.l))
         self.assertFalse(is_palindrome(self.l1))
+
     def test_is_palindrome_stack(self):
         self.assertTrue(is_palindrome_stack(self.l))
         self.assertFalse(is_palindrome_stack(self.l1))
+
     def test_is_palindrome_dict(self):
         self.assertTrue(is_palindrome_dict(self.l))
         self.assertFalse(is_palindrome_dict(self.l1))
 
+    def test_solution_0(self):
+        self._init_random_list_nodes()
+        result = copy_random_pointer_v1(self.random_list_node1)
+        self._assert_is_a_copy(result)
+
+    def test_solution_1(self):
+        self._init_random_list_nodes()
+        result = copy_random_pointer_v2(self.random_list_node1)
+        self._assert_is_a_copy(result)
+
+    def _assert_is_a_copy(self, result):
+        self.assertEqual(5, result.next.next.next.next.label)
+        self.assertEqual(4, result.next.next.next.label)
+        self.assertEqual(3, result.next.next.label)
+        self.assertEqual(2, result.next.label)
+        self.assertEqual(1, result.label)
+        self.assertEqual(3, result.next.next.next.next.random.label)
+        self.assertIsNone(result.next.next.next.random)
+        self.assertEqual(2, result.next.next.random.label)
+        self.assertEqual(5, result.next.random.label)
+        self.assertEqual(4, result.random.label)
+
+    def _init_random_list_nodes(self):
+        self.random_list_node1 = RandomListNode(1)
+        random_list_node2 = RandomListNode(2)
+        random_list_node3 = RandomListNode(3)
+        random_list_node4 = RandomListNode(4)
+        random_list_node5 = RandomListNode(5)
+
+        self.random_list_node1.next, self.random_list_node1.random = random_list_node2, random_list_node4
+        random_list_node2.next, random_list_node2.random = random_list_node3, random_list_node5
+        random_list_node3.next, random_list_node3.random = random_list_node4, random_list_node2
+        random_list_node4.next = random_list_node5
+        random_list_node5.random = random_list_node3
+
+
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_maths.py b/tests/test_maths.py
index 2499a4f..0777f9a 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -1,6 +1,7 @@
 from algorithms.maths import (
     int_to_base, base_to_int,
     decimal_to_binary_ip,
+    euler_totient,
     extended_gcd,
     factorial, factorial_recur,
     gcd, lcm,
@@ -36,8 +37,8 @@ class TestBaseConversion(unittest.TestCase):
         self.assertEqual(5, base_to_int("101", 2))
         self.assertEqual(0, base_to_int("0", 2))
         self.assertEqual(255, base_to_int("FF", 16))
-        
-        
+
+
 class TestDecimalToBinaryIP(unittest.TestCase):
     """
     Test for the file decimal_to_binary_ip.py
@@ -55,6 +56,21 @@ class TestDecimalToBinaryIP(unittest.TestCase):
                          decimal_to_binary_ip("192.168.0.1"))
 
 
+class TestEulerTotient(unittest.TestCase):
+    """[summary]
+    Test for the file euler_totient.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_euler_totient(self):
+        self.assertEqual(4, euler_totient(8))
+        self.assertEqual(12, euler_totient(21))
+        self.assertEqual(311040, euler_totient(674614))
+        self.assertEqual(2354352, euler_totient(3435145))
+
+
 class TestExtendedGcd(unittest.TestCase):
     """[summary]
     Test for the file extended_gcd.py
@@ -274,4 +290,3 @@ class TestFactorial(unittest.TestCase):
 
 if __name__ == "__main__":
     unittest.main()
-