jules0707

Solver.java

Dec 2nd, 2020
437
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. /*
  3. Correctness:  51/51 tests passed
  4. Memory:       22/22 tests passed
  5. Timing:       125/125 tests passed
  6. Aggregate score: 100.00%
  7. */
  8.  
  9. import edu.princeton.cs.algs4.Stack;
  10. import edu.princeton.cs.algs4.Queue;
  11. import edu.princeton.cs.algs4.MinPQ;
  12.  
  13. import java.util.Objects;
  14.  
  15. public class Solver {
  16.     private boolean firstRun1;
  17.     private boolean firstRun2;
  18.     private Node node;
  19.     private int movesValue;
  20.     private final boolean isSolvable;
  21.     private Iterable<Board> solutionBoards;
  22.  
  23.  
  24.     // find a solution to the initial board (using the A* algorithm)
  25.     public Solver(Board board) {
  26.         if (null == board) throw new IllegalArgumentException();
  27.         movesValue = -1;
  28.         firstRun1 = true;
  29.         firstRun2 = true;
  30.         Board twin = board.twin();
  31.         Node neighbour1 = new Node(board.neighbors().iterator().next(), 0, null);
  32.         Node neighbour2 = new Node(twin.neighbors().iterator().next(), 0, null);
  33.  
  34.         // to avoid a null pointer when we query the previous board as part of the critical optimisation we add itself as previous
  35.         Node node1 = new Node(board, 0, neighbour1);
  36.         Node node2 = new Node(twin, 0, neighbour2);
  37.  
  38.         // Exactly one of the two (initial node or any twin node made from initial) will lead to the goal board.
  39.         // we run A* on two board instances, in lock-steps?, to find which board will lead to the goal board
  40.         MinPQ<Node> pq1 = new MinPQ<>(); // the initial board PQ
  41.         MinPQ<Node> pq2 = new MinPQ<>(); // a twin board PQ
  42.  
  43.         pq1.insert(node1); // insert initial node into PQ
  44.         pq2.insert(node2);
  45.  
  46.         // the first goal board found exits the search as they can't both be a goal board
  47.         while (!node1.board.isGoal() && !node2.board.isGoal()) {
  48.             Node min1 = pq1.delMin();
  49.             for (Node neighbor : min1.neighbors()) {
  50.                 // critical optimisation do not re-insert the previous node
  51.                 if(firstRun1){
  52.                     firstRun1 = false;
  53.                     neighbor.previous = min1;
  54.                     neighbor.moves = min1.moves + 1;
  55.                     pq1.insert(neighbor);
  56.                 }
  57.                 else if (!neighbor.board.equals(min1.previous.board)) {
  58.                     neighbor.previous = min1;
  59.                     neighbor.moves = min1.moves + 1;
  60.                     pq1.insert(neighbor);
  61.                 }
  62.             }
  63.             node1 = min1;
  64.  
  65.             // build of the second tree with twin as root
  66.             Node minNode2 = pq2.delMin();
  67.             for (Node neighbor : minNode2.neighbors()) {
  68.                 if (firstRun2){
  69.                     firstRun2 = false;
  70.                     neighbor.previous = minNode2;
  71.                     neighbor.moves = minNode2.moves + 1;
  72.                     pq2.insert(neighbor);
  73.                 }
  74.                 else if (!neighbor.board.equals(minNode2.previous.board)) {
  75.                     neighbor.previous = minNode2;
  76.                     neighbor.moves = minNode2.moves + 1;
  77.                     pq2.insert(neighbor);
  78.                 }
  79.             }
  80.             node2 = minNode2;
  81.         }
  82.  
  83.         // we have exited the search so one of the boards is a goal!
  84.         isSolvable = node1.board.isGoal(); // we are only interested in the solvability of node1?
  85.         if (isSolvable) {
  86.             node = node1;
  87.             movesValue = node1.moves;
  88.         } // if node2 is solvable we can be certain that node1 isn't see propriety of boards.
  89.     }
  90.  
  91.     // is the initial board solvable? (see below)
  92.     public boolean isSolvable() {
  93.         return isSolvable;
  94.     }
  95.  
  96.     // min number of moves to solve initial board
  97.     public int moves() {
  98.         return movesValue;
  99.     }
  100.  
  101.     // sequence of boards in a shortest solution
  102.     public Iterable<Board> solution() {
  103.         if (!isSolvable()) return null;
  104.  
  105.         if (null != solutionBoards) return solutionBoards;
  106.         else {
  107.             Stack<Board> reversedStack = new Stack<>();
  108.             Queue<Board> invertedSolutionQueue = new Queue<>();
  109.             Queue<Board> solutionQueue = new Queue<>();
  110.  
  111.             while (null != node.previous) {
  112.                 invertedSolutionQueue.enqueue(node.board);
  113.                 node = node.previous;
  114.             }
  115.             while (!invertedSolutionQueue.isEmpty()) {
  116.                 reversedStack.push(invertedSolutionQueue.dequeue());
  117.             }
  118.             while (!reversedStack.isEmpty()) {
  119.                 solutionQueue.enqueue(reversedStack.pop());
  120.             }
  121.             solutionBoards = solutionQueue;
  122.         }
  123.         return solutionBoards;
  124.     }
  125.  
  126.     // the Node type that holds:
  127.     private static class Node implements Comparable<Node> {
  128.         Board board;
  129.         Node previous;
  130.         int moves;
  131.         final int manhattanValue;
  132.  
  133.         Node(Board board, int moves, Node previous) {
  134.             this.board = board;
  135.             this.moves = moves;
  136.             this.previous = previous;
  137.             this.manhattanValue = this.board.manhattan();
  138.         }
  139.  
  140.         private final int priorityFunction() {
  141.             return manhattanValue + moves; // We choose the manhattan priority function
  142.         }
  143.  
  144.         // all the neighboring nodes
  145.         Queue<Node> neighbors() {
  146.             Queue<Node> nodeNeighbors = new Queue<>();
  147.             for (Board neighbor : this.board.neighbors()) {
  148.                 Node nodeNeighbor = new Node(neighbor, this.moves + 1, this);
  149.                 nodeNeighbors.enqueue(nodeNeighbor);
  150.             }
  151.             return nodeNeighbors;
  152.         }
  153.  
  154.         @Override
  155.         public boolean equals(Object y) {
  156.             if (y == this) return true;
  157.             if (null == y) return false;
  158.             if (y.getClass() != this.getClass()) return false;
  159.  
  160.             Node that = (Node) y;
  161.             if (this.moves != that.moves) return false;
  162.             if (this.priorityFunction() != that.priorityFunction()) return false;
  163.             if (this.previous != that.previous) return false;
  164.             if (!this.board.equals(that.board)) return false;
  165.             return true;
  166.         }
  167.  
  168.         @Override
  169.         public int hashCode() {
  170.             return Objects.hash(board, previous, priorityFunction(), moves);
  171.         }
  172.  
  173.         @Override
  174.         public int compareTo(Node that) {
  175.             int res = -1;
  176.             if (this.priorityFunction() > that.priorityFunction()) res = 1;
  177.             else if (this.priorityFunction() < that.priorityFunction()) res = 0;
  178.             else if (this.priorityFunction() == that.priorityFunction()) {
  179.                 if (this.manhattanValue > that.manhattanValue) res = 1;
  180.                 else if (this.manhattanValue < that.manhattanValue) res = 0;
  181.                 else res = 1;
  182.             }
  183.             return res;
  184.         }
  185.  
  186.  
  187.     } // END of Node class
  188.  
  189.  
  190. // test client (see below)
  191. /*    public static void main(String[] args) {
  192.         // create initial board from file
  193.          In in = new In(args[0]);
  194.         int n = in.readInt();
  195.         int[][] tiles = new int[n][n];
  196.         for (int i = 0; i < n; i++)
  197.             for (int j = 0; j < n; j++)
  198.                 tiles[i][j] = in.readInt();
  199.         Board initial = new Board(tiles);
  200.  
  201.         StdOut.println("initial board :");
  202.         StdOut.println(initial);
  203.  
  204.         // solve the puzzle
  205.         Solver solver = new Solver(initial);
  206.  
  207.         // print solution to standard output
  208.         if (!solver.isSolvable())
  209.             StdOut.println("No solution possible");
  210.         else {
  211.             StdOut.println("1st call to moves() = " + solver.moves());
  212.             solver.solution();
  213.             StdOut.println("2nd call to moves() = " + solver.moves());
  214.             solver.isSolvable();
  215.             StdOut.println("3rd call to moves() = " + solver.moves());
  216.  
  217.             for (Board board : solver.solution())
  218.                 StdOut.println(board);
  219.  
  220.         }
  221.     }*/
  222. }
RAW Paste Data