開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Python 3.7 (プログラミング言語)
問題解決の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 コメント:
コメントを投稿