Another neat interview question: a kind of crossword puzzle

My friend had another interview question. You have already seen the first one.
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!