Skip to content

Instantly share code, notes, and snippets.

@docent666
Created February 22, 2013 19:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save docent666/5016135 to your computer and use it in GitHub Desktop.
Save docent666/5016135 to your computer and use it in GitHub Desktop.
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 -> p._2.map(_._2)
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
}
}
}
@docent666
Copy link
Author

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