/*
 * Yajilin Solver in Copris
 * by Naoyuki Tamura
 * http://bach.istc.kobe-u.ac.jp/copris/puzzles/yajilin/
 */
package yajilin

import jp.kobe_u.copris._
import jp.kobe_u.copris.dsl._
import puzzle._

case class Yajilin(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
  def isBlank(cell: Cell) = at(cell) == "-"
  def isArrow(cell: Cell) = at(cell).matches("\\d+[nsew]")
  def arrow(cell: Cell): (Int,(Int,Int)) = {
    require(isArrow(cell))
    val len = at(cell).init.toInt
    at(cell).last match {
      case 'n' => (len, (-1, 0))
      case 's' => (len, ( 1, 0))
      case 'e' => (len, ( 0, 1))
      case 'w' => (len, ( 0,-1))
    }
  }
  val blankCells = cells.filter(isBlank)
  def adjBlankCells(cell: Cell) = adjCells(cell).filter(isBlank)
  def cellBlock(cell: Cell, dij: Cell): Seq[Cell] =
    if (! isCell(cell)) Seq.empty else cell +: cellBlock(move(cell, dij), dij)
  def block(cell: Cell): (Set[Cell],Int) = {
    require(isArrow(cell))
    val (len,dij) = arrow(cell)
    val (block1,block2) =
      cellBlock(move(cell, dij), dij).span(cell => ! isArrow(cell) || arrow(cell)._2 != dij)
    if (block2.isEmpty)
      (block1.filter(isBlank).toSet, len)
    else
      (block1.filter(isBlank).toSet, len - arrow(block2.head)._1)
  }
  val blocks = cells.filter(isArrow).map(cell => block(cell)).filter(! _._1.isEmpty)
  def show(sol: Seq[Cell]) {
    val arcs = sol.sliding(2).map(e => (e(0),e(1))).toSet
    def connected(cell1: Cell, cell2: Cell) =
      arcs.contains((cell1,cell2)) || arcs.contains((cell2,cell1))
    for (i <- 0 until m) {
      print(" .")
      for (j <- 0 until n) {
	val cell = (i,j); val cell1 = (i-1,j)
	if (isCell(cell1) && connected(cell, cell1)) print(" | .")
	else print("   .")
      }
      println
      for (j <- 0 until n) {
	val cell = (i,j); val cell1 = (i,j-1)
	val e = if (isCell(cell1) && connected(cell, cell1)) "---"
		else "   "
	val x = if (isArrow(cell)) at(cell)
		else if (sol.contains(cell)) "+"
		else "#"
	print((e + x).takeRight(4))
      }
      println
    }
    println(" ." + "   ." * n)
  }
}

object Solver extends BoardPuzzleSolver[Yajilin] {
  import scala.math.Ordering.Implicits._

  val name = "yajilin.Solver"
  var cycles: Set[Seq[Cell]] = _

  def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
    Yajilin(m, n, board)

  def define = {
    for (cell <- puzzle.blankCells)
      int('x(cell), 0, 1)
    for (cell <- puzzle.blankCells; cell1 <- puzzle.adjBlankCells(cell); if cell < cell1)
      add('x(cell) + 'x(cell1) <= 1)
    for ((block,len) <- puzzle.blocks)
      add(Add(block.map(cell => 'x(cell))) === len)
    for (cell <- puzzle.blankCells; cell1 <- puzzle.adjBlankCells(cell))
      int('e(cell,cell1), 0, 1)
    for (cell <- puzzle.blankCells; cell1 <- puzzle.adjBlankCells(cell); if cell < cell1)
      add('e(cell,cell1) + 'e(cell1,cell) <= 1)
    for (cell <- puzzle.blankCells) {
      val in = puzzle.adjBlankCells(cell).map(cell1 => 'e(cell1,cell))
      val ot = puzzle.adjBlankCells(cell).map(cell1 => 'e(cell,cell1))
      int('io(cell), 0, 1)
      add('io(cell) === Add(in))
      add('io(cell) === Add(ot))
      add(('io(cell) === 1) <==> ('x(cell) === 0))
    }
  }

  def checkSolution: Boolean = {
    val nodes = puzzle.blankCells.filter(cell => solution('io(cell)) > 0).toSet
    def nextCells(cell: Cell) =
      puzzle.adjBlankCells(cell).filter(cell1 => solution('e(cell,cell1)) > 0).toSet
    val arcs = nodes.map(cell => cell -> nextCells(cell)).toMap
    cycles = getCycles(nodes, arcs)
    if (verbose >= 2)
      println("Components = " + cycles.size)
    cycles.size == 1
  }
  def addNegation {
    for (cycle <- cycles) {
      add(Or(cycle.sliding(2).map(e => 'e(e(0),e(1)) === 0).toSeq))
      add(Or(cycle.reverse.sliding(2).map(e => 'e(e(0),e(1)) === 0).toSeq))
    }
  }
  override def findFirstSolution = findIncremental(true, checkSolution, addNegation)
  override def findNextSolution = findIncremental(false, checkSolution, addNegation)

  def showSolution {
    // Cycle
    require(cycles.size == 1)
    val sol = cycles.head
    if (quiet == 0) {
      println("Solution = " + sol)
      println("Size = " + sol.size)
      puzzle.show(sol)
    }
  }
}