class Domino {
  int gauche, droite;

  Domino(int g, int d) {
    gauche = g;
    droite = d;
  }

  public String toString() {
    return gauche + "-" + droite;
  }

  public boolean equals(Object o) {
    if(this==o) return true;
    if(o instanceof Domino) {
      Domino d = (Domino) o;
      return (gauche==d.gauche && droite==d.droite) 
            || (gauche==d.droite && droite==d.gauche);
    }
    return false;
  }

  void retourne() {
    int d = droite;
    droite = gauche;
    gauche = d;
  }
}

/* Question 2.1 */
class Liste {
  Domino dom;
  Liste suite;

  Liste(Domino d, Liste s) {
    dom = d;
    suite = s;
  }
}
/* Question 4.1 */
class Sequence {
  private Liste gauche;

  Sequence(Domino d) {
    gauche = new Liste(d, null);
  }

  void imprimer() {
    System.out.println("Sur la table :");
    Partie.lister(gauche);
    System.out.println("\n------");
  }

  /* Question 4.2 */
  int valeurGauche(){
    return gauche.dom.gauche;
  }

  void ajouterAGauche(Domino d) {
    gauche = new Liste(d, gauche);
  }

  /* Question 4.3 */
  int valeurDroite(){
    Liste l = gauche;
    for(; l.suite!=null; l = l.suite);
    return l.dom.droite;
  }

  void ajouterADroite(Domino d) {
    if(gauche==null) {
      gauche = new Liste(d,null);
      return;
    }
    Liste l = gauche;
    for(; l.suite!=null; l = l.suite);
    l.suite = new Liste(d,null);
  }

  /* Question 4.4

     private Liste droite;

     void ajouterAGauche(Domino d) {
     gauche = new Liste(d, gauche);
     if(droite==null) droite = gauche;
     }

     int valeurDroite() {
     return droite.dom.droite;
     }

     void ajouterADroite(Domino d) {
     if(gauche==null) {
     ajouterAGauche(d);
     return;
     }
     droite.suite = new Liste(d,null);
     droite = droite.suite;
     }
     */

}

class Partie {
  final static int TAILLEDOMINO = 6;//Le plus grand nombre sur un domino
  final static int[] TAILLEMAIN = {0,0,7,6,6};//La taille des mains en fonction
  //du nombre de joueurs.
  static Liste pioche;
  static Liste[] mains;

  /* Question 2.2 */
  static int longueur(Liste l) {
    if(l==null) return 0;
    return 1 + longueur(l.suite);
  }

  /* Question 2.3 */
  static void lister(Liste l) {
    if(l==null) return;
    System.out.print(l.dom + " ");
    lister(l.suite);
  }

  /* Question 3.1 */
  static void creerPioche(){
    pioche = null;
    for(int i = 0; i<TAILLEDOMINO+1; i++) {
      for(int j = i; j<7; j++) pioche = new Liste(new Domino(i,j), pioche);
    }
  }

  /* Question 3.2 */
  static Domino nieme(Liste l, int n) {
    if(n==0) return l.dom;
    return nieme(l.suite, n-1);
  }

  /* Question 3.3 */
  static Liste supprimer(Liste l, Domino d) {
    if(l==null) return null;
    if(l.dom.equals(d)) return l.suite;
    return new Liste(l.dom, supprimer(l.suite, d));
  }

  static int entierAuHasard(int max) {
    return (int) (Math.random() * max);
  }

  /* Question 3.4 */
  static Domino piocher(){
    int l = longueur(pioche);
    Domino d = nieme(pioche, entierAuHasard(l));
    pioche = supprimer(pioche, d);
    return d;
  }

  /* Question 3.5 */
  static void creerMain(int joueur, int nombre) {
    mains[joueur] = null;
    for(int i=0; i<nombre; i++) {
      mains[joueur] = new Liste(piocher(), mains[joueur]);
    }
  }

  /* Question 3.6 */
  static int valeurDomino(Domino d){
    if(d.gauche > d.droite) return d.gauche * 10 + d.droite;
    return d.droite * 10 + d.gauche;
  }

  static int valeurMain(int joueur) {
    int res = 0;
    for(Liste l = mains[joueur]; l != null; l = l.suite) {
      int v = valeurDomino(l.dom);
      res = (v>res)?v:res;
    }
    return res;
  }

  static int plusForteMain() {
    int res = valeurMain(0);
    int j = 0;
    for(int i = 0; i<mains.length; i++){
      int v = valeurMain(i);
      if(v>res) {
	res = v;
	j = i;
      }
    }
    return j;
  }

  /* Question 5.1 */
  static Domino retourne(Domino d) {
    return new Domino(d.droite, d.gauche);
  }

  static Sequence premierCoup(int joueur) {
    Domino aJouer = nieme(mains[joueur], 
	entierAuHasard(longueur(mains[joueur])));
    mains[joueur] = supprimer(mains[joueur], aJouer);
    return new Sequence(aJouer);
  }

  static boolean jouer(int joueur, Sequence jeu) {
		/* Pour la question 5.3, on avantage le joueur 1 */
		if(joueur==1) mains[1]=mettreMeilleurDevant(mains[1], jeu);
    Domino aJouer=null;
    int g = jeu.valeurGauche();
    int d = jeu.valeurDroite(); 
    int longueur = longueur(mains[joueur]);
    for(Liste l = mains[joueur]; l != null; l = l.suite) {
      /* Version objet
	 if(l.dom.gauche == g) l.dom.retourne();
	 else if(l.dom.droite == d) l.dom.retourne();
	 */
      if(l.dom.gauche == g) l.dom = retourne(l.dom);
      else if(l.dom.droite == d) l.dom = retourne(l.dom);
      if(l.dom.droite == g) {
	jeu.ajouterAGauche(l.dom);
	aJouer = l.dom;
	break;
      } else if (l.dom.gauche == d) {
	jeu.ajouterADroite(l.dom);
	aJouer = l.dom;
	break;
      } 
    }
    if(aJouer != null) {
			System.out.println("Le joueur " + joueur + " joue le domino " + aJouer);
      mains[joueur] = supprimer(mains[joueur], aJouer);
      return true;
    }
    if(pioche == null) {
      System.out.println("Le joueur "+ joueur +" boude.");
      return false;
    }
    System.out.print("Le joueur "+ joueur +" pioche");
    mains[joueur] = new Liste(piocher(), mains[joueur]);
		System.out.println(" le domino " + mains[joueur].dom);
    return true;
  }

  /* Question 5.2 */
  static void imprimeMain(int joueur) {
    System.out.println("Main du joueur "+joueur+" :");
    lister(mains[joueur]);
    System.out.println("\n");
  }

  static void imprimeGagnants(){
    int dominos = longueur(mains[0]);
    int[] gagnants = {0};
    for(int i=1; i<mains.length; i++) {
      int l = longueur(mains[i]);
      if(l<dominos) {
	dominos = l;
	gagnants = new int[1];
	gagnants[0] = i;
      }
      else if(l==dominos) {
	int[] g = new int[gagnants.length + 1];
	for(int j=0; j<gagnants.length; j++) g[j] = gagnants[j];
	gagnants = g;
	gagnants[g.length-1] = i;
      }
    }
    if(gagnants.length == 1) {
      System.out.println("\nLe joueur " + gagnants[0] + " a gagne.");
      return;
    }
    if(gagnants.length == mains.length) {
      System.out.println("\nMatch nul.");
      for(int i=0; i<gagnants.length; i++)
	System.out.println("Le joueur " + i + " a " +
	    sommeValeursMain(i) + " points.");
      return;
    }
    System.out.print("\nLes joueurs ");
    for(int i=0; i<gagnants.length-1; i++) System.out.print(gagnants[i] + ", ");
    System.out.println("et " + gagnants[gagnants.length-1] + " sont gagnants" +
	" ex-aequo.");
    for(int i=0; i<gagnants.length; i++)
      System.out.println("Le joueur " + gagnants[i] + " a " +
	  sommeValeursMain(gagnants[i]) + " points.");
  }

  /* Question 5.3 */
  static int sommeValeursMain(int joueur) {
    int res = 0;
    for(Liste l = mains[joueur]; l!=null; l = l.suite) 
      res += valeurDomino(l.dom);
    return res;
  }

  static boolean jouable(Domino d, Sequence jeu) {
    int x = jeu.valeurGauche();
    int y = jeu.valeurDroite();
    return d.gauche==x || d.droite==x || d.gauche==y || d.droite==y;
  }

  static Liste mettreMeilleurDevant(Liste l, Sequence jeu) {
    if(l==null || l.suite==null) return l;
    Liste ll = mettreMeilleurDevant(l.suite,jeu);
    boolean jouableTrouve = jouable(ll.dom, jeu);
    if(jouable(l.dom, jeu) && (
	  (jouableTrouve && valeurDomino(l.dom) > valeurDomino(ll.dom) )
	  || !jouableTrouve )) 
    {
      l.suite = ll;
      return l;
    }
    l.suite = ll.suite;
    ll.suite = l;
    return ll;
  }

  public static void main(String[] args) {
    int nombreDeJoueurs = 2;
    if(args.length>0) nombreDeJoueurs = Integer.parseInt(args[0]);
    int tailleMain = TAILLEMAIN[nombreDeJoueurs];
    mains = new Liste[nombreDeJoueurs];
    creerPioche();
    for(int i=0; i<nombreDeJoueurs; i++) {
      creerMain(i, tailleMain);
      imprimeMain(i);
    }
    int joueur = plusForteMain();
    System.out.println("Le joueur "+joueur+" commence.");
    Sequence jeu = premierCoup(joueur);
    joueur = (joueur + 1) % nombreDeJoueurs;
    int bloques = 0;
    while(bloques<nombreDeJoueurs){
      jeu.imprimer();
      imprimeMain(joueur);
      if(jouer(joueur, jeu)) bloques = 0; 
      else bloques++;
      if(mains[joueur]==null) {
	System.out.println("Le joueur " + joueur + " a gagne.");
	return;
      }
      joueur = (joueur + 1) % nombreDeJoueurs;
    }
    imprimeGagnants();
  }
}