2019年4月16日火曜日

開発環境

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の21章(質問するにもお金がかかる)、練習問題(問題4)の解答を求めてみる。

コード

Python 3

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


class BSTreeTest(TestCase):
    def setUp(self):
        self.t0 = BSTree()
        self.t1 = BSTree(BSTVertex(22))
        self.t2 = BSTree(BSTVertex(22,
                                   BSTVertex(21)))
        self.t3 = BSTree(BSTVertex(22,
                                   BSTVertex(21),
                                   BSTVertex(23, None, BSTVertex(24))))

    def tearDown(self):
        pass

    def test_len_zero(self):
        self.assertEqual(0, len(self.t0))

    def test_len_one(self):
        self.assertEqual(1, len(self.t1))

    def test_len_two(self):
        self.assertEqual(2, len(self.t2))

    def test_len_four(self):
        self.assertEqual(4, len(self.t3))

    def test_range_keys(self):
        bst = BSTree(BSTVertex(22,
                               BSTVertex(14,
                                         BSTVertex(2, None, None),
                                         BSTVertex(17, None, None)),
                               BSTVertex(33,
                                         BSTVertex(27, None, None),
                                         None)))
        self.assertEqual([14, 17, 22], bst.range_keys(10, 22))


class BSTVertex:
    def __init__(self, val, left_child=None, right_child=None):
        self.val = val
        self.left_child = left_child
        self.right_child = right_child

    def __len__(self):
        count = 1
        if self.left_child is not None:
            count += len(self.left_child)
        if self.right_child is not None:
            count += len(self.right_child)
        return count

    def range_keys(self, k1, k2):
        keys = []
        if k1 <= self.val <= k2:
            keys.append(self.val)
        if self.left_child is not None:
            keys += self.left_child.range_keys(k1, k2)
        if self.right_child is not None:
            keys += self.right_child.range_keys(k1, k2)
        return sorted(keys)


class BSTree:
    def __init__(self, root=None):
        self.root = root

    def lookup(self, val) -> bool:
        def helper(val, vertex):
            if vertex == None:
                return False
            if val == vertex.val:
                return True
            if val < vertex.val:
                return helper(val, vertex.left_child)
            return lookup(val, vertex.right_child)
        return helper(val, self.root)

    def __len__(self) -> int:
        if self.root is None:
            return 0
        return len(self.root)

    def range_keys(self, k1, k2):
        if self.root is None:
            return []
        return self.root.range_keys(k1, k2)


if __name__ == '__main__':
    main()

入出力結果(cmd(コマンドプロンプト)、Terminal、Jupyter(IPython))

C:\Usrs\...>py sample4.py 
EEEE
======================================================================
ERROR: test_len_four (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 28, in test_len_four
    self.assertEqual(4, len(self.t3))
TypeError: 'NoneType' object cannot be interpreted as an integer

======================================================================
ERROR: test_len_one (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 22, in test_len_one
    self.assertEqual(1, len(self.t1))
TypeError: 'NoneType' object cannot be interpreted as an integer

======================================================================
ERROR: test_len_two (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 25, in test_len_two
    self.assertEqual(2, len(self.t2))
TypeError: 'NoneType' object cannot be interpreted as an integer

======================================================================
ERROR: test_len_zero (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 19, in test_len_zero
    self.assertEqual(0, len(self.t0))
TypeError: 'NoneType' object cannot be interpreted as an integer

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

FAILED (errors=4)

C:\Usrs\...>py sample4.py 
EEE.
======================================================================
ERROR: test_len_four (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 28, in test_len_four
    self.assertEqual(4, len(self.t3))
  File "sample4.py", line 64, in __len__
    return len(self.root)
TypeError: object of type 'BSTVertex' has no len()

======================================================================
ERROR: test_len_one (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 22, in test_len_one
    self.assertEqual(1, len(self.t1))
  File "sample4.py", line 64, in __len__
    return len(self.root)
TypeError: object of type 'BSTVertex' has no len()

======================================================================
ERROR: test_len_two (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 25, in test_len_two
    self.assertEqual(2, len(self.t2))
  File "sample4.py", line 64, in __len__
    return len(self.root)
TypeError: object of type 'BSTVertex' has no len()

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

FAILED (errors=3)

C:\Usrs\...>py sample4.py 
F...
======================================================================
FAIL: test_len_four (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 28, in test_len_four
    self.assertEqual(4, len(self.t3))
AssertionError: 4 != 2

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

FAILED (failures=1)

C:\Usrs\...>py sample4.py 
....
----------------------------------------------------------------------
Ran 4 tests in 0.000s

OK

C:\Usrs\...>py sample4.py 
....E
======================================================================
ERROR: test_range_keys (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 38, in test_range_keys
    self.assertEqual([14, 17, 22], bst.range_keys(10, 22))
AttributeError: 'BSTree' object has no attribute 'range_keys'

----------------------------------------------------------------------
Ran 5 tests in 0.001s

FAILED (errors=1)

C:\Usrs\...>py sample4.py 
....E
======================================================================
ERROR: test_range_keys (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 38, in test_range_keys
    self.assertEqual([14, 17, 22], bst.range_keys(10, 22))
  File "sample4.py", line 89, in range_keys
    return self.root.range_keys(k1, k2)
AttributeError: 'BSTVertex' object has no attribute 'range_keys'

----------------------------------------------------------------------
Ran 5 tests in 0.001s

FAILED (errors=1)

C:\Usrs\...>py sample4.py 
....E
======================================================================
ERROR: test_range_keys (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "sample4.py", line 38, in test_range_keys
    self.assertEqual([14, 17, 22], bst.range_keys(10, 22))
  File "sample4.py", line 89, in range_keys
    return self.root.range_keys(k1, k2)
  File "sample4.py", line 62, in range_keys
    keys += self.right_child.range_keys(k1, k2)
  File "sample4.py", line 62, in range_keys
    keys += self.right_child.range_keys(k1, k2)
AttributeError: 'NoneType' object has no attribute 'range_keys'

----------------------------------------------------------------------
Ran 5 tests in 0.001s

FAILED (errors=1)

C:\Usrs\...>py sample4.py 
.....
----------------------------------------------------------------------
Ran 5 tests in 0.000s

OK

C:\Usrs\...>py sample4.py  -v
test_len_four (__main__.BSTreeTest) ... ok
test_len_one (__main__.BSTreeTest) ... ok
test_len_two (__main__.BSTreeTest) ... ok
test_len_zero (__main__.BSTreeTest) ... ok
test_range_keys (__main__.BSTreeTest) ... ok

----------------------------------------------------------------------
Ran 5 tests in 0.000s

OK

C:\Users\...>

ついでに問題2のsize関数を、ビルトイン関数のlen関数を使えるように、特殊メソッド__len__に変更してみた。

0 コメント:

コメントを投稿

関連コンテンツ