import java.io.{File, PrintWriter}

object HitoriSolver {

  class Square(_num:Int, _x:Int, _y:Int,  _white:Boolean = true, _solved:Boolean = false) {
    val num = _num;
    val x = _x;
    val y = _y;
    val white:Boolean = _white;
    val solved:Boolean = _solved;

    override def toString():String = {
      val tall = if (num > 9) num else "0"+num
      //"Num: " + num + " x: " + x + " y: " + y + " White: " + white + " Solved: " + solved;
      if (solved){
        if (white) ":" + tall + ":"
        else "|" + tall + "|"
      }else " " + tall + " ";
    }

    def setColor(b:Boolean):Square = new Square(num, x, y, b, true);
    def isWhite():Boolean = solved && white;
    def isBlack():Boolean = solved && !white;
    def isUnsolved():Boolean = !solved;
  }

  class Board(_list:List[Square], _unsolved:List[Square], _whites:List[Square], _blacks:List[Square]) {
    //Save lists instead of filter allSquares to reduce computation times.
    val allSquares:List[Square] = _list;
    val unsolved = _unsolved;
    val whites =  _whites;
    val blacks = _blacks;
    val size:Int = Math.sqrt(_list.length).toInt;

    //Solve a square and return new board with this changed square
    def setColor(x:Int, y:Int, b:Boolean):Board = {
        println("Setting square (" + x + "," + y + ") to " + (if (b) "White" else "Black"));
        val without = allSquares.filterNot((s:Square) => s.x==x && s.y==y);
        val solvedSquare = getSquare(x,y).setColor(b);
        val newUnsolved = this.unsolved.filterNot((s:Square) => s.x==x && s.y==y);
        val newWhites = if (b) this.whites :+ solvedSquare else this.whites;
        val newBlacks = if (!b) this.blacks :+ solvedSquare else this.blacks;
        new Board(without :+ solvedSquare, newUnsolved, newWhites, newBlacks);
    }

    //Grabs a square from allSquares at a specified location
    def getSquare(x:Int, y:Int):Square = {
      allSquares.filter((s:Square) => s.x==x && s.y==y)(0);
    }

    //Gets an ordered list of all squares in row from x=0 until size from the unordered list of squares allSquares.
    def getRow(row:Int):List[Square] = {
      val list = for{ y<-(0 until size).toList; x<-(0 until size).toList if y==row } yield getSquare(x,y);
      return list;
    }
    //Gets an ordered list of all squares in col from x=0 until size from the unordered list of squares allSquares.
    def getCol(col:Int):List[Square] = {
      val list = for{ y<-(0 until size).toList; x<-(0 until size).toList if x==col } yield getSquare(x,y);
      return list;
    }

    def getUnsolved():List[Square] = unsolved;
    def getWhites():List[Square] = whites;
    def getBlacks():List[Square] = blacks;

    def whiteCheck():Boolean = {
      val whitesRow = for(i<- (0 until this.size).toList) yield this.getRow(i).filter( x=> x.isWhite() );
      val whitesCol = for(i<- (0 until this.size).toList) yield this.getCol(i).filter( x=> x.isWhite() );

      def checks(s:List[List[Square]]):Boolean = {
        for(i <- s){
          val check = i.filter(x => i.exists(y => y.num == x.num && !y.equals(x)));
          if(check.length > 0) return false;
        }
        return true;
      }
      return checks(whitesCol) && checks(whitesRow);
    }

    def blackCheck():Boolean = {
      for(black<-this.blacks){
        val x = black.x;
        val y = black.y;
        //Neighbours also black? If so return incorrect (false)
        if (x+1 < this.size && this.getSquare(x+1, y).isBlack()) return false;
        if (x-1 >= 0        && this.getSquare(x-1, y).isBlack()) return false;
        if (y+1 < this.size && this.getSquare(x, y+1).isBlack()) return false;
        if (y-1 >= 0        && this.getSquare(x, y-1).isBlack()) return false;
      }
      return true;
    }

    def checkConnected(s:Square):Boolean = {
      //TODO
      val list = countWhiteFromSquare(s, List());
      return (list.length == (whites.length + unsolved.length));
    }

    def countWhiteFromSquare(s:Square, list:List[Square]):List[Square] = {
      if (s.isBlack()) return list;
      if (list.exists(s equals _)) return list;
      val newList = list :+ s;
      val a1 = if (s.x+1 < size) countWhiteFromSquare(getSquare(s.x+1, s.y), newList) else newList;
      val a2 = if (s.x-1 >=0)    countWhiteFromSquare(getSquare(s.x-1, s.y), a1) else a1;
      val a3 = if (s.y+1 < size) countWhiteFromSquare(getSquare(s.x, s.y+1), a2) else a2;
      val a4 = if (s.y-1 >=0)    countWhiteFromSquare(getSquare(s.x, s.y-1), a3) else a3;
      return a4;
    }


    //Checks if this board has not broken any of the following rules
    //1) All whites must be connected
    //2) Cannot be two whites on a row/col
    //3) Cannot be two blacks connected
    def correct():Boolean = {
      return checkConnected((whites:::unsolved)(0)) && whiteCheck() && blackCheck();
    }

    def printBoard = {
      println("");
      for(y<-0 until size){
        for (x<-0 until size){
          print(getSquare(x, y));
        }
        println("");
      }
      println("");
    }
  }

  object Patterns {

    //optimize with list of greys and only check this list instead of whole allSquares list
    def resolveGray(b:Board):Board = {
      for(s<-b.getUnsolved()){
        val row = b.getRow(s.y);
        val col = b.getCol(s.x);
        if (row.filter(x => x.num==s.num && !x.isBlack()).length < 2 && col.filter(x => x.num==s.num && !x.isBlack()).length < 2){
          return b.setColor(s.x, s.y, true);
        }
      }
      return b;
    }

    def resolveWhite(b:Board):Board = {
      for(white<-b.whites){
        val row = b.getRow(white.y);
        val col = b.getCol(white.x);
        val equalNums = (row ::: col).filter((s:Square) => !s.solved && s.num == white.num)
        if (equalNums.length > 0){
          val e = equalNums(0);
          return b.setColor(e.x, e.y, false);
        }
      }
      return b;
    }

    /**
     * Should be optimized so only black are checked from a list instead of all the squares in allSquares list
     */
    def resolveBlack(b:Board):Board = {
      for(s<-b.blacks){
        val x = s.x;
        val y = s.y;
        if (x+1 < b.size && !b.getSquare(x+1, y).solved) return b.setColor(x+1, y, true);
        if (x-1 >= 0     && !b.getSquare(x-1, y).solved) return b.setColor(x-1, y, true);
        if (y+1 < b.size && !b.getSquare(x, y+1).solved) return b.setColor(x, y+1, true);
        if (y-1 >= 0     && !b.getSquare(x, y-1).solved) return b.setColor(x, y-1, true);
      }
      return b;
    }

    def middleOfTwo(b:Board):Board = {
      for(y<- 0 until b.size){
        val row = b.getRow(y);
        val index = _middleOfTwoPattern(row, true);
        if (index >= 0) return b.setColor(index, y, true);
      }
      for(x<- 0 until b.size){
        val col = b.getCol(x);
        val index = _middleOfTwoPattern(col, false);
        if (index >= 0) return b.setColor(x, index, true);
      }
      return b;
    }

    def _middleOfTwoPattern(list:List[Square], isRow:Boolean):Int = {
      list match {
        case (a :: rest) => rest match {
          case (b :: c :: other)  if (a.num==c.num && !b.solved) => if (isRow) b.x else b.y;
          case _ => _middleOfTwoPattern(rest, isRow);
        }
        case _ => -1;
      }
    }

    def matchingTwo(b:Board):Board = {
      for(y<- 0 until b.size){
        val row = b.getRow(y);
        val index = _matchingTwoPattern(row, true);
        if (index >= 0){
          val s = b.getSquare(index, y);
          val toBlackOut = row.filter((a:Square) => !a.solved && a.num==s.num && a.x != s.x && a.x != s.x+1);
          if (toBlackOut.length > 0) return b.setColor(toBlackOut(0).x, toBlackOut(0).y, false);
        }
      }
      for(x<- 0 until b.size){
        val col = b.getCol(x);
        val index = _matchingTwoPattern(col, false);
        if (index >= 0){
          val s = b.getSquare(x, index);
          val toBlackOut = col.filter((a:Square) => !a.solved && a.num==s.num && a.y != s.y && a.y != s.y+1);
          if (toBlackOut.length > 0) return b.setColor(toBlackOut(0).x, toBlackOut(0).y, false);
        }
      }
      return b;
    }
    //TODO
    //do recurive and return list of all equal stuffs
    def _matchingTwoPattern(list:List[Square], isRow:Boolean):Int = {
      list match {
        case (a :: rest) => rest match {
          case (b :: other) if (a.num==b.num) => if (isRow) a.x else a.y;
          case _  => _matchingTwoPattern(rest, isRow);
        }
        case _  => -1;
      }
    }

    //TODO
    //works for only the coloums atm and only for the first equal numbers in each coloum.
    def matchingTwoDiagonal(b:Board):Board = {
      for(x<-0 until b.size){
        val col = b.getCol(x);
        val index = _matchingTwoPattern(col, false);
        if (index >= 0){
          val square = b.getSquare(x, index);
          val row = b.getRow(index);
          for(s<-row){
            if ((square.x!=s.x || square.y!=s.y) && square.num==s.num){
               if (s.x-1 >= 0){
                 val diagSquare1 = b.getSquare(s.x-1, s.y+1);
                 if (diagSquare1.x != square.x && diagSquare1.num==s.num){
                   if (!b.getSquare(s.x-1, s.y).solved) return b.setColor(s.x-1, s.y, true);
                   if (!b.getSquare(s.x, s.y+1).solved) return b.setColor(s.x, s.y+1, true);
                 }
               }
               if (s.x+1 < b.size){
                 val diagSquare2 = b.getSquare(s.x+1, s.y+1);
                 if (diagSquare2.x != square.x && diagSquare2.num==s.num){
                   if (!b.getSquare(s.x+1, s.y).solved) return b.setColor(s.x+1, s.y, true);
                   if (!b.getSquare(s.x, s.y+1).solved) return b.setColor(s.x, s.y+1, true);
                 }
               }
            }
          }
        }

      }
      return b;
    }

    /*def _matchingTwoDiagonal(list:List[Square], list2:List[Square], isRow:Boolean):Int = {

    }*/

  }

  def main(args: Array[String]){
    //TODO
    val inputPath = "puzzleTest.txt"//args(0)
    val outputPath = args(1)
    println(inputPath)
    println(outputPath)

    val puzzleFile = new File(inputPath);

    solvePuzzle(puzzleFile);

    def solvePuzzle(f:File):Unit = {
      val lines = scala.io.Source.fromFile(f).mkString.split("\n");
      val puzzleSize = lines.length;

      // Make list of square objects from numbers in text file
      val allSquares:List[Square] = {
          for(y<-(0 until lines.length).toList; x<-(0 until lines.length).toList)
            yield new Square(lines(y).split(" ")(x).trim().toInt, x, y);
      }

      val startingBoard = new Board(allSquares,allSquares,List(),List());

      startingBoard.printBoard;

      var num:Int = 0;

      //Begin solving from this initial list of squares
      solve(startingBoard, 2).printBoard;

      //println("Num grey: " + solve(startingBoard, 0).allSquares.filter(!_.solved).length);

      /*
       * Not making any new variables, but solving with new boards recursively to fulfill function requirement.
       * Steps through several "patterns" to approach the solution
       * and then bruteforsly checks every single possibility in the end to find the unique solution.
       */
      def solve(b:Board, pat:Int):Board = {
        b.printBoard;
        num = num + 1;
        println("This is the " + num + " time we run solve");
        //If the board is correct
          //PATTERN 0: Numbers between two other equal numbers are white (ex: 343, where 4 is white)
          if (pat==0){
            /*val b1 = Patterns.middleOfTwo(b);
            if (!b1.equals(b)) return solve(b1, pat);
            else return solve(b1, pat+1);*/
          }else if (pat==1){
            /*val b1 = Patterns.matchingTwo(b);
            if (!b1.equals(b)) return solve(b1, pat);
            else return solve(b1, pat+1);*/
          }else if (pat==2){
            val b1 = Patterns.matchingTwoDiagonal(b);
            if (!b1.equals(b)) return solve(b1, pat);
            else return solve(b1, pat+1);
          }else if (pat==3){
            return solve(b, pat+1);
          }else if (pat==4){
            /*val b1 = Patterns.resolveWhite(b);
            if (!b1.equals(b)) return solve(b1, pat);
            else {
              val b2 = Patterns.resolveBlack(b1);
              if (!b2.equals(b1)) return solve(b2, pat);
              else return solve(b2, pat+1);
            }*/
          }else if (pat==5){
            //Only check the greys as sander said... is faster as sonic x
            /*val b1 = Patterns.resolveGray(b);
            if (!b1.equals(b)) return solve(b1, pat);
            else return solve(b1, pat+1);*/
          }

          /*
          for (un<-b.getUnsolved()){
            println("Im guessing that (" + un.x + "," + un.y + ") is black");
            b.setColor(un.x, un.y, false).printBoard;
            val newBoard = solve(b.setColor(un.x, un.y, false), 2);
            println("This becomes: ");
            newBoard.printBoard;
            if (!newBoard.correct()){
              println("Error it cannot be black");
              return solve(b.setColor(un.x, un.y, true), 2);
            }
          }*/

          /*
          //Bruteforce
          val numUnsolved = b.getUnsolved().length;
          for(i<-0 until numUnsolved){
            val bb = Patterns.bruteforce(b, i).correct();
            if (bb.correct()) return bb;
          }
          */
          return b;
      }
    }
  }

  def outputSolution(outputPath:String) = {
    var outputFile = new PrintWriter( new File(outputPath) , "UTF-8")

    outputFile.println("");

    outputFile.close()
  }
}