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):Unit = {
      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
    }

  }

  //Global variables
  //TODO: Minimize these
  var allSquares = List[Square]()
  var unsolvedSquares = List[Square]()
  var boatsList = List[List[Square]]()
  var savedShips = List[(Int, Int)]()

  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 {
        println("Already placed all boats of size " + size)
        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 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, "built")) return false
    }
    */

    true
  }


  def bruteforceParty(changeSquare:Int, boats:List[(Int, Int)], horizontalHints:List[Int], verticalHints:List[Int]):List[(Int, Int)] = {
    println("Arrived at the bruteforce party")
    unsolvedSquares = getUnsolved

    if(unsolvedSquares.isEmpty) return boats

    val x = unsolvedSquares(changeSquare).x
    val y = unsolvedSquares(changeSquare).y

    //Change the first square in unsolvedSquare, set it to value "boat"
    val chosen = allSquares.filter((s:Square) => getSquare(s.x, s.y) == unsolvedSquares.head)
    chosen.head.setValues("S")
    if(!allowedMove(horizontalHints, verticalHints)) {
      println("Not allowed")
      chosen.head.removeValue("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)
    println(updatedShips)

    updatedShips
  }


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

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

  def isBoatBuilt(boat:List[Square], boardSize:Int, usage:String):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 {
      val headNeighbours = boat.head.getNeighbours(boardSize)
      val lastNeighbours = boat.last.getNeighbours(boardSize)

      if (usage == "built") {
        //Check for horizontal boat
        //Head -> left tile = water, right tile = boat
        //Last -> left tile = boat, right tile = water
        if (headNeighbours(2) == "-" && headNeighbours.head == "S"
          && lastNeighbours(2) == "S" && lastNeighbours.head == "-") 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(3) == "S" && lastNeighbours(1) == "-") return true

      } else if (usage == "finished") {
        //Horizontal
        if (headNeighbours(2) == "-" && headNeighbours.head != "?"
          && lastNeighbours(2) != "?" && lastNeighbours.head == "-") return true

        //Vertical
        if (headNeighbours(3) == "-" && headNeighbours(1) != "?"
          && lastNeighbours(3) != "?" && lastNeighbours(1) == "-") return true
      }
    }
    false
  }

  //TODO: Comment this function
  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 (line.filter((s: Square) => s.x == i).head.possibleValues.head == "S") {
          boat2 = boat2 :+ line.filter((s:Square) => s.x == i).head
          if(row == boardSize && i == boardSize){
            if(boat2.length > boat.length){
              boat = boat2
              if(isBoatBuilt(boat, boardSize, "built")) {
                if(!boatsList.contains(boat)) {
                  updatedShips = decrementBoats(boat.length, updatedShips)
                  boatsList = boatsList :+ boat
                }
              }
            }
          }
        }
        else {
          if(boat2.length > boat.length){
            boat = boat2
            if(isBoatBuilt(boat, boardSize, "built")) {
              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 (line.filter((s: Square) => s.y == i).head.possibleValues.head == "S") {
          boat2 = boat2 :+ line.filter((s:Square) => s.y == i).head
          if(col == boardSize && i == boardSize){
            if(boat2.length > boat.length){
              boat = boat2
              if(isBoatBuilt(boat, boardSize, "built")) {
                if(!boatsList.contains(boat)) {
                  boatsList = boatsList :+ boat
                  updatedShips = decrementBoats(boat.length, updatedShips)
                }
              }
            }
          }
        }
        else {
          if(boat2.length > boat.length){
            boat = boat2
            if(isBoatBuilt(boat, boardSize, "built")) {
              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,"-"))
      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 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[(Int, Int)], currentSize:(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 (line.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, "finished")) {
              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 (line.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, "finished")) {
              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))

  }

  def checkPlus(k:Square):Unit={
    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 == List("-") || getSquare(k.x-1,k.y).possibleValues == List("-")){
      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(ships:List[(Int, Int)]):Boolean = {
    allSquares.forall(_.s) && ships.forall(_._1 == 0)
  }

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

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

  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 bruteForceTries = 1
    var bfInnerLoop = 0
    var bfFlag = true
    var savedBoard = List[Square]()

    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()
      }

      def printSavedBoard():Unit = {
        for(y <- 1 to size){
          for(x <- 1 to size){
            if(savedBoard.filter((k:Square) => k.x == x && k.y == y).head.possibleValues.length > 1) print("? ")
            else print(savedBoard.filter((k:Square) => k.x == x && k.y == y).head.possibleValues.head + " ")
          }
          println()
        }
        println()
      }

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

      while (!checkIfSolved(updatedShips)) {
        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 all boats of size 0 has been placed, fill all empty 1x1-squares with water
        //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(bfFlag){
            savedBoard = currentBoard
            savedShips = updatedShips

            println("------------------------------------Saved board and ships")
            printSavedBoard()
            bfFlag = false
          }
          updatedShips = bruteforceParty(bfInnerLoop, updatedShips, horizontalHints, verticalHints)
          println("Bruteforce inner loop: " + bfInnerLoop)
          println("--------------------------------------Saved board is now:")
          printSavedBoard()
          bfInnerLoop += 1
        }


        if(allSquares.forall(_.possibleValues.length == 1) && !checkIfSolved(updatedShips)){

          println("--------------------------------------Loaded board and ships")
          printSavedBoard()

          printTempSolution()
          allSquares = savedBoard
          updatedShips = savedShips
          bfInnerLoop = 0
          bruteForceTries += 1

        }

        println("Bruteforce tries: " + bruteForceTries)

      }

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


      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")

}