#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# getestet mit Python 2.7.8 und 3.4.2
'''Generiert oder löst Alphametiken'''
# Nicht als root ausführen.
# Die Ausführung dauert bis zu zwei Minuten, abhängig von der Länge des
# Alphametiks. Die Generierung dauert unter Umständen 5 Minuten oder länger.

# Programm löst das Alphametik "SUCHEN-MACHT=SPASS"
# und generiert eines mit einem Rechenzeichen

import re, random

ALPHAMETIK = "SUCHEN-MACHT=SPASS"

ZAHLEN = ["EINS", "ZWEI", "DREI", "VIER", "FÜNF", \
 "SECHS", "SIEBEN", "ACHT", "NEUN", "ZEHN"]
#RECHENZEICHEN = ["+", "-", "*", "/"]
RECHENZEICHEN = ["+", "-"] # schneller

def buchstaben_liste(wort):
    '''Erstellt eine Liste der Buchstaben'''
    buchstaben = []
    for char in wort:
        if (char not in RECHENZEICHEN) \
            and (char not in buchstaben) \
            and (char not in " ="):

            buchstaben.append(char)

    return buchstaben

def ersetze(buchst, wort, \
    benutzte_zahlen=None, loesungen=None, alle_buchstaben=None):
    '''Ersetzt einen Buchstaben aus `buchst` in einem Wort `wort` \
nacheinander durch `0-9` und ruft sich selbst auf. \
Ist `buchst` leer, wird das Alphametik auf Richtigkeit getestet
und ggf. zu `loesungen` hinzugefügt. \
Zurückgegeben wird eine Liste mit Lösungen. \
Element der Liste ist der Rechnungsstring und ein dict.'''

    if alle_buchstaben == None:
        alle_buchstaben = buchst
    if benutzte_zahlen == None:
        benutzte_zahlen = []
    if loesungen == None:
        loesungen = []

    if len(buchst):
        for j in range(10):
            if j in benutzte_zahlen: # jede Zahl nur einmal verwenden
                continue

            m_benutzte_zahlen = benutzte_zahlen[:]
            m_benutzte_zahlen.append(j)

            m_wort = wort.replace(buchst[0], str(j))
            ersetze(buchst[1:], m_wort, m_benutzte_zahlen, \
                loesungen, alle_buchstaben)
    else:
        if re.search(r"\b0", wort):
            # 0 als erste Ziffer in einer Zahl ist nicht erlaubt
            return

        if eval(wort.replace("=", "==")):
            lsg = [wort, dict()]
            for j, k in zip(alle_buchstaben, benutzte_zahlen):
                lsg[1][j] = k

            loesungen.append(lsg)

    return loesungen

def loese(alpham):
    '''kleiner Wrapper, der die Benutzung von `ersetze` vereinfacht'''
    return ersetze(buchstaben_liste(alpham), alpham, None, None, None)

def generiere(laenge=1):
    '''gibt ein zufälliges Alphametik mit `laenge` \
"Ziffern" vor dem Gleichheitszeichen zurück'''
    while True:
        rechnung_ok = False
        while rechnung_ok == False: # sucht nach wahren Gleichungen
            alphametik = "x" + "_x" * laenge + "=y" # Template für Rechnung

            for j in range(laenge + 1): # zufällige Rechenzeichen einsetzen
                alphametik = alphametik.replace("_", \
                    random.choice(RECHENZEICHEN), 1)

            alphametik = alphametik.replace("y", str(random.randrange(1, 9)))
            # Ergebnis

            for j in range(laenge + 2):
                alphametik = alphametik.replace("x", \
                    str(random.randrange(1, 9)), 1)

            rechnung_ok = eval(alphametik.replace("=", "=="))

        # jetzt passende Alphametiken suchen oder weitersuchen
        for j in range(1, 10):
            alphametik = alphametik.replace(str(j), ZAHLEN[j - 1])

        loe = loese(alphametik)
        if len(loe) > 0:
            return alphametik # Geschafft, wir haben eines gefunden!

if __name__ == "__main__":
    LOESUNG = loese(ALPHAMETIK)

    if len(LOESUNG) == 0:
        print("Keine Lösungen vorhanden")
    else:
        print("Es konnten folgende Lösungen gefunden werden:")
        print(LOESUNG)

    print(generiere())