"""
Urheber: Jonathan Püttmann 2020
Quelle: www.mengenwertskala.de/informatik/Palindromlaenge.py
Dieses Programm ist freigegeben zur Weiterverwendung und -entwicklung im Sinne der Freie-Software-Bewegung
Bugs und Verbesserungsvorschläge an kontakt@mengenwertskala.de
"""

import numpy as np

wort=input("Wort: ")

while wort!="exit" and wort!="q":
    
    laenge=len(wort)
    matrix=np.zeros([laenge, laenge])
    
    def isPalindrom(wort):
        laenge=len(wort)
        if laenge<=1:
            return True
        if wort[0]==wort[laenge-1]:
            wort=wort[1:laenge-1]
            return isPalindrom(wort)
        else:
            return False
        
    def fillMatrix(wort, matrix):
        for a in range(len(wort)):
            for b in range(len(wort)-a):
                i = b
                j = a+b
                if isPalindrom(wort[i:j+1]):
                    matrix[i][j]=1 
                else:
                    minimum = matrix[i][i] + matrix[i+1][j]
                    for k in range(j-i):
                        minimum = min(minimum, matrix[i][i+k]+matrix[i+k+1][j])
                    matrix[i][j]=minimum
        return matrix
    
    fillMatrix(wort, matrix)
    loesung = str(int(matrix[0][laenge-1]))
    print()
    print("Anzahl Zeichen: "+(str(laenge)))
    print("Palindromlänge: "+loesung)
    print()
    #print(matrix)
    print()
    wort=input("Wort: ")