GraphWalkWithProbabilities.py

import math,string,itertools,fractions,heapq,collections,re,array,bisect,random

class GraphWalkWithProbabilities:
    def findprob(self, graph, winprob, looseprob, Start):
        g=[];n=len(winprob)
        for i,j in zip(winprob,looseprob):g+=[1.*i/(i+j)]
        for _ in range(55):
            for i in range(n):
                for j in range(n):
                    if graph[i][j]=='1':
                        g[i]=max(g[i],winprob[j]*0.01
                                 +(100.-(winprob[j]+looseprob[j]))*0.01*g[j]
                                 )
        return g[Start]

# BEGIN KAWIGIEDIT TESTING
# Generated by KawigiEdit-pf 2.3.0
import sys
import time
def KawigiEdit_RunTest(testNum, p0, p1, p2, p3, hasAnswer, p4):
	sys.stdout.write(str("Test ") + str(testNum) + str(": [") + str("{"))
	for i in range(len(p0)):
		if (i > 0):
			sys.stdout.write(str(","))
		
		sys.stdout.write(str("\"") + str(p0[i]) + str("\""))
	
	sys.stdout.write(str("}") + str(",") + str("{"))
	for i in range(len(p1)):
		if (i > 0):
			sys.stdout.write(str(","))
		
		sys.stdout.write(str(p1[i]))
	
	sys.stdout.write(str("}") + str(",") + str("{"))
	for i in range(len(p2)):
		if (i > 0):
			sys.stdout.write(str(","))
		
		sys.stdout.write(str(p2[i]))
	
	sys.stdout.write(str("}") + str(",") + str(p3))
	print(str("]"))
	obj = GraphWalkWithProbabilities()
	startTime = time.clock()
	answer = obj.findprob(p0, p1, p2, p3)
	endTime = time.clock()
	res = True
	print(str("Time: ") + str((endTime - startTime)) + str(" seconds"))
	if (hasAnswer):
		res = answer == answer and abs(p4 - answer) <= 1e-9 * max(1.0, abs(p4))
	
	if (not res):
		print(str("DOESN'T MATCH!!!!"))
		if (hasAnswer):
			print(str("Desired answer:"))
			print(str("\t") + str(p4))
		
		print(str("Your answer:"))
		print(str("\t") + str(answer))
	elif ((endTime - startTime) >= 2):
		print(str("FAIL the timeout"))
		res = False
	elif (hasAnswer):
		print(str("Match :-)"))
	else:
		print(str("OK, but is it right?"))
	
	print(str(""))
	return res

all_right = True
tests_disabled = False


# ----- test 0 -----
disabled = False
p0 = ("1",)
p1 = (1,)
p2 = (1,)
p3 = 0
p4 = 0.5
all_right = (disabled or KawigiEdit_RunTest(0, p0, p1, p2, p3, True, p4) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

# ----- test 1 -----
disabled = False
p0 = ("11","11")
p1 = (60,40)
p2 = (40,60)
p3 = 0
p4 = 0.6
all_right = (disabled or KawigiEdit_RunTest(1, p0, p1, p2, p3, True, p4) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

# ----- test 2 -----
disabled = False
p0 = ("11","11")
p1 = (2,3)
p2 = (3,4)
p3 = 0
p4 = 0.4285714285714286
all_right = (disabled or KawigiEdit_RunTest(2, p0, p1, p2, p3, True, p4) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

# ----- test 3 -----
disabled = False
p0 = ("110","011","001")
p1 = (2,1,10)
p2 = (20,20,10)
p3 = 0
p4 = 0.405
all_right = (disabled or KawigiEdit_RunTest(3, p0, p1, p2, p3, True, p4) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

# ----- test 4 -----
disabled = False
p0 = ("111","111","011")
p1 = (100,1,1)
p2 = (0,50,50)
p3 = 2
p4 = 0.5
all_right = (disabled or KawigiEdit_RunTest(4, p0, p1, p2, p3, True, p4) ) and all_right
tests_disabled = tests_disabled or disabled
# ------------------

if (all_right):
	if (tests_disabled):
		print(str("You're a stud (but some test cases were disabled)!"))
	else:
		print(str("You're a stud (at least on given cases)!"))
	
else:
	print(str("Some of the test cases had errors."))

# END KAWIGIEDIT TESTING
#Powered by KawigiEdit-pf 2.3.0!