• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
46%
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