https://www.janestreet.com/puzzles/archive/ Tile and Trouble

TileAndTrouble

package test

object TileAndTrouble extends App {
  //val row = List(8, 8, 20, 17, 25, 25, 11)
  //val col = List(15, 13, 10, 21, 20, 18, 17)
  val row = List(12, 17, 43, 44, 34, 42, 43, 21, 36, 29, 30, 26)
  val col = List(30, 35, 45, 43, 41, 28, 25, 29, 25, 38, 18, 20)
  val size = row.length

  def seperate_inner(n: Int, c: Int, max: Int): Seq[Map[Int, Int]] = {
    if (max == 0 || c == 0) {
      if (n == 0) Map[Int, Int]() :: Nil else Nil
    } else {
      for (
        x <- (0 to Math.min(c, n / (max * max)));
        m <- seperate_inner(n - x * max * max, c - x * max, max - 1)
      ) yield if (x == 0) m else m + (max -> x)
    }
  }

  def seperate(n: Int) = {
    seperate_inner(n, size, Stream.from(1).find(x => x * x > n).get - 1)
  }

  def verify_inner(remain: List[Seq[Map[Int, Int]]], need: Map[Int, List[Int]]): Seq[List[Map[Int, Int]]] = remain match {
    case head :: tail =>
      head.flatMap { head1 =>
        ((1 to size).foldLeft(Some(need): Option[Map[Int, List[Int]]]) {
          case (Some(m), i) =>
            val c = m.getOrElse(i, Nil)
            val h = head1.getOrElse(i, 0)
            if (h < c.length)
              None
            else {
              Some(m + (i -> (c ++ (0 until h - c.length).map(x => i)).map(_ - 1).filter(_ > 0)))
            }
          case (None, i) => None
        }) match {
          case Some(n) => verify_inner(tail, n).map { head1 :: _ }
          case None => Nil
        }
      }
    case Nil => if (need.filterNot { case (k, v) => v.isEmpty }.isEmpty) (Nil) :: Nil else Nil
  }

  def verify(remain: List[Seq[Map[Int, Int]]]) = verify_inner(remain, Map())

  val rowss = verify(row.map(seperate))
  val colss = verify(col.map(seperate))

  def place(i: Int, xmin: Int, ymin: Int, row: Array[Array[Int]], col: Array[Array[Int]], a: Array[Int]): List[Array[Int]] = {
    if (i == 0) {
      a.clone() :: Nil
    } else if (row.forall(_(i) == 0) && col.forall(_(i) == 0)) {
      place(i - 1, 0, 0, row, col, a)
    } else if (xmin + i > size) {
      Nil
    } else if (ymin + i > size) {
      place(i, xmin + 1, 0, row, col, a)
    } else if (row(xmin)(i) > 0) {
      if ((xmin until xmin + i).forall(row(_)(i) > 0) && (ymin until ymin + i).forall(col(_)(i) > 0) &&
        (for (x <- (xmin until xmin + i); y <- (ymin until ymin + i)) yield a(x * size + y)).forall(_ == 0)) {
        for (x <- xmin until xmin + i)
          row(x)(i) -= 1
        for (y <- ymin until ymin + i)
          col(y)(i) -= 1
        for (
          x <- xmin until xmin + i;
          y <- ymin until ymin + i
        ) {
          a(x * size + y) = i
        }
        val r = place(i, xmin, ymin + i, row, col, a)
        for (x <- xmin until xmin + i)
          row(x)(i) += 1
        for (y <- ymin until ymin + i)
          col(y)(i) += 1
        for (
          x <- xmin until xmin + i;
          y <- ymin until ymin + i
        ) {
          a(x * size + y) = 0
        }
        r ++ place(i, xmin, ymin + 1, row, col, a)
      } else
        place(i, xmin, ymin + 1, row, col, a)
    } else
      place(i, xmin + 1, 0, row, col, a)
  }

  val r = for (rows <- rowss; cols <- colss) yield {
    val rows_r = for (row <- rows)
      yield row.foldLeft(Array.ofDim[Int](size + 1)) { case (a, (k, v)) => a(k) = v; a }
    val cols_r = for (col <- cols)
      yield col.foldLeft(Array.ofDim[Int](size + 1)) { case (a, (k, v)) => a(k) = v; a }
    val a = Array.ofDim[Int](size * size)
    place(size, 0, 0, rows_r.toArray, cols_r.toArray, a)
  }

  def count(a: Array[Int]) = {
    def zero(x: Int, y: Int) = {
      def findzero(x: Int, y: Int): Int = if (x < 0 || x >= size || y < 0 || y >= size || a(x * size + y) != 0)
        0
      else {
        a(x * size + y) = -1
        1 + findzero(x - 1, y) + findzero(x + 1, y) + findzero(x, y - 1) + findzero(x, y + 1)
      }

      if (a(x * size + y) != 0)
        1
      else
        findzero(x, y)
    }
    (for (x <- 0 until size; y <- 0 until size)
      yield zero(x, y)).foldLeft(1)(_ * _)
  }

  for (b <- r; a <- b) {
    for (x <- 0 until size) {
      for (y <- 0 until size) {
        print(a(x * size + y))
      }
      println()
    }
    println()
    println(count(a))
    println()
  }
}