﻿

# 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]);
195.         int[][] tiles = new int[n][n];
196.         for (int i = 0; i < n; i++)
197.             for (int j = 0; j < n; j++)
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