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
|
import math
import pytest
from backtracking.all_combinations import combination_lists, generate_all_combinations
from backtracking.all_permutations import generate_all_permutations
from backtracking.all_subsequences import generate_all_subsequences
from backtracking.coloring import color
from backtracking.combination_sum import combination_sum
from backtracking.crossword_puzzle_solver import solve_crossword
from backtracking.generate_parentheses import generate_parenthesis
from backtracking.hamiltonian_cycle import hamilton_cycle
from backtracking.knight_tour import get_valid_pos, is_complete, open_knight_tour
from backtracking.match_word_pattern import match_word_pattern
from backtracking.minimax import minimax
from backtracking.n_queens import is_safe
from backtracking.n_queens import solve as n_queens_solve
from backtracking.n_queens_math import depth_first_search
from backtracking.power_sum import solve
from backtracking.rat_in_maze import solve_maze
from backtracking.sudoku import sudoku
from backtracking.sum_of_subsets import generate_sum_of_subsets_soln
from backtracking.word_search import word_exists
@pytest.mark.parametrize("sequence", [[1, 2, 3], ["A", "B", "C"]])
def test_generate_all_permutations(benchmark, sequence):
benchmark(generate_all_permutations, sequence)
@pytest.mark.parametrize("n, k", [(4, 2), (0, 0), (5, 4)])
def test_combination_lists(benchmark, n, k):
benchmark(combination_lists, n, k)
@pytest.mark.parametrize("n, k", [(4, 2), (0, 0), (5, 4)])
def test_generate_all_combinations(benchmark, n, k):
benchmark(generate_all_combinations, n, k)
@pytest.mark.parametrize("sequence", [[3, 2, 1], ["A", "B"]])
def test_generate_all_subsequences(benchmark, sequence):
benchmark(generate_all_subsequences, sequence)
@pytest.mark.parametrize("candidates, target", [([2, 3, 5], 8)])
def test_combination_sum(benchmark, candidates, target):
benchmark(combination_sum, candidates, target)
@pytest.mark.parametrize(
"initial_grid",
[
[
[3, 0, 6, 5, 0, 8, 4, 0, 0],
[5, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 7, 0, 0, 0, 0, 3, 1],
[0, 0, 3, 0, 1, 0, 0, 8, 0],
[9, 0, 0, 8, 6, 3, 0, 0, 5],
[0, 5, 0, 0, 9, 0, 6, 0, 0],
[1, 3, 0, 0, 0, 0, 2, 5, 0],
[0, 0, 0, 0, 0, 0, 0, 7, 4],
[0, 0, 5, 2, 0, 6, 3, 0, 0],
]
],
)
def test_sudoku(benchmark, initial_grid):
benchmark(sudoku, initial_grid)
@pytest.mark.parametrize("nums, max_sum", [([3, 34, 4, 12, 5, 2], 9)])
def test_generate_sum_of_subsets_soln(benchmark, nums, max_sum):
benchmark(generate_sum_of_subsets_soln, nums, max_sum)
@pytest.mark.parametrize("scores", [[90, 23, 6, 33, 21, 65, 123, 34423]])
def test_minimax(benchmark, scores):
height = math.log(len(scores), 2)
benchmark(minimax, 0, 0, True, scores, height)
@pytest.mark.parametrize(
"graph, max_colors",
[
(
[
[0, 1, 0, 0, 0],
[1, 0, 1, 0, 1],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 0],
[0, 1, 0, 0, 0],
],
3,
)
],
)
def test_color(benchmark, graph, max_colors):
benchmark(color, graph, max_colors)
@pytest.mark.parametrize("n", [3])
def test_generate_parenthesis(benchmark, n):
benchmark(generate_parenthesis, n)
@pytest.mark.parametrize("x, n", [(13, 2)])
def test_solve_power_sum(benchmark, x, n):
benchmark(solve, x, n)
@pytest.mark.parametrize("board, row, col", [([[0, 0, 0], [0, 0, 0], [0, 0, 0]], 1, 1)])
def test_is_safe(benchmark, board, row, col):
benchmark(is_safe, board, row, col)
@pytest.mark.parametrize("board", [[[0 for i in range(4)] for j in range(4)]])
def test_n_queens_solve(benchmark, board):
benchmark(n_queens_solve, board, 0)
@pytest.mark.parametrize("pattern, string", [("aba", "GraphTreesGraph")])
def test_match_word_pattern(benchmark, pattern, string):
benchmark(match_word_pattern, pattern, string)
@pytest.mark.parametrize("pos, board_size", [((1, 3), 4)])
def test_get_valid_pos(benchmark, pos, board_size):
benchmark(get_valid_pos, pos, board_size)
@pytest.mark.parametrize("board", [[[1]]])
def test_is_complete(benchmark, board):
benchmark(is_complete, board)
@pytest.mark.parametrize("board_size", [1])
def test_open_knight_tour(benchmark, board_size):
benchmark(open_knight_tour, board_size)
@pytest.mark.parametrize(
"graph",
[
[
[0, 1, 0, 1, 0],
[1, 0, 1, 1, 1],
[0, 1, 0, 0, 1],
[1, 1, 0, 0, 1],
[0, 1, 1, 1, 0],
]
],
)
def test_hamilton_cycle(benchmark, graph):
benchmark(hamilton_cycle, graph)
@pytest.mark.parametrize(
"maze",
[
[
[0, 1, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1],
[0, 0, 1, 0, 0],
[1, 0, 0, 1, 0],
]
],
)
def test_solve_maze(benchmark, maze):
benchmark(solve_maze, maze, 0, 0, len(maze) - 1, len(maze) - 1)
@pytest.mark.parametrize(
"board, word",
[([["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], "ABCCED")],
)
def test_word_exists(benchmark, board, word):
benchmark(word_exists, board, word)
@pytest.mark.parametrize(
"puzzle, words", [([[""] * 3 for _ in range(3)], ["cat", "dog", "car"])]
)
def test_solve_crossword(benchmark, puzzle, words):
benchmark(solve_crossword, puzzle, words)
@pytest.mark.parametrize("n", [4])
def test_depth_first_search(benchmark, n):
boards = []
benchmark(depth_first_search, [], [], [], boards, n)
|
