import java.io._
import scala.io.Source

object PuzzleSolver extends App {

  class Square(xNumber:Int, yNumber:Int, values:List[String] = List("-","S"), solved:Boolean = false) {
    var possibleValues = values
    val x = xNumber
    val y = yNumber
    var s = solved

    def setValues(solution: String) = {
      this.s = true
      this.possibleValues = List(solution)
      // new Square(this.box, this.x, this.y, List(solution), true)
    }

    def getValue:String = {
      if(this.s) possibleValues.head
      else "Not solved"
    }

    def removeValue(wrongSolution:String):Square = {
      val newList = this.possibleValues.filter(_ != wrongSolution)
      if(newList.length > 1)
        new Square(x, y, newList, false)
      else
        new Square(x,y,newList,true)
    }

    // Returns a list with all neighbour squares in clockwise rotation
    def getNeighbours(boardSize:Int):List[String] = {
      var right = ""
      var left = ""
      var over = ""
      var under = ""

      if(x == boardSize) right = "-"
      else {
        if(getSquare(x+1, y).possibleValues.length > 1) right = "?"
        else right = getSquare(x+1,y).possibleValues.head
      }

      if(x == 1) left = "-"
      else {
        if(getSquare(x-1, y).possibleValues.length > 1) left = "?"
        else left = getSquare(x-1, y).possibleValues.head
      }

      if(y == 1) over = "-"
      else {
        if(getSquare(x, y-1).possibleValues.length > 1) over = "?"
        else over = getSquare(x, y-1).possibleValues.head
      }

      if(y == boardSize) under = "-"
      else {
        if(getSquare(x, y+1).possibleValues.length > 1) under = "?"
        else under = getSquare(x, y+1).possibleValues.head
      }

      val neighbours = List[String](right, under, left, over)
      neighbours
    }

  }

  var allSquares = List[Square]()
  var unsolvedSquares = List[Square]()
  var boatsList = List[List[Square]]()
  var savedBoard = List[Square]()

  def getAllFromX(i:Int):List[Square] = {
    allSquares.filter(_.x == i)
  }

  def getAllFromY(i:Int):List[Square] = {
    allSquares.filter(_.y == i)
  }

  def getSquare(x:Int, y:Int):Square = {
    allSquares.filter(_.x == x).filter(_.y == y).head
  }

  def setValue(x:Int, y:Int, solution:String):Unit = {
    val s = getSquare(x,y)
    allSquares = allSquares.filter(_ != s)
    s.setValues(solution)
    allSquares = allSquares :+ s
  }

  def removeValue(x:Int, y:Int, wrongSolution:String):Unit = {
    var s = getSquare(x,y)
    allSquares = allSquares.filter(_ != s)
    s = s.removeValue(wrongSolution)
    allSquares = allSquares :+ s
  }

  def getShips(ships:String):List[(Int, Int)] = {
    var boats = List[(Int, Int)]()
    var shipList = List[String]()

    // Read in ships from file
    for(i <- 0 until ships.length){
      if(ships.charAt(i) == 'x'){
        shipList = shipList ::: List(s"${ships(i-1)}${ships(i)}${ships(i+1)}")
      }
    }

    var amount = 0
    var size = 0
    var xIndex = 0

    // Save ships in a list of tuples(amount, size)
    // Example: (3, 1) means 3x1, or 3 boats of size 1
    for(ship <- shipList){
      xIndex = ship.indexOf('x')
      amount = ship.substring(0, xIndex).toInt
      size = ship.substring(xIndex + 1, ship.length).toInt

      boats = boats :+ (amount, size)
    }

    // Return tuple list:
    boats
  }

  // Takes in a size as parameter, and loops through the list of tuples for the correct size
  // When it finds the correct tuple, decrement the amount
  // Return the new list
  def decrementBoats(size:Int, boats:List[(Int, Int)]):List[(Int, Int)] = {
    var boats2 = List[(Int, Int)]()
    for(boat <- boats){
      if(boat._2 == size && boat._1 > 0) boats2 = boats2 :+ (boat._1 - 1, boat._2)
      else boats2 = boats2 :+ (boat._1, boat._2)
    }
    boats2
  }

  def incrementBoats(size:Int, boats:List[(Int, Int)]):List[(Int, Int)] = {
    var boats2 = List[(Int, Int)]()
    for(boat <- boats){
      if(boat._2 == size) boats2 = boats2 :+ (boat._1 + 1, boat._2)
      else boats2 = boats2 :+ (boat._1, boat._2)
    }
    boats2
  }

  def saveBoard(allSquares:List[Square]):Unit = {
    savedBoard = allSquares
  }

  def allowedMove(horizontalHints:List[Int], verticalHints:List[Int]):Boolean = {
    var boardSize = horizontalHints.length
    // Check if board fulfills all rules
    // No boats touch each other
    // Correct amount of boats in each row/col according to hints
    var i = 1
    for(hint <- horizontalHints){
      if(getAllFromX(i).count((s:Square) => s.getValue == "S") > hint) return false
      i += 1
    }
    i = 1
    for(hint <- verticalHints){
      if(getAllFromY(i).count((s:Square) => s.getValue == "S") > hint) return false
      i += 1
    }

    for(boat <- boatsList){
      if(!isBoatBuilt(boat, boardSize)) return false
    }

    true
  }

  def bruteforceParty(boats:List[(Int, Int)], horizontalHints:List[Int], verticalHints:List[Int]):List[(Int, Int)] = {
    var maxShip = 0
    unsolvedSquares = getUnsolved

    for(boat <- boats){
      if(boat._2 > maxShip && boat._1 > 0) maxShip = boat._2
    }

    saveBoard(allSquares)

    var x = unsolvedSquares.head.x
    var y = unsolvedSquares.head.y
    var hint = verticalHints(y-1)

    //Get all lines where maxShip can mathematically be placed from hint and where the amount of boats is not yet solved
    //Change the first square in unsolvedSquare, set it to value "boat"
    if(hint >= maxShip && getAllFromY(x).count((s:Square) => s.getValue == "S") < hint){
      val chosen = allSquares.filter((s:Square) => getSquare(s.x, s.y) == unsolvedSquares.head)
      chosen.head.setValues("S")
      println("Value of (" + getSquare(x, y).x + "," + getSquare(x, y).y + ") is changed to S\n")
    }
    var updatedShips = boats
    updatedShips = updateBoatsList(horizontalHints.length, boats)

    updatedShips
  }

  def getUnsolved:List[Square] = {
    unsolvedSquares = allSquares.filter((u:Square) => !u.s)
    unsolvedSquares
  }



  def updateUnsolved():List[Square] = {
    unsolvedSquares = unsolvedSquares.drop(1)
    unsolvedSquares
  }

  //TODO: Update so function checks if an entire boat is surrounded by water instead of only checking endpoints of boat
  def isBoatBuilt(boat:List[Square], boardSize:Int):Boolean = {
    //Check for boat of size 1 (one boat-tile is surrounded by water)
    if(boat.length == 1){
      if(boat.head.getNeighbours(boardSize).forall((n:String) => n == "-")) return true
    }

    else {
      var headNeighbours = boat.head.getNeighbours(boardSize)
      var lastNeighbours = boat.last.getNeighbours(boardSize)

      //Check for horizontal boat (Head -> left tile = water, right tile = boat)(Last -> left tile = boat, right tile = water)
      if (headNeighbours(2) == "-" && headNeighbours(0) == "S"
        && lastNeighbours(0) == "-" && lastNeighbours(2) == "S") return true

      //Check for vertical boat (Head -> upper tile = water, lower tile = boat)(Last -> upper tile = boat, lower tile = water)
      if (headNeighbours(3) == "-" && headNeighbours(1) == "S"
        && lastNeighbours(1) == "-" && lastNeighbours(3) == "S") return true
    }
    false
  }

  def isBoatFinished(boat:List[Square], boardSize:Int): Boolean ={
    //Check for boat of size 1 (one boat-tile is surrounded by water)
    if(boat.length == 1){
      if(boat.head.getNeighbours(boardSize).forall((n:String) => n == "-")) return true
    }

    else {
      var headNeighbours = boat.head.getNeighbours(boardSize)
      var lastNeighbours = boat.last.getNeighbours(boardSize)

      //Check for horizontal boat (Head -> left tile = water, right tile = boat)(Last -> left tile = boat, right tile = water)
      if (headNeighbours(2) == "-" && headNeighbours(0) != "?"
        && lastNeighbours(0) == "-" && lastNeighbours(2) != "?") return true

      //Check for vertical boat (Head -> upper tile = water, lower tile = boat)(Last -> upper tile = boat, lower tile = water)
      if (headNeighbours(3) == "-" && headNeighbours(1) != "?"
        && lastNeighbours(1) == "-" && lastNeighbours(3) != "?") return true
    }
    false
  }

  def updateBoatsList(boardSize:Int, ships:List[(Int, Int)]):List[(Int, Int)] = {
    var boat = List[Square]()
    var boat2 = List[Square]()
    var updatedShips = ships

    //Horizontal boats
    for(row <- 1 to boardSize) {
      val line = getAllFromY(row)
      for (i <- 1 to boardSize) {
        if (getAllFromY(row).filter((s: Square) => s.x == i).head.possibleValues.head == "S") {
          boat2 = boat2 :+ line.filter((s:Square) => s.x == i).head
        }
        else {
          if(boat2.length > boat.length){
            boat = boat2
            if(isBoatBuilt(boat, boardSize)) {
              if(!boatsList.contains(boat)) {
                boatsList = boatsList :+ boat
                updatedShips = decrementBoats(boat.length, updatedShips)
              }
            }
            boat = List[Square]()
            boat2 = List[Square]()
          }
        }
      }
    }

    boat = List[Square]()
    boat2 = List[Square]()

    //Vertical boats
    for(col <- 1 to boardSize) {
      val line = getAllFromX(col)
      for (i <- 1 to boardSize) {
        if (getAllFromX(col).filter((s: Square) => s.y == i).head.possibleValues.head == "S") {
          boat2 = boat2 :+ line.filter((s:Square) => s.y == i).head
        }
        else {
          if(boat2.length > boat.length){
            boat = boat2
            if(isBoatBuilt(boat, boardSize)) {
              if(!boatsList.contains(boat)) {
                boatsList = boatsList :+ boat
                updatedShips = decrementBoats(boat.length, updatedShips)
              }
            }
            boat = List[Square]()
            boat2 = List[Square]()
          }
        }
      }
    }
    updatedShips
  }

  def getHints(hintLine:String):List[Int] = {
    var hint = List[Int]()
    for(i <- 0 until hintLine.length){
      if(hintLine.charAt(i) == ' '){
        hint = hint ::: List(hintLine.charAt(i+1).toString.toInt)
      }
    }
    hint
  }

  def waterZeros(verticalHints:List[Int], horizontalHints:List[Int], size:Int):Unit = {
    horizontalHints.foreach(hint => if(hint == 0) getAllFromX(horizontalHints.indexOf(hint)+1).foreach(u => setValue(u.x, u.y,"-")))
    verticalHints.foreach(hint => if(hint == 0) getAllFromY(verticalHints.indexOf(hint)+1).foreach(u => setValue(u.x, u.y,"-")))
  }

  def fillAroundHints():Unit={
    allSquares.filter(_.possibleValues.length==1).foreach(k=> k.possibleValues.head match {
      case "*" => {
        allSquares.filter((b: Square) => (b.y == k.y - 1 && (b.x == k.x - 1 || b.x == k.x || b.x == k.x + 1)) || (b.y == k.y + 1 && (b.x == k.x - 1 || b.x == k.x || b.x == k.x + 1)) || (b.y == k.y && (b.x == k.x - 1 || b.x == k.x + 1))).foreach(z => setValue(z.x, z.y, "-"))
        setValue(k.x, k.y, "S")
      }
      case "<" => {
        allSquares.filter((b: Square) => (b.y == k.y - 1 && (b.x == k.x - 1 || b.x == k.x || b.x == k.x + 1)) || (b.y == k.y + 1 && (b.x == k.x - 1 || b.x == k.x || b.x == k.x + 1)) || (b.y == k.y && b.x == k.x - 1)).foreach(z => setValue(z.x, z.y, "-"))
        if(getSquare(k.x+1,k.y).possibleValues.length!=1)setValue(k.x + 1, k.y, "S")
        setValue(k.x, k.y, "S")
      }
      case ">" => {
        allSquares.filter((b: Square) => (b.y == k.y - 1 && (b.x == k.x - 1 || b.x == k.x || b.x == k.x + 1)) || (b.y == k.y + 1 && (b.x == k.x - 1 || b.x == k.x || b.x == k.x + 1)) || (b.y == k.y && b.x == k.x + 1)).foreach(z => setValue(z.x, z.y, "-"))
        if(getSquare(k.x-1,k.y).possibleValues.length!=1)setValue(k.x - 1, k.y, "S")
        setValue(k.x, k.y, "S")
      }
      case "A" => {
        allSquares.filter((b:Square)=> (b.y == k.y-1 && (b.x ==k.x-1||b.x ==k.x || b.x ==k.x+1)) || (b.y ==k.y+1 && (b.x ==k.x-1|| b.x==k.x+1)) || (b.y==k.y && (b.x==k.x-1 || b.x==k.x+1))).foreach(z=>setValue(z.x,z.y,"-"))
        if(getSquare(k.x,k.y+1).possibleValues.length!=1)setValue(k.x, k.y+1, "S")
        setValue(k.x, k.y, "S")
      }
      case "V" => {
        allSquares.filter((b:Square)=> (b.y == k.y-1 && (b.x ==k.x-1|| b.x ==k.x+1)) || (b.y ==k.y+1 && (b.x ==k.x-1||b.x==k.x || b.x==k.x+1)) || (b.y==k.y && (b.x==k.x-1 || b.x==k.x+1))).foreach(z=>setValue(z.x,z.y,"-"))
        if(getSquare(k.x,k.y-1).possibleValues.length!=1)setValue(k.x, k.y-1, "S")
        setValue(k.x, k.y, "S")
      }
      case "+" => allSquares.filter((b:Square)=> (b.y == k.y-1 && (b.x ==k.x-1|| b.x ==k.x+1)) || (b.y ==k.y+1 && (b.x ==k.x-1|| b.x==k.x+1))).foreach(z=>setValue(z.x,z.y,"-"))
      /*{
              allSquares.filter((b:Square)=> (b.y == k.y-1 && (b.x ==k.x-1|| b.x ==k.x+1)) || (b.y ==k.y+1 && (b.x ==k.x-1|| b.x==k.x+1))).foreach(z=>setValue(z.x,z.y,"-"))
              setValue(k.x, k.y, "S")
            }*/
      case "S" => allSquares.filter((b:Square)=> (b.y == k.y-1 && (b.x ==k.x-1|| b.x ==k.x+1)) || (b.y ==k.y+1 && (b.x ==k.x-1|| b.x==k.x+1))).foreach(z=>setValue(z.x,z.y,"-"))
      case "-" =>
    })
  }

  def checkPlus(k:Square)={
    if(getSquare(k.x,k.y-1).possibleValues== List("-") || getSquare(k.x,k.y+1).possibleValues== List("-")){
      setValue(k.x+1,k.y,"S")
      setValue(k.x-1,k.y,"S")
      setValue(k.x,k.y,"S")
    }
    else if (getSquare(k.x+1,k.y).possibleValues== "-" || getSquare(k.x-1,k.y).possibleValues== "-"){
      setValue(k.x,k.y+1,"S")
      setValue(k.x,k.y-1,"S")
      setValue(k.x,k.y,"S")
    }
  }


  // Fills water in the corner squares of each boat
  def waterCorners():Unit = {
    allSquares.filter(_.possibleValues.head == "S").foreach(k => k.possibleValues.head match {
      case "S" => allSquares.filter((b:Square) => (b.y == k.y-1 && (b.x ==k.x-1|| b.x ==k.x+1)) || (b.y ==k.y+1 && (b.x ==k.x-1|| b.x==k.x+1))).foreach(z=>setValue(z.x,z.y,"-"))
      case _ =>
    })
  }

  def checkBoatsXY(horizontal:List[Int], vertical:List[Int], size:Int):Unit = {
    for (i <- 0 until size) {
      if (getAllFromX(i + 1).filter(_.possibleValues.length == 1).count(_.possibleValues.head != "-") == horizontal(i)) {
        getAllFromX(i + 1).filter(_.possibleValues.length != 1).foreach(u => setValue(u.x, u.y, "-"))
      } else if (horizontal(i) - getAllFromX(i + 1).count(_.possibleValues.head == "S") == getAllFromX(i + 1).count(_.possibleValues.length != 1)){
        getAllFromX(i + 1).filter(_.possibleValues.length != 1).foreach(u => setValue(u.x, u.y, "S"))
      }

      if (getAllFromY(i + 1).filter(_.possibleValues.length == 1).count(_.possibleValues.head != "-") == vertical(i)) {
        getAllFromY(i + 1).filter(_.possibleValues.length != 1).foreach(u => setValue(u.x, u.y, "-"))
      } else if (vertical(i) - getAllFromY(i + 1).count(_.possibleValues.head == "S") == getAllFromY(i + 1).count(_.possibleValues.length != 1)) {
        getAllFromY(i + 1).filter(_.possibleValues.length != 1).foreach(u => setValue(u.x, u.y, "S"))
      }
    }
  }

  def checkIfSolved():Boolean = {
    allSquares.forall(_.s)
  }

  def printToFile(solved:String):Unit = {
    val out = new BufferedWriter(new FileWriter(new File("puzzle_solved.txt")))

    out.write(solved)
    out.close()
  }

  def fillOnebyOneSquares(size:Int): Unit ={
    allSquares.filter(_.possibleValues.length==2).filter(_.getNeighbours(size)==List("-","-","-","-")).foreach(i=>setValue(i.x,i.y,"-"))
  }

  def fillBydecreasingsize(boardSize:Int,currentround:Int,boats:List[Tuple2[Int,Int]],currentsize:Tuple2[Int,Int]): Unit ={
    var boat = List[Square]()
    var boat2 = List[Square]()


    for(row <- 1 to boardSize) {
      val line = getAllFromY(row)
      for (i <- 1 to boardSize) {
        if (getAllFromY(row).filter((s: Square) => s.x == i).head.possibleValues.head == "S") {
          boat2 = boat2 :+ line.filter((s:Square) => s.x == i).head
        }
        else {
          if(boat2.length > boat.length){
            boat = boat2
            if(isBoatFinished(boat, boardSize)) {
              if(boat.head.x-1!=0) {
                setValue(boat.head.x - 1,boat.head.y, "-")
              }
              if(boat.last.x+1<=boardSize){
                setValue(boat.last.x + 1,boat.last.y, "-")

              }
              }
            boat = List[Square]()
            boat2 = List[Square]()
          }
        }
      }
    }

    boat = List[Square]()
    boat2 = List[Square]()

    //Vertical boats
    for(col <- 1 to boardSize) {
      val line = getAllFromX(col)
      for (i <- 1 to boardSize) {
        if (getAllFromX(col).filter((s: Square) => s.y == i).head.possibleValues.head == "S") {
          boat2 = boat2 :+ line.filter((s:Square) => s.y == i).head
        }
        else {
          if(boat2.length > boat.length){
            boat = boat2
            if(isBoatFinished(boat, boardSize)) {
              if(boat.head.y-1>0) {
                setValue(boat.head.x, boat.head.y-1, "-")
              }
              if(boat.last.y+1<=boardSize){
                setValue(boat.head.x,boat.last.y + 1, "-")
              }
            }
            boat = List[Square]()
            boat2 = List[Square]()
          }
        }
      }
    }
      //fill currentsize-1's
    if(currentsize._2==2){
      return
    }
    fillBydecreasingsize(boardSize,currentround+1,boats,boats(boats.length-currentround-1))
    return

  }

  def mainSolver(path:String):Unit = {
    val lines = Source.fromFile(path).getLines.toList
    var smolLines = lines
    val puzzleAmount = lines(0).charAt(8).toString.toInt
    var solved = "Puzzles " + puzzleAmount +"\n"
    var currentBoard = List[Square]()
    var lastBoard = List[Square]()
    var updatedShips = List[(Int, Int)]()
    var bruteforceFlag = true

    smolLines = smolLines.drop(1)

    for(i <- 0 until puzzleAmount){ //one loop is one puzzle solving sequence

      smolLines = smolLines.drop(1)
      val ships = getShips(smolLines.head)
      smolLines = smolLines.drop(1)
      val horizontalHints = getHints(smolLines.head)
      smolLines = smolLines.drop(1)
      val verticalHints = getHints(smolLines.head)
      val size = verticalHints.length
      smolLines = smolLines.drop(1)
      smolLines = smolLines.drop(1)

      for (y <- 0 until size) {
        var boatline = smolLines.head.filter(_ != ' ')

        for (x <- 0 until size) {
          if (boatline.charAt(x) != '?') {
            allSquares = allSquares ::: List(new Square(x + 1, y + 1, List(boatline.charAt(x).toString), true))
          } else {
            allSquares = allSquares ::: List(new Square(x + 1, y + 1))
          }
        }
        smolLines = smolLines.drop(1)
      }

      currentBoard = allSquares
      updatedShips = ships

      /*****************************************************************************************************************/

      def printTempSolution():Unit = {
        print("   ")
        horizontalHints.foreach((h:Int) => print(h + " "))
        println()
        for(y <- 1 to size){
          print(verticalHints(y-1) + "  ")
          for(x <- 1 to size){
            if(getSquare(x,y).possibleValues.length > 1) print("? ")
            else print(getSquare(x,y).possibleValues.head + " ")
          }
          println()
        }
        println()
      }

      printTempSolution() // Original puzzle
      fillAroundHints()
      waterZeros(verticalHints, horizontalHints, size)
      printTempSolution()

      while (!checkIfSolved()) {
        lastBoard = currentBoard
        checkBoatsXY(horizontalHints, verticalHints, size)
        waterCorners()
        printTempSolution()
        currentBoard = allSquares



        for(x <- 1 to size){
          for(y <- 1 to size){
            if(getSquare(x,y).possibleValues==List("+")) {
              checkPlus(getSquare(x, y))
            }
          }
        }

        updatedShips = updateBoatsList(size, updatedShips)


        if(updatedShips.head._2==1 && updatedShips.head._1==0){
          fillOnebyOneSquares(size)
        }
        if(updatedShips.last._1==0){
          fillBydecreasingsize(size,0,updatedShips,updatedShips.last)
        }


        if(currentBoard == lastBoard) {

          println("I AM STUCK PLEASE HELP")
          if(bruteforceFlag) updatedShips = bruteforceParty(updatedShips, horizontalHints, verticalHints)
          unsolvedSquares = updateUnsolved()
        }
      }

      /****************************************************************************************************************/

      updatedShips = updateBoatsList(size, updatedShips)
      println("Ships: " + ships)
      println("Updated: " + updatedShips)
      println("Vertical: " + verticalHints)
      println("Horizontal: " + horizontalHints)

      solved += "Size " + size + "x" + size + "\n"

      for(y <- 1 to size) {
        for(x <- 1 to size){
          solved += getSquare(x,y).possibleValues.head + " "
          print(getSquare(x,y).possibleValues.head + " ")
        }
        solved += "\n"
        println()
      }

      //println(size)
      allSquares = List[Square]()
      boatsList = List[List[Square]]()
      println("\n")
    }

    printToFile(solved)
  }

  mainSolver("puzzle_unsolved.txt")

}