## 2020年4月8日水曜日

### Python - Designing Algorithms - Dutch National Flag problem(Edsgar Dijkstra)、リスト、添字、並べ替え、whileループ

Practical Programming: An Introduction to Computer Science Using Python 3.6 (Paul Gries(著)、Jennifer Campbell(著)、Jason Montojo(著)、Pragmatic Bookshelf)のChapter 12(Designing Algorithms)、Exercise 7の解答を求めてみる。

コード

```#!/usr/bin/env python3
from unittest import TestCase, main
from typing import List, Tuple, Union

print('7.')

class TestFindTwoSmallest(TestCase):
def test_empty(self):
colors = []
dutch_flag([])
self.assertEqual(colors, [])

def test_red(self):
colors = ['red']
dutch_flag(colors)
self.assertEqual(colors, ['red'])

def test_green(self):
colors = ['green']
dutch_flag(colors)
self.assertEqual(colors, ['green'])

def test_blue(self):
colors = ['blue']
dutch_flag(colors)
self.assertEqual(colors, ['blue'])

def test_red_green(self):
colors = ['red', 'green']
dutch_flag(colors)
self.assertEqual(colors, ['red', 'green'])

def test_blue_red(self):
colors = ['blue', 'red']
dutch_flag(colors)
self.assertEqual(colors, ['red', 'blue'])

def test_other(self):
colors = ['blue', 'red', 'green', 'green', 'red',
'blue', 'blue', 'blue', 'red', 'green']
dutch_flag(colors)
self.assertEqual(colors,
['red', 'red', 'red',
'green', 'green', 'green',
'blue', 'blue', 'blue', 'blue'])

def dutch_flag(colors: List[str]) -> None:
i: int = 0
green_index: int = 0
last_index: int = len(colors) - 1
while i <= last_index:
if colors[i] == 'red':
colors[green_index], colors[i] = colors[i], colors[green_index]
i += 1
green_index += 1
elif colors[i] == 'green':
i += 1
else:
colors[last_index], colors[i] = colors[i], colors[last_index]
last_index -= 1

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

```% ./sample7.py
7.
.F..F..
======================================================================
FAIL: test_blue_red (__main__.TestFindTwoSmallest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample7.py", line 37, in test_blue_red
self.assertEqual(colors, ['red', 'blue'])
AssertionError: Lists differ: ['blue', 'red'] != ['red', 'blue']

First differing element 0:
'blue'
'red'

- ['blue', 'red']
+ ['red', 'blue']

======================================================================
FAIL: test_other (__main__.TestFindTwoSmallest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "./sample7.py", line 43, in test_other
self.assertEqual(colors,
AssertionError: Lists differ: ['blue', 'red', 'green', 'green', 'red', 'blue', 'blue', 'blue', 'red', 'green'] != ['red', 'red', 'red', 'green', 'green', 'green', 'blue', 'blue', 'blue', 'blue']

First differing element 0:
'blue'
'red'

- ['blue', 'red', 'green', 'green', 'red', 'blue', 'blue', 'blue', 'red', 'green']
?  --------                            ^                            ^ ----------

+ ['red', 'red', 'red', 'green', 'green', 'green', 'blue', 'blue', 'blue', 'blue']
?        ++++++++++++++                    +  ^^                            ^^^

----------------------------------------------------------------------
Ran 7 tests in 0.002s

FAILED (failures=2)
% mypy sample7.py
Success: no issues found in 1 source file
% ./sample7.py -v
7.
test_blue (__main__.TestFindTwoSmallest) ... ok
test_blue_red (__main__.TestFindTwoSmallest) ... ok
test_empty (__main__.TestFindTwoSmallest) ... ok
test_green (__main__.TestFindTwoSmallest) ... ok
test_other (__main__.TestFindTwoSmallest) ... ok
test_red (__main__.TestFindTwoSmallest) ... ok
test_red_green (__main__.TestFindTwoSmallest) ... ok

----------------------------------------------------------------------
Ran 7 tests in 0.000s

OK
%
```