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

Practical Programming
楽天ブックス 紀伊国屋書店

開発環境

• macOS Catalina - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.8 (プログラミング言語)

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()

入出力結果(Zsh、PowerShell、Terminal、Jupyter(IPython))

% ./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
%