This one is about crosswords. It involves graphs obviously.
Let me start by giving a brief overview of the problem he had to solve, and my Scala take on it ;-)
Question Imagine a crossword grid of size n x n containing letters. Given a dictionary of words, find all possible paths in the grid that match the words in the dictionary.
For Example:
MBC
ARA
NMO
is a 3x3 grid of letters, if the dictionary contains the word MAN, there are two paths possible: [(0,0), (0,1), (0,2)] and [(1,2), (0,1), (0,2)].
My Scala take on it
Let's define a Coord class that represents the grid coordinates - and a bunch of methods to work out the neighbours of a given coordinate:
val gridSize = 3 //> gridSize : Int = 3
case class Coord(val x: Int, y: Int) {
def /\ = Coord(x, y - 1)
def \/ = Coord (x, y + 1)
def |> = Coord(x + 1, y)
def <| = Coord(x - 1, y)
def -/ = Coord(x + 1, y - 1)
def -\ = Coord(x + 1, y + 1)
def \- = Coord(x - 1, y - 1)
def /- = Coord(x - 1, y + 1)
def isValid = x >= 0 && x < gridSize && y >= 0 && y < gridSize
}
type Path = List[Coord]
type Paths = List[Path]
The next method works out all valid neighbours for a given coordinate:
def /\/\ (c: Coord) = List(c /\, c \/, c |>, c <|, c -/, c -\, c \-, c /-).filter(_.isValid)For example:
require((/\/\(Coord(1, 1))).size == 8) require((/\/\(Coord(0, 0))).size == 3)Let's define a dictionary for our tests:
val dict = Set("MAN", "ARM", "CAR") //> dict : scala.collection.immutable.Set[String] = Set(MAN, ARM, CAR)
val dictMaxLength = dict.map(w => w.size).max //> dictMaxLength : Int = 3
The main algorithm is the following that enumerates all the paths between two nodes in the graph.
Note that I restrict the path length based on the maximum of letters defined in the dictionary.
This can be improved further using the dictionary (prefix.. etc. left as an exercise).
def allPaths(from: Coord, to: Coord): Paths = {
def allPathsRec(currentCoord: Coord, currentPath: Path): Paths = {
if (currentPath.size > dictMaxLength) Nil
else if (currentCoord == to) List(currentPath)
else /\/\(currentCoord).filter(c => !(currentPath contains c)).flatMap(c => allPathsRec(c, c :: currentPath))
}
allPathsRec(from, List(from)).map(_.reverse)
}
As an example, the following will give you the diagonal:
allPaths(Coord(0, 0), Coord(2, 2)) //WordGrid.Paths = List(List(Coord(0,0), Coord(1,1), Coord(2,2)))Before we test it, we need one final procedure: a def to generate all pairs of cells (from one cell to another cell):
def fromsTos: List[(Coord, Coord)] = {
val keys = dictMap.keySet.toList
for {
c1 <- keys
c2 <- keys.filter(_ != c1)
} yield (c1, c2)
}
dictMap is the crossword definition:
val dictMap = Map(Coord(0, 0) -> 'M', Coord(1, 0) -> 'B', Coord(2, 0) -> 'C',
Coord(0, 1) -> 'A', Coord(1, 1) -> 'R', Coord(2, 1) -> 'A',
Coord(0, 2) -> 'N', Coord(1, 2) -> 'M', Coord(2, 2) -> 'O')
Test Time to put this to the test:
// Generates all possible pairs path in the grid
// List(List(Coord(0,2), Coord(0,1), Coord(0,0)), ...
val allPairsPaths = fromsTos.map(t => allPaths(t._1, t._2)).flatten
// Generates all words from the pairs path
// List(NAM, NRM, NRC, NAR, NMR, NR, NMO ....
val words = allPairsPaths.map(p => p.map(c => dictMap(c))).map(cs => cs.mkString)
// Combine the two lists, keep only what is in the dictionary
// List((MAN,List(Coord(0,0), Coord(0,1), Coord(0,2))), (CAR,List(Coord(2,0), Coord(2,1), Coord(1,1))) ....
val wordsPath = (words, allPairsPaths).zipped.map((_, _)).filter(t => dict contains t._1)
// Pretty print
wordsPath.foreach(wp => {println(s"Word ${wp._1} has path ${wp._2}")})
//> Word MAN has path List(Coord(0,0), Coord(0,1), Coord(0,2))
//| Word CAR has path List(Coord(2,0), Coord(2,1), Coord(1,1))
//| Word ARM has path List(Coord(0,1), Coord(1,1), Coord(0,0))
//| Word ARM has path List(Coord(0,1), Coord(1,1), Coord(1,2))
//| Word MAN has path List(Coord(1,2), Coord(0,1), Coord(0,2))
//| Word ARM has path List(Coord(2,1), Coord(1,1), Coord(0,0))
//| Word ARM has path List(Coord(2,1), Coord(1,1), Coord(1,2))
There are a few optimizations to do here and there. An interview question not easy to get right on a white board!
