Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import math
- def gcd(a,b):
- if a < 0: return -gcd(-a,b)
- if b < 0: return -gcd(a,-b)
- if a == 0: return b
- if b == 0: return a
- x = 1
- for i in range(1, min(a,b)+1):
- if a%i==0 and b%i==0:
- x = i
- return x
- assert gcd(0,8) == 8
- def factor(row):
- x = __builtins__.reduce(gcd, row, 0)
- if x == 0: return row
- return [item/x for item in row]
- def multiply(row, amt):
- return [x*amt for x in row]
- def add(row_a, row_b):
- return [a+b for a,b in zip(row_a, row_b)]
- def subtract(row_a, row_b):
- return add(row_a, multiply(row_b, -1))
- def reduce(a,b, column_idx):
- x = multiply(a, b[column_idx])
- y = multiply(b, a[column_idx])
- return subtract(x,y)
- def pad(s, size):
- while len(s) < size:
- s = " " + s
- return s
- def nice(data):
- row_widths = [max(len(str(row[idx])) for row in data) for idx in range(len(data[0]))]
- result = []
- for row in data:
- result.append(" ".join(pad(str(item), width) for item, width in zip(row, row_widths)))
- return "\n".join(result) + "\n"
- def switch(x,y):
- data[x], data[y] = data[y], data[x]
- def solve(data):
- print(nice(data))
- for x in range(len(data[0])-1):
- #find a row whose xth element is nonzero. The first x rows are excluded from this search since they've already been used.
- try:
- y = next(y for y, row in enumerate(data) if y >= x and row[x] != 0)
- except StopIteration:
- print("Couldn't find target row for reduction of column {}.".format(x+1))
- break
- #reduce every other row using the yth row.
- for i in range(len(data)):
- if i == y: continue
- data[i] = reduce(data[i], data[y], x)
- data[i] = factor(data[i])
- #move the yth row to the xth position.
- data[x], data[y] = data[y], data[x]
- print(nice(data))
- raw_data = """
- +GA = 1
- +GA -AB = 0
- +AB -BC -BD -BE = 0
- +BC -CD -CF = 0
- +BD +CD -DE -DF = 0
- +CF +DF +EF -FG = 0
- +FG -GA = 0
- """
- data = []
- for line in raw_data.strip().split("\n"):
- lhs, _, rhs = line.partition(" = ")
- d = {}
- for r in lhs.split():
- sign, a, b = r
- acc = 1 if sign == "+" else -1
- d[a] = d.get(a,0) + acc
- d[b] = d.get(b,0) - acc
- d["rhs"] = int(rhs)
- data.append(d)
- vars = sorted({x for d in data for x in d})
- assert vars[-1] == "rhs"
- rows = []
- for d in data:
- row = [d.get(k,0) for k in vars]
- rows.append(row)
- solve(rows)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement