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

    static func Ok(_ board: [Int]) -> Bool {
        for i in 0 ..< board.count {
            for j in i + 1 ..< board.count {
                let x = board[i]
                let y = board[j]
                let d = j - i
                if (x == y || y == x - d || y == x + d) {
                    return false
                }
            }
        }
        return true
    }


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

    static func NQueens(_ n: Int) -> [Int] {

        func loopGen(_ count: Int, _ limit: Int, _ acc: [[Int]]) -> [Int]? {
            if (count == 0) {
                return acc.filter( { (board) in Ok(board)  } ).first
            } else {
                return loopGen(
                    count-1,
                    limit,
                    acc.flatMap( { (l) in (0 ..< limit).map( { (x) in l + [x] } ) } )
                )
            }
        }

        return loopGen(n, n, [[]]) ?? []
    }

    /*
     * Oben haben wir einen For-Ausdruck als Argument eines rekursiven Aufrufs. Wen das zu funktional ist,
     * der kann es auch auseinander ziehen:
     */
    static func QueensNI(n: Int) -> [Int] {
        var acc: [[Int]] = []

        func Loops(_ count: Int, _ limit: Int, _ board: [Int]) {
            if count == 0 {
                if Ok(board) {
                    acc = acc + [board]
                }
            } else {
                for x in 0 ..< limit {
                    Loops(count-1, limit, board + [x])
                }
            }
        }

        Loops(n, n, [])
        return acc.count > 0 ? acc[0] : []
    }


    static func run() {
        for nq in [NQueens, QueensNI] {
            for n in 2 ... 8 {
                print("\(n) Damen")
                print("   sind verträglich an den Positionen \(nq(n).map( { (i) in String(i)} ).joined(separator: ", "))")
            }
            print()
        }
    }

}