word-distance.scala

package wlhn

/**
 * West London Hack Night 2014-08-13
 * Finding the minimum distance
 * between any two words in a Shakespeare
 * play
 * http://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm
 * http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Scala (with amendments)
 */
object Dijkstra {

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

    def Dijkstra[Key](lookup: Map[Key, List[(Int, 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 {
                    val paths =
                        if (lookup.contains(key))
                            (lookup(key).flatMap { case (d, key) => if (!visited.contains(key)) List((dist + d, key :: path)) else Nil })
                        else
                            Nil
                    val sorted_fringe = (paths ++ fringe_rest).sortWith { case ((d1, _), (d2, _)) => d1 < d2 }
                    Dijkstra(lookup, sorted_fringe, dest, visited + key)
                }
        }
        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+""").toList
        //val words = Array("the", "lion", "killed", "the", "zebra")

        val pairs = (words zip words.tail).toSet
        //println(s"pairs $pairs")

        val grouped = pairs groupBy { case pair => pair._1 }
        //println(s"grouped $grouped")

        //Map[Key, List[(Int, Key)]]
        val lookup: Map[String, List[(Int, String)]] = grouped map (kv => (kv._1, (kv._2 map (pair => (1, pair._2))).toList))
        //println(s"lookup $lookup")

        val uniqueWords = lookup.keys
        //println(s"uniqueWords $uniqueWords")

        val paths = (
            (uniqueWords flatMap (start =>
                (uniqueWords filter (_ != start)) map (end =>
                    (start, end) -> Dijkstra[String](lookup, List((0, List(start))), end, Set())
                )
            ) filter (kv => kv._2._1 != 0)
            ).toList
            sortBy (kv => kv._2._1)
            map (path => (path._1._1, Tuple3(path._1._2, path._2._1, path._2._2)))
        ) groupBy ({ case (k, v) => k })
        paths.toList.sortBy(kv => kv._2.length) foreach { x => println(s"paths: ${x}") }

        println(s"uniqueWords ${uniqueWords.count(_ => true)}. paths ${paths.keys.count(_ => true)}.  No way to Ham.")
    }

}