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

import Foundation

struct AuD_08_02_KnapsackBruteForce {

    /*
     * Im Pseudocode wird eine Menge und ihre Teilmengen verwendet. Das ist
     * wieder nicht so zu verstehen, dass im Code mit dem Typ Set gearbeitet werden soll.
     * Es handelt sich um eine Menge von Elementen, die in irgendeiner Datstruktur stecken.
     * Wir nehmen eine Liste als Datenstruktur.
     *
     * Die Menge aller Teilmengen einer Menge M mit |M| Elementen können wir finden, indem wir alle
     * Kombinationen von 0 und 1 der Länge |M| als Auswahlfunktion auf M anwenden.
     * Die Kombinationen können bei bekannter Länge mit geschachtelten for-Schleifen gefunden werden.
     * Bei unbekannte Länge können die Schleifen rekursiv erzeugt werden:
     */

    static func AllSubListsViaBitSequence<A>(lst: [A]) -> [[A]] {

        func bitSeqOfLength(n: Int) -> [[Int]] {
            n == 0 ? [[]] :
                bitSeqOfLength(n: n-1).flatMap( {
                    s -> [[Int]] in [[0] + s] + [[1] + s]
                } )
        }

        func allSubLists(lst: [A]) -> [[A]] {
            bitSeqOfLength(n: lst.count).map { (selection: [Int]) in
                let zippedWithIndex: [(A, Int)] =  Array(zip(lst, Array(0 ..< lst.count)))
                return zippedWithIndex.flatMap {
                    (itemIndex: (A, Int)) -> [A] in
                    let item = itemIndex.0
                    let index = itemIndex.1
                    return (selection[index] == 0) ? [] : [item] }
            }
        }

        return allSubLists(lst: lst)
    }


    /*
     * Es ist nicht notwendig die Folgen von  Nullen und Einsen zu bilden.
     * Man kann auch gleich die Liste der Möglichkeiten auch erzeugen:
     */
    static func AllSubLists<A>(lst: [A]) -> [[A]] {
        lst.count == 0 ? [[]] :
            AllSubLists(lst: Array(lst.dropFirst())).flatMap( {
                s -> [[A]] in [s] + [[lst[0]] + s]
            } )
    }

    struct Item : Comparable, CustomStringConvertible {
        let name : String
        let gewicht: Int
        let wert: Int
        var attraktion: Double {
            Double(wert) / Double(gewicht)
        }
        static func > (lhs: Item, rhs: Item) -> Bool {
            lhs.attraktion > rhs.attraktion
        }
        static func < (lhs: Item, rhs: Item) -> Bool {
            lhs.attraktion < rhs.attraktion
        }
        var description: String {
            "(\(name), \(gewicht), \(wert))"
        }
    }

    static func KnapsackBruteForce(M: [Item], T: Int) -> [Item] {
        var S_opt: [Item] = []
        var w_opt = 0
        for s in AllSubLists(lst: M) {
            let w = s.map( { i in i.wert }  ).reduce(0, +)
            let g = s.map( { i in i.gewicht } ).reduce(0, +)
            if ((g <= T) && (w > w_opt)) {
                S_opt = s
                w_opt = w
            }
        }
        return S_opt
    }


    static func run() {
        let items1: [Item] = [Item(name: "A", gewicht: 7, wert: 42), Item(name: "B", gewicht: 3, wert: 12), Item(name: "C", gewicht: 4, wert: 40), Item(name: "D", gewicht: 5, wert: 25)]
        let items2: [Item] = [Item( name: "Goldkorn", gewicht: 1, wert: 10), Item(name: "Silberbarren", gewicht: 200, wert: 500)]
        let items3: [Item] = [Item(name: "Computer", gewicht: 3, wert: 300), Item(name: "TV", gewicht: 12, wert: 200), Item(name: "Uhr", gewicht: 10, wert: 150), Item(name: "Vase", gewicht: 7, wert: 100)]

        let selection1 = KnapsackBruteForce(M: items1, T: 10)
        let selection2 = KnapsackBruteForce(M: items2, T: 200)
        let selection3 = KnapsackBruteForce(M: items3, T: 20)

        print(selection1.map( { i in i.description } ).joined(separator: ", ") )
        print(selection2.map( { i in i.description } ).joined(separator: ", ") )
        print(selection3.map( { i in i.description } ).joined(separator: ", ") )
    }

}