markov thing

blah.py

#!/usr/bin/env python
from __future__ import division

from itertools import compress, starmap
from operator import mul

M = [[0, 2, 1, 0, 0], [0, 0, 0, 3, 4], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]


class Fraction:

    @staticmethod
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    def __init__(self, numerator, denominator):
        g = Fraction.gcd(numerator, denominator)
        self._numerator = numerator // g
        self._denominator = denominator // g

    @property
    def numerator(a):
        return a._numerator

    @property
    def denominator(a):
        return a._denominator

    def __add__(a, b):
        """a + b"""
        return Fraction(a.numerator * b.denominator +
                        b.numerator * a.denominator,
                        a.denominator * b.denominator)
    __radd__ = __add__
    # def __radd__(a, b):
    #     if b == 0:
    #         return a
    #     else:
    #         return a.__add__(b)

    def _mul(a, b):
        """a * b"""
        return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
    __mul__ = __rmul__ = _mul





def convert_matrix(matrix):
    ret = []
    for i, row in enumerate(matrix):
        new_row = []
        row_sum = sum(row)

        if row_sum == 0:
            new_row = row
            new_row[i] = 1
        else:
            for p in row:
                if p == 0:
                    new_row.append(Fraction(0, 1))
                else:
                    new_row.append(Fraction(p, row_sum))
        ret.append(new_row)
    return ret


def prob_dist_vector(matrix, row=0, steps=10000):
    vector = matrix[row]
    for _ in range(steps):
        vector = [sum(starmap(mul, zip(vector, col))) for col in zip(*matrix)]
    return vector


def answer(m):
    terminal_states = [sum(r) == 0 for r in m]
    probability_matrix = convert_matrix(m)
    prob_vector = prob_dist_vector(probability_matrix)

    # fractionss = [fractions.Fraction(p).limit_denominator() for p in prob_vector
    # if not isinstance(p, fractions.Fraction)]

    nums = [x.numerator for x in prob_vector]
    denoms = [x.denominator for x in prob_vector]

    factors = [max(denoms) / x for x in denoms]

    numerators_times_factors = [a * b for a, b in zip(nums, factors)]
    ans = list(compress(numerators_times_factors, terminal_states)) + [max(denoms)]
    return list(map(int, ans))

print(answer(M))