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

struct AuD_11_10_MazeBranchAndBoundImp {

    struct Edge: Equatable {
        let s: Int
        let d: Int
        init (_ s: Int, _ d: Int) {
            self.s = s
            self.d = d
        }
    }

    static let V = (0 ... 45)

    // Der Irrgarten aus Kapitel 11
    static let E1: [(Int, Int)] = [
        (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),
        // Zykel:
        (8, 19),
        // Abkuerzung:
        (9, 10)]

    // reflexiver Abschluss
    static let E = E1.flatMap ( { (s,d) in [Edge(s, d), Edge(d,s)]} )

    static let start = 0
    static let dest = 45


    static func MazeBTImp(_ start: Int, _ dest: Int) -> [Int] {
        var path : [Int] = []
        var bestPath: [Int] = []
        var bestLength = Int.max

        path.append(start)

        func solve () {
            if path.last == dest {
                if path.count < bestLength {
                    bestPath = path
                    bestLength = bestPath.count
                }
            } else {
                for x in V {
                    if !path.contains(x) && E.contains(Edge(path.last!, x)) {
                        if path.count <= bestLength {
                            path.append(x)
                            solve()
                            path.removeLast()
                        }
                    }
                }
            }
        }

        solve()
        return bestPath
    }

    /* Ausgabe des besten Wegs vom Start zum Ziel */
    static func run() {
        print(
            MazeBTImp(start, dest)
                .map({ (i: Int) in String(i) })
                .joined(separator: ", ")
        )
    }
}