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

    /**
     * Editierdistanz mit (rekursivem) Teilen und Herrschen
     *
     * Die Editierdistanz von zwei Strings ist die minimale Anzahl an Editieroperationen die benötigt werden, um einen
     * swe beiden Strings in einen andern zu transformieren.  Die erlaubten Editieroperationen sind dabei:
     *
     *   - Einfügen eines Zeichens
     *   - Löschen eines Zeichens
     *   - Ersetzen eines Zeichens
     *
     * Eine rekursive Definition der Editierdistanz d(x, y) von zwei Strings
     * der Länge |x| = n und |y| = m beruht auf folgender Beobachtung:
     *
     *   - Ein String x in einen leeren String zu transformieren erfordert |x| (Lösch-) Operationen.
     *   - Den leeren String in einen String x zu transformieren erfordert x (Einfüge-) Operationen.
     *   - Bei längeren Strings müssen wir prüfen was weniger Operationen erfordert:
     *
     *     - Löschung des letzten Zeichens von x, oder
     *     - Löschung des letzten Zeichens von y, oder
     *     - Ersetzen des letzten Zeichens von x durch das letzte Zeichen von y,
     *       falls sie sich unterscheiden, ansonsten mache nichts am Ende von x und y
     *     und dann den Anfang von x in den Anfang von y transformieren.
     *
     * Statt am Ende können die Operationen genauso gut am Anfang der Strings ausgeführt werden:
     */

    static func d(_ x: [Character], _ y: [Character]) -> Int {
        switch (x, y) {
        case (_, []):
            return x.count
        case ([], _):
            return y.count
        default :
            let a = x[0]
            let tail_x = Array(x.dropFirst())
            let b = y[0]
            let tail_y = Array(y.dropFirst())
            return min(
                d(x, tail_y)+1,
                d(tail_x, y)+1,
                d(tail_x, tail_y) + ((a == b) ? 0 : 1))

        }
    }

    /*
     * Mit ein wenig Buchhaltung kann man auch die notwendigen Operationen aufzeichnen:
     */

    enum EditOp : CustomStringConvertible {
        case Delete(_ c: Character)
        case Insert(_ c: Character)
        case Replace(_ c1: Character, _ c2: Character)

        var description : String {
            switch self {
            case .Delete(let c): return "Delete(\(c))"
            case .Insert(let c): return "Insert(\(c))"
            case .Replace(let c1, let c2): return "Replace(\(c1), \(c2))"
            }
        }
    }

    static func dS(_ x: [Character], _ y: [Character]) -> [EditOp] {
        switch (x, y) {
        case (_, []):
            return x.map({ (c: Character) in .Delete(c)})
        case ([], _):
            return y.map({ (c: Character) in .Insert(c)})
        default :
            let a = x[0]
            let tail_x = Array(x.dropFirst())
            let b = y[0]
            let tail_y = Array(y.dropFirst())
            return [
                [.Insert(b)] + dS(x, tail_y),
                [.Delete(a)] + dS(tail_x, y),
                (a == b) ? dS(tail_x, tail_y) : [.Replace(a, b)] + dS(tail_x, tail_y)
            ].min(by: { (l1, l2) in l1.count < l2.count } )!
        }
    }


    /*
     * Statt am vorderen Ende (wie in d oben) können die Strings genauso gut am hinteren Ende reduziert werden.
     * Wie haben das oben nicht gemacht, weil  Listen sich leichter am vorderen Ende bearbeiten lassen.
     * Gehen wir wieder zurück ans hintere Ende.
     *
     * In Definition von d
     * d(x, y) &= min(
     *   d(x_0 ... x_{n-2}), y) +1
     *   d(x, y_0 ... y_{m-2}) +1
     *   d(x_0 ... x_{n-2}, y_0 ... y_{m-2}) falls x_(n-1) = y_(m-1)
     *   d(x_0 ... x_{n-2}, y_0 ... y_{m-2}) falls x_(n-1) != y_(m-1)
     *
     * sehen wir, dass nur das letzte Zeichen der Strings (x_(n-1) und x_(m-1), n = |x|, m = |y|)
     * relevant ist.
     * Statt die Strings von Aufruf zu Aufruf herum zu reichen und am Ende zu kürzen, reicht es
     * allein mit der Länge (Position des letzten Zeichens) zu arbeiten:
     */
    static func dI(_ x: [Character], _ y: [Character]) -> Int {

        func d(_ n: Int, _ m: Int) -> Int {
            switch (n, m) {
            case (let i, 0):
                return i
            case (0, let j):
                return j
            case (let i, let j) :
                return min(
                    d(i, j-1)+1,
                    d(i-1, j)+1,
                    d(i-1, j-1) + (x[i-1] == y[j-1] ? 0 : 1))
            }
        }

        return d(x.count, y.count)
    }

    static func run() {
        print(d(Array("fenestra"), Array("fenster"))) // 3
        print(dS(Array("fenestra"), Array("fenster"))) // [Delete(e), Insert(e), Delete(a)]
        print(dI(Array("fenestra"), Array("fenster"))) // 3
    }

}