Skip to content

Commit 6288300

Browse files
author
Мето Трајковски
committed
Added new solutions
1 parent 19950e4 commit 6288300

9 files changed

Lines changed: 765 additions & 0 deletions

File tree

‎Backtracking/power_set.py‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
'''
2+
The power set
3+
4+
The power set of a set is the set of all its subsets.
5+
Write a function that, given a set, generates its power set.
6+
7+
Input: {1, 2, 3}
8+
Output: {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
9+
* You may also use a list or array to represent a set.
10+
11+
=========================================
12+
Simple recursive combinations algorithm.
13+
Time Complexity: O(Sum(C(I, N))) , sum of all combinations between 0 and N = C(0, N) + C(1, N) + ... + C(N, N)
14+
Space Complexity: O(Sum(C(I, N))) , this is for the result array, if we print the number then the space complexity will be O(1)
15+
'''
16+
17+
18+
############
19+
# Solution #
20+
############
21+
22+
def power_set(arr):
23+
return combinations(arr, [], 0)
24+
25+
# arr and taken are the same pointer always
26+
# the same arrays are used always
27+
def combinations(arr, taken, pos):
28+
result = []
29+
result.append([arr[i] for i in taken]) # create the current combination
30+
31+
if len(arr) == pos:
32+
return result
33+
34+
n = len(arr)
35+
# start from the last position (don't need duplicates)
36+
for i in range(pos, n):
37+
taken.append(i)
38+
result += combinations(arr, taken, i + 1) # append the combinations
39+
del taken[-1] # return to the old state
40+
41+
return result
42+
43+
44+
###########
45+
# Testing #
46+
###########
47+
48+
# Test 1
49+
# Correct result => [[], [1], [1, 2], [2]]
50+
print(power_set([1, 2]))
51+
52+
# Test 2
53+
# Correct result => [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
54+
print(power_set([1, 2, 3]))

‎Backtracking/queens_problem.py‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
'''
2+
Queens Problem
3+
4+
You have an N by N board. Write a function that, given N, returns the number of possible arrangements
5+
of the board where N queens can be placed on the board without threatening each other,
6+
i.e. no two queens share the same row, column, or diagonal.
7+
8+
=========================================
9+
Backtracking solution.
10+
Time Complexity: O(N!) (but I think it's much faster!)
11+
Space Complexity: O(N)
12+
* There are much faster solutions, like O(N^2)
13+
'''
14+
15+
16+
############
17+
# Solution #
18+
############
19+
20+
def place_n_queens(n):
21+
columns = [False for i in range(n)]
22+
order = []
23+
24+
return backtracking(columns, order)
25+
26+
def backtracking(columns, order):
27+
# columns and order are references, no extra memory for those arrays (they are just pointers)
28+
n = len(columns)
29+
30+
if len(order) == n:
31+
return 1
32+
33+
total = 0
34+
35+
for i in range(n):
36+
if (not columns[i]) and check_diagonals(order, i):
37+
order.append(i)
38+
columns[i] = True
39+
total += backtracking(columns, order)
40+
# return to the old state
41+
columns[i] = False
42+
del order[-1]
43+
44+
return total
45+
46+
def check_diagonals(order, pos):
47+
current_row = len(order)
48+
49+
for i in range(current_row):
50+
if (i - order[i]) == (current_row - pos):
51+
return False
52+
if (i + order[i]) == (current_row + pos):
53+
return False
54+
55+
return True
56+
57+
58+
###########
59+
# Testing #
60+
###########
61+
62+
# Test 1
63+
# Correct result => 1
64+
print(place_n_queens(1))
65+
66+
# Test 2
67+
# Correct result => 0
68+
print(place_n_queens(2))
69+
70+
# Test 3
71+
# Correct result => 0
72+
print(place_n_queens(3))
73+
74+
# Test 4
75+
# Correct result => 2
76+
print(place_n_queens(4))
77+
78+
# Test 5
79+
# Correct result => 10
80+
print(place_n_queens(5))
81+
82+
# Test 6
83+
# Correct result => 4
84+
print(place_n_queens(6))
85+
86+
# Test 7
87+
# Correct result => 40
88+
print(place_n_queens(7))
89+
90+
# Test 8
91+
# Correct result => 92
92+
print(place_n_queens(8))
93+
94+
# Test 9
95+
# Correct result => 352
96+
print(place_n_queens(9))
97+
98+
# Test 10
99+
# Correct result => 724
100+
print(place_n_queens(10))

‎Backtracking/river_sizes.py‎

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
'''
2+
River Sizes
3+
4+
You are given a two-dimensional array (matrix) of potentially unequal height and width containing only 0s and 1s.
5+
Each 0 represents land, and each 1 represents part of a river. A river consists of any number of 1s that are
6+
either horizontally or vertically adjacent (but not diagonally adjacent).
7+
The number of adjacent 1s forming a river determine its size.
8+
Write a function that returns an array of the sizes of all rivers represented in the input matrix.
9+
Note that these sizes do not need to be in any particular order.
10+
11+
Input:
12+
[
13+
[1, 0, 0, 1],
14+
[1, 0, 1, 0],
15+
[0, 0, 1, 0],
16+
[1, 0, 1, 0]
17+
]
18+
Output: [2, 1, 3, 1]
19+
20+
21+
=========================================
22+
This problem can be solved using DFS or BFS.
23+
If 1 is found, find all horizontal or vertical neighbours (1s), and mark them as 0.
24+
Time Complexity: O(N*M)
25+
Space Complexity: O(R) , R = num of rivers
26+
'''
27+
28+
29+
############
30+
# Solution #
31+
############
32+
33+
def river_sizes(matrix):
34+
n = len(matrix)
35+
m = len(matrix[0])
36+
37+
results = []
38+
39+
for i in range(n):
40+
for j in range(m):
41+
if matrix[i][j] != 0:
42+
# find the river size
43+
size = dfs((i, j), matrix)
44+
45+
# save the river size
46+
results.append(size)
47+
48+
return results
49+
50+
def dfs(coord, matrix):
51+
(i, j) = coord
52+
53+
if i < 0 or j < 0:
54+
# invalid position
55+
return 0
56+
57+
n = len(matrix)
58+
m = len(matrix[0])
59+
60+
if i == n or j == m:
61+
# invalid position
62+
return 0
63+
64+
if matrix[i][j] == 0:
65+
# not a river
66+
return 0
67+
68+
# update the matrix, the matrix is passed by reference
69+
matrix[i][j] = 0
70+
# this position is part of river
71+
size = 1
72+
73+
# directions: down, left, up, right
74+
dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
75+
76+
# check all 4 directions
77+
for d in dirs:
78+
size += dfs((i + d[0], j + d[1]), matrix)
79+
80+
return size
81+
82+
83+
###########
84+
# Testing #
85+
###########
86+
87+
# Test 1
88+
# Correct result => [2, 1, 3, 1]
89+
matrix = [
90+
[1, 0, 0, 1],
91+
[1, 0, 1, 0],
92+
[0, 0, 1, 0],
93+
[1, 0, 1, 0]
94+
]
95+
print(river_sizes(matrix))

‎Dynamic Programming/number_of_decodings.py‎

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
'''
2+
Number of decodings
3+
4+
Given the mapping a=1, b=2, ... , z=26, and an encoded message, count the number of ways it can be decoded.
5+
For example, the message "111" would give 3, since it could be decoded as "aaa", "ka" and "ak".
6+
All of the messages are decodable!
7+
8+
=========================================
9+
The easiest solution is Brute-Force (building a tree and making all combinations),
10+
and in the worst case there will be Fibbionaci(N) combinations, so the worst Time Complexity will be O(Fib(N))
11+
12+
Dynamic programming solution.
13+
Time Complexity: O(N)
14+
Space Complexity: O(N)
15+
'''
16+
17+
18+
############
19+
# Solution #
20+
############
21+
22+
def num_decodings(code):
23+
n = len(code)
24+
dp = [0 for i in range(n)]
25+
26+
if n == 0:
27+
return 0
28+
dp[0] = 1
29+
if n == 1:
30+
return dp[0]
31+
dp[1] = (code[1] != '0') + is_valid(code[0:2])
32+
33+
for i in range(2, n):
34+
if code[i] != '0':
35+
# looking for how many combinations are there till now if this is a single digit
36+
dp[i] += dp[i-1]
37+
if is_valid(code[i-1 : i+1]):
38+
# looking for how many combinations are there till now if this is a number of 2 digits
39+
dp[i] += dp[i-2]
40+
41+
return dp[n-1]
42+
43+
def is_valid(code):
44+
k = int(code)
45+
return (k < 27) and (k > 9)
46+
47+
48+
###########
49+
# Testing #
50+
###########
51+
52+
# Test 1
53+
# Correct result => 5
54+
print(num_decodings('12151'))
55+
56+
# Test 2
57+
# Correct result => 5
58+
print(num_decodings('1111'))
59+
60+
# Test 3
61+
# Correct result => 3
62+
print(num_decodings('111'))
63+
64+
# Test 4
65+
# Correct result => 1
66+
print(num_decodings('1010'))
67+
68+
# Test 5
69+
# Correct result => 4
70+
print(num_decodings('2626'))
71+
72+
# Test 6
73+
# Correct result => 1
74+
print(num_decodings('1'))
75+
76+
# Test 7
77+
# Correct result => 2
78+
print(num_decodings('11'))
79+
80+
# Test 8
81+
# Correct result => 3
82+
print(num_decodings('111'))
83+
84+
# Test 9
85+
# Correct result => 5
86+
print(num_decodings('1111'))
87+
88+
# Test 10
89+
# Correct result => 8
90+
print(num_decodings('11111'))
91+
92+
# Test 11
93+
# Correct result => 13
94+
print(num_decodings('111111'))
95+
96+
# Test 12
97+
# Correct result => 21
98+
print(num_decodings('1111111'))
99+
100+
# Test 13
101+
# Correct result => 34
102+
print(num_decodings('11111111'))

0 commit comments

Comments
 (0)