/**
 * 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_14_GetAlgnment {

    // Rückverweise rekonstruieren statt speichern (speichereffizienter)
    static func getAlignment(_ a: String, _ b: String) -> [(Character, Character)] {
        let n = a.count
        let m = b.count
        let aa = Array(a)
        let bb = Array(b)

        var Tab: [[Int]] = Array(repeating: Array(repeating: 0, count: m+1), count: n+1)

        for i in 0 ... n {
            for j in 0 ... m {
                switch (i, j) {
                case (0, _) :
                    Tab[i][j] = j
                case (_, 0) :
                    Tab[i][j] = i
                case (_, _) :
                    Tab[i][j] = min(
                        Tab[i - 1][j - 1] + ((aa[i-1] != bb[j-1]) ? 1 : 0),
                        Tab[i - 1][j] + 1,
                        Tab[i][j - 1] + 1
                    )
                }
            }
        }

        var i = n
        var j = m
        var A: [(Character, Character)] = []

        // Rückverweise rekonstruieren
        while (i > 0 || j > 0) {
            if i == 0 {
                A.insert( (Character("-"), bb[j-1]), at:0)
                j = j-1
            } else if j == 0 {
                A.insert((aa[j-1], Character("-")), at:0)
                i = i - 1
            } else {
                let D = Tab[i-1][j-1] + ((aa[i-1] != bb[j-1]) ? 1 : 0 )
                let V = Tab[i-1][j]
                let H = Tab[i][j-1]
                if D == Tab[i][j] {
                    A.insert((aa[i-1], bb[j-1]), at: 0)
                    i = i - 1
                    j = j - 1
                } else if V == Tab[i][j] {
                    A.insert((aa[i-1], Character("-")), at: 0)
                    i = i - 1
                } else if H == Tab[i][j] {
                    A.insert((Character("-"), bb[j-1]), at: 0)
                    j = j - 1
                }
            }
        }

        return A
    }


    // Rueckverweise als Bestandteil der Tabelle (einfacher)
    static func alignIter(_ x: String, _ y: String) -> [(Character, Character)] {

        func countDiffs(_ l: [(Character, Character)]) -> Int {
            l.filter({ (pair: (Character, Character)) in pair.0 != pair.1}).count
        }

        let X = Array(x)
        let Y = Array(y)
        var align : [[[(Character, Character)]]] = Array(
            repeating: Array(repeating: [] as [(Character, Character)], count: y.count),
            count: x.count)

        for n in 0 ... X.count {
            for m in 0 ... Y.count {
                switch (n, m) {
                case (_, 0) :
                    align[n][m] = (0 ..< n).map( { (i) in (X[i], Character("_")) } )
                case (0, _) :
                    align[n][m] = (0 ..< m).map( { (i) in (Character("_"), Y[i]) } )
                case (let i, let j) :
                    align[n][m] = [
                        align[i - 1][j - 1] + [(X[i - 1], Y[j - 1])],
                        align[i - 1][j] + [(X[i - 1], Character("-"))],
                        align[i][j - 1] + [(Character("-"), Y[j - 1])]
                    ].min(
                        by: { (l1:[(Character, Character)], l2: [(Character, Character)]) in
                            countDiffs(l1) < countDiffs(l2) })!
                }
            }
        }

        return align[X.count][Y.count]
    }

    static func run () {
        let a1 = getAlignment("LIEBEN", "FLIEGEN")
        print(a1.map({ p in String(p.0)}).joined(separator: " "))
        print(a1.map({ p in String(p.1)}).joined(separator: " "))
        print()
        let a2 = alignIter("LIEBEN", "FLIEGEN")
        print(a2.map({ p in String(p.0)}).joined(separator: " "))
        print(a2.map({ p in String(p.1)}).joined(separator: " "))
    }

}