import mathe.FormattedOut;
/**
 * AlgDs WS99 Aufgabe 33.
 * Tuerme von Hanoi
 *
 * @author Christian Semrau, 26.12.1999
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
class ChS_Aufg33 {
	int anzahl;    // die gesamte Anzahl der Scheiben
	int[][] stab;  // die Scheiben auf den Staeben
	int[] stabtop; // die Anzahl der Scheiben auf den Staeben


/**
 * Legt neue "Tuerme von Hanoi" an. Die Anzahl der Scheiben wird als Parameter
 * uebergeben. Stab 0 wird mit den Scheiben gefuellt, die beiden anderen Staebe
 * (1 und 2) sind leer.
 */
public ChS_Aufg33(int anz) {
	anzahl = anz;
	stab = new int[3][anz]; stab[0] = init(anz);
	stabtop = new int[3];   stabtop[0] = anz;
}

/** Liefert ein int-Feld, das absteigend mit den Zahlen anzahl bis 1 gefuellt ist. */
public static int[] init(int anzahl) {
  int[] a = new int[anzahl];
  for (int i=0; i<anzahl; a[i] = anzahl-(i++));
  return a;
}

public static void main(java.lang.String[] args) {
	System.out.println("AlgDs WS99 Aufgabe 33, Christian Semrau 26.12.1999");
	int hoehe = 8;
	// zwei Tuerme werden angelegt
	ChS_Aufg33 turm1 = new ChS_Aufg33(hoehe);
	ChS_Aufg33 turm2 = new ChS_Aufg33(hoehe);
	// einer wird ausgegeben
	turm1.output();
	// der erste  wird rekursiv bewegt: von 0(=A) ueber 1(=B) nach 2(=C)
	turm1.versetzeTurmRekursiv(hoehe,0,1,2);
	// der zweite wird iterativ bewegt: von 0(=A) ueber 1(=B) nach 2(=C)
	turm2.versetzeTurmIterativ(hoehe,0,1,2);
}

/** Gibt die aktuelle Konfiguration auf die Konsole aus. */
public void output() {
  for (int k=0; k<3; k++) {
	System.out.print( (char)('A'+k) +":");
	for (int i=0; i<stabtop[k]; i++) System.out.print(" "+stab[k][i]);
	System.out.println();
  }
}

public void output(String s) { System.out.println(s); output(); }

/**
 * Versetzt eine Scheibe von S1 nach S2 oder umgekehrt,
 * je nachdem, was moeglich ist.
 */
public void versetzeMoeglich(int S1, int S2) {
  int l1 = stabtop[S1], l2 = stabtop[S2];
  if (l1<=0&&l2<=0) return; // kein Versetzen moeglich
  // wenn Stab S1 leer ist, dann tauschen,
  // sonst wenn Stab S2 leer ist, dann nicht tauschen,
  // sonst wenn oberste Scheibe von S1 groesser als die von S2 ist, dann tauschen,
  // sonst nicht tauschen
  if ((l1==0) || (l2!=0 && stab[S1][l1-1]>stab[S2][l2-1]))
	// tauschen: statt von S1 nach S2 jetzt von S2 nach S1 verschieben
	{int h = S1; S1 = S2; S2 = h;}
  versetzeObersten(S1,S2); output("von "+S1+" nach "+S2+":");
}

/** Versetzt die oberste Scheibe von <code>Quelle</code> nach <code>Ziel</code>. */
public void versetzeObersten(int Quelle, int Ziel) {
  stab[Ziel][stabtop[Ziel]++] = stab[Quelle][--stabtop[Quelle]];
}

/**
 * Verlagert iterativ <code>hoehe</code> Scheiben von Stab
 * <code>Quelle</code> nach Stab <code>Ziel</code>.
 * 
 * @param hoehe die Hoehe des zu bewegenden Turmes
 * (dh wieviele Scheiben bewegt werden sollen)
 * @param Quelle von welchem Stab
 * @param Hilfe auf welchen Stab wird ausgelagert
 * @param Ziel auf welchen Stab
 */
public void versetzeTurmIterativ(int hoehe, int Quelle, int Hilfe, int Ziel) {
  if (hoehe <= 0) return; // sicher ist sicher
  int[] next = new int[3];
  if (hoehe % 2 == 0){
	// kleinste Scheibe wandert von Quelle nach Hilfe nach Ziel nach Quelle
	next[Quelle] = Hilfe;  next[Hilfe] = Ziel;  next[Ziel] = Quelle;
  }else{
	// kleinste Scheibe wandert von Quelle nach Ziel nach Hilfe nach Quelle
	next[Quelle] = Ziel;  next[Hilfe] = Quelle;  next[Ziel] = Hilfe;
  }
  int aktQ = Quelle, aktH = Hilfe, aktZ = Ziel, schritte = (1 << hoehe) - 1;
  System.out.println(schritte+" Schritte.");

  while (schritte > 0) {
	if (schritte % 2 == 1) {
	  int nextQ = next[aktQ];
	  versetzeObersten(aktQ, nextQ);
	  output("Obersten von "+aktQ+" nach "+nextQ+":");
	  aktQ = nextQ; aktH = next[aktH]; aktZ = next[aktZ];
	}else{
	  versetzeMoeglich(aktH, aktZ);
	}
	schritte--;
  }
}

/**
 * Verlagert rekursiv <code>hoehe</code> Scheiben von Stab
 * <code>Quelle</code> nach Stab <code>Ziel</code>.
 *
 * @param hoehe die Hoehe des zu bewegenden Turmes
 * (dh wieviele Scheiben bewegt werden sollen)
 * @param Quelle von welchem Stab
 * @param Hilfe auf welchen Stab wird ausgelagert
 * @param Ziel auf welchen Stab
 */
public void versetzeTurmRekursiv(int hoehe, int Quelle, int Hilfe, int Ziel) {
  if (hoehe <= 0) return; // man weiss ja nie
  if (hoehe > 1) versetzeTurmRekursiv(hoehe-1, Quelle, Ziel, Hilfe);
  versetzeObersten(Quelle, Ziel);
  output("Obersten von "+Quelle+" nach "+Ziel+":");
  if (hoehe > 1) versetzeTurmRekursiv(hoehe-1, Hilfe, Quelle, Ziel);
}
} // ChS_Aufg33