## 2020年5月11日月曜日

### Python - Searching and Sorting - linear search, while loop, for loop, sentinel, TDD(test-driven development)

Practical Programming: An Introduction to Computer Science Using Python 3.6 (Paul Gries(著)、Jennifer Campbell(著)、Jason Montojo(著)、Pragmatic Bookshelf)のChapter 13(Searching and Sorting)、Exercise 1の解答を求めてみる。

コード

```#!/usr/bin/env python3
from unittest import TestCase, main
from typing import Any

print('1.')

class TestLinearSearch(TestCase):
def test1(self):
self.assertEqual(linear_search([2, 5, 1, -3], 5), 1)

def test0(self):
self.assertEqual(linear_search([2, 4, 2], 2), 2)

def test_none1(self):
self.assertEqual(linear_search([2, 5, 1, -3], 4), -1)

def test_empty(self):
self.assertEqual(linear_search([], 5), -1)

def linear_search(lst: list, value: Any) -> int:
i: int = len(lst) - 1
while i >= 0 and lst[i] != value:
i -= 1
if i < 0:
return -1
return i

class TestLinearSearchForLoop(TestCase):
def test1(self):
self.assertEqual(linear_search_for_loop([2, 5, 1, -3], 5), 1)

def test0(self):
self.assertEqual(linear_search_for_loop([2, 4, 2], 2), 2)

def test_none1(self):
self.assertEqual(linear_search_for_loop([2, 5, 1, -3], 4), -1)

def test_empty(self):
self.assertEqual(linear_search_for_loop([], 5), -1)

def linear_search_for_loop(lst: list, value: Any) -> int:
for i in range(len(lst) - 1, -1, -1):
if lst[i] == value:
return i
return -1

class TestLinearSearchSentinel(TestCase):
def test1(self):
self.assertEqual(linear_search_sentinel([2, 5, 1, -3], 5), 1)

def test0(self):
self.assertEqual(linear_search_sentinel([2, 4, 2], 2), 2)

def test_none1(self):
self.assertEqual(linear_search_sentinel([2, 5, 1, -3], 4), -1)

def test_empty(self):
self.assertEqual(linear_search_sentinel([], 5), -1)

def linear_search_sentinel(lst: list, value: Any) -> int:
lst.insert(0, value)
i = len(lst) - 1
while lst[i] != value:
i -= 1
lst.pop(0)
if i == 0:
return -1
return i - 1

if __name__ == "__main__":
main()
```

```% ./sample1.py
1.
FFFF
======================================================================
FAIL: test0 (__main__.TestLinearSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 13, in test0
self.assertEqual(linear_search([2, 4, 2], 2), 2)
AssertionError: None != 2

======================================================================
FAIL: test1 (__main__.TestLinearSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 10, in test1
self.assertEqual(linear_search([2, 5, 1, -3], 5), 1)
AssertionError: None != 1

======================================================================
FAIL: test_empty (__main__.TestLinearSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 19, in test_empty
self.assertEqual(linear_search([], 5), -1)
AssertionError: None != -1

======================================================================
FAIL: test_none1 (__main__.TestLinearSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 16, in test_none1
self.assertEqual(linear_search([2, 5, 1, -3], 4), -1)
AssertionError: None != -1

----------------------------------------------------------------------
Ran 4 tests in 0.001s

FAILED (failures=4)
% ./sample1.py
1.
....
----------------------------------------------------------------------
Ran 4 tests in 0.000s

OK
% ./sample1.py
1.
....FFFF
======================================================================
FAIL: test0 (__main__.TestLinearSearchForLoop)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 36, in test0
self.assertEqual(linear_search_for_loop([2, 4, 2], 2), 2)
AssertionError: None != 2

======================================================================
FAIL: test1 (__main__.TestLinearSearchForLoop)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 33, in test1
self.assertEqual(linear_search_for_loop([2, 5, 1, -3], 5), 1)
AssertionError: None != 1

======================================================================
FAIL: test_empty (__main__.TestLinearSearchForLoop)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 42, in test_empty
self.assertEqual(linear_search_for_loop([], 5), -1)
AssertionError: None != -1

======================================================================
FAIL: test_none1 (__main__.TestLinearSearchForLoop)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 39, in test_none1
self.assertEqual(linear_search_for_loop([2, 5, 1, -3], 4), -1)
AssertionError: None != -1

----------------------------------------------------------------------
Ran 8 tests in 0.001s

FAILED (failures=4)
% ./sample1.py
1.
........
----------------------------------------------------------------------
Ran 8 tests in 0.000s

OK
% ./sample1.py
1.
........FFFF
======================================================================
FAIL: test0 (__main__.TestLinearSearchSentinel)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 57, in test0
self.assertEqual(linear_search_sentinel([2, 4, 2], 2), 2)
AssertionError: None != 2

======================================================================
FAIL: test1 (__main__.TestLinearSearchSentinel)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 54, in test1
self.assertEqual(linear_search_sentinel([2, 5, 1, -3], 5), 1)
AssertionError: None != 1

======================================================================
FAIL: test_empty (__main__.TestLinearSearchSentinel)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 63, in test_empty
self.assertEqual(linear_search_sentinel([], 5), -1)
AssertionError: None != -1

======================================================================
FAIL: test_none1 (__main__.TestLinearSearchSentinel)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample1.py", line 60, in test_none1
self.assertEqual(linear_search_sentinel([2, 5, 1, -3], 4), -1)
AssertionError: None != -1

----------------------------------------------------------------------
Ran 12 tests in 0.001s

FAILED (failures=4)
% open ../Exercise\ Solutions/Chapter13.pdf
% ./sample1.py
1.
............
----------------------------------------------------------------------
Ran 12 tests in 0.001s

OK
% ./sample1.py -v
1.
test0 (__main__.TestLinearSearch) ... ok
test1 (__main__.TestLinearSearch) ... ok
test_empty (__main__.TestLinearSearch) ... ok
test_none1 (__main__.TestLinearSearch) ... ok
test0 (__main__.TestLinearSearchForLoop) ... ok
test1 (__main__.TestLinearSearchForLoop) ... ok
test_empty (__main__.TestLinearSearchForLoop) ... ok
test_none1 (__main__.TestLinearSearchForLoop) ... ok
test0 (__main__.TestLinearSearchSentinel) ... ok
test1 (__main__.TestLinearSearchSentinel) ... ok
test_empty (__main__.TestLinearSearchSentinel) ... ok
test_none1 (__main__.TestLinearSearchSentinel) ... ok

----------------------------------------------------------------------
Ran 12 tests in 0.001s

OK
% mypy sample1.py
Success: no issues found in 1 source file
%
```