Rosetta Code

Stable marriage problem: Difference between revisions

Page Discussion

Stable marriage problem (view source)

Revision as of 13:16, 22 January 2017

678 bytes removed ,  7 years ago
→‎{{header|Scala}}: simplification of method signatures
m (Reverted edits by Simple9371 (talk) to last revision by Jolkdarr)
(→‎{{header|Scala}}: simplification of method signatures)
Line 5,654:
=={{header|Scala}}==
{{trans|Java}}
<lang scala>importobject scala.collection.mutable.AbstractMapSMP extends App {
import scala.collection.mutable.HashMap▼
import scala.collection.mutable.HashSet
import scala.collection.mutable.Queue
import scala.collection.mutable.TreeMap
 
object SMP extends App {
def run() {
val matches = matching(guys, guyPrefers, girlPrefers)
matches.foreach { e => println(s"${e._1} is engaged to ${e._2}") }
if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
println("Marriages are stable")
else
Line 5,675 ⟶ 5,669:
matches += girl2 -> tmp
println(girl1 + " and " + girl2 + " have switched partners")
if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
println("Marriages are stable")
else
Line 5,681 ⟶ 5,675:
}
 
▲ import scala.collection.mutableimmutable.HashMapMap
private def matching(guys: Seq[String],▼
private type TM = guyPrefers: AbstractMapscala.collection.mutable.TreeMap[String, List[String]],
 
girlPrefers: AbstractMap[String, List[String]]): TreeMap[String, String] = {
▲ private def matching(guys: Seq[String],= {
val engagements = new TreeMap[String, String]
val freeGuysengagements = new Queue[String]TM
val freeGuys = scala.collection.mutable.Queue.empty ++= guys
while (freeGuys.nonEmpty) {
val guy = freeGuys.dequeue()
Line 5,711 ⟶ 5,705:
}
 
private def checkMatches(guysmatches: Seqscala.collection.Map[String], girlsString]): Seq[String],Boolean = {
if (!girls.toSet.subsetOf(matches.keySet) || !guys.toSet.subsetOf(HashSet() ++= matches.values.toSet))▼
matches: AbstractMap[String, String],
guyPrefers: AbstractMap[String, List[String]],
girlPrefers: AbstractMap[String, List[String]]): Boolean = {
▲ if (!girls.toSet.subsetOf(matches.keySet) || !guys.toSet.subsetOf(HashSet() ++= matches.values))
return false
 
val invertedMatches = new TreeMap[String, String]TM
matches.foreach { invertedMatches += _.swap }
 
for ((k, v) <- matches) {
val shePrefers = girlPrefers(k)
val sheLikesBetter = Queue() ++= shePrefers.slice(0, shePrefers.indexOf(v))
val hePrefers = guyPrefers(v)
val heLikesBetter = Queue() ++= hePrefers.slice(0, hePrefers.indexOf(k))
 
for (guy <- sheLikesBetter) {
Line 5,750 ⟶ 5,741:
private val guys = "abe" :: "bob" :: "col" :: "dan" :: "ed" :: "fred" :: "gav" :: "hal" :: "ian" :: "jon" :: Nil
private val girls = "abi" :: "bea" :: "cath" :: "dee" :: "eve" :: "fay" :: "gay" :: "hope" :: "ivy" :: "jan" :: Nil
private val guyPrefers = HashMapMap("abe" -> List("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
"bob" -> List("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
"col" -> List("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
Line 5,760 ⟶ 5,751:
"ian" -> List("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
"jon" -> List("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope"))
private val girlPrefers = HashMapMap("abi" -> List("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
"bea" -> List("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
"cath" -> List("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/154431"