package kapitel_11

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 11, Probleme totschlagen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_11_04_RecursiveLoopGeneration_App extends App {

  def Ok(board: List[Int]): Boolean =
    (for (i <- 0 until board.length;
          j <- i+1 until board.length
          ) yield {
      val x = board(i)
      val y = board(j)
      val d = j-i
      ! (x == y || y == x-d || y == x+d)
    }).find( _ == false)
      .getOrElse(true)


 /*
 * Pseudocode mit Code-Ellipsen (Pünktchen, oder syntaktsche Schleifen)
 * kann nicht direkt in Code umgewandelt werden, die Anweisungen an den Codierer sind.
 * Die Pübktchen sind Anweisungen an den Codierer. Sie können aber auf unterschiedliche Arten als Anweisungen an die
 * Maschine formuliert. Beispielsweise so:
 */


  def NQueens(n: Int): List[Int] = {
    @tailrec
    def loopGen(count: Int, limit: Int, acc: List[List[Int]]): Option[List[Int]] = {
      if (count == 0) {
        acc.find(Ok)
      } else {
        loopGen(
          count-1,
          limit,
          for (
            l <- acc;
            x <- 0 until limit
          ) yield l ++ List(x)
        )
      }
    }

    loopGen(n, n, List(Nil)).getOrElse( throw new NoSuchElementException )
  }

  /*
   * Hier haben wir einen For-Ausdruck als Argument eines rekursiven Aufrufs. Wen das zu funktional ist,
   * der kann es auch auseinander ziehen:
   */

  def QueensNI(n: Int): List[Int] = {

    var acc: List[List[Int]] = Nil

    // NICHT @tailrec !!!
    def Loops(count: Int, limit: Int, board: List[Int]): Unit = {
      if (count == 0) {
        if (Ok(board)) { acc = acc ++ List(board) }
      } else {
        for (x <- 0 until limit) {
          Loops(count-1, limit, board ++ List(x))
        }
      }
    }

    Loops(n, n, Nil)
    acc.headOption.getOrElse( throw new NoSuchElementException )
  }

  for (nq <- List(NQueens _, QueensNI _)) { /*_: eta-Expansion, Konversion methode => Funktion */
    for (n <- 2 to 8) try {
      print(s"$n Damen ")
      println(s"sind verträglich an den Positionen ${nq(n).mkString(", ")} ")
    } catch {
      case _: NoSuchElementException => println("können nicht friedvoll arrangiert werden")
    }
    println()
  }

}