Repository: keon/algorithms
Pull request #343 (2018-06-09 14:26:00)

Created BFS maze_search.py and test case
I created maze search problem using BFS.
For example if the input grid is:
101111
101010
101011
111011
The minimum steps from location (0,0) to (3,5) is 14, so the output is 14.
Another example:
100
011
011
You cannot go from (0,0) to (2,2), so the output is -1.


- [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 compleixty, and possible edge case) in docstrings ?



Patch:
diff --git a/README.md b/README.md
index 8cbf568..f1497ca 100644
--- a/README.md
+++ b/README.md
@@ -87,6 +87,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [subsets](algorithms/backtrack/subsets.py)
     - [subsets_unique](algorithms/backtrack/subsets_unique.py)
 - [bfs](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder](algorithms/bfs/word_ladder.py)
 - [bit](algorithms/bit)
@@ -176,6 +177,7 @@ If you want to uninstall algorithms, it is as simple as:
 - [maths](algorithms/maths)
     - [base_conversion](algorithms/maths/base_conversion.py)
     - [combination](algorithms/maths/combination.py)
+    - [decimal_to_binary_ip](algorithms/maths/decimal_to_binary_ip.py)
     - [extended_gcd](algorithms/maths/extended_gcd.py)
     - [factorial](algorithms/maths/factorial.py)    
     - [gcd/lcm](algorithms/maths/gcd.py)
diff --git a/README_CN.md b/README_CN.md
index 43032d9..efff430 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -104,6 +104,7 @@ pip3 uninstall -y algorithms
     - [subsets：子集](algorithms/backtrack/subsets.py)
     - [subsets_unique：唯一子集](algorithms/backtrack/subsets_unique.py)
 - [bfs：广度优先搜索](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings：所有建筑物的最短路径：](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder：词语阶梯](algorithms/bfs/word_ladder.py)
 - [bit：位操作](algorithms/bit)
diff --git a/README_GE.md b/README_GE.md
index 529ce79..afdcc32 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -94,6 +94,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [subsets](algorithms/backtrack/subsets.py)
     - [subsets_unique](algorithms/backtrack/subsets_unique.py)
 - [bfs](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder](algorithms/bfs/word_ladder.py)
 - [bit](algorithms/bit)
diff --git a/README_JP.md b/README_JP.md
index f47bec7..d3603b7 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -38,7 +38,7 @@ Python 3で開発された簡単で明確なデータ構造とアルゴリズム
 
     $ pip3 install git+https://github.com/keon/algorithms
 
-Pythonファイルを作成してテストを行うことができます：（例：「sort」の「merge_sort」を使用）
+Pythonファイルを作成してテストを実行することができます：（例：「sort」の「merge_sort」を使用）
 
 ```python3
 from sort import merge_sort
@@ -88,6 +88,7 @@ if __name__ == "__main__":
     - [subsets](algorithms/backtrack/subsets.py)
     - [subsets_unique](algorithms/backtrack/subsets_unique.py)
 - [bfs : 幅優先探索](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder](algorithms/bfs/word_ladder.py)
 - [bit : ビット](algorithms/bit)
diff --git a/README_KR.md b/README_KR.md
index 8487541..e5b5283 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -87,6 +87,7 @@ if __name__ == "__main__":
     - [subsets](algorithms/backtrack/subsets.py)
     - [subsets_unique](algorithms/backtrack/subsets_unique.py)
 - [bfs : 너비 우선 탐색](algorithms/bfs)
+    - [maze_search](algorithms/bfs/maze_search.py)
     - [shortest_distance_from_all_buildings](algorithms/bfs/shortest_distance_from_all_buildings.py)
     - [word_ladder](algorithms/bfs/word_ladder.py)
 - [bit : 비트](algorithms/bit)
diff --git a/algorithms/bfs/__init__.py b/algorithms/bfs/__init__.py
new file mode 100644
index 0000000..b3d3b0c
--- /dev/null
+++ b/algorithms/bfs/__init__.py
@@ -0,0 +1,3 @@
+from .maze_search import *
+from .shortest_distance_from_all_buildings import *
+from .word_ladder import *
diff --git a/algorithms/bfs/maze_search.py b/algorithms/bfs/maze_search.py
new file mode 100644
index 0000000..efa65c3
--- /dev/null
+++ b/algorithms/bfs/maze_search.py
@@ -0,0 +1,33 @@
+'''
+BFS time complexity : O(|E|)
+BFS space complexity : O(|V|)
+
+do BFS from (0,0) of the grid and get the minimum number of steps needed to get to the lower right column
+
+only step on the columns whose value is 1
+
+if there is no path, it returns -1
+'''
+
+def maze_search(grid):
+    dx = [0,0,-1,1]
+    dy = [-1,1,0,0]
+    n = len(grid)
+    m = len(grid[0])
+    q = [(0,0,0)]
+    visit = [[0]*m for _ in range(n)]
+    if grid[0][0] == 0:
+        return -1
+    visit[0][0] = 1
+    while q:
+        i, j, step = q.pop(0)
+        if i == n-1 and j == m-1:
+            return step
+        for k in range(4):
+            x = i + dx[k]
+            y = j + dy[k]
+            if x>=0 and x<n and y>=0 and y<m:
+                if grid[x][y] ==1 and visit[x][y] == 0:
+                    visit[x][y] = 1
+                    q.append((x,y,step+1))
+    return -1
diff --git a/algorithms/maths/__init__.py b/algorithms/maths/__init__.py
index 2bf44a7..543d8d3 100644
--- a/algorithms/maths/__init__.py
+++ b/algorithms/maths/__init__.py
@@ -1,4 +1,5 @@
 from .base_conversion import *
+from .decimal_to_binary_ip import *
 from .extended_gcd import *
 from .factorial import *
 from .gcd import *
diff --git a/algorithms/maths/decimal_to_binary_ip.py b/algorithms/maths/decimal_to_binary_ip.py
new file mode 100644
index 0000000..579e340
--- /dev/null
+++ b/algorithms/maths/decimal_to_binary_ip.py
@@ -0,0 +1,27 @@
+"""
+Given an ip address in dotted-decimal representation, determine the
+binary representation. For example,
+decimal_to_binary(255.0.0.5) returns 11111111.00000000.00000000.00000101
+accepts string
+returns string
+"""
+
+def decimal_to_binary_util(val):
+    bits = [128, 64, 32, 16, 8, 4, 2, 1]
+    val = int(val)
+    binary_rep = ''
+    for bit in bits:
+        if val >= bit:
+            binary_rep += str(1)
+            val -= bit
+        else:
+            binary_rep += str(0)
+
+    return binary_rep
+
+def decimal_to_binary_ip(ip):
+    values = ip.split('.')
+    binary_list = []
+    for val in values:
+        binary_list.append(decimal_to_binary_util(val))
+    return '.'.join(binary_list)


Test patch:
diff --git a/tests/test_bfs.py b/tests/test_bfs.py
new file mode 100644
index 0000000..129d6d0
--- /dev/null
+++ b/tests/test_bfs.py
@@ -0,0 +1,18 @@
+from algorithms.bfs import (
+    maze_search,
+    shortest_distance_from_all_buildings,
+    word_ladder
+)
+
+import unittest
+
+class TestMazeSearch(unittest.TestCase):
+    
+    def test_maze_search(self):
+        grid_1 = [[1,0,1,1,1,1],[1,0,1,0,1,0],[1,0,1,0,1,1],[1,1,1,0,1,1]]
+        self.assertEqual(14, maze_search(grid_1))
+        grid_2 = [[1,0,0],[0,1,1],[0,1,1]]
+        self.assertEqual(-1, maze_search(grid_2))
+        
+if __name__ == "__main__":
+    unittest.main()
diff --git a/tests/test_maths.py b/tests/test_maths.py
index ece9ab7..1514907 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -1,5 +1,6 @@
 from algorithms.maths import (
     int_to_base, base_to_int,
+    decimal_to_binary_ip,
     extended_gcd,
     factorial, factorial_recur,
     gcd, lcm,
@@ -25,15 +26,29 @@ class TestBaseConversion(unittest.TestCase):
         unittest {[type]} -- [description]
     """
 
-    def test_int2base(self):
+    def test_int_to_base(self):
         self.assertEqual("101", int_to_base(5, 2))
         self.assertEqual("0", int_to_base(0, 2))
         self.assertEqual("FF", int_to_base(255, 16))
 
-    def test_base2int(self):
+    def test_base_to_int(self):
         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
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_decimal_to_binary_ip(self):
+        self.assertEqual("00000000.00000000.00000000.00000000", decimal_to_binary_ip("0.0.0.0"))
+        self.assertEqual("11111111.11111111.11111111.11111111", decimal_to_binary_ip("255.255.255.255"))
+        self.assertEqual("11000000.10101000.00000000.00000001", decimal_to_binary_ip("192.168.0.1"))
 
 
 class TestExtendedGcd(unittest.TestCase):