Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Union find exercise - scala dojo 21st of Feb 2013

View Connector.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)
}
View Connector.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
}
}
}
Owner

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.