GraphWalkWithProbabilities.java

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;

public class GraphWalkWithProbabilities
{
	public double findprob(String[] graph, int[] winprob, int[] looseprob, int Start)
	{
		double[] dp = new double[winprob.length];
		dp[Start] = 1;
		double win = 0;
		while (true) {
			double[] newDP = new double[winprob.length];
			double max = 0;
			int maxP = 0;
			for (int j = 0; j < newDP.length; j++) {
				double d = newDP[j];
				if (max < d) {
					max = d;
					maxP = j;
				}
			}
			double plus = dp[maxP] * winprob[maxP];
			win += plus;

			if (plus < 1E-9) {
				return win;
			}
			for (int i = 0; i < dp.length; i++) {
				for (int j = 0; j < dp.length; j++) {
					if (graph[i].charAt(j) == '1') {
						newDP[i] = Math.max(newDP[i],
								dp[j] * (1.0*winprob[i] / (winprob[i] + looseprob[i])));
					}
				}
			}
			dp = newDP;
		}
	}

	// BEGIN KAWIGIEDIT TESTING
	// Generated by KawigiEdit-pf 2.3.0
	private static boolean KawigiEdit_RunTest(int testNum, String[] p0, int[] p1, int[] p2, int p3, boolean hasAnswer,
			double p4) {
		System.out.print("Test " + testNum + ": [" + "{");
		for (int i = 0; p0.length > i; ++i) {
			if (i > 0) {
				System.out.print(",");
			}
			System.out.print("\"" + p0[i] + "\"");
		}
		System.out.print("}" + "," + "{");
		for (int i = 0; p1.length > i; ++i) {
			if (i > 0) {
				System.out.print(",");
			}
			System.out.print(p1[i]);
		}
		System.out.print("}" + "," + "{");
		for (int i = 0; p2.length > i; ++i) {
			if (i > 0) {
				System.out.print(",");
			}
			System.out.print(p2[i]);
		}
		System.out.print("}" + "," + p3);
		System.out.println("]");
		GraphWalkWithProbabilities obj;
		double answer;
		obj = new GraphWalkWithProbabilities();
		long startTime = System.currentTimeMillis();
		answer = obj.findprob(p0, p1, p2, p3);
		long endTime = System.currentTimeMillis();
		boolean res;
		res = true;
		System.out.println("Time: " + (endTime - startTime) / 1000.0 + " seconds");
		if (hasAnswer) {
			res = answer == answer && Math.abs(p4 - answer) <= 1e-9 * Math.max(1.0, Math.abs(p4));
		}
		if (!res) {
			System.out.println("DOESN'T MATCH!!!!");
			if (hasAnswer) {
				System.out.println("Desired answer:");
				System.out.println("\t" + p4);
			}
			System.out.println("Your answer:");
			System.out.println("\t" + answer);
		} else if ((endTime - startTime) / 1000.0 >= 2) {
			System.out.println("FAIL the timeout");
			res = false;
		} else if (hasAnswer) {
			System.out.println("Match :-)");
		} else {
			System.out.println("OK, but is it right?");
		}
		System.out.println("");
		return res;
	}

	public static void main(String[] args) {
		boolean all_right;
		boolean disabled;
		boolean tests_disabled;
		all_right = true;
		tests_disabled = false;

		String[] p0;
		int[] p1;
		int[] p2;
		int p3;
		double p4;

		// ----- test 0 -----
		disabled = true;
		p0 = new String[] { "1" };
		p1 = new int[] { 1 };
		p2 = new int[] { 1 };
		p3 = 0;
		p4 = 0.5D;
		all_right = (disabled || KawigiEdit_RunTest(0, p0, p1, p2, p3, true, p4)) && all_right;
		tests_disabled = tests_disabled || disabled;
		// ------------------

		// ----- test 1 -----
		disabled = true;
		p0 = new String[] { "11", "11" };
		p1 = new int[] { 60, 40 };
		p2 = new int[] { 40, 60 };
		p3 = 0;
		p4 = 0.6D;
		all_right = (disabled || KawigiEdit_RunTest(1, p0, p1, p2, p3, true, p4)) && all_right;
		tests_disabled = tests_disabled || disabled;
		// ------------------

		// ----- test 2 -----
		disabled = false;
		p0 = new String[] { "11", "11" };
		p1 = new int[] { 2, 3 };
		p2 = new int[] { 3, 4 };
		p3 = 0;
		p4 = 0.4285714285714286D;
		all_right = (disabled || KawigiEdit_RunTest(2, p0, p1, p2, p3, true, p4)) && all_right;
		tests_disabled = tests_disabled || disabled;
		// ------------------

		// ----- test 3 -----
		disabled = false;
		p0 = new String[] { "110", "011", "001" };
		p1 = new int[] { 2, 1, 10 };
		p2 = new int[] { 20, 20, 10 };
		p3 = 0;
		p4 = 0.405D;
		all_right = (disabled || KawigiEdit_RunTest(3, p0, p1, p2, p3, true, p4)) && all_right;
		tests_disabled = tests_disabled || disabled;
		// ------------------

		// ----- test 4 -----
		disabled = false;
		p0 = new String[] { "111", "111", "011" };
		p1 = new int[] { 100, 1, 1 };
		p2 = new int[] { 0, 50, 50 };
		p3 = 2;
		p4 = 0.5D;
		all_right = (disabled || KawigiEdit_RunTest(4, p0, p1, p2, p3, true, p4)) && all_right;
		tests_disabled = tests_disabled || disabled;
		// ------------------

		if (all_right) {
			if (tests_disabled) {
				System.out.println("You're a stud (but some test cases were disabled)!");
			} else {
				System.out.println("You're a stud (at least on given cases)!");
			}
		} else {
			System.out.println("Some of the test cases had errors.");
		}
	}
	// END KAWIGIEDIT TESTING
}

// Powered by KawigiEdit-pf 2.3.0!