SHARE
TWEET

Untitled

a guest Sep 13th, 2017 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.{File, PrintWriter}
  2.  
  3. object HitoriSolver {
  4.  
  5.   class Square(_num:Int, _x:Int, _y:Int,  _white:Boolean = true, _solved:Boolean = false) {
  6.     val num = _num;
  7.     val x = _x;
  8.     val y = _y;
  9.     val white:Boolean = _white;
  10.     val solved:Boolean = _solved;
  11.    
  12.     override def toString():String = {
  13.       val tall = if (num > 9) num else "0"+num
  14.       //"Num: " + num + " x: " + x + " y: " + y + " White: " + white + " Solved: " + solved;
  15.       if (solved){
  16.         if (white) ":" + tall + ":"
  17.         else "|" + tall + "|"
  18.       }else " " + tall + " ";
  19.     }
  20.    
  21.     def setColor(b:Boolean):Square = new Square(num, x, y, b, true);    
  22.     def isWhite():Boolean = solved && white;
  23.     def isBlack():Boolean = solved && !white;
  24.     def isUnsolved():Boolean = !solved;
  25.   }
  26.  
  27.   class Board(_list:List[Square], _unsolved:List[Square], _whites:List[Square], _blacks:List[Square]) {
  28.     //Save lists instead of filter allSquares to reduce computation times.
  29.     val allSquares:List[Square] = _list;
  30.     val unsolved = _unsolved;
  31.     val whites =  _whites;
  32.     val blacks = _blacks;
  33.     val size:Int = Math.sqrt(_list.length).toInt;
  34.    
  35.     //Solve a square and return new board with this changed square
  36.     def setColor(x:Int, y:Int, b:Boolean):Board = {
  37.         println("Setting square (" + x + "," + y + ") to " + (if (b) "White" else "Black"));
  38.         val without = allSquares.filterNot((s:Square) => s.x==x && s.y==y);
  39.         val solvedSquare = getSquare(x,y).setColor(b);
  40.         val newUnsolved = this.unsolved.filterNot((s:Square) => s.x==x && s.y==y);
  41.         val newWhites = if (b) this.whites :+ solvedSquare else this.whites;
  42.         val newBlacks = if (!b) this.blacks :+ solvedSquare else this.blacks;
  43.         new Board(without :+ solvedSquare, newUnsolved, newWhites, newBlacks);
  44.     }
  45.    
  46.     //Grabs a square from allSquares at a specified location
  47.     def getSquare(x:Int, y:Int):Square = {
  48.       allSquares.filter((s:Square) => s.x==x && s.y==y)(0);
  49.     }
  50.    
  51.     //Gets an ordered list of all squares in row from x=0 until size from the unordered list of squares allSquares.
  52.     def getRow(row:Int):List[Square] = {
  53.       val list = for{ y<-(0 until size).toList; x<-(0 until size).toList if y==row } yield getSquare(x,y);
  54.       return list;
  55.     }
  56.     //Gets an ordered list of all squares in col from x=0 until size from the unordered list of squares allSquares.
  57.     def getCol(col:Int):List[Square] = {
  58.       val list = for{ y<-(0 until size).toList; x<-(0 until size).toList if x==col } yield getSquare(x,y);
  59.       return list;
  60.     }
  61.    
  62.     def getUnsolved():List[Square] = unsolved;
  63.     def getWhites():List[Square] = whites;
  64.     def getBlacks():List[Square] = blacks;
  65.    
  66.     def whiteCheck():Boolean = {
  67.       val whitesRow = for(i<- (0 until this.size).toList) yield this.getRow(i).filter( x=> x.isWhite() );
  68.       val whitesCol = for(i<- (0 until this.size).toList) yield this.getCol(i).filter( x=> x.isWhite() );
  69.      
  70.       def checks(s:List[List[Square]]):Boolean = {
  71.         for(i <- s){
  72.           val check = i.filter(x => i.exists(y => y.num == x.num && !y.equals(x)));
  73.           if(check.length > 0) return false;
  74.         }
  75.         return true;
  76.       }
  77.       return checks(whitesCol) && checks(whitesRow);
  78.     }
  79.    
  80.     def blackCheck():Boolean = {
  81.       for(black<-this.blacks){
  82.         val x = black.x;
  83.         val y = black.y;
  84.         //Neighbours also black? If so return incorrect (false)
  85.         if (x+1 < this.size && this.getSquare(x+1, y).isBlack()) return false;
  86.         if (x-1 >= 0        && this.getSquare(x-1, y).isBlack()) return false;
  87.         if (y+1 < this.size && this.getSquare(x, y+1).isBlack()) return false;
  88.         if (y-1 >= 0        && this.getSquare(x, y-1).isBlack()) return false;
  89.       }
  90.       return true;
  91.     }
  92.    
  93.     def checkConnected(s:Square):Boolean = {
  94.       //TODO
  95.       val list = countWhiteFromSquare(s, List());
  96.       return (list.length == (whites.length + unsolved.length));
  97.     }
  98.    
  99.     def countWhiteFromSquare(s:Square, list:List[Square]):List[Square] = {
  100.       if (s.isBlack()) return list;
  101.       if (list.exists(s equals _)) return list;
  102.       val newList = list :+ s;
  103.       val a1 = if (s.x+1 < size) countWhiteFromSquare(getSquare(s.x+1, s.y), newList) else newList;
  104.       val a2 = if (s.x-1 >=0)    countWhiteFromSquare(getSquare(s.x-1, s.y), a1) else a1;
  105.       val a3 = if (s.y+1 < size) countWhiteFromSquare(getSquare(s.x, s.y+1), a2) else a2;
  106.       val a4 = if (s.y-1 >=0)    countWhiteFromSquare(getSquare(s.x, s.y-1), a3) else a3;
  107.       return a4;
  108.     }
  109.    
  110.    
  111.     //Checks if this board has not broken any of the following rules
  112.     //1) All whites must be connected
  113.     //2) Cannot be two whites on a row/col
  114.     //3) Cannot be two blacks connected
  115.     def correct():Boolean = {
  116.       return checkConnected((whites:::unsolved)(0)) && whiteCheck() && blackCheck();
  117.     }
  118.    
  119.     def printBoard = {
  120.       println("");
  121.       for(y<-0 until size){
  122.         for (x<-0 until size){
  123.           print(getSquare(x, y));
  124.         }
  125.         println("");
  126.       }
  127.       println("");
  128.     }
  129.   }
  130.  
  131.   object Patterns {
  132.    
  133.     //optimize with list of greys and only check this list instead of whole allSquares list
  134.     def resolveGray(b:Board):Board = {
  135.       for(s<-b.getUnsolved()){
  136.         val row = b.getRow(s.y);
  137.         val col = b.getCol(s.x);
  138.         if (row.filter(x => x.num==s.num && !x.isBlack()).length < 2 && col.filter(x => x.num==s.num && !x.isBlack()).length < 2){
  139.           return b.setColor(s.x, s.y, true);
  140.         }
  141.       }
  142.       return b;
  143.     }
  144.    
  145.     def resolveWhite(b:Board):Board = {
  146.       for(white<-b.whites){
  147.         val row = b.getRow(white.y);
  148.         val col = b.getCol(white.x);
  149.         val equalNums = (row ::: col).filter((s:Square) => !s.solved && s.num == white.num)
  150.         if (equalNums.length > 0){
  151.           val e = equalNums(0);
  152.           return b.setColor(e.x, e.y, false);
  153.         }
  154.       }
  155.       return b;
  156.     }
  157.    
  158.     /**
  159.      * Should be optimized so only black are checked from a list instead of all the squares in allSquares list
  160.      */
  161.     def resolveBlack(b:Board):Board = {
  162.       for(s<-b.blacks){
  163.         val x = s.x;
  164.         val y = s.y;
  165.         if (x+1 < b.size && !b.getSquare(x+1, y).solved) return b.setColor(x+1, y, true);
  166.         if (x-1 >= 0     && !b.getSquare(x-1, y).solved) return b.setColor(x-1, y, true);
  167.         if (y+1 < b.size && !b.getSquare(x, y+1).solved) return b.setColor(x, y+1, true);
  168.         if (y-1 >= 0     && !b.getSquare(x, y-1).solved) return b.setColor(x, y-1, true);
  169.       }
  170.       return b;
  171.     }
  172.    
  173.     def middleOfTwo(b:Board):Board = {
  174.       for(y<- 0 until b.size){
  175.         val row = b.getRow(y);
  176.         val index = _middleOfTwoPattern(row, true);
  177.         if (index >= 0) return b.setColor(index, y, true);
  178.       }
  179.       for(x<- 0 until b.size){
  180.         val col = b.getCol(x);
  181.         val index = _middleOfTwoPattern(col, false);
  182.         if (index >= 0) return b.setColor(x, index, true);
  183.       }
  184.       return b;
  185.     }
  186.    
  187.     def _middleOfTwoPattern(list:List[Square], isRow:Boolean):Int = {
  188.       list match {
  189.         case (a :: rest) => rest match {
  190.           case (b :: c :: other)  if (a.num==c.num && !b.solved) => if (isRow) b.x else b.y;
  191.           case _ => _middleOfTwoPattern(rest, isRow);
  192.         }
  193.         case _ => -1;
  194.       }
  195.     }
  196.    
  197.     def matchingTwo(b:Board):Board = {
  198.       for(y<- 0 until b.size){
  199.         val row = b.getRow(y);
  200.         val index = _matchingTwoPattern(row, true);
  201.         if (index >= 0){
  202.           val s = b.getSquare(index, y);
  203.           val toBlackOut = row.filter((a:Square) => !a.solved && a.num==s.num && a.x != s.x && a.x != s.x+1);
  204.           if (toBlackOut.length > 0) return b.setColor(toBlackOut(0).x, toBlackOut(0).y, false);
  205.         }
  206.       }
  207.       for(x<- 0 until b.size){
  208.         val col = b.getCol(x);
  209.         val index = _matchingTwoPattern(col, false);
  210.         if (index >= 0){
  211.           val s = b.getSquare(x, index);
  212.           val toBlackOut = col.filter((a:Square) => !a.solved && a.num==s.num && a.y != s.y && a.y != s.y+1);
  213.           if (toBlackOut.length > 0) return b.setColor(toBlackOut(0).x, toBlackOut(0).y, false);
  214.         }
  215.       }
  216.       return b;
  217.     }
  218.     //TODO
  219.     //do recurive and return list of all equal stuffs
  220.     def _matchingTwoPattern(list:List[Square], isRow:Boolean):Int = {
  221.       list match {
  222.         case (a :: rest) => rest match {
  223.           case (b :: other) if (a.num==b.num) => if (isRow) a.x else a.y;
  224.           case _  => _matchingTwoPattern(rest, isRow);
  225.         }
  226.         case _  => -1;
  227.       }
  228.     }
  229.    
  230.     //TODO
  231.     //works for only the coloums atm and only for the first equal numbers in each coloum.
  232.     def matchingTwoDiagonal(b:Board):Board = {
  233.       for(x<-0 until b.size){
  234.         val col = b.getCol(x);
  235.         val index = _matchingTwoPattern(col, false);
  236.         if (index >= 0){
  237.           val square = b.getSquare(x, index);
  238.           val row = b.getRow(index);
  239.           for(s<-row){
  240.             if ((square.x!=s.x || square.y!=s.y) && square.num==s.num){
  241.                if (s.x-1 >= 0){
  242.                  val diagSquare1 = b.getSquare(s.x-1, s.y+1);
  243.                  if (diagSquare1.x != square.x && diagSquare1.num==s.num){
  244.                    if (!b.getSquare(s.x-1, s.y).solved) return b.setColor(s.x-1, s.y, true);
  245.                    if (!b.getSquare(s.x, s.y+1).solved) return b.setColor(s.x, s.y+1, true);
  246.                  }
  247.                }
  248.                if (s.x+1 < b.size){
  249.                  val diagSquare2 = b.getSquare(s.x+1, s.y+1);
  250.                  if (diagSquare2.x != square.x && diagSquare2.num==s.num){
  251.                    if (!b.getSquare(s.x+1, s.y).solved) return b.setColor(s.x+1, s.y, true);
  252.                    if (!b.getSquare(s.x, s.y+1).solved) return b.setColor(s.x, s.y+1, true);
  253.                  }
  254.                }
  255.             }
  256.           }
  257.         }
  258.        
  259.       }
  260.       return b;
  261.     }
  262.    
  263.     /*def _matchingTwoDiagonal(list:List[Square], list2:List[Square], isRow:Boolean):Int = {
  264.      
  265.     }*/
  266.    
  267.   }
  268.  
  269.   def main(args: Array[String]){
  270.     //TODO
  271.     val inputPath = "puzzleTest.txt"//args(0)
  272.     val outputPath = args(1)
  273.     println(inputPath)
  274.     println(outputPath)
  275.  
  276.     val puzzleFile = new File(inputPath);
  277.    
  278.     solvePuzzle(puzzleFile);
  279.  
  280.     def solvePuzzle(f:File):Unit = {
  281.       val lines = scala.io.Source.fromFile(f).mkString.split("\n");
  282.       val puzzleSize = lines.length;            
  283.      
  284.       // Make list of square objects from numbers in text file
  285.       val allSquares:List[Square] = {
  286.           for(y<-(0 until lines.length).toList; x<-(0 until lines.length).toList)
  287.             yield new Square(lines(y).split(" ")(x).trim().toInt, x, y);
  288.       }
  289.      
  290.       val startingBoard = new Board(allSquares,allSquares,List(),List());
  291.      
  292.       startingBoard.printBoard;
  293.      
  294.       var num:Int = 0;
  295.      
  296.       //Begin solving from this initial list of squares
  297.       solve(startingBoard, 2).printBoard;      
  298.      
  299.       //println("Num grey: " + solve(startingBoard, 0).allSquares.filter(!_.solved).length);
  300.      
  301.       /*
  302.        * Not making any new variables, but solving with new boards recursively to fulfill function requirement.
  303.        * Steps through several "patterns" to approach the solution
  304.        * and then bruteforsly checks every single possibility in the end to find the unique solution.
  305.        */
  306.       def solve(b:Board, pat:Int):Board = {
  307.         b.printBoard;
  308.         num = num + 1;
  309.         println("This is the " + num + " time we run solve");
  310.         //If the board is correct
  311.           //PATTERN 0: Numbers between two other equal numbers are white (ex: 343, where 4 is white)
  312.           if (pat==0){
  313.             /*val b1 = Patterns.middleOfTwo(b);
  314.             if (!b1.equals(b)) return solve(b1, pat);
  315.             else return solve(b1, pat+1);*/
  316.           }else if (pat==1){
  317.             /*val b1 = Patterns.matchingTwo(b);
  318.             if (!b1.equals(b)) return solve(b1, pat);
  319.             else return solve(b1, pat+1);*/
  320.           }else if (pat==2){
  321.             val b1 = Patterns.matchingTwoDiagonal(b);
  322.             if (!b1.equals(b)) return solve(b1, pat);
  323.             else return solve(b1, pat+1);
  324.           }else if (pat==3){
  325.             return solve(b, pat+1);
  326.           }else if (pat==4){
  327.             /*val b1 = Patterns.resolveWhite(b);
  328.             if (!b1.equals(b)) return solve(b1, pat);
  329.             else {
  330.               val b2 = Patterns.resolveBlack(b1);
  331.               if (!b2.equals(b1)) return solve(b2, pat);
  332.               else return solve(b2, pat+1);
  333.             }*/
  334.           }else if (pat==5){
  335.             //Only check the greys as sander said... is faster as sonic x
  336.             /*val b1 = Patterns.resolveGray(b);
  337.             if (!b1.equals(b)) return solve(b1, pat);
  338.             else return solve(b1, pat+1);*/
  339.           }
  340.          
  341.           /*
  342.           for (un<-b.getUnsolved()){
  343.             println("Im guessing that (" + un.x + "," + un.y + ") is black");
  344.             b.setColor(un.x, un.y, false).printBoard;
  345.             val newBoard = solve(b.setColor(un.x, un.y, false), 2);
  346.             println("This becomes: ");
  347.             newBoard.printBoard;
  348.             if (!newBoard.correct()){
  349.               println("Error it cannot be black");
  350.               return solve(b.setColor(un.x, un.y, true), 2);
  351.             }
  352.           }*/
  353.          
  354.           /*
  355.           //Bruteforce
  356.           val numUnsolved = b.getUnsolved().length;
  357.           for(i<-0 until numUnsolved){
  358.             val bb = Patterns.bruteforce(b, i).correct();
  359.             if (bb.correct()) return bb;
  360.           }
  361.           */
  362.           return b;
  363.       }
  364.     }
  365.   }
  366.  
  367.   def outputSolution(outputPath:String) = {
  368.     var outputFile = new PrintWriter( new File(outputPath) , "UTF-8")
  369.    
  370.     outputFile.println("");
  371.      
  372.     outputFile.close()
  373.   }
  374. }
RAW Paste Data
Top