-
Notifications
You must be signed in to change notification settings - Fork 0
/
matrix.py
331 lines (305 loc) · 13.2 KB
/
matrix.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
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
"""The goal here is to create an implementation of
1. inverse_method
2. the gauss elimination algorithm:
reducing a matrix to row echelon form
performing back substitution on the returned row echelon matrix
for finding unkowns in a system of linear equations
The solution will then hence forth be used to solve the solvit problem that happens
in the leisure page of the standard newspaper
:sample:
B + E + D + F = 17
A + B + D + G = 26
C + f + E + A = 16
H + J + G + H =18
B + A + C + H = 20
E + B + F + J = 19
D + D + E + G = 20
F + G + A + H = 18
"""
import unittest, random, re
try:
import numpy as np
except ImportError:
import operator
import numpy.matlib as mt
from copy import deepcopy
from fractions import Fraction
import unittest
def translate(eqstring, solutions):
solutions = [int(i) for i in solutions]
eqstring = [char.upper() for char in eqstring]
eqlist = [map(str.strip, char.split("+")) for char in eqstring]
temp = []
for charlist in eqlist:
temp.extend(charlist)
unknownset = set(temp)
#issue 1: the system does not translate to a square matrix
translated_matrix = []
for string in eqstring:
coeff = []
for unknown in unknownset:
coeff.append(string.count(unknown))
translated_matrix.append(coeff)
return translated_matrix, list(unknownset), solutions
def add_list(list1, list2):
if len(list1) == len(list2):
ans = []
for i in range(len(list1)):
ans.append(list1[i] + list2[i])
return ans
else: raise Exception()
def squarify(A, x, b):
#make A into a square matrix with order len(b) * len(b)
diff = len(x) - len(b)
for i in range(diff):
first_rand = random.randint(0, len(A) - 1)
second_rand = random.randint(0, len(A) - 1)
A.append(add_list(A[first_rand],A[second_rand]))
b.append(b[first_rand] + b[second_rand])
return A, x, b
def inverse_method(A, x, b):
"""linear system format: Ax = b"""
A, x, b = squarify(A, x, b)
try:
inverse = np.linalg.inv(A)
sols = inverse * b
sols_dic = {}
for i in range(len(sols)):
sols_dic[x[i]] = sols[i]
return sols_dic
except np.linalg.linalg.LinAlgError as err:
print(err.message) #usually singular matrix not invertible
return A, x, b
#Gaussian eliminations
def echelon(A, x, b):
#reducing to row echelon format
x = list(x)
try:
n , m = len(A), len(A[0])
except IndexError:
print("not a Matrix, seems like a vector")
# for a matrix A with order n x m ; n rows and m columns
rows, columns = 0, 0
while rows < n and columns < m:
# get the max for certain columns for all rows
temp = [abs(A[i][columns]) for i in range(rows, n)]
try:
big_ind = np.argmax(temp) #found pivot
except NameError:
big_ind, max_val = max(enumerate(temp), key=operator.itemgetter(1))
big_ind = big_ind + len(A) - len(temp)
big_value = A[big_ind][columns]
if A[big_ind][columns] == 0:
#no pivot, skip column
columns += 1
else:
#swap big_ind with current rows **** DONT FORGET ABOUT THE b ****
if big_ind != rows:
A[big_ind], A[rows] = A[rows], A[big_ind]
b[big_ind], b[rows] = b[rows], b[big_ind]
#optimize full big_ind row by dividing with big-value use fractions
for index in range(m):
A[rows][index] = Fraction(A[rows][index], big_value)
b[rows] = Fraction(b[rows], big_value)
#for all rows below pivot: and b
for index in range(rows+1, n):
fact = deepcopy(A[index][columns])
if A[index][columns] < 0 and A[rows][columns]*fact < 0 or A[index][columns] > 0 and A[rows][columns]*fact > 0:
sign = -1
else:
sign = 1
if fact != 0:
for idx in range(columns, m):
A[index][idx] = A[index][idx] + A[rows][idx] * fact *sign
b[index] = b[index] + b[rows] * fact * sign
#subtract A[rows][column] * 1 - full rows
columns += 1
rows += 1
return A, x, b
def back_substitution(A, x, b):
"""Back substitution"""
# seems like the puzzle leaves 2 variables to be guessed- for this we have no other choice but brute force
# populate dict with unkowns and initialize with zero
d = {}
for _x in list(x):
d[_x] = 0
cset_dict = {} # dict to preserve the state for corr last check
def corr(key, iter1, iter2):
#key is between 0 and 10 excluding both
_in = key < 10 and key > 0
if not _in:
return False
#key is int and not float
_int = Fraction(key, 1).denominator == 1
if not _int:
return False
#key is not the same for the current iterations
if cset_dict.get((iter1, iter2)) is not None:
#means that we have already started recording for this iter
_found = key in cset_dict[(iter1, iter2)]
if not _found:
cset_dict[(iter1, iter2)].add(key)
else:
cset_dict[(iter1, iter2)] = set()
cset_dict[(iter1, iter2)].add(key)
_found = False
return _in and _int and not _found
check = False
try:
for d[x[len(x) -2]] in range(1, 10):
for d[x[len(x) -1]] in range(1, 10):
if d[x[len(x) - 2]] != d[x[len(x) - 1]]:
for row in range(len(A) - 1, -1, -1):
#find the last pivot: will be the first non zero value in current row
def pivot(A):
"""Given a reduced row it will return first non zero"""
for index, value in enumerate(A[row]):
if value != 0:
return value, index
return 0, len(A[row])-1
pivvalue, pivindex = pivot(A)
if pivvalue == 0:
continue #? what if there does not exist a pivot in this row
total = 0
for i in range(len(x)):
if i != pivindex:
total += A[row][i] * d[x[i]]
temp = (b[pivindex] - total)/pivvalue
if corr(temp, d[x[len(x) -2]], d[x[len(x) -1]]):
d[x[pivindex]] = temp
if pivindex == 0:
check = True
raise StopIteration("Found our matches")
else:
break
except StopIteration as err:
pass
if check:
return {key: int(value) for key, value in d.items()}
else:
return "Could not converge, no values of unknowns found within range(1,10)"
def validates(_input):
"""format :E + B + F + J = 19"""
#^\S{1}\s*[+]\s*\S{1}\s*[+]\s*\S{1}\s*[+]\s*\S{1}\s*=\s*\d+\s*$
pattern = r'^\s*\S{1}\s*[+]\s*\S{1}\s*[+]\s*\S{1}\s*[+]\s*\S{1}\s*=\s*\d+\s*$'
if _input.lower() == "quit" or _input.lower() == "q":
raise Exception("Program stopping")
return re.search(pattern, _input)
def separate(_input):
"""sample input = :E + B + F + J = 19"""
temp = _input.split("=")
return [char.strip() for char in temp]
def run():
"""defines the input data structure and form"""
# am thinking using the command line and filling each linear system in a linear line
eqstring, solutions = [], []
print("type in the equations below: sample: E + B + F + J = 19(q/quit)")
for i in range(1,9):
while True:
uinput = input("eq. #{} : ".format(str(i)))
if validates(uinput):
res = separate(uinput)
eqstring.append(res[0])
solutions.append(res[1])
break
else:
print("seems like something went wrong, please retype that(q/quit):")
#here should have A, x, and b
return eqstring, solutions
if __name__ == '__main__':
while True:
try:
eqstring, solutions = run() #put in while loop
A, x, b = translate(eqstring, solutions)
A, x, b = echelon(A,x,b)
d = back_substitution(A,x,b)
print(d)
#the end
except Exception as error:
if error.args[0] == "Program stopping":
print(error)
break
else:
raise(error)
class SecondaryTests(unittest.TestCase):
def test_validates_function_for_valid_data(self):
sample1 = "E + B + F + J = 19"
sample2 = " E + B + F + J = 19 "
sample3 = "E + b + F + j = 19"
sample4 = "e + b + f + j = 19"
self.assertTrue(validates(sample1))
self.assertTrue(validates(sample2))
self.assertTrue(validates(sample3))
self.assertTrue(validates(sample4))
def test_validate_function_at_stop(self):
with self.assertRaises(Exception):
validates("q")
validates("quit")
validates("Quit")
validates("qUiT")
validates("QUIT")
def test_validate_function_for_invalid_data(self):
sample1 = "E B + F + J = 19"
sample2 = "E + B + F + J 19"
sample3 = "E + B + F + J = D"
sample4 = "E + B + F = 19"
self.assertFalse(validates(sample1))
self.assertFalse(validates(sample2))
self.assertFalse(validates(sample3))
self.assertFalse(validates(sample4))
def test_separate_function_for_valid(self):
sample = "E + B + F + J = 19"
res = separate(sample)
self.assertListEqual(res, ["E + B + F + J", "19"])
def test_translate_function(self):
eqstring = ["B + E + D + F","A +B + D + G ","C + F + E + A", "H + J + G + H",
"B + A + C + H","E + B + F + J ","D + D + E + G", "F + G + A + H"]
solutions = [17, 26, 16, 18, 20, 19, 20, 18]
eqsol = [" 17"," 26"," 16"," 18"," 20"," 19"," 20"," 18"]
res = translate(eqstring, eqsol)
import random
self.assertIsInstance(res[random.randint(0, 2)], list)
self.assertIsInstance(res[2][random.randint(0, 6)], int)
self.assertEqual(len(res[0]), 8)
self.assertEqual(len(res[0][random.randint(0, 5)]), 9)
self.assertListEqual(res[2], solutions)
self.assertEqual(len(res[1]), 9)
class MatrixTests(unittest.TestCase):
def test_echelon_function_simple(self):
A = [[2, 1, 1],
[1, 2, 1],
[1, 1, 2]]
b = [1, 1, 1]
Asol = [
[Fraction(1, 1), Fraction(1,2), Fraction(1,2)],
[Fraction(0, 1), Fraction(1, 1), Fraction(1,3)],
[Fraction(0, 1), Fraction(0,1), Fraction(1,1)]
]
bsol = [Fraction(1, 2), Fraction(1, 3), Fraction(1, 4)]
self.assertListEqual(Asol, echelon(A, [], b)[0])
self.assertListEqual(bsol, echelon(A, [], b)[2])
def test_echelon_function_with_sample_problem_matrix(self):
A =[[1, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1, 0, 1, 1],
[0, 1, 1, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 1],
[0, 1, 1, 0, 0, 0, 1, 0, 1],
[2, 0, 1, 0, 0, 0, 0, 1, 0],
[0, 1, 0, 0, 1, 1, 0, 1, 0]]
b = [17, 26, 16, 18, 20, 19, 20, 18]
x = ["D","F","E","C","H","A","J","G","B"]
Asol = [
[Fraction(1, 1), Fraction(0, 1), Fraction(1, 2), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(1, 2), Fraction(0, 1)],
[Fraction(0, 1), Fraction(1, 1), Fraction(1, 1), Fraction(1, 1), Fraction(0, 1), Fraction(1, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1)],
[Fraction(0, 1), Fraction(0, 1), Fraction(1, 1), Fraction(1, 1), Fraction(-1, 1), Fraction(0, 1), Fraction(0, 1), Fraction(-1, 1), Fraction(0, 1)],
[Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(1, 1), Fraction(1, 1), Fraction(1, 1), Fraction(0, 1), Fraction(0, 1), Fraction(1, 1)],
[Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(1, 1), Fraction(0, 1), Fraction(1, 2), Fraction(1, 2), Fraction(0, 1)],
[Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(1, 1), Fraction(0, 1), Fraction(2, 1), Fraction(-3, 1)],
[Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(1, 1), Fraction(-1, 1), Fraction(4, 1)],
[Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(0, 1)]]
bsol = [Fraction(10, 1), Fraction(16, 1), Fraction(-2, 1), Fraction(20, 1), Fraction(9, 1),
Fraction(0, 1), Fraction(28, 1), Fraction(0, 1)]
res = echelon(A, x, b)
self.assertListEqual(res[0], Asol)
self.assertListEqual(res[2], bsol)