WLHN - Finding the minimum distance between 2 words

word-distance.scala

package wlhn

/**
 * West London Hack Night 2014-08-13
 * Finding the minimum distance
 * between any two words in a Shakespeare
 * play
 */
object Dijkstra {

  type Path[Key] = (Double, List[Key])

  def Dijkstra[Key](lookup: Map[Key, List[(Double, Key)]], fringe: List[Path[Key]], dest: Key, visited: Set[Key]): Path[Key] = fringe match {
    case (dist, path) :: fringe_rest => path match {case key :: path_rest =>
      if (key == dest) (dist, path.reverse)
      else if (lookup.contains(key)) {
        val paths = lookup(key).flatMap {
          case (d, key) =>
            if (!visited.contains(key))
              List((dist + d, key :: path))
            else
              Nil
        }
        val sorted_fringe = (paths ++ fringe_rest).sortWith {case ((d1, _), (d2, _)) => d1 < d2}
        Dijkstra(lookup, sorted_fringe, dest, visited + key)
      } else (dist, path)
    }
    case Nil => (0, List())
  }

  def main(x: Array[String]): Unit = {

    //val words = Source.fromFile("/Users/aretter/NetBeansProjects/wlhn-20140813/hamlet.txt").mkString.split("""\s+""")
val words="""Ham. To be, or not to be, that is the Question:
             |Whether 'tis Nobler in the minde to suffer
             |The Slings and Arrowes of outragious Fortune,
             |Or to take Armes against a Sea of troubles,
             |And by opposing end them: to dye, to sleepe
             |No more; and by a sleepe, to say we end
             |The Heart-ake, and the thousand Naturall shockes
             |That Flesh is heyre too? 'Tis a consummation
             |Deuoutly to be wish'd. To dye to sleepe,
             |To sleepe, perchance to Dreame; I, there's the rub,
             |For in that sleepe of death, what dreames may come,
             |When we haue shuffel'd off this mortall coile,
             |Must giue vs pawse. There's the respect
             |That makes Calamity of so long life:
             |For who would beare the Whips and Scornes of time,
             |The Oppressors wrong, the poore mans Contumely,
             |The pangs of dispriz'd Loue, the Lawes delay,
             |The insolence of Office, and the Spurnes
             |That patient merit of the vnworthy takes,
             |When he himselfe might his Quietus make
             |With a bare Bodkin? Who would these Fardles beare
             |To grunt and sweat vnder a weary life,
             |But that the dread of something after death,
             |The vndiscouered Countrey, from whose Borne
             |No Traueller returnes, Puzels the will,
             |And makes vs rather beare those illes we haue,
             |Then flye to others that we know not of.
             |Thus Conscience does make Cowards of vs all,
             |And thus the Natiue hew of Resolution
             |Is sicklied o're, with the pale cast of Thought,
             |And enterprizes of great pith and moment,
             |With this regard their Currants turne away,
             |And loose the name of Action. Soft you now,
             |The faire Ophelia? Nimph, in thy Orizons
             |Be all my sinnes remembred
             |""".mkString.split("""\W+""")
    //val words = Array("the", "lion", "killed", "the", "zebra")

    val pairs = words.toList.zip(words.tail).groupBy{
      case (k,v) => k
    }.map {
      case (k, v) =>
        (k, v.map(_._2))
    }

    //println("pairs=" + pairs)

    val lookup = pairs map {
      case(k, v) =>
        (k, v map {
          case x =>
            (1.0, x)
        })
    }

    println("lookup=" + lookup.keys)

    for(word <- lookup.keys) {

      //val res = Dijkstra[String](lookup, List((0, List("Conscience"))), "Resolution", Set())
      val res = Dijkstra[String](lookup, List((0, List("Conscience"))), word, Set())
      println(res)

      if(res._2.length > 1) {
        val crazy = (res._2(0), res._2(1)) -> res._1
        println(s"crazy=$crazy")
      }
    }
  }

}