MDP Planning using Howard's Policy Iteration and as a Linear Program

MDP_planner.py

"""
    File:               planner.py
    Author:             Dhruv Ilesh Shah. CS 747, Autumn 2018.
                        Indian Institute of Technology, Bombay.
    Date created:       8/30/2018
    Date last modified: 9/07/2018
    Python Version:     2.7.12

This file contains two ways of solving an MDP planning problem: (i) using Howard's PI (Howard, 1960)
or (ii) by posing it as a linear program. The PuLP package has been used to solve the linear system
(download link: https://pythonhosted.org/PuLP/)
The format of an input MDP is attached as a second file titled test.txt, with solution in test_sol.txt

"""

from pulp import *
import numpy as np
import time
import matplotlib.pyplot as plt
import sys


class MDP:

    """MDP model
    
    Attributes:
        actions (int): Number of actions
        gamma (float): Discount factor
        horizon (string): Type (episodic/continuing)
        R (numpy 3D): Reward matrix
        states (int): Number of states
        T (numpy 3D): Transition matrix
    """

    def __init__(self, states, actions, T, R, gamma, horizon="episodic"):
        """Complete constructor
        
        Args:
            states (int): Number of states
            actions (int): Number of actions
            T (numpy 3D): Transition matrix
            R (numpy 3D): Reward matrix
            gamma (float): Discount factor
            horizon (string): Type (episodic/continuing)
        """
        self.states = states
        self.actions = actions
        self.T = T
        self.R = R
        self.gamma = gamma
        self.horizon = horizon


def print_result(V, pi):
    """Print value function and corresponding policy
    
    Args:
        V (numpy 1D): value function
        pi (numpy 1D): policy
    """
    for s in range(len(pi)):
        print("%s\t%d" % ("{0:4.8f}".format(V[s]), pi[s]))
    print "\n"


def vis_result(V, pi, ph=0.4):
    """Plot value function and policy
    
    Args:
        V (numpy 1D): value function
        pi (numpy 1D): policy
        ph (float, optional): P(success) for Gambler's problem
    """
    f, axarr = plt.subplots(2, sharex=True, figsize=(12, 12))
    f.suptitle('$p_h = %s$' % ("{0:0.1f}".format(ph)))
    axarr[0].plot(V[0:len(V)-1])
    axarr[1].plot(pi[1:len(V)-1])
    plt.show()

def optimal_policy(model, V_opt):
    """Identify optimal policy for a given value function
    
    Args:
        model (MDP): MDP model
        V_opt (numpy 1D): value function
    
    Returns:
        pi_opt (numpy 1D): optimal policy
    """
    pi_opt = np.ones(model.states, dtype=int)
    for s in range(model.states):
        # Evaluating optimal policy as argmax of Q(s, a)
        Q_sa = [np.sum([model.T[s, a, sp] *
                        (model.R[s, a, sp] + (model.gamma*V_opt[sp])) for sp in range(model.states)]) for a in range(model.actions)]

        pi_opt[s] = 1
        for a in range(model.actions):
            if model.T[s, a, s] == 1:
                continue                                # Looping action; not a valid policy
            if (Q_sa[a] - Q_sa[pi_opt[s]]) > 1e-6:
                pi_opt[s] = a

    return pi_opt


def process_file(filename):
    """Process file to generate MDP model
    
    Args:
        filename (string): Location of description file
    
    Returns:
        MDP: MDP model
    """
    f = open(filename, 'rt')
    states = int(f.readline().split('\n')[0])
    actions = int(f.readline().split('\n')[0])
    T = np.zeros([states, actions, states], dtype=float)
    R = np.zeros([states, actions, states], dtype=float)
    for s in range(states):
        for a in range(actions):
            R_sa = f.readline().split('\t')[:states]
            for sp in range(states):
                R[s, a, sp] = float(R_sa[sp])
    for s in range(states):
        for a in range(actions):
            T_sa = f.readline().split('\t')[:states]
            for sp in range(states):
                T[s, a, sp] = float(T_sa[sp])
    gamma = float(f.readline().split('\n')[0])
    horizon = f.readline().split('\n')[0]

    return MDP(states, actions, T, R, gamma, horizon)


def identifyTerminal(model):
    """Identify terminal states of an MDP
    
    Args:
        model (MDP): MDP model
    
    Returns:
        term (list): list of terminal states
    """
    term = np.array([], dtype=int)
    for s in range(model.states):
        if np.array_equal(model.T[s, :, s], np.ones(model.actions)):
            term = np.append(term, [s])
    return term


def LP_solve(model):
    """Linear Programming solver for MDP planning
    
    Args:
        model (MDP): MDP model
    
    Returns:
        V_opt, pi_opt (numpy 1D): Optimal value function and corresponding policy
    """
    prob = LpProblem("MDP Planning", LpMinimize)    # Creating the LP problem
    Vs = np.arange(model.states)
    Vs_term = np.array([], dtype=int)
    if model.horizon == "episodic":
        Vs_term = identifyTerminal(model)
    Vs_vars = LpVariable.dicts("Vs", Vs)            # State space for LP
    # Defining the optimization problem
    prob += lpSum([Vs_vars[i] for i in Vs]), "Sum of V(s) over states"
    for s in Vs:
        for a in range(model.actions):
            prob += Vs_vars[s] - lpSum([model.T[s, a, sp] *
                                        (model.R[s, a, sp] + (model.gamma*Vs_vars[sp])) for sp in Vs]) >= 0, "%s: [%i, %i]" % ("Constraint on [s, a] pair", s, a)
    for s in Vs_term:
        prob += Vs_vars[s] == 0, "Terminal state %s" % (s)

    # prob.writeLP("MDP_solution.lp")
    prob.solve()

    if (prob.status != 1):
        print("Optimal Solution DNE")
        return

    V_opt = np.zeros(model.states)
    if model.horizon == "episodic":
        for i in range(len(Vs)):
            s = Vs[i]
            v = prob.variables()[i]
            V_opt[int(v.name.split('_')[1])] = v.varValue
    else:
        V_opt = np.array([prob.variables()[i].varValue for i in Vs])

    pi_opt = optimal_policy(model, V_opt)
    for s in Vs_term:
        pi_opt[s] = 0
    return V_opt, pi_opt


def HPI_solve(model):
    """Howard's Policy Iteration solver for MDP planning [Howard 1960]
    
    Args:
        model (MDP): MDP model
    
    Returns:
        V_opt, pi_opt (numpy 1D): Optimal value function and corresponding policy
    """
    pi_prev = np.ones(
        model.states)                                     # Choosing an arbitrary policy
    pi_curr = np.random.randint(model.actions, size=model.states)
    V_curr = np.zeros([model.states, model.actions])
    Vs_term = np.array([], dtype=int)
    it = 0; max_iter = 50
    while (not np.array_equal(pi_curr, pi_prev)) and (it < max_iter):
        # Computing the value function for policy pi_curr
        # Note that a simpler method would be to formulate Ax=b and x=inv(A)*b, but PuLP has been used
        # since it is stable and the formulation is symbolic & legible.

        it += 1
        pi_prev = np.copy(pi_curr)
        V_curr = np.zeros([model.states])
        prob = LpProblem("Computing V^pi_curr", LpMinimize)
        Vs_all = np.arange(model.states)
        Vs = np.copy(Vs_all)
        if model.horizon == "episodic":
            Vs_term = identifyTerminal(model)
        Vs_vars = LpVariable.dicts("Vs", Vs)
        prob += 1, "Constant objective"
        for s in Vs:
            a = pi_curr[s]
            prob += Vs_vars[s] - lpSum([model.T[s, a, sp] *
                                        (model.R[s, a, sp] + (model.gamma*Vs_vars[sp])) for sp in Vs]) == 0, "%s: [%i, %i]" % ("Constraint on [s, a] pair", s, a)
        for s in Vs_term:
            prob += Vs_vars[s] == 0, "Terminal state constraint %i" % (s)

        # prob.writeLP("HPI_Vpi_solution.lp")
        prob.solve()
        if (prob.status != 1):
            print("Solution DNE")
            return
        # Value function for pi_curr
        V_curr = np.zeros(model.states)
        for i in range(len(Vs)):
            s = Vs[i]
            v = prob.variables()[i]
            V_curr[int(v.name.split('_')[1])] = v.varValue

        pi_curr = optimal_policy(model, V_curr)

    return np.squeeze(V_curr), pi_curr


def VI_solve(model, epsilon=0.00001):
    """Value Iteration solver for MDP Planning 
    
    Args:
        model (MDP): MDP model
        epsilon (float, optional): convergence tolerance for updates
    
    Returns:
        V_opt, pi_opt (numpy 1D): Optimal value function and corresponding policy
    """
    Vs = np.zeros(model.states)
    while True:
        Vs_curr = np.copy(Vs)
        delta = 0
        for s in range(model.states):
            Q_sa = [np.sum([model.T[s, a, sp] * (model.R[s, a, sp] + (model.gamma*Vs_curr[sp]))
                            for sp in range(model.states)]) for a in range(model.actions)]
            Vs[s] = np.max(Q_sa)
            delta = max(delta, abs(Vs[s] - Vs_curr[s]))
        if delta < epsilon:
            break
    V_opt = np.copy(Vs)
    pi_opt = optimal_policy(model, V_opt)
    return V_opt, pi_opt


if __name__ == '__main__':

    model_descriptor = sys.argv[2]
    V_opt = []; pi_opt = [];
    if sys.argv[1] == "hpi":
        V_opt, pi_opt = HPI_solve(process_file(model_descriptor))    
        print_result(V_opt, pi_opt)
    elif sys.argv[1] == "lp":
        V_opt, pi_opt = LP_solve(process_file(model_descriptor))
        print_result(V_opt, pi_opt)

test.txt

10
5
0.6165282431445691      	0.7205669043681562      	0.2952576135177756      	-0.44653851855435445      	-0.8006047142326982      	-0.13944537606502827      	0.8419852907548973      	0.7067508409918879      	-0.752602024172458      	-0.14159725869459638      	
-0.24605360948188548      	-0.2779123786717379      	0.9253853106046406      	0.1420253725655638      	0.7117251092447963      	-0.5651463615017966      	-0.4198545071232971      	-0.19385451002986565      	-0.01094542536871601      	-0.7694625675794262      	
0.7524532196920719      	-0.24616695414394196      	-0.8009107211433224      	0.36901024480670275      	-0.9172995630769736      	0.6877433136674178      	0.6746207599559695      	-0.9897433820229253      	0.48179170749536326      	0.32291134645811104      	
-0.5173377275437259      	-0.5516743200728662      	0.03924094202771222      	-0.9498912574935936      	-0.16666111726050659      	-0.09005601010502784      	-0.778673014361843      	-0.3668010890015827      	-0.10280774859498032      	-0.8427884473476495      	
0.8202587240274344      	-0.04890193848512836      	-0.9994910213156807      	0.3916438438267742      	-0.32476763819909027      	-0.3628468522279753      	-0.27286784237690087      	0.5247237056434022      	-0.25574127189662366      	0.2857696739580946      	
0.2189106460491419      	-0.46135035420817494      	0.7308858361706421      	0.1311823317700176      	0.30487028828646734      	0.02462768528580317      	0.9820695614772892      	0.6968921933857122      	0.5242284887789035      	-0.8357293069053451      	
-0.21734335205955158      	0.8372827243090082      	0.1152643406745637      	0.4207881741718622      	0.16635014019582828      	0.9467396039897675      	0.22865054519730021      	0.37455112194451523      	-0.03649543145966794      	0.05853246402083068      	
0.044114433581651236      	-0.018991556112037955      	0.26012453169914407      	0.4574712294658987      	-0.5285634713426024      	0.14128753010309603      	-0.17578849112108985      	-0.3808489534614876      	0.7827267292686635      	-0.5390042258419561      	
-0.3035187396675394      	0.6902983177201316      	-0.5868004343073894      	-0.30233072109893744      	0.04642424261508138      	-0.6800258885688626      	-0.8327546316896071      	-0.3527316759928667      	-0.04469535797952706      	0.2771826320970272      	
0.14103709863283576      	0.2637638120608221      	-0.7445519788193011      	-0.9872715892933783      	-0.30613002589442795      	0.7525360833577743      	-0.3526919698291786      	0.8137089647625528      	0.4627530698914135      	0.428779834502812      	
0.2968246634215741      	-0.0026794765839384116      	-0.22280797505248073      	0.7770184225184857      	-0.15553950813760276      	0.8291207728004868      	0.8632795041009258      	0.5955231563572128      	0.7334502640745268      	-0.5952156796880217      	
-0.2936725131780191      	0.7303904515686033      	-0.4166930381208147      	0.0197972824082282      	-0.5632006202316431      	-0.3721193312971294      	-0.36971636438632016      	-0.1833161297193031      	-0.16757549175875597      	-0.8500007586773513      	
0.8074692280221403      	0.8585872407834936      	-0.5222860334979529      	-0.12385456188526445      	0.45883305269652364      	-0.966081198152227      	0.24333336690090346      	-0.9848152415470313      	-0.7332799032109194      	0.05249329834841876      	
-0.294756627763618      	0.15982456519570487      	-0.6400797631237243      	0.2548547113646926      	0.9601897498918301      	-0.4434034998559415      	-0.023451504080478802      	0.049969409885559424      	-0.23665157170383444      	0.32869587827215874      	
-0.9792156997823553      	-0.780765132597788      	-0.03816528859998658      	0.6698927946519981      	0.9159288561057326      	-0.18737064481554233      	0.7658248101917182      	-0.010352417481604537      	-0.48887810177909463      	0.38011611405119794      	
0.41192651433077465      	-0.04378162221933546      	-0.47623452175900405      	-0.041373905040876346      	-0.03294563479928225      	0.3528321969087882      	0.8439311804797327      	0.45372438755688904      	-0.4660373151699493      	-0.41310240691068745      	
0.09272946888282085      	0.7699222262251644      	-0.96293018167284      	-0.9723850158369043      	0.15563837169550165      	-0.41781412263942386      	0.5650693072615482      	0.003975582329665217      	0.9124621718014301      	0.7437718854901847      	
0.3527586287929356      	-0.6262884074049917      	0.12201570341803691      	-0.5283953273808528      	-0.9205250519991046      	0.37510154255640926      	-0.40458365103599814      	-0.42039285922971237      	0.34034597922412213      	-0.8167321206829541      	
0.7852989677380515      	-0.18358739190111373      	-0.7545043115450147      	0.6494656034147355      	-0.41518897853703374      	-0.11950278855943863      	-0.5487721717075584      	-0.13521210477711088      	-0.07081545274037593      	-0.04585643172345244      	
0.6678760400680079      	-0.5240281538281719      	-0.19320176220171748      	-0.5818177498408545      	-0.590378318530399      	0.48820673781502544      	-0.3928928286740947      	0.9545882629953943      	-0.8517602703645424      	-0.3575400141355283      	
0.23415026368522818      	-0.5565968599672366      	0.6139224386024014      	-0.8550958302945817      	-0.3428811870167776      	0.4120188760278696      	0.8294844391235172      	0.24884145392712798      	0.7978470253924725      	0.3114756633500253      	
-0.13440176804293413      	0.5572046127007346      	-0.1157866124771747      	0.06306951289544016      	-0.4709734122572544      	0.24182341095765758      	-0.12877487509250796      	-0.953753455424764      	0.7532521809164525      	-0.13424719300316257      	
-0.44125399748722516      	-0.9683606573972443      	-0.5891432652569968      	-0.253780010776149      	-0.8263189551230377      	-0.8656941296836647      	0.60023493658494      	-0.36836168455614304      	0.8928726357388403      	-0.016196151734471975      	
-0.2083384783993003      	-0.9531376654326691      	0.020498925553892988      	-0.7580194284153499      	0.7674295163308935      	-0.6449469019792777      	0.5072334636147338      	-0.009313299554642995      	0.4580955704506029      	0.6638064080737969      	
-0.1225720318874306      	0.2932835958458482      	-0.3234232462701352      	0.8004408220169392      	0.5987723003762067      	0.11678948933948052      	0.6096847908817431      	-0.3738469442116372      	0.21963534180190036      	0.6019168576609324      	
0.7349774308933235      	-0.3579220908463927      	0.7153991451110877      	-0.5482535759937261      	-0.4203352098313755      	-0.22244307995529278      	-0.08751687676176712      	-0.07402420639249607      	-0.9935744494924108      	-0.148580361913484      	
-0.4285981345267196      	0.7772345522449338      	-0.9796615307246204      	-0.42477668622374276      	0.02547888491042638      	0.8266340297026262      	0.06581200626672912      	0.0017529168766035053      	-0.855889717563858      	-0.47889154406459844      	
0.7020111456090488      	0.3878357583164067      	0.5565088816721986      	0.4079914725275706      	0.19929087388347377      	0.1465747815855296      	-0.6571682893970343      	-0.6096760573256113      	0.387717927733761      	0.8748652690678955      	
-0.47347322248860557      	0.8502814850107456      	0.5276663532705423      	-0.21188398761880745      	0.23498816749854168      	0.9260232369739629      	-0.9099618031531296      	-0.602478490388324      	-0.1257844763329412      	0.8372288315893059      	
-0.4386203002843032      	-0.7661847008403146      	0.48334252374205056      	-0.6065238989965747      	-0.2719304818866384      	-0.7576946113187026      	-0.438362520378484      	0.3561899940508775      	-0.9486048553611617      	0.30617439626005005      	
-0.5869480570535963      	-0.3894868906721831      	-0.713738032063844      	-0.476996015815379      	0.3507456098763697      	0.4806621548086525      	-0.8788139304098141      	-0.22762456020939004      	0.2168134697848474      	-0.22623740321671226      	
0.5224209720640369      	0.31573044914929116      	-0.9962586353888265      	-0.3162876001098771      	0.5753000341609373      	0.13100622923844862      	0.6314869195211026      	-0.978415153635624      	0.8101081215251729      	0.9276268739789146      	
0.24135546551415965      	0.7052676068114274      	-0.5650498396514643      	-0.45937338372485725      	0.48713602596285477      	-0.2808601450947299      	0.9888060456058616      	0.5922621743449368      	0.17841569814768166      	-0.04198734582039587      	
0.8021106058280978      	0.21878632101876172      	0.2104745574757232      	-0.6610538028195589      	-0.30740978041409406      	-0.9680124141188451      	-0.48663101674591447      	-0.9202684337037597      	0.9140305018040675      	0.547587341117395      	
0.3420649587210609      	0.8166447937810211      	0.9622205755231414      	0.9174401244146113      	-0.6685573074862865      	-0.3452828327354742      	0.6621379927444977      	0.37346394634212143      	0.8178158986735067      	-0.6832131884361006      	
0.3934325453409868      	-0.4037755463837587      	-0.0911348051901053      	0.328933817005594      	-0.18728560480889933      	0.8475604293471357      	0.5145639748387381      	0.006205784750928922      	0.45269404884391506      	0.24482280808059853      	
0.6716278655967127      	-0.9175265938896005      	0.9505070808823362      	-0.48832515587718084      	-0.5927306956597669      	0.4346498466218305      	0.1376546815524271      	-0.47765364665228294      	0.7572411178051353      	-0.7511822164068633      	
-0.2676709042137335      	-0.3112644577803405      	-0.40454313384853613      	-0.057822202357088015      	0.27291937226314533      	-0.2544182932259562      	-0.4061772679492299      	-0.0975879632548573      	0.91054058240657      	0.1786468515748474      	
0.9800502508577418      	-0.9170859514139773      	-0.6645946757868046      	0.5603508744173891      	-0.6974063208496135      	0.6711684157496141      	-0.15900718983181306      	-0.14118865820479343      	-0.44401517338584084      	0.6250997386277832      	
0.5000782044541732      	0.13355108277470218      	-0.17623065167228558      	0.558369073866327      	0.02532399918699002      	0.21304928740307583      	-0.4094986180304738      	0.1686180267181332      	0.7538900573122647      	0.3280077492394964      	
0.8675277181050063      	-0.5865615177577519      	0.002025018839606485      	-0.6379898861495132      	0.9489927200093966      	0.8013221558111947      	0.22301509808541664      	0.28558501243320134      	-0.33128024506361253      	0.01463751591156437      	
0.3436505379787911      	0.8537446107961542      	-0.3642704146802769      	0.28557038183521644      	-0.7413221755694273      	0.09133434151315178      	0.18564278287497382      	-0.23121165833391388      	0.9152670093926618      	0.36802057202465677      	
-0.19775289718498557      	0.9180703402649188      	-0.5391899499559785      	0.07513377137390975      	0.14503877928908282      	0.38337125391003357      	0.6636148368584704      	-0.8192751351339749      	-0.06668416818831968      	0.5483827858813959      	
-0.0206751746268643      	0.2063814087203648      	0.9368893468461736      	0.6924858950277233      	0.7177440234732322      	-0.40652707735857807      	0.4046890121067015      	0.2564039378833529      	0.21269545182775706      	-0.28029486645778756      	
-0.12501227845287022      	-0.23419327143163393      	0.6430888764231504      	0.9791408171794189      	-0.2805394003624786      	0.4708438202464853      	0.48891757338543473      	-0.6445440242808578      	-0.8027828069090117      	0.009205807614633521      	
-0.3666965837728817      	0.7319609006426793      	-0.699218729151784      	-0.3220071403099243      	0.20688495252443873      	-0.10617667672360387      	-0.8213506687066205      	0.7840693960970435      	-0.5230777486296347      	0.20038676902127106      	
-0.8227995810345654      	0.8545750473821638      	0.4843390899544149      	0.11002148069546558      	-0.2059665041005614      	0.287953799647068      	0.9363393787387457      	0.06042775020323932      	-0.6607879940927717      	0.052243266268017896      	
-0.4181621840785419      	0.6039786659016939      	-0.19647881659956035      	0.24349885455787867      	-0.30504692128524336      	0.7294414830318141      	-0.9682612853754704      	0.18611863841709897      	-0.5000610106596735      	-0.31366365792577455      	
-0.5257854255532295      	-0.04383738509160828      	0.8223856470251703      	-0.5258594656931577      	-0.5880947280775148      	-0.2506618414584103      	-0.6971574724335954      	-0.318122687411718      	-0.17295288245372054      	0.15825301355951482      	
0.24321457431274918      	-0.34534479294075093      	0.5605681765888524      	-0.40484503504475344      	0.22729565884224145      	-0.6046481582475307      	-0.444534751946549      	-0.06865662170871478      	0.9611236104062344      	-0.4820927317204575      	
0.10721649484536082      	0.14432989690721648      	0.01443298969072165      	0.004123711340206186      	0.12989690721649486      	0.10103092783505155      	0.020618556701030927      	0.12164948453608247      	0.15463917525773196      	0.2020618556701031      	
0.0989345509893455      	0.060882800608828      	0.1050228310502283      	0.0898021308980213      	0.0821917808219178      	0.1461187214611872      	0.1126331811263318      	0.1385083713850837      	0.0441400304414003      	0.121765601217656      	
0.0800711743772242      	0.026690391459074734      	0.15658362989323843      	0.16370106761565836      	0.10142348754448399      	0.03914590747330961      	0.033807829181494664      	0.16370106761565836      	0.1583629893238434      	0.07651245551601424      	
0.07360861759425494      	0.14542190305206462      	0.16696588868940754      	0.09156193895870736      	0.1561938958707361      	0.02872531418312388      	0.05206463195691203      	0.07719928186714542      	0.11490125673249552      	0.0933572710951526      	
0.10090361445783133      	0.13855421686746988      	0.09789156626506024      	0.10993975903614457      	0.13253012048192772      	0.14006024096385541      	0.012048192771084338      	0.07379518072289157      	0.11596385542168675      	0.0783132530120482      	
0.047377326565143825      	0.14720812182741116      	0.04568527918781726      	0.1065989847715736      	0.16412859560067683      	0.1319796954314721      	0.16751269035532995      	0.03553299492385787      	0.0829103214890017      	0.07106598984771574      	
0.09284332688588008      	0.11605415860735009      	0.06769825918762089      	0.12572533849129594      	0.0      	0.18568665377176016      	0.172147001934236      	0.1470019342359768      	0.05415860735009671      	0.03868471953578337      	
0.09671179883945841      	0.0735009671179884      	0.05415860735009671      	0.05029013539651837      	0.0      	0.12379110251450677      	0.09477756286266925      	0.18181818181818182      	0.1702127659574468      	0.15473887814313347      	
0.06643356643356643      	0.06468531468531469      	0.03496503496503497      	0.09965034965034965      	0.14335664335664336      	0.0944055944055944      	0.08391608391608392      	0.1258741258741259      	0.17132867132867133      	0.11538461538461539      	
0.013671875      	0.1796875      	0.126953125      	0.064453125      	0.126953125      	0.16015625      	0.00390625      	0.095703125      	0.166015625      	0.0625      	
0.05793991416309013      	0.045064377682403435      	0.08583690987124463      	0.20815450643776823      	0.13090128755364808      	0.13948497854077252      	0.01072961373390558      	0.12017167381974249      	0.06223175965665236      	0.13948497854077252      	
0.023936170212765957      	0.023936170212765957      	0.05851063829787234      	0.07712765957446809      	0.15425531914893617      	0.22606382978723405      	0.026595744680851064      	0.05053191489361702      	0.22872340425531915      	0.13031914893617022      	
0.22779043280182232      	0.011389521640091117      	0.07289293849658314      	0.16856492027334852      	0.16400911161731208      	0.08200455580865604      	0.1548974943052392      	0.002277904328018223      	0.05011389521640091      	0.06605922551252848      	
0.11834319526627218      	0.15581854043392504      	0.14398422090729784      	0.11637080867850098      	0.07297830374753451      	0.05128205128205128      	0.07100591715976332      	0.011834319526627219      	0.09072978303747535      	0.16765285996055226      	
0.03125      	0.01838235294117647      	0.14522058823529413      	0.13419117647058823      	0.11764705882352941      	0.15073529411764705      	0.06801470588235294      	0.16727941176470587      	0.014705882352941176      	0.15257352941176472      	
0.15486725663716813      	0.030973451327433628      	0.084070796460177      	0.10176991150442478      	0.17256637168141592      	0.05530973451327434      	0.06637168141592921      	0.13274336283185842      	0.19247787610619468      	0.008849557522123894      	
0.12846347607052896      	0.09571788413098237      	0.07052896725440806      	0.022670025188916875      	0.04785894206549118      	0.017632241813602016      	0.163727959697733      	0.23425692695214106      	0.15365239294710328      	0.0654911838790932      	
0.22714681440443213      	0.16066481994459833      	0.09141274238227147      	0.11911357340720222      	0.12742382271468145      	0.0110803324099723      	0.08033240997229917      	0.10249307479224377      	0.07479224376731301      	0.00554016620498615      	
0.03978779840848806      	0.042440318302387266      	0.029177718832891247      	0.16445623342175067      	0.17771883289124668      	0.1962864721485411      	0.11140583554376658      	0.06631299734748011      	0.042440318302387266      	0.129973474801061      	
0.13602391629297458      	0.14349775784753363      	0.07772795216741404      	0.13303437967115098      	0.13153961136023917      	0.007473841554559043      	0.11509715994020926      	0.06427503736920777      	0.12406576980568013      	0.06726457399103139      	
0.10142348754448399      	0.17437722419928825      	0.12811387900355872      	0.15480427046263345      	0.06227758007117438      	0.0693950177935943      	0.09074733096085409      	0.13167259786476868      	0.019572953736654804      	0.06761565836298933      	
0.11564625850340136      	0.0022675736961451248      	0.20861678004535147      	0.018140589569160998      	0.16326530612244897      	0.11564625850340136      	0.14512471655328799      	0.12018140589569161      	0.07482993197278912      	0.036281179138321996      	
0.0511727078891258      	0.03624733475479744      	0.03411513859275053      	0.13432835820895522      	0.10660980810234541      	0.0021321961620469083      	0.19189765458422176      	0.208955223880597      	0.14712153518123666      	0.08742004264392324      	
0.014732965009208104      	0.17679558011049723      	0.16758747697974216      	0.13075506445672191      	0.003683241252302026      	0.13075506445672191      	0.09760589318600368      	0.13443830570902393      	0.034990791896869246      	0.10865561694290976      	
0.12468827930174564      	0.22942643391521197      	0.09226932668329177      	0.08728179551122195      	0.02493765586034913      	0.04239401496259352      	0.059850374064837904      	0.2194513715710723      	0.10473815461346633      	0.014962593516209476      	
0.0976      	0.1136      	0.1168      	0.056      	0.032      	0.1232      	0.0608      	0.1472      	0.136      	0.1168      	
0.029850746268656716      	0.029850746268656716      	0.16417910447761194      	0.0255863539445629      	0.0255863539445629      	0.1812366737739872      	0.07249466950959488      	0.11300639658848614      	0.17484008528784648      	0.18336886993603413      	
0.01808785529715762      	0.2454780361757106      	0.07493540051679587      	0.031007751937984496      	0.1111111111111111      	0.04909560723514212      	0.21963824289405684      	0.041343669250646      	0.12661498708010335      	0.082687338501292      	
0.01411764705882353      	0.20470588235294118      	0.17647058823529413      	0.17411764705882352      	0.023529411764705882      	0.18588235294117647      	0.018823529411764704      	0.12705882352941175      	0.021176470588235293      	0.05411764705882353      	
0.09859154929577464      	0.11619718309859155      	0.008802816901408451      	0.09154929577464789      	0.07394366197183098      	0.13380281690140844      	0.14964788732394366      	0.09154929577464789      	0.0721830985915493      	0.1637323943661972      	
0.07989690721649484      	0.12371134020618557      	0.061855670103092786      	0.15721649484536082      	0.13144329896907217      	0.020618556701030927      	0.13402061855670103      	0.023195876288659795      	0.09278350515463918      	0.17525773195876287      	
0.13432835820895522      	0.22686567164179106      	0.005970149253731343      	0.011940298507462687      	0.03283582089552239      	0.18208955223880596      	0.14925373134328357      	0.04477611940298507      	0.10149253731343283      	0.11044776119402985      	
0.07547169811320754      	0.0440251572327044      	0.05660377358490566      	0.0880503144654088      	0.14779874213836477      	0.06918238993710692      	0.1949685534591195      	0.16666666666666666      	0.012578616352201259      	0.14465408805031446      	
0.12271973466003316      	0.13266998341625208      	0.12437810945273632      	0.16417910447761194      	0.13266998341625208      	0.04145936981757877      	0.11608623548922056      	0.07296849087893864      	0.06965174129353234      	0.02321724709784411      	
0.0603448275862069      	0.07327586206896551      	0.01939655172413793      	0.01939655172413793      	0.11206896551724138      	0.17456896551724138      	0.1875      	0.10129310344827586      	0.14224137931034483      	0.10991379310344827      	
0.07947019867549669      	0.0380794701986755      	0.033112582781456956      	0.08443708609271523      	0.10596026490066225      	0.10099337748344371      	0.152317880794702      	0.15728476821192053      	0.16390728476821192      	0.08443708609271523      	
0.13143872113676733      	0.04085257548845471      	0.13854351687388988      	0.047957371225577264      	0.12433392539964476      	0.16163410301953818      	0.13676731793960922      	0.037300177619893425      	0.09769094138543517      	0.08348134991119005      	
0.09036144578313253      	0.030120481927710843      	0.16666666666666666      	0.05622489959839357      	0.12650602409638553      	0.19678714859437751      	0.20080321285140562      	0.03413654618473896      	0.08634538152610442      	0.012048192771084338      	
0.15839694656488548      	0.18893129770992367      	0.1049618320610687      	0.0648854961832061      	0.09541984732824428      	0.05725190839694656      	0.08587786259541985      	0.08015267175572519      	0.05152671755725191      	0.11259541984732824      	
0.012915129151291513      	0.13653136531365315      	0.12361623616236163      	0.03690036900369004      	0.14760147601476015      	0.06642066420664207      	0.05350553505535055      	0.13284132841328414      	0.18081180811808117      	0.1088560885608856      	
0.1358695652173913      	0.024456521739130436      	0.11956521739130435      	0.18206521739130435      	0.1983695652173913      	0.15760869565217392      	0.10869565217391304      	0.021739130434782608      	0.019021739130434784      	0.03260869565217391      	
0.1375186846038864      	0.14050822122571002      	0.06278026905829596      	0.14798206278026907      	0.017937219730941704      	0.14798206278026907      	0.12556053811659193      	0.025411061285500747      	0.13303437967115098      	0.061285500747384154      	
0.036734693877551024      	0.036734693877551024      	0.04693877551020408      	0.13877551020408163      	0.02857142857142857      	0.16938775510204082      	0.1653061224489796      	0.14285714285714285      	0.044897959183673466      	0.18979591836734694      	
0.15526802218114602      	0.12939001848428835      	0.10166358595194085      	0.025878003696857672      	0.1478743068391867      	0.11090573012939002      	0.014787430683918669      	0.05545286506469501      	0.17929759704251386      	0.07948243992606285      	
0.14488636363636365      	0.08238636363636363      	0.11931818181818182      	0.16761363636363635      	0.0625      	0.20738636363636365      	0.022727272727272728      	0.09090909090909091      	0.014204545454545454      	0.08806818181818182      	
0.0896358543417367      	0.12745098039215685      	0.12605042016806722      	0.0784313725490196      	0.03361344537815126      	0.0742296918767507      	0.12745098039215685      	0.12745098039215685      	0.0938375350140056      	0.12184873949579832      	
0.03424657534246575      	0.0547945205479452      	0.17123287671232876      	0.02968036529680365      	0.0547945205479452      	0.21689497716894976      	0.0045662100456621      	0.1780821917808219      	0.1963470319634703      	0.0593607305936073      	
0.16500994035785288      	0.041749502982107355      	0.061630218687872766      	0.07952286282306163      	0.08548707753479125      	0.1848906560636183      	0.09542743538767395      	0.15109343936381708      	0.11332007952286283      	0.02186878727634195      	
0.04477611940298507      	0.2025586353944563      	0.14925373134328357      	0.07036247334754797      	0.21108742004264391      	0.017057569296375266      	0.006396588486140725      	0.16417910447761194      	0.02771855010660981      	0.10660980810234541      	
0.05128205128205128      	0.12980769230769232      	0.004807692307692308      	0.14903846153846154      	0.11217948717948718      	0.1346153846153846      	0.09775641025641026      	0.06570512820512821      	0.09935897435897435      	0.15544871794871795      	
0.16571042403503378
continuing

test_sol.txt

0.05828026505163125 0
0.4671539356096856 1
0.34562358582362035 0
0.33140705210866006 1
0.15493089941922517 4
0.4098995443608635 3
0.46564150791604136 1
0.33328021531302676 0
0.4040390895816435 1
0.10088701746846701 1