106 lines
4.3 KiB
Kotlin
106 lines
4.3 KiB
Kotlin
data class Person(val name: String) {
|
|
val preferences = mutableListOf<Person>()
|
|
var matchedTo: Person? = null
|
|
|
|
fun trySwap(p: Person) {
|
|
if (prefers(p)) {
|
|
matchedTo?.matchedTo = null
|
|
matchedTo = p
|
|
p.matchedTo = this
|
|
}
|
|
}
|
|
|
|
fun prefers(p: Person) = when (matchedTo) {
|
|
null -> true
|
|
else -> preferences.indexOf(p) < preferences.indexOf(matchedTo!!)
|
|
}
|
|
|
|
fun showMatch() = "$name <=> ${matchedTo?.name}"
|
|
}
|
|
|
|
fun match(males: Collection<Person>) {
|
|
while (males.find { it.matchedTo == null }?.also { match(it) } != null) {
|
|
}
|
|
}
|
|
|
|
fun match(male: Person) {
|
|
while (male.matchedTo == null) {
|
|
male.preferences.removeAt(0).trySwap(male)
|
|
}
|
|
}
|
|
|
|
fun isStableMatch(males: Collection<Person>, females: Collection<Person>): Boolean {
|
|
return males.all { isStableMatch(it, females) }
|
|
}
|
|
|
|
fun isStableMatch(male: Person, females: Collection<Person>): Boolean {
|
|
|
|
val likesBetter = females.filter { !male.preferences.contains(it) }
|
|
val stable = !likesBetter.any { it.prefers(male) }
|
|
|
|
if (!stable) {
|
|
println("#### Unstable pair: ${male.showMatch()}")
|
|
}
|
|
return stable
|
|
}
|
|
|
|
|
|
fun main(args: Array<String>) {
|
|
val inMales = mapOf(
|
|
"abe" to mutableListOf("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
|
|
"bob" to mutableListOf("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
|
|
"col" to mutableListOf("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
|
|
"dan" to mutableListOf("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"),
|
|
"ed" to mutableListOf("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"),
|
|
"fred" to mutableListOf("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"),
|
|
"gav" to mutableListOf("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"),
|
|
"hal" to mutableListOf("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"),
|
|
"ian" to mutableListOf("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
|
|
"jon" to mutableListOf("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"))
|
|
|
|
val inFemales = mapOf(
|
|
"abi" to listOf("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
|
|
"bea" to listOf("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
|
|
"cath" to listOf("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
|
|
"dee" to listOf("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"),
|
|
"eve" to listOf("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"),
|
|
"fay" to listOf("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"),
|
|
"gay" to listOf("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"),
|
|
"hope" to listOf("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"),
|
|
"ivy" to listOf("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
|
|
"jan" to listOf("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"))
|
|
|
|
|
|
fun buildPrefs(person: Person, stringPrefs: List<String>, population: List<Person>) {
|
|
person.preferences.addAll(
|
|
stringPrefs.map { name -> population.single { it.name == name } }
|
|
)
|
|
}
|
|
|
|
val males = inMales.keys.map { Person(it) }
|
|
val females = inFemales.keys.map { Person(it) }
|
|
|
|
males.forEach { buildPrefs(it, inMales[it.name]!!, females) }
|
|
females.forEach { buildPrefs(it, inFemales[it.name]!!, males) }
|
|
|
|
|
|
match(males)
|
|
males.forEach { println(it.showMatch()) }
|
|
println("#### match is stable: ${isStableMatch(males, females)}")
|
|
|
|
|
|
fun swapMatch(male1: Person, male2: Person) {
|
|
val female1 = male1.matchedTo!!
|
|
val female2 = male2.matchedTo!!
|
|
|
|
male1.matchedTo = female2
|
|
male2.matchedTo = female1
|
|
|
|
female1.matchedTo = male2
|
|
female2.matchedTo = male1
|
|
}
|
|
|
|
swapMatch(males.single { it.name == "fred" }, males.single { it.name == "jon" })
|
|
males.forEach { println(it.showMatch()) }
|
|
println("#### match is stable: ${isStableMatch(males, females)}")
|
|
}
|