Advertisement
Guest User

Untitled

a guest
Apr 25th, 2017
198
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.51 KB | None | 0 0
  1. import math
  2.  
  3. def gcd(a,b):
  4. if a < 0: return -gcd(-a,b)
  5. if b < 0: return -gcd(a,-b)
  6. if a == 0: return b
  7. if b == 0: return a
  8. x = 1
  9. for i in range(1, min(a,b)+1):
  10. if a%i==0 and b%i==0:
  11. x = i
  12. return x
  13.  
  14. assert gcd(0,8) == 8
  15.  
  16. def factor(row):
  17. x = __builtins__.reduce(gcd, row, 0)
  18. if x == 0: return row
  19. return [item/x for item in row]
  20.  
  21. def multiply(row, amt):
  22. return [x*amt for x in row]
  23.  
  24. def add(row_a, row_b):
  25. return [a+b for a,b in zip(row_a, row_b)]
  26.  
  27. def subtract(row_a, row_b):
  28. return add(row_a, multiply(row_b, -1))
  29.  
  30. def reduce(a,b, column_idx):
  31. x = multiply(a, b[column_idx])
  32. y = multiply(b, a[column_idx])
  33. return subtract(x,y)
  34.  
  35. def pad(s, size):
  36. while len(s) < size:
  37. s = " " + s
  38. return s
  39.  
  40. def nice(data):
  41. row_widths = [max(len(str(row[idx])) for row in data) for idx in range(len(data[0]))]
  42. result = []
  43. for row in data:
  44. result.append(" ".join(pad(str(item), width) for item, width in zip(row, row_widths)))
  45. return "\n".join(result) + "\n"
  46.  
  47. def switch(x,y):
  48. data[x], data[y] = data[y], data[x]
  49.  
  50.  
  51. def solve(data):
  52. print(nice(data))
  53. for x in range(len(data[0])-1):
  54. #find a row whose xth element is nonzero. The first x rows are excluded from this search since they've already been used.
  55. try:
  56. y = next(y for y, row in enumerate(data) if y >= x and row[x] != 0)
  57. except StopIteration:
  58. print("Couldn't find target row for reduction of column {}.".format(x+1))
  59. break
  60. #reduce every other row using the yth row.
  61. for i in range(len(data)):
  62. if i == y: continue
  63. data[i] = reduce(data[i], data[y], x)
  64. data[i] = factor(data[i])
  65. #move the yth row to the xth position.
  66. data[x], data[y] = data[y], data[x]
  67. print(nice(data))
  68.  
  69.  
  70. raw_data = """
  71. +GA = 1
  72. +GA -AB = 0
  73. +AB -BC -BD -BE = 0
  74. +BC -CD -CF = 0
  75. +BD +CD -DE -DF = 0
  76. +CF +DF +EF -FG = 0
  77. +FG -GA = 0
  78. """
  79. data = []
  80. for line in raw_data.strip().split("\n"):
  81. lhs, _, rhs = line.partition(" = ")
  82. d = {}
  83. for r in lhs.split():
  84. sign, a, b = r
  85. acc = 1 if sign == "+" else -1
  86. d[a] = d.get(a,0) + acc
  87. d[b] = d.get(b,0) - acc
  88. d["rhs"] = int(rhs)
  89. data.append(d)
  90.  
  91. vars = sorted({x for d in data for x in d})
  92. assert vars[-1] == "rhs"
  93. rows = []
  94. for d in data:
  95. row = [d.get(k,0) for k in vars]
  96. rows.append(row)
  97.  
  98. solve(rows)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement