Skip to content

Instantly share code, notes, and snippets.

@hedefalk
Created February 16, 2011 19:42
Show Gist options
  • Save hedefalk/830021 to your computer and use it in GitHub Desktop.
Save hedefalk/830021 to your computer and use it in GitHub Desktop.
def shorten(input: String, acronyms: Set[String]) = {
type Shortenee = String
type Acronym = String
val orderByLength = Ordering[Int].on[Shortenee](c => c.length)
def shortest(unvisited: Set[Shortenee], visited: Set[Shortenee]): Shortenee = {
if (unvisited isEmpty)
visited min orderByLength
else {
val next = unvisited head
val shorterOnes = removeAcronyms(next) &~ visited
shortest(unvisited - next ++ shorterOnes, visited + next)
}
}
def removeAcronyms(s: Shortenee) = {
def removeAcronym(a: Acronym) = {
def removeAcronymAt(position: Int) = {
val (prefix, rest) = s splitAt position
prefix ++ (rest drop (a length))
}
def indicesFrom(offset: Int): List[Int] = {
val index = s indexOfSlice (a, offset)
if (index < 0) Nil else index :: indicesFrom(index + 1)
}
indicesFrom(0) map removeAcronymAt _
}
acronyms flatMap removeAcronym
}
shortest(unvisited = Set(input), visited = Set())
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment