/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 13, Dynamisches Programmieren
 *
 * @author A. Gogol-Döring, Th. Letschert
 */


import Foundation

struct AuD_13_12_NeedlemanWunsch {

    /*
     * Der NeedlemanWunsch-Algorithmus tabelliert die align-Funktion:
     */
    static func NeedlemanWunsch_V1(_ a: [Character], _ b: [Character]) -> Int {
        let n = a.count
        let m = b.count
        var Tab: [[Int]] = Array(repeating: Array(repeating: -1, count: m+1), count: n+1)

        for j in 0 ...  m {
            Tab[0][j] = j
        }

        for i in 1 ... n {
            Tab[i][0] = i
            for j in 1 ... m {
                var D = Tab[i - 1][j - 1]
                if a[i-1] != b[j-1] {
                    D = D + 1
                }
                let V = Tab[i - 1][j] + 1
                let H = Tab[i][j - 1] + 1
                Tab[i][j] = min(D, V, H)
            }
        }
        return Tab[n][m]
    }

    static func run() {
        let a = NeedlemanWunsch_V1(Array("LIEBEN"), Array("FLIEGE"))
        print(a) // 3
    }

}