// Lösen von Textsummen-Denksportaufgaben mittels Backtracking (Angabe)
//
// Aufruf: textsumme operand1 operand2 summe
//
// Klaus Kusche

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>

// Maximale Länge der Wörter
#define MAX_WORTLEN 32

// die in der Aufgabe vorkommenden Buchstaben (max. 10, siehe buch_anz)
char buchst[10];

// deren Anzahl
int buch_anz = 0;

// die zum i-ten Buchstaben in buchst gehörige Ziffer
// für noch nicht belegte Buchstaben ist ziffer[i] gleich -1
// ziffer[10] ist 0 (für die führenden Leerzeichen in den Worten),
// das spart ein paar if
int ziffer[11];

// kleinster Wert für den i-ten Buchstaben
// 1 für Buchstaben, die am Anfang eines Wortes stehen (dürfen nicht 0 werden),
// 0 für alle anderen
int anfang[10];

// ist die Ziffer i schon verwendet?
// (damit wir nicht jedesmal "ziffer" komplett durchsuchen müssen)
bool belegt[10];

// die Eingabe-Wörter in interner Darstellung:
// * Buchstaben werden ersetzt durch ihren Index in "buchst" und "ziffer"
//   ==> ziffer[op1[i]] liefert die Ziffer,
//       die für den i-ten Buchstaben des ersten Wortes eingesetzt wurde,
//       oder -1, wenn dem i-ten Buchstaben noch keine Ziffer zugeordnet wurde,
//       oder 0, wenn der i-te Buchstabe ein führendes Leerzeichen ist.
// * alle Wörter gleichlang (wort_len Elemente)
// * rechtsbündig, vorne aufgefüllt mit 10 (für den Zugriff auf ziffer[10])
short int op1[MAX_WORTLEN];
short int op2[MAX_WORTLEN];
short int sum[MAX_WORTLEN];

// Anzahl der Werte in op1, op2 und sum = Länge des längsten Eingabe-Wortes
int wort_len;

// für Fehlermeldungen
const char *prog_name;

int buchstabe(char c);
void eingabe(int argc, const char *argv[]);
bool sinnvoll(void);
bool loesung(int pos);
void print_wort(const short int wort[]);
void ausgabe(void);

int main(int argc, const char *argv[])
{
  prog_name = argv[0];
  
  eingabe(argc, argv);
  
  if (!loesung(0)) {
    printf("Keine Lösung!\n");
  }
  
  exit(EXIT_SUCCESS);
}

// liefert den Index von c in "buchst"
// prüft, ob c gültig ist
// hängt ihn an "buchst" an, wenn er neu ist
int buchstabe(char c)
{
  int i;

  if (!isalpha(c)) {
    fprintf(stderr, "%s: Bitte nur Buchstaben eingeben! (%c?)\n", prog_name, c);
    exit(EXIT_FAILURE);
  }

  for (i = 0; i < buch_anz; ++i) {
    if (buchst[i] == tolower(c)) {
      return i;
    }
  }

  if (buch_anz == 10) {
    fprintf(stderr,
      "%s: Die Eingabe darf maximal 10 verschiedene Buchstaben enthalten\n",
      prog_name);
    exit(EXIT_FAILURE);
  }

  buchst[buch_anz] = tolower(c);
  return buch_anz++;
}

void eingabe(int argc, const char *argv[])
{
  int l1, l2, l3, i;
  
  if (argc != 4) {
    fprintf(stderr, "Aufruf: %s operand1 operand2 summe\n", prog_name);
    exit(EXIT_FAILURE);
  }

  for (i = 0; i < 10; ++i) {
    belegt[i] = false;
    ziffer[i] = -1;
    anfang[i] = 0;
  }
  ziffer[10] = 0;

  l1 = strlen(argv[1]);
  l2 = strlen(argv[2]);
  l3 = strlen(argv[3]);

  wort_len = l1;
  if (l2 > wort_len) wort_len = l2;
  if (l3 > wort_len) wort_len = l3;
  if (wort_len > MAX_WORTLEN) {
    fprintf(stderr, "%s: Maximale Wortlänge %d\n", prog_name, MAX_WORTLEN);
    exit(EXIT_FAILURE);
  }
  if ((l1 == 0) || (l2 == 0) || (l3 == 0)) {
    fprintf(stderr, "%s: Bitte keine leeren Worte\n", prog_name);
    exit(EXIT_FAILURE);
  }

  // man kommt am schnellsten zu Ergebnissen,
  // wenn man die Zeichen der Eingabeworte
  // in buchst spaltenweise von hinten nach vorne speichert!
  // ==> Backtracking löst hinterste Spalte zuerst, dann zweit-hinterste, ...
  for ( i = wort_len - 1; i >= 0; --i) {
    op1[i] = (i < wort_len - l1) ? 10 : buchstabe(argv[1][i - (wort_len - l1)]); 
    op2[i] = (i < wort_len - l2) ? 10 : buchstabe(argv[2][i - (wort_len - l2)]); 
    sum[i] = (i < wort_len - l3) ? 10 : buchstabe(argv[3][i - (wort_len - l3)]); 
  }

  // die vordersten Buchstaben jedes Wortes dürfen nicht mit 0 belegt werden
  anfang[buchstabe(argv[1][0])] = 1;
  anfang[buchstabe(argv[2][0])] = 1;
  anfang[buchstabe(argv[3][0])] = 1;
}

// können die bisher in "ziffer" gespeicherten Ziffern noch eine Lösung ergeben?
// "false" wenn jetzt schon ein Rechenfehler in der Lösung ist, "true" sonst
// einfachere Variante: Prüft nur bis zur ersten Spalte,
// die noch unbekannte Werte enthält
bool sinnvoll(void)
{
  //// schreiben!
}

// löse ab dem Buchstaben mit Index "pos" in den Arrays buchst und ziffer
// wenn pos schon buch_anz ist (alle Buchstaben belegt): ausgabe() aufrufen!
// jede Ebene der Rekursion löst *einen* Buchstaben, nämlich buchst[pos]
// d.h. belegt das Element ziffer[pos] mit der zu buchst[pos] gehörenden Ziffer
//      und markiert die gewählte Ziffer im Array belegt als belegt
// Returnwert: true ... Lösung gefunden, false ... Keine Lösung
//             (brauchen wir für die Ausgabe "Keine Lösung!" im main)
bool loesung(int pos)
{
  //// schreiben!
}

// gib die dem Wort (op1, op2, sum) entsprechende Ziffernfolge aus
void print_wort(const short int wort[])
{
  int i;

  for (i = 0; i < wort_len; ++i) {
    if (wort[i] == 10) putchar(' ');
    else putchar('0' + ziffer[wort[i]]);
  }
  putchar('\n');
}

void ausgabe(void)
{
  int i;

  for (i = 0; i < buch_anz; ++i) {
    printf("%c=%d%s", buchst[i], ziffer[i], (i == buch_anz - 1) ? "\n" : ", ");
  }
  print_wort(op1);
  print_wort(op2);
  print_wort(sum);
  putchar('\n');
}