• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
91%
SHARE
TWEET

# Untitled

a guest Mar 20th, 2017 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. package hw3.puzzle;
2.
3. import  edu.princeton.cs.algs4.MinPQ;
4. import java.util.HashSet;
6.
7. public class Solver {
8.     private int moves;
10.     private HashSet<WorldState> worldStateSet;
11.     /*
12.     Constructor which solves the puzzle, computing
13.                  everything necessary for moves() and solution() to
14.                  not have to solve the problem again. Solves the
15.                  puzzle using the A* algorithm. Assumes a solution exists.
16.      */
17.
18.     public Solver(WorldState initial) {
19.         worldStateSet = new HashSet<>();
20.         Iterable<WorldState> neighbors;
21.         SearchNode currNode = new SearchNode(initial);
22.         MinPQ<SearchNode> queue = new MinPQ<>();
23.         queue.insert(currNode);
24.         queue.delMin();
25.
26.         while (!currNode.getWorldState().isGoal()) {
27.             neighbors = currNode.getWorldState().neighbors();
28.             for (WorldState i: neighbors) {
29.                 if (!worldStateSet.contains(i)) {
30.                     queue.insert(new SearchNode(i, moves() + 1, currNode));
32.                 }
33.             }
34.             currNode = queue.delMin();
35.         }
36.
37.         while (currNode != null) {
39.             currNode = currNode.getPrevNode();
40.         }
41.     }
42.
43.     /*
44.     Returns the minimum number of moves to solve the puzzle starting
45.                  at the initial WorldState.
46.      */
47.     public int moves() {
48.         return solution.size();
49.     }
50.
51.     /*
52.     Returns a sequence of WorldStates from the initial WorldState
53.     to the solution.
54.     */
55.     public Iterable<WorldState> solution() {
56.         return solution;
57.     }
58.
59.     public class SearchNode implements Comparable<SearchNode> {
60.         private WorldState worldState;
61.         private int numMoves;
62.         private SearchNode prevNode;
63.
64.         public SearchNode() {
65.             worldState = null;
66.             numMoves = 0;
67.             prevNode = null;
68.         }
69.
70.         public SearchNode(WorldState word) {
71.             this.worldState = word;
72.             numMoves = 0;
73.             prevNode = null;
74.         }
75.
76.         public SearchNode(WorldState word, int numMoves, SearchNode prevNode) {
77.             this.worldState = word;
78.             this.numMoves = numMoves;
79.             this.prevNode = prevNode;
80.         }
81.
82.         public WorldState getWorldState() {
83.             return worldState;
84.         }
85.
86.         public int getMoves() {
87.             return numMoves;
88.         }
89.
90.         public SearchNode getPrevNode() {
91.             return prevNode;
92.         }
93.
94.         public int compareTo(SearchNode n2) {
95.             if ((getWorldState().estimatedDistanceToGoal() + getMoves()) >
96.                     n2.getWorldState().estimatedDistanceToGoal() + n2.getMoves()) {
97.                 return 1;
98.             } else if(getWorldState().estimatedDistanceToGoal() < n2.getWorldState().estimatedDistanceToGoal()){
99.                 return -1;
100.             } else {
101.                 return 0;
102.             }
103.         }
104.
105.     }
106. }
RAW Paste Data
Top