Implements simplex method algorithm, pretty prints the table on every step

simplex.py

from fractions import Fraction

def is_straight(z):
	rows = len(z)
	for i in range(1, rows):
		if z[i][0] < 0:
			return False
	return True

def is_dual(z):
	cols = len(z[0])
	for i in range(1, cols):
		if z[0][i] < 0:
			return False
	return True

def simplex_iteration(z):
	if not is_straight(z):
		print "BAD TABLE"
		return False

	if is_dual(z):
		print "OPTIMAL"
		return True

	rows, cols = len(z), len(z[0])	
	candidates = [] # (s, r, zio/zis)
	minimal_fracture = None
	for i in range(1, cols):
		if z[0][i] < 0:
			for j in range(1, rows):
				if z[j][i] > 0:
					fracture = z[j][0]/z[j][i]
					candidates += [(i, j, fracture)]
					minimal_fracture = fracture if minimal_fracture is None or fracture < minimal_fracture else minimal_fracture

	if len(candidates) == 0:
		print "UNSAT"
		return False

	# select candidate with minimal zio/zis
	# if there are multiple, select with minimal s, then r
	s, r = None, None
	for i in range(0, len(candidates)):
		if candidates[i][2] != minimal_fracture:
			continue

		if s is None or candidates[i][0] < s:
			s, r, _ = candidates[i]
		if candidates[i][0] == s and candidates[i][1] < r:
			s, r, _ = candidates[i]


	new_z = []
	for i in range(0, rows):
		new_row = []
		for j in range(0, cols):
			# z[i][j] = z[i][j] - z[i][s] * z[r][j] / z[r][s]
			# z[r][j] = z[r][j] / z[r][s]
			if i == r:
				new_row += [z[i][j]/z[r][s]]
			else:
				new_row += [z[i][j] - z[i][s]*z[r][j]/z[r][s]]
		new_z += [new_row]
	return new_z

def pretty_print(fr, l):
	fr = str(fr)
	ln = len(fr)
	rest = l-ln
	rest_left = rest//2 + 1
	rest_right = rest-rest_left + 2
	return (' '*rest_right) + fr + (' '*rest_left) # swapped those for prettier look

def print_table(z):
	rows, cols = len(z), len(z[0])
	lens = []
	for j in range(0, cols):
		mxln = 0
		for i in range(0, rows):
			ln = len(str(z[i][j]))
			if mxln < ln:
				mxln = ln
		lens += [mxln]

	for i in range(0, rows):
		line = ""
		for j in range(0, cols):
			line += pretty_print(z[i][j], lens[j])
			if j == 0:
				line += "|"
		print line
		if i == 0:
			print "-" * len(line)
	print " "

def simplex(z):
	while True:
		print_table(z)
		ret = simplex_iteration(z)
		if ret == True or ret == False:
			break
		z = ret

def to_fractions(z):
	rows, cols = len(z), len(z[0])
	new_z = []
	for i in range(0, rows):
		new_row = []
		for j in range(0, cols):
			new_row += [Fraction(z[i][j])]
		new_z += [new_row]
	return new_z

"""
z = [
	[7, -1, -2, 0, 0],
	[1, 1, -1, 1, 0],
	[5, 2, 1, 0, 1]
]
"""
"""
z = [
	[7,0,0,8,-6,4],
	[1,1,0,2,-1,1],
	[2,0,1,-3,3,1]
]
"""
"""
z = [
	[1,0,0,1,0,-5],
	[2,1,0,-1,2,-4],
	[3,0,1,1,3,-6]
]
"""
z = [
	[-8,0,0,0,-1,-2],
	[3,1,0,0,2,1],
	[1,0,1,0,1,-1],
	[1,0,0,1,0,1],
]

z = to_fractions(z)
simplex(z)