// Towers of Hanoi
//
// Aufruf: hanoi
//
// Klaus Kusche, 2002

#include <stdio.h>
#include <stdlib.h>

// für usleep, nur Linux
#include <unistd.h>
// für Sleep, nur Windows
//#include <windows.h>

// Anzahl der Scheiben
#define ANZAHL 5
// Verzögerung zwischen zwei Zügen in Millisekunden
#define DELAY 300
// Zeilen am Terminal
#define LINES 24

// Die drei Türme
// Index ANZAHL-1 ist ganz oben, Index 0 ganz unten
// Jedes Element enthält die Größe der Scheibe, die auf dieser Höhe liegt
// (kleinste Scheibe 1, größte Scheibe ANZAHL)
// freie Elemente am oberen Ende sind 0
int a[ANZAHL], b[ANZAHL], c[ANZAHL];

// Gib eine Scheibe der Größe n aus
void scheibe(int n);
// Gib den aktuellen Stand der Türme aus
void ausgabe(void);
// Bewege die obenauf liegende Scheibe von Turm "von" nach Turm "nach"
void lege(int von[], int nach[]);
// Rek. Funktion: Bewege "anzahl" Scheiben von Turm "von" auf Turm "nach"
void bewege(int anzahl, int von[], int nach[], int zwischen[]);

// Gib eine Scheibe der Größe n aus
// Fülle mit Leerzeichen auf fixe Breite auf
// Bei n==0 wird nur die richtige Anzahl Leerzeichen ausgegeben
void scheibe(int n)
{
  // Leerzeichen links von der Scheibe
  for (int i = 0; i < ANZAHL + 1 - n; ++i) {
    putchar(' ');
  }
  // Scheibe (Scheibe Nummer n ist 2 * n Zeichen breit)
  for (int i = 0; i < 2 * n; ++i) {
    putchar('#');
  }
  // Leerzeichen rechts von der Scheibe
  for (int i = 0; i < ANZAHL + 1 - n; ++i) {
    putchar(' ');
  }
}

// Gib den aktuellen Stand der Türme aus
// Warte die Verzögerung ab
void ausgabe(void)
{
  // Terminal-Fenster-Inhalt löschen
  system("clear");  // Linux
  //system("cls");    // Windows  

  for (int i = LINES - 1; i >= 0; --i) {   // zeilenweise
    // Türme in den untersten ANZAHL Zeilen des Bildschirmes
    // Zeilen darüber bleiben komplett leer
    if (i < ANZAHL) {
      // Der Array-Index läuft von unten nach oben
      // ==> unterste Zeile des Bildschirms = Array-Element 0
      scheibe(a[i]);
      scheibe(b[i]);
      scheibe(c[i]);
    }
    putchar('\n');
  }

  // DELAY ms warten
  usleep(DELAY * 1000);  // Linux, aus unistd.h, Argument = Mikrosekunden
  //Sleep(DELAY);          // Windows, aus windows.h, Argument = Millisekunden
}

// Bewege die obenauf liegende Scheibe von Turm "von" nach Turm "nach"
void lege(int von[], int nach[])
{
  int i_von, i_nach;

  // Stelle i_von auf den Index der obersten Scheibe in "von":
  // Zähle von oben runter, bis eine Scheibe kommt
  for (i_von = ANZAHL - 1; von[i_von] == 0; --i_von) { }
  // Stelle i_nach auf den Index des untersten freien Platzes in "nach":
  // Zähle von unten rauf, bis keine Scheibe mehr da ist
  for (i_nach = 0; nach[i_nach] != 0; ++i_nach) { }
  // lege die Scheibe um (und lösche sie am alten Platz)
  nach[i_nach] = von[i_von];
  von[i_von] = 0;

  // gib den Zug aus
  ausgabe();
}

// Die zentrale rekursive Lösungsfunktion:
// Bewege "anzahl" Scheiben von Turm "von" auf Turm "nach"
// Verwende Turm "zwischen" als Zwischenablage
void bewege(int anzahl, int von[], int nach[], int zwischen[])
{
  if (anzahl == 0) return;  // nichts zu bewegen
  // Bewege alle Scheiben außer der untersten auf den Zwischen-Turm
  bewege(anzahl - 1, von, zwischen, nach);
  // Bewege die unterste, jetzt obenauf liegende Scheibe auf den Ziel-Turm
  lege(von, nach);
  // Lege die auf den Zwischen-Turm gelegten Scheiben
  // auf die unterste Scheibe am Ziel-Turm
  bewege(anzahl - 1, zwischen, nach, von);
}

int main(void)
{
  // a, b, c sind global, daher sind zu Programmstart alle Werte automatisch 0
  // Am Anfang liegen alle Scheiben auf Turm a, größte Scheibe in a[0]
  for (int i = 0; i < ANZAHL; ++i) {
    a[i] = ANZAHL - i;
  }
  ausgabe();

  bewege(ANZAHL, a, b, c);  // Bewege ANZAHL Scheiben von a nach b
  
  exit(EXIT_SUCCESS);
}
