-
Notifications
You must be signed in to change notification settings - Fork 0
/
Decoding.py
114 lines (100 loc) · 3.57 KB
/
Decoding.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
"""
This method determines whether a list of square matrices of the same size can
be decoded according to fountain code.
"""
def is_decodable(list_of_matrices):
"""
Checks if all the items have been decoded.
"""
def all_true(found):
for item in found:
if not item:
return False
return True
if len(list_of_matrices) == 0:
return False
size = len(list_of_matrices[0])**2
element_connections = [[] for x in range(0,size)]
list_connections = [[] for x in range(0,len(list_of_matrices))]
found = [False for x in range(0,size)]
"""
This part of the code creates lists on the element
side and on the list side in order to run the algorithm
to test whether it is decodable.
"""
index = 0
while index < len(list_of_matrices):
matrix = list_of_matrices[index]
for i in range(0, len(matrix)):
for j in range(0, len(matrix)):
checked = matrix[i][j]
if(checked):
element_num = i*len(matrix) + j
list_connections[index].append(element_num)
element_connections[element_num].append(index)
index = index + 1;
"""
This part of the code uses the list created in the previous section
to test if this combination of matrices is decodable.
"""
while not all_true(found):
hasChanged = False
for lis in list_connections:
if len(lis) == 1:
element_index = lis[0]
found[element_index] = True
to_delete = element_connections[element_index]
for index in to_delete:
list_connections[index].remove(element_index)
hasChanged = True
if not hasChanged:
return False
return True
"""
This tests the is_decodable method.
"""
def test():
all_passed = True
matrix1 = [[True,True, True],[True,True, True],[True, True, True]]
matrix2 = [[True,True, False],[True,True, False],[True, True, False]]
matrix3 = [[True,True, False],[False,False, False],[False, False, False]]
matrix4 = [[False,True, False],[False,False, False],[False, False, False]]
matrix5 = [[False,False, False],[True,True, True],[False, False, False]]
matrix6 = [[False,False, False],[True,True, False],[False, False, False]]
matrix7 = [[False,False, False],[True,False, False],[False, False, False]]
matrix8 = [[False,False, False],[False,False, False],[True, False, False]]
matrix9 = [[False,False, False],[False,False, False],[False, True, False]]
matrix10 = [[False,False, False],[False,False, False],[True, True, True]]
# Should be True.
first_test = (is_decodable([matrix1, matrix2, matrix3, matrix4, matrix5, matrix6, matrix7, matrix8, matrix9, matrix10]))
if(not first_test):
print("First test failed.")
all_passed = False
matrix1 = [[True,True, False],[True,True, False],[True, False, False]]
matrix2 = [[True, True, False],[True, False, False], [True, True, True]]
matrix3 = [[True,False, False],[True,True, True],[True, True, False]]
# Should be False.
second_test = not (is_decodable([matrix1, matrix2, matrix3]))
if(not second_test):
print("Second test failed.")
all_passed = False
matrix1 = [[True, True], [True, True]]
matrix2 = [[False, False], [True, False]]
matrix3 = [[True, True], [False, False]]
matrix4 = [[False, True], [False, False]]
# Should be True
third_test = is_decodable([matrix1, matrix2, matrix3, matrix4])
if(not third_test):
print("Third test failed.")
all_passed = False
matrix1 = [[True, True], [True, True]]
matrix2 = [[False, False], [True, False]]
matrix3 = [[True, True], [False, False]]
# Should be False
fourth_test = not (is_decodable([matrix1, matrix2, matrix3]))
if(not third_test):
print("Fourt test failed.")
all_passed = False
# Prints if everything is passed.
if(all_passed):
print("All tests passed.")