solver.scala

/**
 * Created by petrrezikov on 27.07.15.
 */

package ru.innopolis.crazypit.SokobanSolver

import scala.collection.mutable.HashMap

class SokobanSolver(val map: Array[Array[Field]]) {


  class Position(val map: Array[Array[Field]], val wayString: String) {
    def fields = for {y <- map.indices
                      x <- map(0).indices} yield map(y)(x)
  }

  def calcResult: String = calcResultForList(0, List[Position](new Position(map, "")))

  private def calcResultForList(level: Int, positions: List[Position]): String = {
    println(s"Level: $level Positions: ${positions.size}")
    positions.find(isFinalPosition) match {
      case None => calcResultForList(level + 1, nextPositions(positions))
      case Some(x) => {
        println(new SokobanPrinter(x.map).getMapString)
        x.wayString
      }
    }
  }

  private def isFinalPosition(position: Position): Boolean = {
    !position.fields.exists((f: Field) => f.isFreeTarget)
  }

  private def nextPositions(positions: List[Position]): List[Position] =
    positions.flatMap(nextPositionsForOne)

  private def nextPositionsForOne(position: Position): List[Position] = {
    List[(Int, Int)]((0, 1), (1, 0), (-1, 0), (0, -1)).
      map(movePositionIfGood(position, _)).
      filter(_.isDefined).map(_.get).seq.toList
  }


  private def movePositionIfGood(position: Position, movement: (Int, Int)): Option[Position] = {
    val agentField = getAgentField(position)
    lazy val agentMoveField = getMoveField(position.map, agentField, movement)
    lazy val boxMoveField = getMoveField(position.map, agentMoveField, movement)
    if (agentMoveField.kind == FieldKinds.Wall) return None
    if (agentMoveField.occupant == FieldOccupant.Box &&
      !boxMoveField.canMoveBoxHere) return None
    val newPosition = new Position(deepMapClone(position.map),
      position.wayString + getWayLetter(movement))
    newPosition.map(agentField.y)(agentField.x).occupant = FieldOccupant.Nothing
    newPosition.map(agentMoveField.y)(agentMoveField.x).occupant = FieldOccupant.Agent
    if (agentMoveField.occupant == FieldOccupant.Box)
      newPosition.map(boxMoveField.y)(boxMoveField.x).occupant = FieldOccupant.Box
    if (isDeadEnd(boxMoveField.x, boxMoveField.y, newPosition.map)) return None
    if (isAlreadyBeenMap(newPosition.map)) return None
    Option[Position](newPosition)
  }

  private val mapsHash = HashMap[String, Boolean]()

  private def isAlreadyBeenMap(map: Array[Array[Field]]): Boolean = {
    val hash = new SokobanPrinter(map).getMapString
    if (mapsHash.contains(hash)) return true
    mapsHash.put(hash, true)
    false
  }

  private def getAgentField(position: Position): Field =
    position.fields.find(_.occupant == FieldOccupant.Agent).get

  private def getMoveField(map: Array[Array[Field]], field: Field,
                           movement: (Int, Int)): Field =
    map(field.y + movement._2)(field.x + movement._1)


  private def deepMapClone(map: Array[Array[Field]]): Array[Array[Field]] = {
    val newMap = Array.ofDim[Field](map.length, map(0).length)
    for {y <- map.indices
         x <- map(0).indices
    } {
      val oldField = map(y)(x)
      newMap(y)(x) = new Field(oldField.x, oldField.y, oldField.kind, oldField.occupant)
    }
    newMap
  }

  private def getWayLetter(movement: (Int, Int)): String = movement match {
    case (0, 1) => "D"
    case (0, -1) => "U"
    case (1, 0) => "R"
    case (-1, 0) => "L"
  }


  // TODO: Not all dead end type optimization, but have no time for it.
  private def isDeadEnd(x: Int, y: Int, map: Array[Array[Field]]): Boolean = {
    val field = map(y)(x)
    field.occupant == FieldOccupant.Box &&
      field.kind == FieldKinds.Free && (
      isBothWall(map, x, y, (-1, 0), (0, -1)) ||
        isBothWall(map, x, y, (0, -1), (1, 0)) ||
        isBothWall(map, x, y, (1, 0), (0, 1)) ||
        isBothWall(map, x, y, (0, 1), (-1, 0)))
  }

  private def isBothWall(map: Array[Array[Field]], x: Int, y: Int, firstMove: (Int, Int), secondMove: (Int, Int)): Boolean = {
    val result = map(y + firstMove._2)(x + firstMove._1).isWall &&
      map(y + secondMove._2)(x + secondMove._1).isWall
    result
  }
}