readme

readme.md

Don't Solve it by Hand!

Yeah, I make them to solve my homework!

System of Linear Equations

How many paper will you use when solving this linear equations?

1 -2 2 -1
3 2 2 9
2 -3 -3 6

So, let's solve it with machine (with Gauss-Jordan elimination).

elimination.py

#coding: utf-8

'''Solving system of linear equations with Gauss-Jordan elimination'''

from frac import Frac


class Equation(list):
    def reduce_n(self, n):
        '''Reduce the nth element to 1'''
        r = self[n]
        for i in range(len(self)):
            self[i] /= r

    def __sub__(self, other):
        if isinstance(other, Equation):
            return Equation([a - b for a, b in zip(self, other)])
        else:
            raise NotImplemented

    def __mul__(self, other):
        if isinstance(other, Frac):
            return Equation([self[i] * other for i in range(len(self))])
        else:
            raise NotImplemented


class Equations(list):
    multi_answer_symbol = 'k'

    def __str__(self):
        rep = ''
        for i in range(len(self)):
            rep += ('%s\t' * len(self[i])) % tuple(self[i])
            rep.rstrip()
            rep += '\n'
        return rep.rstrip('\n')

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

    def append(self, other):
        if isinstance(other, Equation):
            if len(self) == 0:
                super(Equations, self).append(other)
            else:
                if len(other) == len(self[-1]):
                    super(Equations, self).append(other)
                else:
                    raise WrongEquationError
        else:
            raise NotSupportedError

    def validate(self, equation):
        '''Validate if the line is possible,
        @ret: 1 possible
              0 multi-answer
              -1 no answer'''
        for i in range(len(equation)-1):
            if not equation[i].is_zero():
                return 1
        if equation[-1].is_zero():
            return 0
        else:
            return -1

    def __solve(self):
        '''Solve the equations with G-J method'''
        for n in range(len(self)):
            # NOTICE FIXME
            # is possible that the MultiAnswersError had raised,
            # but the other line still not be solved?
            # maybe can debug it with printing the line number
            # when MultiAnswersError is raised
            #
            #
            # BUG CASE FIXME
            # 1.
            #
            # 1 -2 3 -1 2
            # -2 5 -1 2 4
            # -1 1 -2 1 8
            # which answer should be:
            # -21+k, -7, 3, k
            check = self.validate(self[n])
            if check == -1:
                raise NoAnswerError
            elif check == 0:
                raise MultiAnswersError
            
            try:
                self[n].reduce_n(n)
            except ZeroDivisionError:
                raise NoAnswerError

            for line in range(len(self)):
                if line != n:
                    self[line] -= self[n] * self[line][n]

        return [self[i][-1] for i in range(len(self))]

    def __multi_answer(self):
        '''Handle multi-answer answer'''
        for n in range(len(self)):
            if self.validate(self[n]) == 0:
                zline = n
                break
        ret = []
        for line in range(len(self)):
            if line != zline:
                solve = '%s' % self[line][-1]
                d = self[line][zline]
                if d.is_minus():
                    d *= -1
                    operator = '+'
                else:
                    operator = '-'
                solve += '%s%s%s' % (operator, d, self.multi_answer_symbol)
                ret.append(solve)
            else:
                ret.append(self.multi_answer_symbol)
        return ret

    @property
    def solve(self):
        try:
            return self.__solve()
        except MultiAnswersError:
            return self.__multi_answer()
        except NoAnswerError:
            return 'No answer.'


class WrongEquationError(Exception):
    pass


class NotSupportedError(Exception):
    pass


class NoAnswerError(Exception):
    pass


class MultiAnswersError(Exception):
    pass

frac.py

#coding: utf-8


class Frac(object):
    '''A fraction number'''
    def __init__(self, numerator, denominator):
        if denominator == 0:
            raise ZeroDivisionError
        self.numer = numerator
        self.denom = denominator
        self.reduction()

    def __str__(self):
        # TODO: display format
        self.reduction()
        if self.denom == 1 or self.numer == 0:
            return '%d' % self.numer
        else:
            #print '%f' % (float(self.numer) / float(self.denom))
            return '%d/%d' % (self.numer, self.denom)

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

    def gcd(self, a, b):
        while (a % b):
            tmp = b
            b = a % b
            a = tmp

        return b

    def lcm(self, a, b):
        return a * b / self.gcd(a, b)

    def is_zero(self):
        return self.numer == 0

    def is_minus(self):
        self.reduction()
        return self.numer < 0

    def reverse(self):
        return Frac(self.denom, self.numer)

    def reduction(self):
        if self.denom * self.numer < 0:
            self.denom = abs(self.denom)
            self.numer = -abs(self.numer)
        else:
            self.denom = abs(self.denom)
            self.numer = abs(self.numer)
        g = self.gcd(abs(self.numer), abs(self.denom))
        self.numer /= g
        self.denom /= g

    def denomination(self, other):
        if isinstance(other, Frac):
            l = self.lcm(self.denom, other.denom)
            self.numer *= l / self.denom
            self.denom = l
            other.numer *= l / other.denom
            other.denom = l
        else:
            raise NotImplemented

    def __add__(self, other):
        if isinstance(other, Frac):
            self.denomination(other)
            return Frac(self.numer + other.numer, self.denom)
        if isinstance(other, int):
            return self.denomination(self.numer + other * self.denom, self.denom)
        else:
            raise NotImplemented

    def __sub__(self, other):
        if isinstance(other, Frac):
            self.denomination(other)
            return Frac(self.numer - other.numer, self.denom)
        if isinstance(other, Int):
            return Frac(self.numer - other * self.denom, self.denom)
        else:
            raise NotImplemented

    def __mul__(self, other):
        if isinstance(other, Frac):
            return Frac(self.numer * other.numer, self.denom * other.denom)
        if isinstance(other, int):
            return Frac(self.numer * other, self.denom)
        else:
            raise NotImplemented

    def __div__(self, other):
        if isinstance(other, Frac):
            if other.is_zero():
                raise ZeroDivisionError
            else:
                return Frac(self.numer * other.denom, self.denom * other.numer)
        if isinstance(other, int):
            if other == 0:
                raise ZeroDivisionError
            else:
                return self.__div__(Frac(other))
        else:
            raise NotImplemented


def frac_factory(raw_num):
    '''Return a frac base on the input'''
    if not isinstance(raw_num, str):
        raw_num = str(raw_num)

    #: is a fraction
    if raw_num.find('/') != -1:
        numer, denom = raw_num.split('/')
        # TODO
        # numer and denom from the input are supposed as int instead of float
        # maybe using int casting's ValueError can improve it
        return Frac(int(numer), int(denom))
    #: is a float
    if raw_num.find('.') != -1:
        # TODO
        # use mathematic method to calculate the len of the b part
        # rather than len()
        a, b = raw_num.split('.')
        denom = 10 ** len(b)
        numer = float(raw_num)
        numer *= denom
        return Frac(numer, denom)
    #: suppose it's an int
    else:
        return Frac(int(raw_num), 1)

main.py

#coding: utf-8

# TODO FEATURES
# Yeah, needs some cool cli options, such as:
# 
#   - read from file
#   - write to file
#   - display format
#   - ...
#

from processing import process


def _read():
    lines = []
    while 1:
        try:
            lines.append(raw_input())
        except EOFError:
            break
    return lines


def _main():
    #print process(_read()).solve
    ret = process(_read())
    print ret.solve


if __name__ == '__main__':
    _main()

processing.py

#coding: utf-8

from frac import frac_factory
from elimination import Equation, Equations


def read(fn):
    f = file(fn, 'r')
    ret = f.readlines()
    f.close()
    return ret


def write(content, dest):
    f = file(dest, 'w')
    f.write(content)
    f.close()
    return


def process(lines):
    '''Read the linear equations system from input and return a Equations system'''
    system = Equations()
    for line in lines:
        equation = Equation([frac_factory(i) for i in line.split()])
        system.append(equation)
    return system