Add static typing to backtracking algorithms (#2684) · zinating/algorithms-python@e077662 · GitHub
Skip to content

Commit e077662

Browse files
jenia90github-actionspoyea
authored
Add static typing to backtracking algorithms (TheAlgorithms#2684)
* Added static typing to backtracking algorithms * Ran psf/black to fix some minor issues. * updating DIRECTORY.md * updating DIRECTORY.md Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: John Law <johnlaw.po@gmail.com>
1 parent 5de90aa commit e077662

6 files changed

Lines changed: 34 additions & 16 deletions

File tree

‎DIRECTORY.md‎

Lines changed: 8 additions & 5 deletions

‎backtracking/all_combinations.py‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,13 @@ def generate_all_combinations(n: int, k: int) -> [[int]]:
1616
return result
1717

1818

19-
def create_all_state(increment, total_number, level, current_list, total_list):
19+
def create_all_state(
20+
increment: int,
21+
total_number: int,
22+
level: int,
23+
current_list: [int],
24+
total_list: [int],
25+
) -> None:
2026
if level == 0:
2127
total_list.append(current_list[:])
2228
return
@@ -27,7 +33,7 @@ def create_all_state(increment, total_number, level, current_list, total_list):
2733
current_list.pop()
2834

2935

30-
def print_all_state(total_list):
36+
def print_all_state(total_list: [int]) -> None:
3137
for i in total_list:
3238
print(*i)
3339

‎backtracking/all_permutations.py‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,11 +7,13 @@
77
"""
88

99

10-
def generate_all_permutations(sequence):
10+
def generate_all_permutations(sequence: [int]) -> None:
1111
create_state_space_tree(sequence, [], 0, [0 for i in range(len(sequence))])
1212

1313

14-
def create_state_space_tree(sequence, current_sequence, index, index_used):
14+
def create_state_space_tree(
15+
sequence: [int], current_sequence: [int], index: int, index_used: int
16+
) -> None:
1517
"""
1618
Creates a state space tree to iterate through each branch using DFS.
1719
We know that each state has exactly len(sequence) - index children.

‎backtracking/n_queens.py‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@
1010
solution = []
1111

1212

13-
def isSafe(board, row, column):
13+
def isSafe(board: [[int]], row: int, column: int) -> bool:
1414
"""
1515
This function returns a boolean value True if it is safe to place a queen there
1616
considering the current state of the board.
@@ -38,7 +38,7 @@ def isSafe(board, row, column):
3838
return True
3939

4040

41-
def solve(board, row):
41+
def solve(board: [[int]], row: int) -> bool:
4242
"""
4343
It creates a state space tree and calls the safe function until it receives a
4444
False Boolean and terminates that branch and backtracks to the next
@@ -68,7 +68,7 @@ def solve(board, row):
6868
return False
6969

7070

71-
def printboard(board):
71+
def printboard(board: [[int]]) -> None:
7272
"""
7373
Prints the boards that have a successful combination.
7474
"""

‎backtracking/rat_in_maze.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
def solve_maze(maze: list) -> bool:
1+
def solve_maze(maze: [[int]]) -> bool:
22
"""
33
This method solves the "rat in maze" problem.
44
In this problem we have some n by n matrix, a start point and an end point.
@@ -67,7 +67,7 @@ def solve_maze(maze: list) -> bool:
6767
return solved
6868

6969

70-
def run_maze(maze, i, j, solutions):
70+
def run_maze(maze: [[int]], i: int, j: int, solutions: [[int]]) -> bool:
7171
"""
7272
This method is recursive starting from (i, j) and going in one of four directions:
7373
up, down, left, right.

‎backtracking/sum_of_subsets.py‎

Lines changed: 9 additions & 2 deletions

0 commit comments

Comments
 (0)