SHARE
TWEET

xd comments 123 idk fam skrr

a guest Sep 21st, 2019 106 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io._
  2. import scala.io.Source
  3.  
  4. object xdxdxd extends App{
  5.   val t1 = System.nanoTime
  6.  
  7.   //{0,0,0,0}
  8.   //top, left, right, down
  9.  
  10.  
  11.   //filene den leser og lagrer dataen
  12.   val unsolved_puzzle_path = "puzzle_unsolved.txt"
  13.   val solved_puzzle_path = "puzzle_solved.txt"
  14.  
  15.  
  16.   //selve løsninga
  17.   val sol =   solveNeighbours(unsolved_puzzle_path);
  18.  
  19.   //printer ut løsninga
  20.   println(sol)
  21.  
  22.   //lagrer løsninga i fila
  23.   writeSolutionToFile(sol, solved_puzzle_path)
  24.  
  25.  
  26.  
  27.   //løsninga
  28.   def solveNeighbours(path:String):String = {
  29.     val lines = Source.fromFile(path).getLines.toList
  30.     val numPuzzles = lines.head
  31.     //println(numPuzzles)
  32.  
  33.  
  34.     //puzzlestart = linja puzzelet starter på. Øker etter at den er ferdig med et puzzle for at den skal bli til linja det neste puzzelet starter
  35.     var puzzlestart = 2;
  36.  
  37.  
  38.     //lagrer hvor mange puzzles det er i fila
  39.     val puzzleamountstring = lines(0)(8).toString
  40.     val puzzleamount = puzzleamountstring.toInt
  41.  
  42.     //sol er linja løsninga lagres i, den som skrives inn i løsningsfila
  43.     var sol = numPuzzles + "\n"
  44.  
  45.  
  46.     //fordi vi har lagra hvor mange puzzles det er i fila, og vi løser et puzzle om ganga, bruker vi for loop til å kjøre den like mange ganger som antall puzzles
  47.     for(puzzles<- 1 to puzzleamount) {
  48.  
  49.       //størrelsen på puzzelet den løser nå
  50.       val sizestring = lines(puzzlestart-1)(5).toString
  51.       val size = sizestring.toInt;
  52.  
  53.  
  54.       //liste som går fra 1 til størrelsen, brukes som x og y verdiene til boksene
  55.       val listeentilsize = List.range(1, size + 1);
  56.  
  57.       //liste som går fra 2 til størrelsen, brukes når man sletter hvis de IKKE er naboer da de med bare 1 forskjell skal bli
  58.       val listeremove = List.range(2, size + 1);
  59.  
  60.  
  61.       //classen for boksene
  62.       class Square(xNumber: Int, yNumber: Int,
  63.                    values: List[Int] = listeentilsize, solved: Boolean = false, neighbours: List[Int] = List(0, 0, 0, 0)) {
  64.  
  65.         val possibleValues = values;
  66.         val x = xNumber;
  67.         val y = yNumber;
  68.         val isSolved = solved;
  69.         val neighbours1 = neighbours;
  70.  
  71.  
  72.         //brukes til å skrive ut en spesifikk boks som en string
  73.         override def toString() = {
  74.           "x:" + xNumber + " y:" + yNumber + " " + possibleValues.mkString(",");
  75.         }
  76.  
  77.         //setter valuen til en boks med å slette den gamle, og lage en ny boks med de nye valuene. endrer ikke bare den eksisterende fordi det må være funksjonell programmering
  78.         def setValue(solution: List[Int], neighbours: List[Int]): Square = {
  79.           var asd = false
  80.           if (solution.length == 1) {
  81.             asd = true
  82.           }
  83.           return new Square(this.x, this.y, solution, asd, neighbours);
  84.         }
  85.  
  86.  
  87.         //fjerner en value fra en boks. ^^^^^^^^^samme som ovenfor
  88.         def removeValue(wrongSolution: Int): Square = {
  89.           val newlist = possibleValues.filter(_ != wrongSolution);
  90.           if (newlist.length == 1) {
  91.             return new Square(this.x, this.y, newlist, solved = true, this.neighbours1);
  92.           }
  93.           return new Square(this.x, this.y, newlist, solved = false, this.neighbours1);
  94.         }
  95.  
  96.       }
  97.  
  98.       //lagrer alle squares i en liste
  99.       var allSquares = List[Square]();
  100.       for (xvalue <- listeentilsize) {
  101.         for (yvalue <- listeentilsize) {
  102.           val s = new Square(xvalue, yvalue);
  103.           allSquares = allSquares :+ s;
  104.         }
  105.       }
  106.  
  107.       //lagrer alle squares med en spesifikk x verdi i en liste
  108.       def getAllFromX(i: Int): List[Square] = {
  109.         return allSquares.filter((s: Square) => s.x == i);
  110.       }
  111.  
  112.       // ^^^^^^^^^^ y verdi
  113.       def getAllFromY(i: Int): List[Square] = {
  114.         //allSquares.filter((s:Square)=>s.y==i);
  115.         allSquares.filter(_.y == i);
  116.  
  117.       }
  118.  
  119.  
  120.       //finner en spesifikk square
  121.       def getSquare(x: Int, y: Int): Square = {
  122.         return allSquares.filter(_.x == x).filter(_.y == y)(0)
  123.       }
  124.  
  125.  
  126.  
  127.       //setvalue igjen, bruker setvalue funskjonen som er inne i boks objektene men oppdaterer også lista for allsquares
  128.       def setValue(x: Int, y: Int, solution: List[Int], neighbours: List[Int]) = {
  129.         var s = getSquare(x, y);
  130.         allSquares = allSquares.filter(_ != s);
  131.         s = s.setValue(solution, neighbours);
  132.         allSquares = allSquares :+ s;
  133.       }
  134.  
  135.       //^^^^^^^^^^ removevalue
  136.       def removeValue(x: Int, y: Int, wrongSolution: Int) = {
  137.         var s = getSquare(x, y);
  138.         if (s.isSolved != true) {
  139.           allSquares = allSquares.filter(_ != s);
  140.           s = s.removeValue(wrongSolution);
  141.           allSquares = allSquares :+ s;
  142.         }
  143.       }
  144.  
  145.  
  146.  
  147.  
  148.  
  149.       //Reading the puzzles from a file
  150.  
  151.  
  152.       //helt jævlig ikke bruk tid på d kan prøve å skrive om det selv
  153.  
  154.       for (a <- 0 to (size * 2 - 2) by 2) {
  155.         for (b <- 0 to size * 4 - 4 by 4) {
  156.           var naboopp = 0
  157.           var nabovenstre = 0
  158.           var nabohøyre = 0
  159.           var naboned = 0
  160.           if (a > 0) {
  161.             if (lines(puzzlestart + a - 1)(b) == 'x')
  162.               naboopp = 1
  163.           }
  164.           if (a < size * 2 - 2) {
  165.             if (lines(puzzlestart + a + 1)(b) == 'x') {
  166.               naboned = 1
  167.             }
  168.           }
  169.           if (b < size * 3) {
  170.             if (lines(puzzlestart + a)(b + 2) == 'x')
  171.               nabohøyre = 1
  172.           }
  173.           if (b > 0) {
  174.             if (lines(puzzlestart + a)(b - 2) == 'x')
  175.               nabovenstre = 1
  176.           }
  177.  
  178.           val naboerxd = List(naboopp, nabovenstre, nabohøyre, naboned)
  179.  
  180.           if (lines(puzzlestart + a)(b) == '_') {
  181.             setValue((size - (a / 2 + 1) + 1), (b / 4 + 1), listeentilsize, naboerxd)
  182.           };
  183.           else {
  184.             val verdi123 = lines(puzzlestart + a)(b).toString
  185.             val verdi1234 = verdi123.toInt
  186.             setValue((size - (a / 2 + 1) + 1), (b / 4 + 1), List(verdi1234), naboerxd)
  187.           }
  188.         }
  189.       }
  190.  
  191.  
  192.  
  193.       //skriver ut hele puzzelet
  194.       def printIt(): Unit = {
  195.         for (x <- listeentilsize) {
  196.           for (y <- listeentilsize) {
  197.             val s = getSquare(x, y);
  198.             print(s.possibleValues);
  199.           }
  200.           println("");
  201.         }
  202.       }
  203.  
  204.  
  205.       //sletting for naboer. hvis de er naboer sletter den alle utenom det tallet som er +1 eller -1
  206.       def deleteifnabo(x:Int, y:Int, ss:Square) = {
  207.         //listermove går fra 2 til size så den sletter alle som er +2, +3, +4 osv men beholder de som er +1 og -1
  208.         for (a <- listeremove) {
  209.           removeValue(x, y, ss.possibleValues(0) + a)
  210.           removeValue(x, y, ss.possibleValues(0) - a)
  211.         }
  212.       }
  213.  
  214.       //sletting hvis de ikke er naboer. sletter tallene som er +1 og -1
  215.       def deleteifnotnabo(x:Int, y:Int, ss:Square ) = {
  216.         removeValue(x, y, ss.possibleValues(0) + 1)
  217.         removeValue(x, y, ss.possibleValues(0) - 1)
  218.       }
  219.  
  220.       //en av hovedfunksjonene, sjekker alle boksene sine values og fjerner alle som ikke er valid.
  221.       def isValid(x: Int, y: Int, solution: Int): Boolean = {
  222.         for (s <- getAllFromX(x) ::: getAllFromY(y)) {
  223.           val oneSquare = s.asInstanceOf[Square];
  224.  
  225.  
  226.           //sjekker om en boks som er løst sin value oppstår i raden/kollonna, sletter fra de andre hvis den finner
  227.           if (x != oneSquare.x || y != oneSquare.y) {
  228.             if (oneSquare.isSolved == true && oneSquare.possibleValues(0) == solution) {
  229.               //println("Has solution " + oneSquare.x, oneSquare.y, oneSquare.possibleValues);
  230.               return false;
  231.             }
  232.  
  233.  
  234.             //lagrer en square fra x og y verdiene
  235.             val s = getSquare(x, y)
  236.  
  237.             //nabolista er
  238.             //(0,0,0,0)
  239.             //(opp,venstre,høyre,ned)
  240.             //der 0 = ikke nabo, 1 = nabo
  241.  
  242.  
  243.             //opp
  244.  
  245.             //hvis opp = nabo
  246.             if (s.neighbours1(0) == 1) {
  247.               if (x < size) {
  248.                 val ss = getSquare(x + 1, y)
  249.                 if (ss.isSolved == true) {
  250.                   deleteifnabo(x,y,ss)
  251.                 }
  252.               }
  253.             }
  254.  
  255.             //hvis opp = ikke nabo
  256.             if (s.neighbours1(0) == 0) {
  257.               if (x < size) {
  258.                 val ss = getSquare(x + 1, y)
  259.                 if (ss.isSolved == true) {
  260.                   deleteifnotnabo(x,y,ss)
  261.                 }
  262.               }
  263.             }
  264.  
  265.  
  266.  
  267.  
  268.             //venstre
  269.  
  270.  
  271.             if (s.neighbours1(1) == 1) {
  272.               if (y > 1) {
  273.                 val ss = getSquare(x, y - 1)
  274.                 if (ss.isSolved == true) {
  275.                   deleteifnabo(x,y,ss)
  276.                 }
  277.               }
  278.             }
  279.  
  280.             if (s.neighbours1(1) == 0) {
  281.               if (y > 1) {
  282.                 val ss = getSquare(x, y - 1)
  283.                 if (ss.isSolved == true) {
  284.                   deleteifnotnabo(x,y,ss)
  285.                 }
  286.               }
  287.             }
  288.  
  289.  
  290.  
  291.  
  292.             //høyre
  293.  
  294.  
  295.             if (s.neighbours1(2) == 1) {
  296.               if (y < size) {
  297.                 val ss = getSquare(x, y + 1)
  298.                 if (ss.isSolved == true) {
  299.                   deleteifnabo(x,y,ss)
  300.                 }
  301.               }
  302.             }
  303.  
  304.             if (s.neighbours1(2) == 0) {
  305.               if (y < size) {
  306.                 val ss = getSquare(x, y + 1)
  307.                 if (ss.isSolved == true) {
  308.                   deleteifnotnabo(x,y,ss)
  309.                 }
  310.               }
  311.             }
  312.  
  313.  
  314.  
  315.  
  316.             //ned
  317.  
  318.  
  319.  
  320.             if (s.neighbours1(3) == 1) {
  321.               if (x > 1) {
  322.                 val ss = getSquare(x - 1, y)
  323.                 if (ss.isSolved == true) {
  324.                   deleteifnabo(x,y,ss)
  325.                 }
  326.               }
  327.             }
  328.  
  329.             if (s.neighbours1(3) == 0) {
  330.               if (x > 1) {
  331.                 val ss = getSquare(x - 1, y)
  332.                 if (ss.isSolved == true) {
  333.                   deleteifnotnabo(x,y,ss)
  334.                 }
  335.               }
  336.             }
  337.           }
  338.         }
  339.         return true;
  340.       }
  341.  
  342.  
  343.       //sjekker alle possible values i en rad, og ser om det er et tall som bare oppstår i en av possible values listene.
  344.       def isOnlyOnePossible(x: Int) = {
  345.  
  346.         val listex = getAllFromX(x)
  347.  
  348.         val listenullasd = List.range(0, size);
  349.  
  350.         for (lookfornumber <- listeentilsize) {
  351.           var countx = 0
  352.           var rowx = 100
  353.           var yvalue = 100
  354.  
  355.  
  356.           for (boxnumberx <- listenullasd) {
  357.             if (listex(boxnumberx).possibleValues.contains(lookfornumber) == true) {
  358.               countx = countx + 1;
  359.               rowx = boxnumberx + 1;
  360.               yvalue = listex(rowx - 1).y
  361.             }
  362.           }
  363.  
  364.  
  365.           if (countx == 1) {
  366.             if (getSquare(x, yvalue).isSolved != true) {
  367.               for (c <- listeentilsize) {
  368.                 if (c != lookfornumber) {
  369.                   removeValue(x, yvalue, c);
  370.                   removeValue(1, 1, 100);
  371.                 }
  372.               }
  373.             }
  374.           }
  375.         }
  376.       }
  377.  
  378.       def isOnlyOnePossibley(y: Int) = {
  379.  
  380.         val listey = getAllFromY(y)
  381.  
  382.         val listenullasd = List.range(0, size);
  383.  
  384.         for (lookfornumber <- listeentilsize) {
  385.           var countx = 0
  386.           var rowx = 5
  387.           var yvalue = 100
  388.  
  389.  
  390.           for (boxnumberx <- listenullasd) {
  391.             if (listey(boxnumberx).possibleValues.contains(lookfornumber) == true) {
  392.               countx = countx + 1;
  393.               rowx = boxnumberx + 1;
  394.               yvalue = listey(rowx - 1).x
  395.             }
  396.           }
  397.  
  398.  
  399.           if (countx == 1) {
  400.             if (getSquare(yvalue, y).isSolved != true) {
  401.               for (c <- listeentilsize) {
  402.                 if (c != lookfornumber) {
  403.                   removeValue(yvalue, y, c);
  404.                   removeValue(1, 1, 100);
  405.                 }
  406.               }
  407.             }
  408.           }
  409.         }
  410.       }
  411.  
  412.  
  413.       def removeIfNotValid(x: Int, y: Int, solution: Int) {
  414.         if (!isValid(x, y, solution)) {
  415.           //println("Removing", x, y, solution);
  416.           removeValue(x, y, solution);
  417.         }
  418.       }
  419.  
  420.       def checkifallsolved():Boolean = {
  421.         val listeavboxer = allSquares;
  422.         for(a<-listeavboxer)
  423.           if(a.isSolved!=true)
  424.             return false
  425.         return true
  426.       }
  427.  
  428.  
  429.  
  430.       //Actual brute force
  431.  
  432.       while(checkifallsolved()==false) {
  433.         for (x <- listeentilsize) {
  434.           for (y <- listeentilsize) {
  435.             for (s <- listeentilsize) {
  436.               removeIfNotValid(x, y, s);
  437.             }
  438.           }
  439.         }
  440.         for (a <- listeentilsize) {
  441.           isOnlyOnePossible(a);
  442.           isOnlyOnePossibley(a);
  443.         }
  444.       }
  445.  
  446.       printIt()
  447.       println("\n")
  448.  
  449.       sol += "size " + size + "x" + size + "\n"
  450.       for (x <- size to 1 by -1) {
  451.         for (y <- 1 to size) {
  452.           sol += getSquare(x, y).possibleValues(0) + " "
  453.         }
  454.         sol += "\n"
  455.       }
  456.  
  457.  
  458.       puzzlestart = puzzlestart + 2*size
  459.     }
  460.  
  461.     return sol
  462.   }
  463.  
  464.   def writeSolutionToFile(obj:String, path:String):Unit = {
  465.     val out = new BufferedWriter(new FileWriter(new File(path)))
  466.  
  467.     out.write(obj)
  468.  
  469.     out.close()
  470.   }
  471.  
  472.   val duration = (System.nanoTime - t1) / 1e9d
  473.   println(duration)
  474.  
  475. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top