Repository: keon/algorithms
Pull request #428 (2018-10-14 02:04:38)

Add `convolve` iteration algorithm with tests
Bonjour, 

I added the `convolve` iteration algorithm with tests: a simple way to do convolutions on lists. 

- [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**~~


guillaume-chevalier: Note: the test `test_plus_one_v3` fails and was already failing before opening this PR, everything else works: 

```
py36 runtests: commands[0] | python3 -m unittest discover tests
.................E...............................................................................................................................................................................................................................
======================================================================
ERROR: test_plus_one_v3 (test_array.TestPlusOne)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/travis/build/keon/algorithms/tests/test_array.py", line 252, in test_plus_one_v3
    self.assertListEqual(plus_one_v3([0]), [1])
  File "/home/travis/build/keon/algorithms/algorithms/arrays/plus_one.py", line 45, in plus_one_v3
    num_arr[idx] = (num_arr[idx] + 1) % 10
TypeError: list indices must be integers, not tuple
----------------------------------------------------------------------
Ran 241 tests in 0.433s
FAILED (errors=1)
ERROR: InvocationError for command '/home/travis/build/keon/algorithms/.tox/py36/bin/python3 -m unittest discover tests' (exited with code 1)
___________________________________ summary ____________________________________
ERROR:   py36: commands failed
The command "tox -e $TOX_ENV" exited with 1.
0.45s$ pip3 uninstall -y algorithms
Uninstalling algorithms-0.1.0:
  Successfully uninstalled algorithms-0.1.0
```

guillaume-chevalier: Thanks for the review and for your time! 
guillaume-chevalier: I made the changes. 
guillaume-chevalier: @keon I finally decided to make the requested changes.

Patch:
diff --git a/README.md b/README.md
index 13f7606..48d4c7f 100644
--- a/README.md
+++ b/README.md
@@ -159,6 +159,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [skyline](algorithms/heap/skyline.py)
     - [sliding_window_max](algorithms/heap/sliding_window_max.py)
     - [binary_heap](algorithms/heap/binary_heap.py)
+- [iterables](algorithms/iterables)
+    - [convolved](algorithms/iterables/convolved.py)
     - [k_closest_points](algorithms/heap/k_closest_points.py)
 - [linkedlist](algorithms/linkedlist)
     - [add_two_numbers](algorithms/linkedlist/add_two_numbers.py)
diff --git a/README_CN.md b/README_CN.md
index e0806be..ca181d6 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -157,6 +157,8 @@ pip3 uninstall -y algorithms
     - [merge_sorted_k_lists：合并k个有序链](algorithms/heap/merge_sorted_k_lists.py)
     - [skyline：天际线](algorithms/heap/skyline.py)
     - [sliding_window_max：滑动窗口最大值](algorithms/heap/sliding_window_max.py)
+- [iterables : 迭代](algorithms/iterables)
+    - [convolved : 卷积](algorithms/iterables/convolved.py)
 - [linkedlist：链表](algorithms/linkedlist)
     - [add_two_numbers：链表数相加](algorithms/linkedlist/add_two_numbers.py)
     - [copy_random_pointer：复制带有随机指针的链表](algorithms/linkedlist/copy_random_pointer.py)
diff --git a/README_FR.md b/README_FR.md
index fc6d41f..99d445a 100644
--- a/README_FR.md
+++ b/README_FR.md
@@ -158,6 +158,8 @@ Si vous voulez désinstaller le paquet algorithms, il suffit de procéder comme
     - [skyline](algorithms/heap/skyline.py)
     - [sliding_window_max](algorithms/heap/sliding_window_max.py)
     - [binary_heap](algorithms/heap/binary_heap.py)
+- [iterables](algorithms/iterables)
+    - [convolved](algorithms/iterables/convolved.py)
 - [linkedlist](algorithms/linkedlist)
     - [add_two_numbers](algorithms/linkedlist/add_two_numbers.py)
     - [copy_random_pointer](algorithms/linkedlist/copy_random_pointer.py)
diff --git a/README_GE.md b/README_GE.md
index ab68bdd..91883c8 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -165,6 +165,8 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [skyline](algorithms/heap/skyline.py)
     - [sliding_window_max](algorithms/heap/sliding_window_max.py)
     - [binary_heap](algorithms/heap/binary_heap.py)
+- [iterables](algorithms/iterables)
+    - [convolved](algorithms/iterables/convolved.py)
 - [linkedlist](algorithms/linkedlist)
     - [add_two_numbers](algorithms/linkedlist/add_two_numbers.py)
     - [copy_random_pointer](algorithms/linkedlist/copy_random_pointer.py)
diff --git a/README_JP.md b/README_JP.md
index ca31bab..28f29cb 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -159,6 +159,8 @@ if __name__ == "__main__":
     - [skyline](algorithms/heap/skyline.py)
     - [sliding_window_max](algorithms/heap/sliding_window_max.py)
     - [binary_heap](algorithms/heap/binary_heap.py)
+- [iterables : 繰り返し可能な](algorithms/iterables)
+    - [convolved](algorithms/iterables/convolved.py)
 - [linkedlist : 連結リスト](algorithms/linkedlist)
     - [add_two_numbers](algorithms/linkedlist/add_two_numbers.py)
     - [copy_random_pointer](algorithms/linkedlist/copy_random_pointer.py)
diff --git a/README_KR.md b/README_KR.md
index f0f583e..ab4ce77 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -155,6 +155,8 @@ if __name__ == "__main__":
     - [skyline](algorithms/heap/skyline.py)
     - [sliding_window_max](algorithms/heap/sliding_window_max.py)
     - [binary_heap](algorithms/heap/binary_heap.py)
+- [iterable : 반복 가능한 것](algorithms/iterables)
+    - [convolved](algorithms/iterables/convolved.py)
 - [linkedlist : 연결 리스트](algorithms/linkedlist)
     - [add_two_numbers](algorithms/linkedlist/add_two_numbers.py)
     - [copy_random_pointer](algorithms/linkedlist/copy_random_pointer.py)
diff --git a/README_PTBR.md b/README_PTBR.md
index a93f45d..c8bed54 100644
--- a/README_PTBR.md
+++ b/README_PTBR.md
@@ -157,6 +157,8 @@ Se você deseja desinstalar os algoritmos, é tão simples quanto:
     - [skyline](algorithms/heap/skyline.py)
     - [sliding_window_max](algorithms/heap/sliding_window_max.py)
     - [binary_heap](algorithms/heap/binary_heap.py)
+- [iterables](algorithms/iterables)
+    - [convolved](algorithms/iterables/convolved.py)
 - [linkedlist](algorithms/linkedlist)
     - [add_two_numbers](algorithms/linkedlist/add_two_numbers.py)
     - [copy_random_pointer](algorithms/linkedlist/copy_random_pointer.py)
diff --git a/algorithms/iterables/__init__.py b/algorithms/iterables/__init__.py
new file mode 100644
index 0000000..f39a0ff
--- /dev/null
+++ b/algorithms/iterables/__init__.py
@@ -0,0 +1,1 @@
+from .convolved import *
diff --git a/algorithms/iterables/convolved.py b/algorithms/iterables/convolved.py
new file mode 100644
index 0000000..4f8b492
--- /dev/null
+++ b/algorithms/iterables/convolved.py
@@ -0,0 +1,154 @@
+"""Iterable to get every convolution window per loop iteration.
+
+## Example Usage
+
+```
+from algorithms.iterables import convolved
+# This would also work: from conv import convolved
+
+some_list = [1, 2, 3]
+for kernel_hover in convolved(some_list, kernel_size=2, stride=1, padding=2, default_value=42):
+    print(kernel_hover)
+```
+
+## Result:
+
+```
+[42, 42]
+[42, 1]
+[1, 2]
+[2, 3]
+[3, 42]
+[42, 42]
+```
+
+"""
+
+
+def convolved(iterable, kernel_size=1, stride=1, padding=0, default_value=None):
+    """Iterable to get every convolution window per loop iteration.
+
+    For example:
+        `convolved([1, 2, 3, 4], kernel_size=2)`
+            will produce the following result:
+            `[[1, 2], [2, 3], [3, 4]]`.
+        `convolved([1, 2, 3], kernel_size=2, stride=1, padding=2, default_value=42)`
+            will produce the following result:
+            `[[42, 42], [42, 1], [1, 2], [2, 3], [3, 42], [42, 42]]`
+
+    Arguments:
+        iterable: An object to iterate on. It should support slice indexing if `padding == 0`.
+        kernel_size: The number of items yielded at every iteration.
+        stride: The step size between each iteration.
+        padding: Padding must be an integer or a string with value `SAME` or `VALID`. If it is an integer, it represents
+            how many values we add with `default_value` on the borders. If it is a string, `SAME` means that the
+            convolution will add some padding according to the kernel_size, and `VALID` is the same as
+            specifying `padding=0`.
+        default_value: Default fill value for padding and values outside iteration range.
+
+    For more information, refer to: 
+    - https://github.com/guillaume-chevalier/python-conv-lib/blob/master/conv/conv.py
+    - https://github.com/guillaume-chevalier/python-conv-lib
+    - MIT License, Copyright (c) 2018 Guillaume Chevalier
+    """
+    # Input validation and error messages
+    if not hasattr(iterable, '__iter__'):
+        raise ValueError(
+            "Can't iterate on object.".format(
+                iterable))
+    if stride < 1:
+        raise ValueError(
+            "Stride must be of at least one. Got `stride={}`.".format(
+                stride))
+    if not (padding in ['SAME', 'VALID'] or type(padding) in [int]):
+        raise ValueError(
+            "Padding must be an integer or a string with value `SAME` or `VALID`.")
+    if not isinstance(padding, str):
+        if padding < 0:
+            raise ValueError(
+                "Padding must be of at least zero. Got `padding={}`.".format(
+                    padding))
+    else:
+        if padding == 'SAME':
+            padding = kernel_size // 2
+        elif padding == 'VALID':
+            padding = 0
+    if not type(iterable) == list:
+        iterable = list(iterable)
+
+    # Add padding to iterable
+    if padding > 0:
+        pad = [default_value] * padding
+        iterable = pad + list(iterable) + pad
+
+    # Fill missing value to the right
+    remainder = (kernel_size - len(iterable)) % stride
+    extra_pad = [default_value] * remainder
+    iterable = iterable + extra_pad
+
+    i = 0
+    while True:
+        if i > len(iterable) - kernel_size:
+            break
+        yield iterable[i:i + kernel_size]
+        i += stride
+
+def convolved_1d(iterable, kernel_size=1, stride=1, padding=0, default_value=None):
+    """1D Iterable to get every convolution window per loop iteration.
+
+    For more information, refer to:
+    - https://github.com/guillaume-chevalier/python-conv-lib/blob/master/conv/conv.py
+    - https://github.com/guillaume-chevalier/python-conv-lib
+    - MIT License, Copyright (c) 2018 Guillaume Chevalier
+    """
+    return convolved(iterable, kernel_size, stride, padding, default_value)
+
+
+def convolved_2d(iterable, kernel_size=1, stride=1, padding=0, default_value=None):
+    """2D Iterable to get every convolution window per loop iteration.
+
+    For more information, refer to:
+    - https://github.com/guillaume-chevalier/python-conv-lib/blob/master/conv/conv.py
+    - https://github.com/guillaume-chevalier/python-conv-lib
+    - MIT License, Copyright (c) 2018 Guillaume Chevalier
+    """
+    kernel_size = dimensionize(kernel_size, nd=2)
+    stride = dimensionize(stride, nd=2)
+    padding = dimensionize(padding, nd=2)
+
+    for row_packet in convolved(iterable, kernel_size[0], stride[0], padding[0], default_value):
+        transposed_inner = []
+        for col in tuple(row_packet):
+            transposed_inner.append(list(
+                convolved(col, kernel_size[1], stride[1], padding[1], default_value)
+            ))
+
+        if len(transposed_inner) > 0:
+            for col_i in range(len(transposed_inner[0])):
+                yield tuple(row_j[col_i] for row_j in transposed_inner)
+
+
+def dimensionize(maybe_a_list, nd=2):
+    """Convert integers to a list of integers to fit the number of dimensions if
+    the argument is not already a list.
+
+    For example:
+    `dimensionize(3, nd=2)`
+        will produce the following result:
+        `(3, 3)`.
+    `dimensionize([3, 1], nd=2)`
+        will produce the following result:
+        `[3, 1]`.
+
+    For more information, refer to:
+    - https://github.com/guillaume-chevalier/python-conv-lib/blob/master/conv/conv.py
+    - https://github.com/guillaume-chevalier/python-conv-lib
+    - MIT License, Copyright (c) 2018 Guillaume Chevalier
+    """
+    if not hasattr(maybe_a_list, '__iter__'):
+        # Argument is probably an integer so we map it to a list of size `nd`.
+        now_a_list = [maybe_a_list] * nd
+        return now_a_list
+    else:
+        # Argument is probably an `nd`-sized list.
+        return maybe_a_list
diff --git a/tree.md b/tree.md
index adaa281..8fe302f 100644
--- a/tree.md
+++ b/tree.md
@@ -107,6 +107,9 @@ algorithms
 │   ├── skyline.py
 │   └── sliding_window_max.py
 ├── __init__.py
+├── iterables
+│   ├── __init__.py
+│   └── convolved.py
 ├── linkedlist
 │   ├── add_two_numbers.py
 │   ├── copy_random_pointer.py
@@ -296,5 +299,5 @@ algorithms
 └── union-find
     └── count_islands.py
 
-27 directories, 267 files
+28 directories, 269 files
 ```


Test patch:
diff --git a/tests/test_iterables.py b/tests/test_iterables.py
new file mode 100644
index 0000000..4e23d85
--- /dev/null
+++ b/tests/test_iterables.py
@@ -0,0 +1,161 @@
+from algorithms.iterables import (
+    convolved_1d, convolved_2d
+)
+
+import itertools
+import unittest
+
+
+class TestConvolved1D(unittest.TestCase):
+    """Tests copied from:
+    - https://github.com/guillaume-chevalier/python-conv-lib/blob/master/conv/tests/test_convolved_1d.py
+    - MIT License, Copyright (c) 2018 Guillaume Chevalier
+    """
+
+    def test_trivial_loop(self):
+        expected = tuple(range(7))
+        result = []
+
+        for kernel_hover in convolved_1d(expected, kernel_size=1, padding=0, stride=1):
+            result.append(*kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_seven_for_with_stride_two(self):
+        expected = tuple(range(0, 7, 2))
+        result = []
+
+        for kernel_hover in convolved_1d(list(range(7)), kernel_size=1, padding=0, stride=2):
+            result.append(*kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_seven_for_with_padding_one(self):
+        expected = tuple([42] + list(range(0, 7)) + [42])
+        result = []
+
+        for kernel_hover in convolved_1d(list(range(7)), kernel_size=1, padding=1, stride=1, default_value=42):
+            result.append(*kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_seven_kernel_of_two(self):
+        expected = tuple([a, b] for a, b in zip(list(range(0, 6)), list(range(1, 7))))
+        result = []
+
+        for kernel_hover in convolved_1d(list(range(7)), kernel_size=2, padding=0, stride=1):
+            result.append(kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_seven_kernel_of_two_and_stride_two(self):
+        expected = ([0, 1], [2, 3], [4, 5], [6, None])
+        result = []
+
+        for kernel_hover in convolved_1d(list(range(7)), kernel_size=2, padding=0, stride=2):
+            result.append(kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_seven_kernel_of_two_and_stride_two_and_padding_two(self):
+        expected = ([None, None], [0, 1], [2, 3], [4, 5], [6, None], [None, None])
+        result = []
+
+        for kernel_hover in convolved_1d(list(range(7)), kernel_size=2, padding=2, stride=2):
+            result.append(kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_seven_kernel_of_two_and_stride_two_and_padding_three(self):
+        expected = ([None, None], [None, 0], [1, 2], [3, 4], [5, 6], [None, None], [None, None])
+        result = []
+
+        for kernel_hover in convolved_1d(list(range(7)), kernel_size=2, padding=3, stride=2):
+            result.append(kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_seven_kernel_of_three_and_stride_two_and_padding_two(self):
+        expected = ([None, None, 0], [0, 1, 2], [2, 3, 4], [4, 5, 6], [6, None, None])
+        result = []
+
+        for kernel_hover in convolved_1d(list(range(7)), kernel_size=3, padding=2, stride=2):
+            result.append(kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_seven_kernel_of_two_and_stride_three_and_padding_two(self):
+        expected = ([None, None], [1, 2], [4, 5], [None, None])
+        result = []
+
+        for kernel_hover in convolved_1d(list(range(7)), kernel_size=2, padding=2, stride=3):
+            result.append(kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_seven_kernel_of_three_and_stride_three_and_padding_three(self):
+        expected = ([None, None, None], [0, 1, 2], [3, 4, 5], [6, None, None], [None, None, None])
+        result = []
+
+        for kernel_hover in convolved_1d(list(range(7)), kernel_size=3, padding=3, stride=3):
+            result.append(kernel_hover)
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+
+class TestConvolved2D(unittest.TestCase):
+    """Tests copied from:
+    - https://github.com/guillaume-chevalier/python-conv-lib/blob/master/conv/tests/test_convolved_1d.py
+    - MIT License, Copyright (c) 2018 Guillaume Chevalier
+    """
+
+    def test_trivial_1x1_loop(self):
+        base = tuple(tuple(range(i ** 2, 7 + i ** 2)) for i in range(7))
+        expected = tuple(([i],) for i in itertools.chain(*base))
+        result = []
+
+        for kernel_hover in convolved_2d(base, kernel_size=1, padding=0, stride=1):
+            result.append(tuple(kernel_hover))
+        result = tuple(result)
+
+        self.assertEqual(expected, result)
+
+    def test_simple_2x2_loop_on_3x2(self):
+        base = [
+            [1, 2],
+            [3, 4],
+            [5, 6]
+        ]
+        expected = (
+            (
+                [1, 2],
+                [3, 4]
+            ), (
+                [3, 4],
+                [5, 6]
+            )
+        )
+        result = []
+
+        for kernel_hover in convolved_2d(base, kernel_size=2, padding=0, stride=1):
+            result.append(tuple(kernel_hover))
+        result = tuple(result)
+
+        print(result)
+        print(expected)
+
+        self.assertEqual(expected, result)
+
+
+if __name__ == "__main__":
+    unittest.main()