Create a gist now

Instantly share code, notes, and snippets.

Union find exercise - scala dojo 21st of Feb 2013
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 ->
new London(routeMap)
object CityMapImplicits {
implicit def stringToPoint(s: String): Point = Point(s)
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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment