Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Gaussian elimination solution in Uncategorized category for Hubspot Amulet by htamas
from fractions import Fraction
def egcd(a, b): # extended gcd
if b:
g, u, v = egcd(b, a % b)
return g, v, u - v * (a//b)
else:
return abs(a), (a>0)-(a<0), 0
def div(a, b): # division over an extension of the Z/360Z ring
g, u, v = egcd(b, 360)
if v * a % g == 0:
return u * a / g
else:
raise Exception("No solution.")
def checkio(matrix):
# find a vector v such that v * matrix = [0, 225, 315] over the Z/360Z ring
# transpose matrix and add the constant column
matrix.extend([[0, 225, 315]])
M = [[Fraction(matrix[i][j]) for i in range(4)] for j in range(3)]
# perform Gaussian elimination
for i in range(3):
for j in range(i, 3):
if M[j][i] != 0:
M[i], M[j] = M[j], M[i]
break
else:
raise Exception("No solution.")
M[i] = [div(M[i][k], M[i][i]) for k in range(4)]
for j in range(3):
if j != i:
M[j] = [M[j][k] - M[j][i] * M[i][k] for k in range(4)]
# extract the result
v = [t[3] for t in M]
if not all(t.denominator == 1 for t in v):
raise Exception("No solution.")
return [(int(t + 180) % 360) - 180 for t in v]
Dec. 16, 2013
Comments:
