Hw2Task1.kt

class Node<T>(val value: T,
              val children: Map<T, Node<T>>)

fun <T> buildTree(initialState: T, childrenProducer: (T) -> Set<T>): Node<T> = Node(
        initialState,
        childrenProducer(initialState).associateBy({ it }, { buildTree(it, childrenProducer) })
)

fun <T> List<T>.withoutItemAt(index: Int) = take(index) + drop(index + 1)

fun <T, R> Node<T>.mapChoose(mapper: (Node<T>) -> R, chooser: (Set<R>) -> R) =
        children.values
                .map(mapper).toSet()
                .let(chooser)

fun <T, R> Node<T>.cascadeChoose(bottomMapper: (Node<T>) -> R, choosers: List<(Set<R>) -> R>): R {
    fun recurse(node: Node<T>, index: Int): R = when {
        index > choosers.lastIndex -> bottomMapper(node)
        else -> node.mapChoose({ recurse(it, index + 1) }, choosers[index])
    }
    return recurse(this, 0)
}

fun <T> choosesByPreference(preference: List<T>): (Set<T>) -> T = { it.minBy { preference.indexOf(it) }!! }
fun <T> choosesByPreference(vararg preference: T): (Set<T>) -> T = choosesByPreference(preference.toList())

fun <T> allPermutations(items: Set<T>): List<List<T>> = when {
    items.size == 1 -> listOf(listOf(items.single()))
    else -> items.flatMap { i -> allPermutations(items - i).map { tail -> listOf(i) + tail } }
}

fun main(args: Array<String>) {
    val options = listOf("A", "B", "C", "D")
    val gameTree = buildTree(
            options,
            { list -> if (list.size == 1) emptySet() else list.indices.map { list.withoutItemAt(it) }.toSet() })

    val allPerms = allPermutations(setOf("A", "B", "C", "D"))
    val keyDroppingA = listOf("B", "C", "D")
    allPerms.flatMap { p2 ->
        allPerms.map { p3 ->
            val result = gameTree.children.map {
                val (k, v) = it
                k to v.cascadeChoose({ it.value.single() }, listOf(choosesByPreference(p2), choosesByPreference(p3)))
            }.toMap()
            println("p2: $p2; p3: $p3; result: ${result.values}")
            val valueDroppingA = result[keyDroppingA]!!
            if (result.all { it.key == keyDroppingA || it.value > valueDroppingA }) {
                println("Found.")
                return
            }
        }
    }
}