Repository: keon/algorithms
Pull request #601 (2019-12-03 11:20:09)

Add bellman-ford algorithm
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [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 ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**



Patch:
diff --git a/PULL_REQUEST_TEMPLATE.md b/PULL_REQUEST_TEMPLATE.md
deleted file mode 100644
index ff98caf..0000000
--- a/PULL_REQUEST_TEMPLATE.md
+++ /dev/null
@@ -1,13 +0,0 @@
-(Put an `X` inside the `[ ]` to denote check mark `[X]`.)
-
-
-- [ ] **If creating a new file :**
-  - [ ] added links to it in the README files ?
-  - [ ] included tests with it ?
-  - [ ] added description (overview of algorithm, time and space complexity, 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**
diff --git a/README.md b/README.md
index f288ee3..d3bc636 100644
--- a/README.md
+++ b/README.md
@@ -160,6 +160,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [satisfiability](algorithms/graph/satisfiability.py)
     - [tarjan](algorithms/graph/tarjan.py)
     - [traversal](algorithms/graph/traversal.py)
+    - [bellman_ford](algorithms/graph/bellman_ford.py)
 - [heap](algorithms/heap)
     - [merge_sorted_k_lists](algorithms/heap/merge_sorted_k_lists.py)
     - [skyline](algorithms/heap/skyline.py)
@@ -215,6 +216,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [sqrt_precision_factor](algorithms/maths/sqrt_precision_factor.py)
     - [summing_digits](algorithms/maths/summing_digits.py)
     - [hailstone](algorithms/maths/hailstone.py)
+	  - [find_order](algorithms/maths/find_order_simple.py)
+	  - [find_primitive_root](algorithms/maths/find_primitive_root_simple.py)
 - [matrix](algorithms/matrix)
     - [sudoku_validator](algorithms/matrix/sudoku_validator.py)
     - [bomb_enemy](algorithms/matrix/bomb_enemy.py)
diff --git a/algorithms/dp/coin_change.py b/algorithms/dp/coin_change.py
index db14796..e9a83fc 100644
--- a/algorithms/dp/coin_change.py
+++ b/algorithms/dp/coin_change.py
@@ -1,37 +1,28 @@
 """
 Problem
-Given a value N, if we want to make change for N cents, and we have infinite supply of each of 
-S = { S1, S2, .. , Sm} valued //coins, how many ways can we make the change? 
+Given a value n, if we want to make change for N cents, and we have infinite supply of each of 
+coins = {S1, S2, .. , Sm} valued coins, how many ways can we make the change? 
 The order of coins doesn't matter.
-For example, for N = 4 and S = [1, 2, 3], there are four solutions: 
+For example, for n = 4 and coins = [1, 2, 3], there are four solutions: 
 [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3]. 
 So output should be 4. 
 
-For N = 10 and S = [2, 5, 3, 6], there are five solutions: 
+For n = 10 and coins = [2, 5, 3, 6], there are five solutions: 
 [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5] and [5, 5]. 
 So the output should be 5.
+
+Time complexity: O(n * m) where n is the value and m is the number of coins
+Space complexity: O(n)
 """
 
-def count(s, n):
-    # We need n+1 rows as the table is consturcted in bottom up
-    # manner using the base case 0 value case (n = 0)
-    m = len(s)
-    table = [[0 for x in range(m)] for x in range(n+1)]
- 
-    # Fill the enteries for 0 value case (n = 0)
-    for i in range(m):
-        table[0][i] = 1
- 
-    # Fill rest of the table enteries in bottom up manner
-    for i in range(1, n+1):
-        for j in range(m):
-            # Count of solutions including S[j]
-            x = table[i - s[j]][j] if i-s[j] >= 0 else 0
- 
-            # Count of solutions excluding S[j]
-            y = table[i][j-1] if j >= 1 else 0
+def count(coins, n):
+    # initialize dp array and set base case as 1
+    dp = [1] + [0] * n
  
-            # total count
-            table[i][j] = x + y
- 
-    return table[n][m-1]
+    # fill dp in a bottom up manner
+    for coin in coins:
+        for i in range(coin, n+1):
+            dp[i] += dp[i-coin]
+
+    return dp[n]
+
diff --git a/algorithms/dp/knapsack.py b/algorithms/dp/knapsack.py
index 65f7d89..530f939 100644
--- a/algorithms/dp/knapsack.py
+++ b/algorithms/dp/knapsack.py
@@ -12,7 +12,7 @@ the total number of items and m is the knapsack's capacity.
 """
 
 
-class Item(object):
+class Item:
 
     def __init__(self, value, weight):
         self.value = value
@@ -22,11 +22,7 @@ class Item(object):
 def get_maximum_value(items, capacity):
     dp = [0] * (capacity + 1)
     for item in items:
-        dp_tmp = [total_value for total_value in dp]
-        for current_weight in range(capacity + 1):
-            total_weight = current_weight + item.weight
-            if total_weight <= capacity:
-                dp_tmp[total_weight] = max(dp_tmp[total_weight],
-                                           dp[current_weight] + item.value)
-        dp = dp_tmp
-    return max(dp)
+        for cur_weight in reversed(range(item.weight, capacity+1)):
+            dp[cur_weight] = max(dp[cur_weight], item.value + dp[cur_weight - item.weight])
+    return dp[capacity]
+
diff --git a/algorithms/graph/__init__.py b/algorithms/graph/__init__.py
index f94f12c..646db09 100644
--- a/algorithms/graph/__init__.py
+++ b/algorithms/graph/__init__.py
@@ -1,2 +1,3 @@
 from .tarjan import *
 from .check_bipartite import *
+from .bellman_ford import *
diff --git a/algorithms/graph/bellman_ford.py b/algorithms/graph/bellman_ford.py
new file mode 100644
index 0000000..518f75c
--- /dev/null
+++ b/algorithms/graph/bellman_ford.py
@@ -0,0 +1,44 @@
+'''
+This Bellman-Ford Code is for determination whether we can get
+shortest path from given graph or not for single-source shortest-paths problem.
+In other words, if given graph has any negative-weight cycle that is reachable
+from the source, then it will give answer False for "no solution exits".
+For argument graph, it should be a dictionary type
+such as
+graph = {
+    'a': {'b': 6, 'e': 7},
+    'b': {'c': 5, 'd': -4, 'e': 8},
+    'c': {'b': -2},
+    'd': {'a': 2, 'c': 7},
+    'e': {'b': -3}
+}
+'''
+
+def bellman_ford(graph, source):
+    weight = {}
+    pre_node = {}
+
+    initialize_single_source(graph, source, weight, pre_node)
+
+    for i in range(1, len(graph)):
+        for node in graph:
+            for adjacent in graph[node]:
+                if weight[adjacent] > weight[node] + graph[node][adjacent]:
+                    weight[adjacent] = weight[node] + graph[node][adjacent]
+                    pre_node[adjacent] = node
+
+    for node in graph:
+        for adjacent in graph[node]:
+            if weight[adjacent] > weight[node] + graph[node][adjacent]:
+                return False
+
+    return True
+
+def initialize_single_source(graph, source, weight, pre_node):
+
+    for node in graph:
+        weight[node] = float('inf')
+        pre_node[node] = None
+
+    weight[source] = 0
+    
diff --git a/algorithms/maths/__init__.py b/algorithms/maths/__init__.py
index 7028a0a..1cb5f7d 100644
--- a/algorithms/maths/__init__.py
+++ b/algorithms/maths/__init__.py
@@ -15,3 +15,5 @@ from .rabin_miller import *
 from .rsa import *
 from .combination import *
 from .cosine_similarity import *
+from .find_order_simple import *
+from .find_primitive_root_simple import *
diff --git a/algorithms/maths/find_order_simple.py b/algorithms/maths/find_order_simple.py
new file mode 100644
index 0000000..d4866ee
--- /dev/null
+++ b/algorithms/maths/find_order_simple.py
@@ -0,0 +1,27 @@
+import math
+
+"""
+For positive integer n and given integer a that satisfies gcd(a, n) = 1,
+the order of a modulo n is the smallest positive integer k that satisfies
+pow (a, k) % n = 1. In other words, (a^k) ≡ 1 (mod n).
+Order of certain number may or may not be exist. If so, return -1.
+"""
+def find_order(a, n):
+    if ((a == 1) & (n == 1)):
+        return 1
+        """ Exception Handeling :
+        1 is the order of of 1 """
+    else:
+        if (math.gcd(a, n) != 1):
+            print ("a and n should be relative prime!")
+            return -1
+        else:
+            for i in range(1, n):
+                if (pow(a, i) % n == 1):
+                    return i
+            return -1
+
+"""
+Time complexity only for calculating order = O(nlog(n))
+O(n) for iteration loop, O(log(n)) for built-in power function
+"""
diff --git a/algorithms/maths/find_primitive_root_simple.py b/algorithms/maths/find_primitive_root_simple.py
new file mode 100644
index 0000000..a5b74f6
--- /dev/null
+++ b/algorithms/maths/find_primitive_root_simple.py
@@ -0,0 +1,71 @@
+import math
+
+"""
+For positive integer n and given integer a that satisfies gcd(a, n) = 1,
+the order of a modulo n is the smallest positive integer k that satisfies
+pow (a, k) % n = 1. In other words, (a^k) ≡ 1 (mod n).
+Order of certain number may or may not be exist. If so, return -1.
+"""
+def find_order(a, n):
+    if ((a == 1) & (n == 1)):
+        return 1
+        """ Exception Handeling :
+        1 is the order of of 1 """
+    else:
+        if (math.gcd(a, n) != 1):
+            print ("a and n should be relative prime!")
+            return -1
+        else:
+            for i in range(1, n):
+                if (pow(a, i) % n == 1):
+                    return i
+            return -1
+
+"""
+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).
+Code from /algorithms/maths/euler_totient.py, written by 'goswami-rahul'
+"""
+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;
+
+"""
+For positive integer n and given integer a that satisfies gcd(a, n) = 1,
+a is the primitive root of n, if a's order k for n satisfies k = ϕ(n).
+Primitive roots of certain number may or may not be exist.
+If so, return empty list.
+"""
+
+def find_primitive_root(n):
+    if (n == 1):
+        return [0]
+        """ Exception Handeling :
+        0 is the only primitive root of 1 """
+    else:
+        phi = euler_totient(n)
+        p_root_list = []
+        """ It will return every primitive roots of n. """
+        for i in range (1, n):
+            if (math.gcd(i, n) != 1):
+                continue
+                """ To have order, a and n must be
+                relative prime with each other. """
+            else:
+                order = find_order(i, n)
+                if (order == phi):
+                    p_root_list.append(i)
+                else:
+                    continue
+        return p_root_list
diff --git a/algorithms/maths/gcd.py b/algorithms/maths/gcd.py
index 1f80fc9..002f4fc 100644
--- a/algorithms/maths/gcd.py
+++ b/algorithms/maths/gcd.py
@@ -10,3 +10,42 @@ def gcd(a, b):
 def lcm(a, b):
     """Computes the lowest common multiple of integers a and b."""
     return a * b / gcd(a, b)
+
+
+"""
+Given a positive integer x, computes the number of trailing zero of x.
+Example
+Input : 34(100010)
+           ~~~~~^
+Output : 1
+
+Input : 40(101000)
+           ~~~^^^
+Output : 3
+"""
+
+def trailing_zero(x):
+    cnt = 0
+    while x and not x & 1:
+        cnt += 1
+        x >>= 1
+    return cnt
+
+"""
+Given two non-negative integer a and b, 
+computes the greatest common divisor of a and b using bitwise operator.
+"""
+
+def gcd_bit(a, b):
+    tza = trailing_zero(a)
+    tzb = trailing_zero(b)
+    a >>= tza
+    b >>= tzb
+    while b:
+        if a < b: 
+            a, b = b, a
+        a -= b
+        a >>= trailing_zero(a)
+    return a << min(tza, tzb)
+
+


Test patch:
diff --git a/tests/test_graph.py b/tests/test_graph.py
index 893ea77..699136a 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -1,6 +1,7 @@
 from algorithms.graph import Tarjan
 from algorithms.graph import check_bipartite
 from algorithms.graph.dijkstra import Dijkstra
+from algorithms.graph import bellman_ford
 
 import unittest
 
@@ -74,4 +75,26 @@ class TestDijkstra(unittest.TestCase):
            [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
+        self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14]);
+        
+class TestBellmanFord(unittest.TestCase):
+    def test_bellman_ford(self):
+        graph1 = {
+            'a': {'b': 6, 'e': 7},
+            'b': {'c': 5, 'd': -4, 'e': 8},
+            'c': {'b': -2},
+            'd': {'a': 2, 'c': 7},
+            'e': {'b': -3}
+        }
+    
+        self.assertEqual(True, bellman_ford(graph1, 'a'))
+    
+        graph2 = {
+            'a': {'d': 3, 'e': 4},
+            'b': {'a': 7, 'e':2},
+            'c': {'a': 12, 'd':9, 'e':11},
+            'd': {'c': 5, 'e': 11},
+            'e': {'a': 7, 'b': 5, 'd': 1}
+        } 
+    
+        self.assertEqual(True, bellman_ford(graph2, 'a'))
diff --git a/tests/test_maths.py b/tests/test_maths.py
index 850cd5d..ce34c3d 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -4,7 +4,7 @@ from algorithms.maths import (
     euler_totient,
     extended_gcd,
     factorial, factorial_recur,
-    gcd, lcm,
+    gcd, lcm, trailing_zero, gcd_bit,
     gen_strobogrammatic, strobogrammatic_in_range,
     is_strobogrammatic, is_strobogrammatic2,
     modular_exponential,
@@ -17,6 +17,8 @@ from algorithms.maths import (
     combination, combination_memo,
     hailstone,
     cosine_similarity,
+    find_order,
+    find_primitive_root,
 )
 
 import unittest
@@ -101,6 +103,13 @@ class TestGcd(unittest.TestCase):
     def test_lcm(self):
         self.assertEqual(24, lcm(8, 12))
 
+    def test_trailing_zero(self):
+        self.assertEqual(1, trailing_zero(34))
+        self.assertEqual(3, trailing_zero(40))
+
+    def test_gcd_bit(self):
+        self.assertEqual(4, gcd_bit(8, 12))
+        self.assertEqual(1, gcd(13, 17))
 
 class TestGenerateStroboGrammatic(unittest.TestCase):
     """[summary]
@@ -317,6 +326,33 @@ class TestCosineSimilarity(unittest.TestCase):
         self.assertAlmostEqual(cosine_similarity(vec_a, vec_b), -1)
         self.assertAlmostEqual(cosine_similarity(vec_a, vec_c), 0.4714045208)
 
+class TestFindPrimitiveRoot(unittest.TestCase):
+    """[summary]
+    Test for the file find_primitive_root_simple.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_find_primitive_root_simple(self):
+        self.assertListEqual([0], find_primitive_root(1))
+        self.assertListEqual([2, 3], find_primitive_root(5))
+        self.assertListEqual([], find_primitive_root(24))
+        self.assertListEqual([2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35], find_primitive_root(37))
+        
+
+class TestFindOrder(unittest.TestCase):
+    """[summary]
+    Test for the file find_order_simple.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_find_order_simple(self):
+        self.assertEqual(1, find_order(1, 1))
+        self.assertEqual(6, find_order(3, 7))
+        self.assertEqual(-1, find_order(128, 256))
+        self.assertEqual(352, find_order(3, 353))
 
 if __name__ == "__main__":
     unittest.main()
+