package kapitel_11

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

import scala.collection.mutable.ListBuffer

object AuD_11_10_MazeBranchAndBoundImp_App extends App {
  val V : List[Int] = (0 to 45).toList

  val E1: List[(Int, Int)] =
    List(
      (0,1),
      (1,3), (4,5), (6,7),
      (3, 9), (4, 10), (5,13), (6,14), (7,17),
      (8,9), (10,11), (13,14), (16,17),
      (1,18), (11,22), (14, 25),
      (18, 19), (20,21), (22,24), (25,26),
      (19, 29), (20,30), (22,32), (24,33), (16, 36), (27, 37),
      (28, 29), (29,30), (31,32), (33,34), (35,36), (36,37),
      (28, 38), (31,39), (32,40), (35,43),
      (38, 39), (40, 41), (42,43), (43, 44),
      (44,45),
      // Zylkel:
      (8, 19),
      // Abkuerzng
      (9, 10)
    )

  val E = E1.flatMap {
    case (s,d) => List((s, d), (d,s))
  }

  val start = 0
  val dest = 45

  def MazeBBImp(start: Int, dest: Int): List[Int] = {
    var bestPath: List[Int] = Nil
    var bestLength = Int.MaxValue
    val path : ListBuffer[Int] = new ListBuffer[Int]

    path.append(start)

    def solve(): Unit = {
      if (path.last == dest && path.toList.length < bestLength) {
        bestPath = path.toList
        bestLength = bestPath.length
      } else {
        for (x <- V // branch
             if !path.contains(x) && E.contains((path.last, x))) {
          if (path.toList.length <= bestLength) { // bound
            path += x
            solve()
            path.trimEnd(1)
          }
        }
      }
    }

    solve()

    bestPath
  }

  println(MazeBBImp(start, dest).mkString(","))

}