public
Created

Union find exercise - scala dojo 21st of Feb 2013

  • Download Gist
Connector.scala
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
package com.bulba.unionfind
 
trait CityMap {
def isConnected(from: Point, to: Point): Boolean
}
 
case class Point(name: String) {
def - (to: Point) = (this, to)
}
 
case class London(routes: Map[Point, Set[Point]]) extends CityMap {
 
def isConnected(from: Point, to: Point): Boolean = {
routes.getOrElse(from, Set()) contains to
}
}
 
 
object London {
 
def apply(routes: (Point, Point)) = {
new London(Map(routes._1, Set(routes._2)))
}
 
def apply(routes: List[(Point, Point)]) = {
// val m: Map[Point, Set[(Point,Point)]] = routes.groupBy(_._1)
// routes.foldLeft(Map[Point,Set[(Point, Point)]]())((map, (from, to)) => )
// val m2: Map[Point, List[Point]] = for (p <- m) p -> p._2.map(_._2)
new London(routeMap)
 
}
}
 
object CityMapImplicits {
implicit def stringToPoint(s: String): Point = Point(s)
}
DisjointSetSpec.scala
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
package com.bulba.unionfind
 
import org.specs2.mutable.Specification
import com.bulba.unionfind.CityMapImplicits._
 
 
class DisjointSetSpec extends Specification {
 
"Disjoint set spec" should {
 
"read a-b into a graph" in {
London("a" - "b").isConnected("a","b") must beTrue
}
 
"for a-b b is not connected to a" in {
London("a" - "b").isConnected("b","a") must beFalse
}
 
"for a-b,b-c a is connected to b and b is connected to c" in {
val london: Any = London(List("a" - "b", "b" - "c"))
london.isConnected("a","c") must beTrue
}
}
}

Exercise was stopped at the stage of parsing the input data - as the last test states, London should allow a list of connections and rule that with so defined connections a and c would be connected. The apply methods in object London are broken - can you fix them?

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.