class Matrix:
    def __init__(self, m):
        self.n = len(m)
        for l in m:
            if self.n != len(l):
                print("La matrice n'est pas carrée")
                raise Exception
        self.m = m

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        return self.m[i]

    def swap(self, i, j):
        tmp = self.m[i-1]
        self.m[i-1] = self.m[j-1]
        self.m[j-1] = tmp

    def dilat(self, i, k):
        self.m[i-1] = list([k*e for e in self.m[i-1]])

    def add(self, i, j, k):
        for c in range(self.n):
            self.m[i-1][c] = self.m[i - 1][c] + k*self.m[j - 1][c]

    def __repr__(self):
        return self.pp()

    def pp(self):
        left = self.n*[0]
        right = self.n*[0]
        for i in range(self.n):
            for j in range(self.n):
                a, b = self.m[i][j].size()
                left[j] = max(left[j], a)
                right[j] = max(right[j], b)

        s = []
        for i in range(self.n):
            s.append(self.n * [""])

        for i in range(self.n):
            for j in range(self.n):
                s[i][j] = self.m[i][j].pp(left[j], right[j])

        s[0].insert(0, "/")
        s[0].append("\\")
        for i in range(1, self.n-1):
            s[i].insert(0, "|")
            s[i].append("|")
        s[self.n - 1].insert(0, "\\")
        s[self.n - 1].append("/")

        output = "\n".join(["  ".join(l) for l in s])

        return output


class Identity(Matrix):
    def __init__(self, n):
        m = []
        for i in range(n):
            m.append(n * [Q(0, 1)])
        for i in range(n):
            m[i][i] = Q(1, 1)
        super(Identity, self).__init__(m)


class Q:
    def __init__(self, p, q):
        self.p = p
        self.q = q

    def __rmul__(self, other):
        return self * other

    def __mul__(self, other):
        if isinstance(other, int):
            return self * Q(other, 1)
        if isinstance(other, Q):
            return Q(self.p*other.p, self.q*other.q).simplify()

    def __radd__(self, other):
        return self + other

    def __add__(self, other):
        if isinstance(other, int):
            return self.__add__(Q(other, 1))
        if isinstance(other, Q):
            return Q(self.p*other.q+self.q*other.p, self.q*other.q).simplify()

    def __eq__(self, other):
        if isinstance(other, int):
            return self.__eq__(Q(other, 1))
        if isinstance(other, Q):
            self.simplify()
            other.simplify()
            return other.p == self.p and other.q == self.q

    def __repr__(self):
        if self.q == 1:
            return "%d" % self.p
        else:
            return "%d/%d" % (self.p, self.q)

    def __neg__(self):
        return Q(-self.p, self.q)

    def pp(self, l, r):
        p = str(self.p)
        q = str(self.q)
        if self.q == 1:
            return (l - len(p))*" " + "%d" % self.p + (r+1)*" "
        else:
            return (l - len(p))*" " + "%d/%d" % (self.p, self.q) + (r - len(q))*" "

    def size(self):
        p = str(self.p)
        q = str(self.q)
        if self.q == 1:
            return len(p), 0
        return len(p), len(q)

    def inv(self):
        return Q(self.q, self.p)

    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a % b)

    def simplify(self):
        if self.q < 0:
            self.q = -self.q
            self.p = -self.p
        if self.p == 0:
            self.q = 1
        else:
            d = self.gcd(self.p, self.q)
            self.p = int(self.p / d)
            self.q = int(self.q / d)
        return self


def gauss(matrix):
    p = 1
    x = matrix
    n = len(x)
    y = Identity(n)
    print(x)
    print(y)
    while p <= n:
        rank = p
        while rank <= n:
            if x.m[rank-1][p-1] != 0:
                break
            rank += 1
        if rank == n+1:
            print("La matrice n'est pas inversible")
            exit(1)
        if rank != p:
            x.swap(rank, p)
            y.swap(rank, p)
            print("\nL_{%d} <-> L_{%d}" % (p, rank))
            print(x)
            print(y)

        v = x[p-1][p-1]
        if v != 1:
            x.dilat(p, v.inv())
            y.dilat(p, v.inv())
            print("\nL_{%d} <- %s * L_{%d}" % (p, repr(v.inv()), p))
            print(x)
            print(y)
        for i in range(1, n+1):
            if i != p:
                v = x[i-1][p-1]
                if v != 0:
                    x.add(i, p, -v)
                    y.add(i, p, -v)
                    print("\nL_{%d} <- L_{%d} + %s * L_{%d}" % (i, i, repr(-v), p))
                    print(x)
                    print(y)
        p += 1
    return y


def main():
    test = [[1, 2, 3],
            [1, 2, 4],
            [0, 1, 2]]
    test = [[Q(e, 1) for e in l] for l in test]
    inverse = gauss(Matrix(test))
    print("\n\nInverse :")
    print(inverse)


if __name__ == '__main__':
    main()