Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Gauss & mod solution in Clear category for Hubspot Amulet by nickie
from itertools import product
# Extended GCD
def egcd(a, b):
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = b, a
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
return (old_r, t, s, old_s, old_t)
# Integer division remainder in the range (-mod/2, mod/2]
def fixmod(x, mod):
return -min((abs(m), -m) for m in [x % mod, x % mod - mod])[1]
# Gaussian elimination for solving a linear system of congruences
# Result contains pairs (x, dx): { x + k*dx | k in Z } are all solutions
def gauss(a, mod):
m, n = len(a), len(a[0])
for k in range(m):
i_min = min((abs(a[i][k]), i) for i in range(k, m))[1]
a[k], a[i_min] = a[i_min], a[k]
for i in range(k+1, m):
(_, t, s, _, _) = egcd(a[i][k], a[k][k])
for j in range(k, n):
a[i][j] = fixmod(a[i][j] * s + a[k][j] * t, mod)
for k in range(m-1, 0, -1):
for i in range(0, k):
(_, t, s, _, _) = egcd(a[i][k], a[k][k])
for j in range(0, n):
a[i][j] = fixmod(a[i][j] * s + a[k][j] * t, mod)
x = []
for k in range(m):
(g, _, f, r, _) = egcd(a[k][k], mod)
if a[k][n-1] % g == 0:
sol = r * a[k][n-1] // g
x.append((sol, abs(f)))
return x
# Solve using Gaussian eliminations and check all possible solutions in
# the range [0, 360) to find one that works
def checkio(matrix):
wanted = [0, 225, 315]
a = list(map(list, zip(*(matrix + [wanted]))))
s = gauss(a, 360)
def f(t):
return [fixmod(t[0] + k * t[1], 360) for k in range(360 // t[1])]
tm = list(zip(*matrix))
def check(x):
return [sum(a*b for (a, b) in zip(row, x)) % 360 for row in tm]
for x in product(*map(f, s)):
if check(x) == wanted:
return x
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
print(checkio([
[1, 2, 3],
[3, 1, 2],
[2, 3, 1]]))
print(checkio([
[1, 4, 2],
[2, 1, 2],
[2, 2, 1]]))
Jan. 15, 2014
