Skip to content
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
Something went wrong with that request. Please try again.