package kapitel_13

/**
 * 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_12_NeedlemanWunsch_App extends App {

  /*
   * Der NeedlemanWunsch-Algorithmus tabelliert die align-Funktion:
   */
  def NeedlemanWunsch_V1(a: Array[Char], b: Array[Char]): Int = {
    val n = a.length
    val m = b.length
    val Tab = Array.ofDim[Int](n+1, m+1)

    for (j <- 0 to  m)
      Tab(0)(j)  =  j

    for (i <- 1 to  n) {
      Tab(i)(0) = i
      for (j <- 1 to m) {
        var D = Tab(i - 1)(j - 1)
        if (a(i-1) != b(j-1)) {
          D = D + 1
        }
        val V = Tab(i - 1)(j) + 1
        val H = Tab(i)(j - 1) + 1
        Tab(i)(j) = List(D, V, H).min
      }
    }
    Tab(n)(m)
  }

  // oder auch mit String-Parametern nur einer Schleife:

  def NeedlemanWunsch_V2(a: String, b: String): Int = {
    val n = a.length
    val m = b.length
    val Tab = Array.ofDim[Int](n+1, m+1)

    for(i <- 0 to n;
        j <- 0 to m) {
      Tab(i)(j) = (i, j) match {
        case (0, _) => j
        case (_, 0) => i
        case (_, _) =>
          List(
            Tab(i - 1)(j - 1) + (if (a(i-1) != b(j-1)) 1 else 0),
            Tab(i - 1)(j) + 1,
            Tab(i)(j - 1) + 1
          ).min
      }
    }
    Tab(n)(m)
  }

  val a1 = NeedlemanWunsch_V1("LIEBEN".toCharArray, "FLIEGE".toCharArray)
  println(a1) // 3

  val a2 = NeedlemanWunsch_V2("LIEBEN", "FLIEGE")
  println(a2) // 3

}