test: add benches for TheAlgorithms/backtracking

art049 · art049 · commit 630460a17ec5 · 2024-09-19T15:03:16.000+02:00
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_all_combinations.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_all_combinations.py
@@ -0,0 +1,17 @@
+from backtracking.all_combinations import combination_lists, generate_all_combinations
+
+
+def test_combination_lists(benchmark):
+    benchmark(combination_lists, n=4, k=2)
+
+
+def test_generate_all_combinations(benchmark):
+    benchmark(generate_all_combinations, n=4, k=2)
+
+
+def test_generate_all_combinations_edge_case(benchmark):
+    benchmark(generate_all_combinations, n=0, k=0)
+
+
+def test_generate_all_combinations_larger(benchmark):
+    benchmark(generate_all_combinations, n=5, k=4)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_all_permutations.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_all_permutations.py
@@ -0,0 +1,11 @@
+from backtracking.all_permutations import generate_all_permutations
+
+
+def test_generate_all_permutations(benchmark):
+    sequence = [1, 2, 3]
+    benchmark(generate_all_permutations, sequence)
+
+
+def test_generate_all_permutations_str(benchmark):
+    sequence = ["A", "B", "C"]
+    benchmark(generate_all_permutations, sequence)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_all_subsequences.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_all_subsequences.py
@@ -0,0 +1,11 @@
+from backtracking.all_subsequences import generate_all_subsequences
+
+
+def test_generate_all_subsequences(benchmark):
+    sequence = [3, 2, 1]
+    benchmark(generate_all_subsequences, sequence)
+
+
+def test_generate_all_subsequences_str(benchmark):
+    sequence = ["A", "B"]
+    benchmark(generate_all_subsequences, sequence)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_coloring.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_coloring.py
@@ -0,0 +1,13 @@
+from backtracking.coloring import color
+
+
+def test_color(benchmark):
+    graph = [
+        [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],
+    ]
+    max_colors = 3
+    benchmark(color, graph, max_colors)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_combination_sum.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_combination_sum.py
@@ -0,0 +1,7 @@
+from backtracking.combination_sum import combination_sum
+
+
+def test_combination_sum(benchmark):
+    candidates = [2, 3, 5]
+    target = 8
+    benchmark(combination_sum, candidates, target)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_crossword_puzzle_solver.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_crossword_puzzle_solver.py
@@ -0,0 +1,7 @@
+from backtracking.crossword_puzzle_solver import solve_crossword
+
+
+def test_solve_crossword(benchmark):
+    puzzle = [[""] * 3 for _ in range(3)]
+    words = ["cat", "dog", "car"]
+    benchmark(solve_crossword, puzzle, words)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_generate_parentheses.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_generate_parentheses.py
@@ -0,0 +1,6 @@
+from backtracking.generate_parentheses import generate_parenthesis
+
+
+def test_generate_parenthesis(benchmark):
+    n = 3
+    benchmark(generate_parenthesis, n)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_hamiltonian_cycle.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_hamiltonian_cycle.py
@@ -0,0 +1,12 @@
+from backtracking.hamiltonian_cycle import hamilton_cycle
+
+
+def test_hamilton_cycle(benchmark):
+    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],
+    ]
+    benchmark(hamilton_cycle, graph)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_knight_tour.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_knight_tour.py
@@ -0,0 +1,13 @@
+from backtracking.knight_tour import get_valid_pos, is_complete, open_knight_tour
+
+
+def test_get_valid_pos(benchmark):
+    benchmark(get_valid_pos, (1, 3), 4)
+
+
+def test_is_complete(benchmark):
+    benchmark(is_complete, [[1]])
+
+
+def test_open_knight_tour(benchmark):
+    benchmark(open_knight_tour, 1)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_match_word_pattern.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_match_word_pattern.py
@@ -0,0 +1,5 @@
+from backtracking.match_word_pattern import match_word_pattern
+
+
+def test_match_word_pattern(benchmark):
+    benchmark(match_word_pattern, "aba", "GraphTreesGraph")
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_minimax.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_minimax.py
@@ -0,0 +1,9 @@
+import math
+
+from backtracking.minimax import minimax
+
+
+def test_minimax(benchmark):
+    scores = [90, 23, 6, 33, 21, 65, 123, 34423]
+    height = math.log(len(scores), 2)
+    benchmark(minimax, 0, 0, True, scores, height)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_n_queens.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_n_queens.py
@@ -0,0 +1,11 @@
+from backtracking.n_queens import is_safe, solve
+
+
+def test_is_safe(benchmark):
+    board = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
+    benchmark(is_safe, board, 1, 1)
+
+
+def test_solve(benchmark):
+    board = [[0 for i in range(4)] for j in range(4)]
+    benchmark(solve, board, 0)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_n_queens_math.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_n_queens_math.py
@@ -0,0 +1,6 @@
+from backtracking.n_queens_math import depth_first_search
+
+
+def test_depth_first_search(benchmark):
+    boards = []
+    benchmark(depth_first_search, [], [], [], boards, 4)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_power_sum.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_power_sum.py
@@ -0,0 +1,5 @@
+from backtracking.power_sum import solve
+
+
+def test_solve(benchmark):
+    benchmark(solve, 13, 2)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_rat_in_maze.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_rat_in_maze.py
@@ -0,0 +1,12 @@
+from backtracking.rat_in_maze import solve_maze
+
+
+def test_solve_maze(benchmark):
+    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],
+    ]
+    benchmark(solve_maze, maze, 0, 0, len(maze) - 1, len(maze) - 1)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_sudoku.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_sudoku.py
@@ -0,0 +1,16 @@
+from backtracking.sudoku import sudoku
+
+
+def test_sudoku(benchmark):
+    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],
+    ]
+    benchmark(sudoku, initial_grid)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_sum_of_subsets.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_sum_of_subsets.py
@@ -0,0 +1,7 @@
+from backtracking.sum_of_subsets import generate_sum_of_subsets_soln
+
+
+def test_generate_sum_of_subsets_soln(benchmark):
+    nums = [3, 34, 4, 12, 5, 2]
+    max_sum = 9
+    benchmark(generate_sum_of_subsets_soln, nums, max_sum)
diff --git a/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_word_search.py b/tests/benchmarks/TheAlgorithms_bench/backtracking/test_bench_word_search.py
@@ -0,0 +1,7 @@
+from backtracking.word_search import word_exists
+
+
+def test_word_exists(benchmark):
+    board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
+    word = "ABCCED"
+    benchmark(word_exists, board, word)
