//
// Toolkit constraint encoding
//
import java.io.*;
import java.util.*;
import static choco.Choco.*;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.kernel.model.Model;
import choco.kernel.solver.Solver;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.kernel.solver.variables.integer.IntDomainVar;
import choco.kernel.solver.ContradictionException;
import choco.cp.solver.search.integer.varselector.StaticVarOrder;

public class SR {	
   
    int n;
    int[][] rank; // rank[i][j] = k <-> agent_i ranks agent_j as k^th choice (see NOTE 1)
    int[][] pref; // pref[i][k] = j <-> agent_i has agent_j as k^th choice
    int[] length; // length of agent's preference list
    Model model;
    Solver solver;
    IntegerVariable[] agent; // domain of ranks, last is unmatched
    long totalTime, modelTime, solveTime, readTime, modelSize;
    boolean search;
    int solutions; // number of matchings
    int size; // size of matching (pairs)
    double[][] lambda; // the looseness of constraint between pairs of agents
    boolean [][] acceptable; // acceptable[i][j] if agents find each other acceptable
    double pSol; // log of probability that a state is a solution, i.e. all constraints satisfied
    double N; // log of number of possible states
    double E; // expected number of solution states
    double kappa; // constrainedness 1 - log<E>/N
    double geoMeanP; // geometric mean of probabilities, only counting actual constraints/edges
    

    //
    // NOTE 1: rank[i][j] = k means that agent j is in the kth position of preference list of agent[i]
    //         rank[i][i] = length[i], i.e. the length of the preference list
    //         if (!acceptable[i][j]) then rank[i][j] = 0
    //         

    SR(String fname) throws IOException {
	search      = true;
	totalTime   = System.currentTimeMillis();
	readTime    = System.currentTimeMillis();
	read(fname);
	readTime = System.currentTimeMillis() - readTime; 
	solutions = size = 0;
    }

    SR(SMSRInstance inst) {
	search      = true;
	totalTime   = System.currentTimeMillis();
	readTime    = System.currentTimeMillis();
	read(inst);
	readTime = System.currentTimeMillis() - readTime; 
	solutions = size = 0;
    }

    void read(String fname) throws IOException {
	BufferedReader fin = new BufferedReader(new FileReader(fname));
	n                  = Integer.parseInt(fin.readLine());
	pref               = new int[n][n]; 
	rank               = new int[n][n]; 
	length             = new int[n];
	lambda             = new double[n][n];
	acceptable         = new boolean[n][n];
	for (int i=0;i<n;i++){
	    StringTokenizer st = new StringTokenizer(fin.readLine()," ");
	    int k = 0;
	    length[i] = 0;
	    while (st.hasMoreTokens()){
		int j            = Integer.parseInt(st.nextToken()) - 1;
		rank[i][j]       = k;
		pref[i][k]       = j;
		k                = k + 1;
		acceptable[i][j] = true;
	    }
	    length[i]  = k;
	    rank[i][i] = k;
	    pref[i][k] = i;
	}
	fin.close();
	calculateKappa();
    }	

    void read(SMSRInstance inst) {
	n                  = inst.n;
	pref               = new int[n][n]; 
	rank               = new int[n][n]; 
	length             = new int[n];
	lambda             = new double[n][n];
	acceptable         = new boolean[n][n];
	for (int i=0;i<n;i++){
	    int k = 0;
	    length[i] = 0;
	    for (int j : (ArrayList<Integer>)inst.pref[i]){
		rank[i][j]       = k;
		pref[i][k]       = j;
		k                = k + 1;
		acceptable[i][j] = true;
	    }
	    length[i]  = k;
	    rank[i][i] = k;
	    pref[i][k] = i;
	}
	calculateKappa();
    }

    void calculateKappa(){
	int edges = 0;
	for (int i=0;i<n;i++) Arrays.fill(lambda[i],1.0);
	for (int i=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++)
		lambda[i][j] = lambda[j][i] = getLambda(i,j);
	for (int i=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++) 
		if (acceptable[i][j]){
		    pSol = pSol + Math.log(lambda[i][j]);
		    edges = edges + 1;
		}
	for (int i=0;i<n;i++) N = N + Math.log((double)(length[i]+1));
	E = N + pSol;
	if (pSol == 0.0) kappa = 0.0; // every state is a solution
	else kappa = 1.0 - E/N;
	if (edges == 0) geoMeanP = 0.0; else geoMeanP =  Math.exp(pSol/(double)edges);
    }

    void build(){
	modelTime = System.currentTimeMillis();
	model     = new CPModel(); 
	agent     = new IntegerVariable[n];
	for (int i=0;i<n;i++){
	    agent[i] = makeIntVar("agent_"+ i,0,length[i],"cp:enum");
	    model.addVariable(agent[i]);
	}
	for (int i=0;i<n;i++)
	    for (int j=0;j<length[i];j++){
		int k = pref[i][j];
		model.addConstraint(implies(gt(agent[i],rank[i][k]),lt(agent[k],rank[k][i])));
		model.addConstraint(implies(eq(agent[i],rank[i][k]),eq(agent[k],rank[k][i])));
	    }
	solver     = new CPSolver(); 
	solver.read(model); 
	modelTime  = System.currentTimeMillis() - modelTime;
	modelSize  = (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/1024; // kilobytes
    }

    void solve(String command) throws ContradictionException {
	solveTime = System.currentTimeMillis();
	solver.setVarIntSelector(new StaticVarOrder(solver,solver.getVar(agent)));
	if (command.equals("count")){ // count all solutions
	    if (solver.solve().booleanValue()){
		solutions = 1;
		size = getSize();
		while (solver.nextSolution().booleanValue()) solutions++;
	    }
	}
	else if (command.equals("all")){ // enumerate all solutions
	    if (solver.solve().booleanValue()){
		displayMatching();
		solutions = 1;
		size = getSize();
		while (solver.nextSolution().booleanValue()){solutions++; displayMatching();}
	    }
	}
	else if (command.equals("propagate")){
	    search = false;
	    try{solver.propagate(); displayPhase1Table();} catch (ContradictionException e){displayPhase1Table();}
	}
	else if (solver.solve().booleanValue()){size = getSize(); solutions = 1; displayMatching();}
	solveTime = System.currentTimeMillis() - solveTime;
	totalTime = System.currentTimeMillis() - totalTime;
    }

    int getSize(){
	int pairs = 0;
	for (int i=0;i<n;i++){
	    int j = pref[i][solver.getVar(agent[i]).getVal()];
	    if (i<j) pairs++;
	}
	return pairs;
    }

    //
    // get constraint tightness between agents i and j
    //
    double getTau(int i,int j){
	if (!acceptable[i][j]) return 0.0; // unconstrained
	double allPairs = 0.0; // also to include unmatched
	double disallowedPairs = 0.0;
	for (int x=0;x<=length[i];x++)
	    for (int y=0;y<=length[j];y++){
		allPairs = allPairs + 1.0;
		if (illegalMatching(i,pref[i][x],j,pref[j][y]))
		    disallowedPairs = disallowedPairs + 1.0;
	    }
	return disallowedPairs/allPairs;
    }

    //
    // Where agents i and j are mutually acceptable, i.e. acceptable[i][j] AND
    // x is in pref[i] and y is in pref[j], i.e. acceptable[i][x] && acceptable[j][y]
    // Are (i,x) and (j,y) an illegal or unstabe pair of matchings?
    //
    boolean illegalMatching(int i,int x,int j,int y){
	return x == j && y != i // i marries j but j does not marry i
	    || x != j && y == i // j marries i but i does not marry j
	    || rank[i][x] > rank[i][j] && rank[j][y] > rank[j][i]; // unstable
    }

    //
    // constraint looseness between agents i and j
    //
    // agent[i]  AAAAAAAAAAAAAXBBBBBBBBBBZ
    // agent[j]  CCCCCCCYDDDDDDDDDDDDZ
    // looseness = (A.C + A.D + C.B + 1)/((1+length[i]).(1+length[j]))
    // where X and Y are marriage and Z is unmatched
    //
    double getLambda(int i,int j){
	if (!acceptable[i][j]) return 1.0;
	int A = rank[i][j];
	int B = length[i] - rank[i][j];
	int C = rank[j][i];
	int D = length[j] - rank[j][i];
	double lambda = (double)(A*C + A*D + C*B + 1)/(double)((1 + length[i]) * (1 + length[j]));
	//System.out.println("lambda("+ i +","+ j +") A: "+ A +" B: "+ B +" C: "+ C +" D: "+ D +" lambda: "+ lambda);
	return lambda;
    }
    
    void displayMatching(){
	for (int i=0;i<n;i++){
	    int j = pref[i][solver.getVar(agent[i]).getVal()];
	    if (i<j) System.out.print("("+ (i+1) +","+ (j+1) +") ");
	}
	System.out.println();
    }

    void displayPhase1Table(){
	for (int i=0;i<n;i++){
	    IntDomainVar v = solver.getVar(agent[i]);
	    System.out.print(i+1 +": ");
	    for (int j=0;j<length[i];j++) if (v.getDomain().contains(j)) System.out.print(pref[i][j]+1 +" ");
	    System.out.println();
	}
    }

    void displayRank(){
	System.out.println("ranks");
	for (int i=0;i<n;i++){
	    System.out.print(i +": ");
	    for (int j=0;j<n;j++) 
		if (acceptable[i][j]) System.out.print(rank[i][j] +" ");
		else System.out.print("- ");
	    System.out.println(" length: " + length[i]);
	}
    }

    void displayPref(){
	System.out.println("preferences");
	for (int i=0;i<n;i++){
	    System.out.print(i +": ");
	    for (int j=0;j<length[i];j++) System.out.print(pref[i][j] +" ");
	    System.out.println(" length: " + length[i]);
	}
    }

    void displayLambda(){
	System.out.println("lambda");
	for (int i=0;i<n;i++){
	    for (int j=0;j<n;j++) System.out.format("%.3f ",lambda[i][j]);
	    System.out.println();
	}
    }	
    
    void display(){
	System.out.println(n);
	for (int i=0;i<n;i++){
	    for (int j=0;j<n;j++)
		if (pref[i][j] != i) System.out.print((pref[i][j] + 1) +" ");
	    System.out.println();
	}
    }

    void stats(){
	if (search) System.out.print("nodes: "+ solver.getNodeCount() +"  ");
	System.out.print("modelTime: "+ modelTime +"  ");
	if (search) System.out.print("solveTime: "+ solveTime +"  ");
	System.out.print("totalTime: "+ totalTime +"  ");
	System.out.print("modelSize: "+ modelSize +"  ");
	System.out.print("readTime: "+ readTime +" ");
	System.out.format(" pSol: %.3f ",pSol);
	System.out.format(" N: %.3f ",N);
	System.out.format(" E: %.3f ",E);
	System.out.format(" kappa: %.3f ",kappa);
	System.out.format(" geoMeanP: %.3f ",geoMeanP);
	System.out.println();
    }

     void shortStats(){
	 System.out.print("solutions: "+ solutions +" ");
	 System.out.print("size: "+ size +" ");
	 if (search) System.out.print("nodes: "+ solver.getNodeCount() +"  ");
	 System.out.print("modelTime: "+ modelTime +"  ");
	 if (search) System.out.print("solveTime: "+ solveTime +"  ");
	 System.out.print("totalTime: "+ totalTime +"  ");
	 System.out.print("modelSize: "+ modelSize +"  ");
	 System.out.print("readTime: "+ readTime +" ");
	 System.out.format(" pSol: %.3f ",pSol);
	 System.out.format(" N: %.3f ",N);
	 System.out.format(" E: %.3f ",E);
	 System.out.format(" kappa: %.3f ",kappa);
	 System.out.format(" geoMeanP: %.3f ",geoMeanP);
	 System.out.println();
     }

    public static void main(String[] args) throws IOException, ContradictionException {
	SR sr = new SR(args[0]);
	sr.build();
	//sr.displayPref();
	//System.out.println();
	//sr.displayRank();
	//System.out.println(); 
	//sr.displayLambda();
	//System.out.println();
	if (args.length > 1) 
	    sr.solve(args[1]);
	else
	    sr.solve("first");
	if (args.length > 1 && args[1].equals("count")) sr.shortStats();
	else sr.stats();
    }
}