/**
 * Code for exercise 3
 * Lecture Series Informatik II D-BAUG ETH Zürich  
 * Felix Friedrich, Georg Ofenbeck, Lars Widmer
 */

class LCG { //this is the random number generator from last exercise
	static final long m = 2147483647;
	static final long b = 12345;
	static final long a = 1103515245;
	static long u = 0; //to use within the judge we fix the "seed", such that we always get the same random numbers	
	
	public static double Uniform(){
		u = (u * a + b) % m;
		return(double)u/m;
	}
}

// provide your modifications in this class only
class RandomSurfer{		
	
	// pre: non-empty matrix m
	// post: matrix printout on System.out
	public static void printMatrix(double[][] m) {
		int rows = m.length;
		int cols = m[0].length;
		System.out.println(rows + " " + cols);
		for(int r = 0; r < rows; r++){									
			for (int c = 0; c < cols; c++){
				System.out.printf("%7.5f ", m[r][c]);
			}
			System.out.println("");
		}
	}

	// pre: matrix data provided via scanner
	// post: returns matrix data
	public static double[][] readMatrix(java.util.Scanner scanner){		
		int M = scanner.nextInt(); // Zeilen
		int N = scanner.nextInt(); // Spalten
		// Daten
		double[][] p = new double[M][N];     
	  	for (int i = 0; i < M; i++)
	  		for (int j = 0; j < N; j++) 
				p[i][j] = scanner.nextDouble(); 
		return p;
	}
	
	// pre: non-empty input vector of length N, matrix of size N times M
	// post: return vector-matrix product v * m. Vector of size M
	public static double[] multiplyVectorMatrix(double[] v, double[][] m) {
		int N = v.length;
		int M = m[0].length;
	    double[] res = new double[M]; // result vector
	    for (int c=0; c < M; ++c) { // for every column of the matrix
	    	res[c] = 0; // initial value (actually also done by the java VM)
	        for (int r=0; r<N; ++r) // for every element of the vector
	        	res[c] += m[r][c] * v[r]; // += adds the product to res[j] 
	    }
	    return res;
	}

	// non-empty vector v and probability matrix m, precision > 0
	// returns if v * m is close at v
	public static boolean checkConvergence(double[] v, double[][] P, double precision){
		double[] product = multiplyVectorMatrix(v, P);
		for (int i = 0; i < v.length; i++)
			if (Math.abs(product[i] - v[i]) > precision)
				return false;
		return true;		
	}



	// single step simulation from the lecture
	public static int simulateLine(double[] prob)
	{
		int res=0;
		double r = LCG.Uniform(); 
		double sum = 0.0; 
		for (int j = 0; j < prob.length; j++) {
			sum += prob[j]; 
			if (r < sum) {res = j; break;}
		}
		return res;
	}
	
	// pre: non-empty probability matrix P 
	// post: return relative frequencies of visits in each point
	//	       after MCMC simulation until convergence reached
	public static double[] simulate(double[][] P, double precision) {					
		int N = P.length;
		int[] freq = new int[N];  // freq[i] = # times surfer hits page i
		int page = 0; 				// start at page 0
		int max_steps = 10000000;
		double[] inv_freq = new double [N];
		
		int t = 1;
		do  
		{
			page = simulateLine(P[page]);
			freq[page]++;
			long sum = 0;
			for(int i = 0; i < freq.length; i++) sum += freq[i];			
			for(int i = 0; i < freq.length; i++) inv_freq[i] = (double)1.0/sum*freq[i];
			t++ ;
		}	
		while (t <= max_steps && !checkConvergence(inv_freq, P, precision));
		//System.out.println("converged after " +t + " steps");
		
		return inv_freq;
	}	
	
	// pre: non-null vector
	// post: vector output to standard out
	public static void show(double[] v) {
		for (int i=0; i<v.length; ++i)
			System.out.printf("%7.5f ",v[i]);
		System.out.println();
	}
	
	
	// pre: non-empty vector v and n times n probability matrix 
	// post: vector v close at stationary distribution of m
	//	       returns number of vector-matrix multiplications required
	public static int calculateDirect(double[] v, double[][] m, double precision){
		int t = 1;
		int max_steps = 10000000;
		double[] vp = v;
		do {
			vp = multiplyVectorMatrix(vp, m);
			t ++;
		} while (t < max_steps && !checkConvergence(vp, m, precision));
		//System.out.println("converged after " +t + " steps");
		for (int i = 0; i < v.length; ++i)
			v[i] = vp[i];
		return t;
	}
	
		
	// test program to test convergence speeds. 
	// Can be freely modified and does not have any impact on the result of the judge
	public static void main(String[] args) {
		double[][] m = { // transition probabilities 
				{0.1,0.3,0.2,0.1,0.3},
				{0.1,0.2,0.1,0.3,0.3},
				{0.3,0.1,0.3,0.2,0.1},
				// {0,0,0.0,0.0,0.0},
				{0.5,0.5,0.0,0.0,0.0},
				{0.9,0.0,0.0,0.1,0.0}};
		
		double precision = 0.0001;
		
		long before_sim = System.currentTimeMillis();
		show(simulate(m, precision));
		long after_sim = System.currentTimeMillis();		
		System.out.println("Simulation took " + (after_sim - before_sim) + " Milliseconds");
		System.out.println("---------------------------------------------------------------");
		
		long before_calculate = System.currentTimeMillis();
		double[] v = {1,0,0,0,0}; // starting state
		System.out.println(calculateDirect(v,m, precision));
		show(v);
		long after_calculate = System.currentTimeMillis();		
		System.out.println("Direct calculation took " + (after_calculate - before_calculate) + " Milliseconds");
		System.out.println("---------------------------------------------------------------");					
	}

}


//---------------------------------------------------------------------------------
// Unfortunately it is a restriction of the judge that we always have to have a public class Main in our file
// The code below is only used to validate your code with the judge - feel free to browse - but its not required for the exercise
//------------------------------------------------------------------------------------------------------------------------
class Main{ 
	
	public static double[] readV(java.util.Scanner scanner){		
		int n = scanner.nextInt();
		double[] res = new double[n];     
	  	for (int i = 0; i < n; i++)
	  		res[i] = scanner.nextDouble(); 
		return res;
	}
		
	public static void main(String[] args) {
		java.util.Scanner scanner = new java.util.Scanner(System.in);
		int choice = scanner.nextInt();
		
		if (choice == 1){
			double[][] o = {{1,2},{3,4},{5,6}};
			RandomSurfer.printMatrix(o);
		}
		if (choice == 2){
			double[][] m = RandomSurfer.readMatrix(scanner);
			RandomSurfer.printMatrix(m);
		}
		if (choice == 3) {
			double[] v = readV(scanner);
			double[][] m = RandomSurfer.readMatrix(scanner); 
			RandomSurfer.show(RandomSurfer.multiplyVectorMatrix(v,m));
		}
		if (choice == 4) {
			double[] v = readV(scanner);
			double[][] m = RandomSurfer.readMatrix(scanner); 
			double precision = scanner.nextDouble();
			System.out.println(RandomSurfer.checkConvergence(v, m, precision));			
		}
		if (choice == 5) {
			double[][] m = RandomSurfer.readMatrix(scanner); 
			double precision = scanner.nextDouble();			
			RandomSurfer.show(RandomSurfer.simulate(m, precision));
		}
		if (choice == 6) {
			double[] v = readV(scanner);
			double[][] m = RandomSurfer.readMatrix(scanner);
			double precision = scanner.nextDouble();
			System.out.println(RandomSurfer.calculateDirect(v, m, precision));
			RandomSurfer.show(v);
		}
	}
}

/*
data that can be used to check (use copy and paste to check)
1. PrintMatrix Input:
1

Expected output:
3 2
1.00000 2.00000 
3.00000 4.00000 
5.00000 6.00000

2. ReadMatrix Input:
2
2 3
1 2 3 4 5 6

Expected output:
2 3
1.00000 2.00000 3.00000 
4.00000 5.00000 6.00000

3. MutiplyVectorMatrix Input:
3
3
1 2 3
3 3 
1 2 3
4 5 6
7 8 9

Expected output:
30.00000 36.00000 42.00000 

4. CheckConvergence Input:
4
5
0.32518 0.22739 0.12541 0.14368 0.17834
5 5
0.10000 0.30000 0.20000 0.10000 0.30000 
0.10000 0.20000 0.10000 0.30000 0.30000 
0.30000 0.10000 0.30000 0.20000 0.10000 
0.50000 0.50000 0.00000 0.00000 0.00000 
0.90000 0.00000 0.00000 0.10000 0.00000
0.0001

Expected output:
true

5. Simulate Input:
5
5 5
0.10000 0.30000 0.20000 0.10000 0.30000 
0.10000 0.20000 0.10000 0.30000 0.30000 
0.30000 0.10000 0.30000 0.20000 0.10000 
0.50000 0.50000 0.00000 0.00000 0.00000 
0.90000 0.00000 0.00000 0.10000 0.00000 
0.0001 

Expected output:
0.32517 0.22769 0.12524 0.14370 0.17821

6. Calculate Direct Input:
6
5 
1 0 0 0 0
5 5 
0.10000 0.30000 0.20000 0.10000 0.30000 
0.10000 0.20000 0.10000 0.30000 0.30000 
0.30000 0.10000 0.30000 0.20000 0.10000 
0.50000 0.50000 0.00000 0.00000 0.00000 
0.90000 0.00000 0.00000 0.10000 0.00000 
0.0001

Expected output:
12
0.32518 0.22739 0.12541 0.14368 0.17834
*/