1
exercism fetch python pov

pov_test.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
import unittest

from pov import Tree

# Tests adapted from `problem-specifications//canonical-data.json` @ v1.1.1


class PovTest(unittest.TestCase):
    def assertTreeEquals(self, result, expected):
        self.assertEqual(result, expected,
                         '{} != {}'.format(result, expected))

    def test_singleton_returns_same_tree(self):
        tree = Tree('x')
        self.assertTreeEquals(tree.fromPov('x'), tree)

    def test_can_reroot_tree_with_parent_and_one_sibling(self):
        tree = Tree('parent', [
            Tree('x'),
            Tree('sibling')
        ])
        expected = Tree('x', [
            Tree('parent', [
                Tree('sibling')
            ])
        ])
        self.assertTreeEquals(tree.fromPov('x'), expected)

    def test_can_reroot_tree_with_parent_and_many_siblings(self):
        tree = Tree('parent', [
            Tree('a'),
            Tree('x'),
            Tree('b'),
            Tree('c')
        ])
        expected = Tree('x', [
            Tree('parent', [
                Tree('a'),
                Tree('b'),
                Tree('c')
            ])
        ])
        self.assertTreeEquals(tree.fromPov('x'), expected)

    def test_can_reroot_a_tree_with_new_root_deeply_nested(self):
        tree = Tree('level-0', [
            Tree('level-1', [
                Tree('level-2', [
                    Tree('level-3', [
                        Tree('x')
                    ])
                ])
            ])
        ])
        expected = Tree('x', [
            Tree('level-3', [
                Tree('level-2', [
                    Tree('level-1', [
                        Tree('level-0')
                    ])
                ])
            ])
        ])
        self.assertTreeEquals(tree.fromPov('x'), expected)

    def test_moves_children_of_new_root_to_same_level_as_former_parent(self):
        tree = Tree('parent', [
            Tree('x', [
                Tree('kid-0'),
                Tree('kid-1')
            ])
        ])
        expected = Tree('x', [
            Tree('parent'),
            Tree('kid-0'),
            Tree('kid-1')
        ])
        self.assertTreeEquals(tree.fromPov('x'), expected)

    def test_can_reroot_complex_tree_with_cousins(self):
        tree = Tree('grandparent', [
            Tree('parent', [
                Tree('x', [
                    Tree('kid-0'),
                    Tree('kid-1')
                ]),
                Tree('sibling-0'),
                Tree('sibling-1')
            ]),
            Tree('uncle', [
                Tree('cousin-0'),
                Tree('cousin-1')
            ])
        ])
        expected = Tree('x', [
            Tree('kid-0'),
            Tree('kid-1'),
            Tree('parent', [
                Tree('sibling-0'),
                Tree('sibling-1'),
                Tree('grandparent', [
                    Tree('uncle', [
                        Tree('cousin-0'),
                        Tree('cousin-1')
                    ])
                ])
            ])
        ])
        self.assertTreeEquals(tree.fromPov('x'), expected)

    def test_errors_if_target_does_not_exist_in_singleton_tree(self):
        tree = Tree('x')
        with self.assertRaises(ValueError):
            tree.fromPov('nonexistent')

    def test_errors_if_target_does_not_exist_in_large_tree(self):
        tree = Tree('parent', [
            Tree('x', [
                Tree('kid-0'),
                Tree('kid-1')
            ]),
            Tree('sibling-0'),
            Tree('sibling-1')
        ])
        with self.assertRaises(ValueError):
            tree.fromPov('nonexistent')

    def test_find_path_between_two_nodes(self):
        tree = Tree('parent', [
            Tree('x'),
            Tree('sibling')
        ])
        expected = ['x', 'parent']
        self.assertEqual(tree.pathTo('x', 'parent'), expected)

    def test_can_find_path_to_sibling(self):
        tree = Tree('parent', [
            Tree('a'),
            Tree('x'),
            Tree('b'),
            Tree('c')
        ])
        expected = ['x', 'parent', 'b']
        self.assertEqual(tree.pathTo('x', 'b'), expected)

    def test_can_find_path_to_cousin(self):
        tree = Tree('grandparent', [
            Tree('parent', [
                Tree('x', [
                    Tree('kid-0'),
                    Tree('kid-1')
                ]),
                Tree('sibling-0'),
                Tree('sibling-1')
            ]),
            Tree('uncle', [
                Tree('cousin-0'),
                Tree('cousin-1')
            ])
        ])
        expected = ['x', 'parent', 'grandparent', 'uncle', 'cousin-1']
        self.assertEqual(tree.pathTo('x', 'cousin-1'), expected)

    def test_can_find_path_from_nodes_other_than_x(self):
        tree = Tree('parent', [
            Tree('a'),
            Tree('x'),
            Tree('b'),
            Tree('c')
        ])
        expected = ['a', 'parent', 'c']
        self.assertEqual(tree.pathTo('a', 'c'), expected)

    def test_errors_if_destination_does_not_exist(self):
        tree = Tree('parent', [
            Tree('x', [
                Tree('kid-0'),
                Tree('kid-1')
            ]),
            Tree('sibling-0'),
            Tree('sibling-1')
        ])
        with self.assertRaises(ValueError):
            tree.pathTo('x', 'nonexistent')

    def test_errors_if_source_does_not_exist(self):
        tree = Tree('parent', [
            Tree('x', [
                Tree('kid-0'),
                Tree('kid-1')
            ]),
            Tree('sibling-0'),
            Tree('sibling-1')
        ])
        with self.assertRaises(ValueError):
            tree.pathTo('nonexistent', 'x')


if __name__ == '__main__':
    unittest.main()