/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 14, Näherungslösungen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_14_05_SetCovering {

    /*
     * AllSubLists (siehe Kapitel 8)
     */
    static func AllSubLists<A>(_ lst: [A]) -> [[A]] {
        lst.count == 0 ? [[]] :
            AllSubLists(Array(lst.dropFirst())).flatMap( {
                s -> [[A]] in [s] + [[lst[0]] + s]
            } )
    }

    static func foldLeft<T, E>(_ list: [T], _ start: E, _ transform: (E, T) -> E) -> E {
        var result = start
        for item in list {
            result = transform(result, item)
        }
        return result
    }

    static func intersect<A: Equatable>(_ l1: [A], _ l2: [A]) -> [A] {
        foldLeft(l1, [], { (acc, x) in (l2.contains(x) ? (acc + [x]) : acc) })
    }

    static func diff<A: Equatable>(_ l1: [A], _ l2: [A]) -> [A] {
        foldLeft(l1, [], { (acc, x) in (!l2.contains(x) ? (acc + [x]) : acc) })
    }

    static func equalAsSet<A: Equatable>(_ l1: [A], _ l2: [A]) -> Bool {
        l1.count == l2.count && diff(l1, l2) == []
    }

    /*
     * SetCoveing brute force mit AllSubLists
     * bestimme die kleinste Teilliste von S die R abdeckt
     */
    static func SetCovering<A: Equatable>(_ S: [[A]], // Teilmengen von R
                                          _ R: [A]) -> [[A]] {
        var result: [[A]] = []
        var count = Int.max

        for t in AllSubLists(S) {
            let join = foldLeft(t, [], { (acc, s) in acc + s } )
            if ( equalAsSet(join, R) && t.count < count) {
                count = t.count
                result = t
            }
        }
        return result
    }

    /*
     * Etwas effizienter ist die gierige Lösung:
     */
    static func SetCoveringG<A: Equatable>(_ S: [[A]], // Teilmengen von R
                                           _ R: [A]) -> [[A]] {
        var result: [[A]] = []
        var notCovered = R
        var sRemaining = S

        while (notCovered.count > 0) {
            let u: [([A], Int)] =
                sRemaining.filter( { l in l.count != 0} )
                    .map( { (s) in (s, intersect(notCovered, s).count) } )
            let s : [A] = u.max(by: { (p1, p2) in p1.1 < p2.1 })!.0
            notCovered = diff(notCovered, s)
            sRemaining = diff(sRemaining, [s])
            result = [s] + result
        }

        return result
    }

    static let R : [Int] = [0,1,2,3,4,5,6,7,8,9]
    static let S: [[Int]] = [
        [0,1,2,3,4,7,8],
        [6,7],
        [9],
        [5],
        [3,4,5,6]]

    static func run() {
        print(SetCovering(S, R))
        print(SetCoveringG(S, R))
    }
}