|
=={{header|Kotlin}}==
{{trans|Java}}
<lang scala>import java.util.*
<lang kotlin>
class People(val map: Map<String, Array<String>>) {
data class Person(val operator fun get(name: String) = map[name]{
val preferences = mutableListOf<Person>()
var matchedTo: Person? = null
fun trySwap(p: Person) {
val names: List<String> by lazy { map.keys.toList() }
if (prefers(p)) {
matchedTo?.matchedTo = null
fun preferences(k: String, v: String): List<String> {
val prefers matchedTo = get(k)!!p
p.matchedTo = this
return ArrayList<String>(prefers.slice(0..prefers.indexOf(v)))
}
}
class EngagementRegistry() : TreeMap<String, String>() {
constructor(guys: People, girls: People) : this() {
val freeGuys = guys.names.toMutableList()
while (freeGuys.any()) {
val guy = freeGuys.removeAt(0) // get a load of THIS guy
val guy_p = guys[guy]!!
for (girl in guy_p)
if (this[girl] == null) {
this[girl] = guy // girl is free
break
} else {
val other = this[girl]!!
val girl_p = girls[girl]!!
if (girl_p.indexOf(guy) < girl_p.indexOf(other)) {
this[girl] = guy // this girl prefers this guy to the guy she's engaged to
freeGuys += other
break
} // else no change... keep looking for this guy
}
}
}
override fun toStringprefers()p: StringPerson) = when (matchedTo) {
valnull s-> = StringBuilder()true
else -> preferences.indexOf(p) < preferences.indexOf(matchedTo!!)
for ((k, v) in this) s.append("$k is engaged to $v\n")
return s.toString()
}
fun analyseshowMatch(guys:) People,= girls:"$name People)<=> ${matchedTo?.name}"
}
if (check(guys, girls))
println("Marriages are stable")
fun match(males: Collection<Person>) {
else
while (males.find { it.matchedTo == null }?.also { match(it) } != null) {
println("Marriages are unstable")
}
}
fun swapmatch(girls: People, i: Int, jmale: IntPerson) {
while (male.matchedTo == null) {
val n1 = girls.names[i]
male.preferences.removeAt(0).trySwap(male)
val n2 = girls.names[j]
val g0 = this[n1]!!
val g1 = this[n2]!!
this[n1] = g1
this[n2] = g0
println("$n1 and $n2 have switched partners")
}
}
private fun checkisStableMatch(guysmales: PeopleCollection<Person>, girlsfemales: PeopleCollection<Person>): Boolean {
return males.all { isStableMatch(it, females) }
val guy_names = guys.names
}
val girl_names = girls.names
if (!keys.containsAll(girl_names) or !values.containsAll(guy_names))
return false
fun isStableMatch(male: Person, females: Collection<Person>): Boolean {
val invertedMatches = TreeMap<String, String>()
for ((k, v) in this) invertedMatches[v] = k
val likesBetter = females.filter { !male.preferences.contains(it) }
for ((k, v) in this) {
val stable = !likesBetter.any { it.prefers(male) }
val sheLikesBetter = girls.preferences(k, v)
val heLikesBetter = guys.preferences(v, k)
for (guy in sheLikesBetter) {
val fiance = invertedMatches[guy]
val guy_p = guys[guy]!!
if (guy_p.indexOf(fiance) > guy_p.indexOf(k)) {
println("$k likes $guy better than $v and $guy likes $k better than their current partner")
return false
}
}
forif (girl in heLikesBetter!stable) {
println("#### Unstable pair: val fiance = get${male.showMatch(girl)}")
val girl_p = girls[girl]!!
if (girl_p.indexOf(fiance) > girl_p.indexOf(v)) {
println("$v likes $girl better than $k and $girl likes $v better than their current partner")
return false
}
}
}
return true
}
return stable
}
fun main(args: Array<String>) {
val inMales = mapOf(
val guys = People(mapOf("abe" to arrayOf("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
"bobabe" to arrayOfmutableListOf("cathabi", "hopeeve", "abicath", "deeivy", "evejan", "faydee", "beafay", "janbea", "ivyhope", "gay"),
"colbob" to arrayOfmutableListOf("hopecath", "evehope", "abi", "dee", "beaeve", "fay", "ivybea", "gayjan", "cathivy", "jangay"),
"dancol" to arrayOfmutableListOf("ivyhope", "fayeve", "deeabi", "gaydee", "hopebea", "evefay", "janivy", "beagay", "cath", "abijan"),
"eddan" to arrayOfmutableListOf("janivy", "deefay", "beadee", "cathgay", "fayhope", "eve", "abijan", "ivybea", "hopecath", "gayabi"),
"freded" to arrayOfmutableListOf("beajan", "abidee", "deebea", "gaycath", "evefay", "ivyeve", "cathabi", "janivy", "hope", "faygay"),
"gavfred" to arrayOfmutableListOf("gaybea", "eveabi", "ivydee", "beagay", "catheve", "abiivy", "deecath", "hopejan", "janhope", "fay"),
"halgav" to arrayOfmutableListOf("abigay", "eve", "hopeivy", "faybea", "ivycath", "cathabi", "jandee", "beahope", "gayjan", "deefay"),
"ianhal" to arrayOfmutableListOf("hopeabi", "catheve", "deehope", "gayfay", "beaivy", "abicath", "fayjan", "ivybea", "jangay", "evedee"),
"jonian" to arrayOfmutableListOf("abihope", "faycath", "jandee", "gay", "evebea", "beaabi", "deefay", "cathivy", "ivyjan", "hopeeve"))),
"jon" to mutableListOf("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"))
val inFemales = mapOf(
val girls = People(mapOf("abi" to arrayOf("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
"beaabi" to arrayOflistOf("bob", "abefred", "coljon", "fredgav", "gavian", "danabe", "iandan", "ed", "joncol", "hal"),
"cathbea" to arrayOflistOf("fredbob", "bobabe", "edcol", "gavfred", "halgav", "coldan", "ian", "abeed", "danjon", "jonhal"),
"deecath" to arrayOflistOf("fred", "jonbob", "coled", "abegav", "ianhal", "halcol", "gavian", "danabe", "bobdan", "edjon"),
"evedee" to arrayOflistOf("jonfred", "haljon", "fredcol", "danabe", "abeian", "gavhal", "colgav", "eddan", "ianbob", "bobed"),
"fayeve" to arrayOflistOf("bobjon", "abehal", "edfred", "iandan", "jonabe", "dangav", "fredcol", "gaved", "colian", "halbob"),
"gayfay" to arrayOflistOf("jonbob", "gavabe", "haled", "fredian", "bobjon", "abedan", "colfred", "edgav", "dancol", "ianhal"),
"hopegay" to arrayOflistOf("gavjon", "jongav", "bobhal", "abefred", "ianbob", "danabe", "halcol", "ed", "coldan", "fredian"),
"ivyhope" to arrayOflistOf("iangav", "coljon", "halbob", "gavabe", "fredian", "bobdan", "abehal", "ed", "joncol", "danfred"),
"janivy" to arrayOflistOf("edian", "halcol", "gavhal", "abegav", "bobfred", "jonbob", "colabe", "ianed", "fredjon", "dan"))),
"jan" to listOf("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan"))
with(EngagementRegistry(guys, girls)) {
fun buildPrefs(person: Person, stringPrefs: List<String>, population: List<Person>) {
print(this)
person.preferences.addAll(
analyse(guys, girls)
stringPrefs.map { name -> population.single { it.name == name } }
swap(girls, 0, 1)
analyse(guys, girls)
}
}</lang>
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)}")
}
</lang>
{{out}}
<pre>
See Java output.
abe <=> ivy
bob <=> cath
col <=> dee
dan <=> fay
ed <=> jan
fred <=> bea
gav <=> gay
hal <=> eve
ian <=> hope
jon <=> abi
##### match is stable: true
abe <=> ivy
bob <=> cath
col <=> dee
dan <=> fay
ed <=> jan
fred <=> abi
gav <=> gay
hal <=> eve
ian <=> hope
jon <=> bea
#### Unstable pair: fred <=> abi
##### match is stable: false
</pre>
=={{header|Lua}}==
|