package kapitel_13

import scala.annotation.tailrec

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

object AuD_13_10_EditDistanceDivideConquer_App extends App {

  /**
   * Editierdistanz mit (rekursiv) Teilen und Herrschen
   *
   * Die Editierdistanz von zwei Strings ist die minimale Anzahl an Editieroperationen die benötigt werden, um einen
   * einen String 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. Das macht es leicht
   * die Editierdistanz von Listen zu berechnen:
   */

  def d(x: List[Char], y: List[Char]): Int = (x, y) match {
    case (_, Nil) => x.length
    case (Nil, _) => y.length
    case (a :: tail_x, b :: tail_y) => List(
      d(x, tail_y)+1,
      d(tail_x, y)+1,
      d(tail_x, tail_y) + (if (a == b) 0 else 1)
    ).min
  }

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

  sealed abstract class EditOp
  case class Delete(c: Char) extends EditOp
  case class Insert(c: Char) extends EditOp
  case class Replace(c1: Char, c2: Char) extends EditOp

  def dS(x: List[Char], y: List[Char]): List[EditOp] = (x, y) match {
    case (_, Nil) => x.map(Delete)
    case (Nil, _) => y.map(Insert)
    case (a :: tail_x, b :: tail_y) => List(
      Insert(b) :: dS(x, tail_y),
      Delete(a) :: dS(tail_x, y),
      if (a == b) dS(tail_x, tail_y) else Replace(a, b) :: dS(tail_x, tail_y)
    ).minBy( x => x.length )
  }

  /*
   * Statt am vorderen Ende 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 der letzte Zeichen der Strings (x_(n-1) und x_(m-1), n = |x|, m = |y|)
   * relevant ist.
   * Statt die Strings herum zu schleifen und am Ende zu kürzen, reicht es allein mit der Länge zu arbeiten:
   */

  def dI(x: String, y: String): Int = {

    def d(n: Int, m: Int): Int = (n, m) match {
      case (i, 0) => i
      case (0, j) => j
      case (i, j) => List(
        d(i, j-1)+1,
        d(i-1, j)+1,
        if (x(i-1) == y(j-1))
          d(i-1, j-1)
        else d(i-1, j-1)+1
      ).min
    }

    d(x.length, y.length)
  }

  println(d("fenestra".toList, "fenster".toList)) // 3

  println(dS("fenestra".toList, "fenster".toList).mkString(", ")) // Delete(e), Insert(e), Delete(a)

  println(dI("fenestra", "fenster")) // 3

}