Repository: keon/algorithms
Pull request #345 (2018-06-10 02:24:36)

top_1.py & trimmean.py created
(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 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 599](https://coveralls.io/builds/17412126)

* **30** of **31**   **(96.77%)**  changed or added relevant lines in **3** files are covered.
* No unchanged relevant lines lost coverage.
* Overall coverage increased (+**0.2%**) to **69.765%**

---

|  Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
| :-----|--------------|--------|---: |
| [algorithms/arrays/top_1.py](https://coveralls.io/builds/17412126/source?filename=algorithms%2Farrays%2Ftop_1.py#L30) | 13 | 14 | 92.86%
<!-- | **Total:** | **30** | **31** | **96.77%** | -->


|  Totals | [![Coverage Status](https://coveralls.io/builds/17412126/badge)](https://coveralls.io/builds/17412126) |
| :-- | --: |
| Change from base [Build 589](https://coveralls.io/builds/17408969): |  0.2% |
| Covered Lines: | 3302 |
| Relevant Lines: | 4733 |

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


Patch:
diff --git a/README.md b/README.md
index c954e5f..18858ce 100644
--- a/README.md
+++ b/README.md
@@ -68,6 +68,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack](algorithms/backtrack)
@@ -87,6 +89,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)
diff --git a/README_CN.md b/README_CN.md
index 43032d9..db759e9 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -85,6 +85,8 @@ pip3 uninstall -y algorithms
     - [rotate：反转数组](algorithms/arrays/rotate.py)
     - [summarize_ranges：数组范围](algorithms/arrays/summarize_ranges.py)
     - [three_sum：三数和为零](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum：两数和](algorithms/arrays/two_sum.py)
     - [move_zeros: 0后置问题](algorithms/arrays/move_zeros.py)
 - [backtrack：回溯](algorithms/backtrack)
@@ -104,6 +106,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..f0a48ca 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -75,6 +75,8 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack](algorithms/backtrack)
@@ -94,6 +96,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 b81f9ce..d50f012 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -69,6 +69,8 @@ if __name__ == "__main__":
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack : バックトラッキング](algorithms/backtrack)
@@ -88,6 +90,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..dd78fa0 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -68,6 +68,8 @@ if __name__ == "__main__":
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack : 백트래킹](algorithms/backtrack)
@@ -87,6 +89,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/arrays/__init__.py b/algorithms/arrays/__init__.py
index 64ba130..7e57f63 100644
--- a/algorithms/arrays/__init__.py
+++ b/algorithms/arrays/__init__.py
@@ -11,4 +11,6 @@ from .plus_one import *
 from .rotate import *
 from .summarize_ranges import *
 from .three_sum import *
+from .trimmean import *
+from .top_1 import *
 from .two_sum import *
diff --git a/algorithms/arrays/top_1.py b/algorithms/arrays/top_1.py
new file mode 100644
index 0000000..dea9aa2
--- /dev/null
+++ b/algorithms/arrays/top_1.py
@@ -0,0 +1,32 @@
+"""
+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 algorithms get array, and make dictionary of it, find most frequent count, and make result list.
+
+For example) top_1([1, 1, 2, 2, 3, 4]) will return [1, 2]
+
+Complexity: O(n)
+"""
+def top_1(arr):
+    values = {}
+    #reserve each value which first appears on keys
+    #reserve how many time each value appears by index number on values
+    result = []
+    f_val = 0
+
+    for i in arr:
+        if i in values:
+            values[i] += 1
+        else:
+            values[i] = 1
+
+    f_val = max(values.values())
+        
+    for i in values.keys():
+        if values[i] == f_val:
+            result.append(i)
+        else:
+            continue
+    
+    return result
diff --git a/algorithms/arrays/trimmean.py b/algorithms/arrays/trimmean.py
new file mode 100644
index 0000000..4cea0db
--- /dev/null
+++ b/algorithms/arrays/trimmean.py
@@ -0,0 +1,22 @@
+"""
+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.
+
+This algorithm gets array and percentage to neglect. After sorted, if index of array is larger or smaller or wanted ratio, we don't
+compute it.
+
+Compleity: O(n)
+"""
+def trimmean(arr, per):
+    ratio = per/200
+    # /100 for easy calculation by *, and /2 for easy adaption to best and worst parts.
+    cal_sum = 0
+    # sum value to be calculated to trimmean.
+    arr.sort()
+    neg_val = int(len(arr)*ratio)
+    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/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


Test patch:
diff --git a/tests/test_array.py b/tests/test_array.py
index ed398bc..e3f6f6d 100644
--- a/tests/test_array.py
+++ b/tests/test_array.py
@@ -12,7 +12,9 @@ from algorithms.arrays import (
     summarize_ranges,
     three_sum,
     two_sum,
-    max_ones_index
+    max_ones_index,
+    trimmean,
+    top_1
 )
 
 import unittest
@@ -306,6 +308,20 @@ class TestSuite(unittest.TestCase):
         self.assertTupleEqual((0, 3), two_sum([-3, 5, 2, 3, 8, -9], target=0))
 
         self.assertIsNone(two_sum([-3, 5, 2, 3, 8, -9], target=6))
+        
+class TestTrimmean(unittest.TestCase):
+
+    def test_trimmean(self):
+
+        self.assertEqual(trimmean([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 20), 5.5)
+        self.assertEqual(trimmean([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 20), 6.0)
+        
+class TestTop1(unittest.TestCase):
+    
+    def test_top_1(self):
+        self.assertListEqual(top_1([1 , 1, 2, 2, 3]), [1, 2])
+        self.assertListEqual(top_1([1, 2, 3, 324, 234, 23, 23, 1, 23, 23]), [23])
+
 
 
 if __name__ == '__main__':
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()