Crossword Generator

import java.io.File
import java.util.Scanner

import scala.collection.mutable
import scala.io.Source
import scala.util.Random

class Word(val letters: Seq[Letter])

sealed abstract class Cell {
  def char(assignment: Map[Word, String]): Char
}
case class Letter() extends Cell {
  var words = Array.empty[(Word, Int)]
  override def char(assignment: Map[Word, String]): Char = assignment.get(words(0)._1).map(_(words(0)._2)).getOrElse('?')
}
case object Empty extends Cell {
  override def char(assignment: Map[Word, String]): Char = '#'
}

object Cross {
  def main(args: Array[String]): Unit = {

    val dictionary: Map[Int, Set[String]] = readWords("cross.txt", "WINDOWS-1251").groupBy(_.length)
    val field: List[List[Cell]] = readField("cross.in")

    val random = new Random(/*345345073895L*/)
    val start = System.currentTimeMillis()
    def dump(result: Map[Word, String]) =
      println(field.map(_.map(_.char(result)).mkString("")).mkString("\n"))

    val cache = new mutable.HashMap[String, Array[String]]()
    val words = (field.flatMap(extractWords) ++ field.transpose.flatMap(extractWords)).filter(_.letters.size != 1)
    for (word <- words; (letter, index) <- word.letters.zipWithIndex) {
      letter.words :+= (word, index)
    }

    var min = words.size
    def search(masks: Map[Word, String], assignment: Map[Word, String]) {
      val level = masks.size
      if (min > level) {
        min = level
        dump(assignment)
        println(min + " " + (System.currentTimeMillis() - start) + " " + cache.size)
      }
      if (masks.isEmpty) {
        dump(assignment)
      } else {
        val (word, mask) = masks.minBy(w => cache(w._2).size)
        for (variant <- cache(mask)) {
          var newVariants = masks - word
          for ((letter, char) <- word.letters.zip(variant); (other, index) <- letter.words; if newVariants.contains(other)) {
            val oldMask = masks(other)
            val newMask = oldMask.updated(index, char)
            cache.getOrElseUpdate(newMask, cache(oldMask).filter(_(index) == char))
            newVariants = newVariants.updated(other, newMask)
          }
          search(newVariants, assignment.updated(word, variant))
        }
      }
    }
    for ((length, variants) <- dictionary) {
      cache.getOrElseUpdate("?" * length, random.shuffle(variants.toList).toArray)
    }
    search(words.map(w => (w, "?" * w.letters.length)).toMap, Map.empty)
  }

  def readField(file: String): List[List[Cell]] =
    readTextField(file).map(_.toList.map(c => if (c == '#') Empty else Letter()))

  def readTextField(file: String): List[String] = {
    val in = new Scanner(new File(file))
    val w = in.nextInt()
    val h = in.nextInt()
    in.nextLine()
    val lineFormat = s"#%-${w}s#"
    List("#" * (w + 2)) ++ (for (i <- 0 until h) yield lineFormat.format(in.nextLine())) ++ List("#" * (w + 2))
  }

  def substringBefore(string: String, substring: String) =
    string.substring(0, string.indexOf(substring))

  def readWords(file: String, encoding: String) =
    Source.fromFile("cross.txt", "WINDOWS-1251").getLines().map(substringBefore(_, " - ")).toSet

  def extractWords(row: List[Cell]): Seq[Word] = {
    val rest = row.dropWhile(_ == Empty)
    if (rest.isEmpty) Seq()
    else new Word(rest.takeWhile(_ != Empty).map(_.asInstanceOf[Letter])) +: extractWords(rest.dropWhile(_ != Empty))
  }
}