Data Structures 2
This puzzle consists of two separate deliverables. The first is a puzzle application (a game) while the second is a solver for the puzzle.
Allowed changes to classes You may add additional methods to the classes you were given and you may also add other classes (that you make) in their own separate files. Just make sure to include all additional files when you make you submission so that I can run your code. You may also make classes implement Comparable if you want.
• Allowed imports You may import and use Java’s Random class as well as Java’s versions of symbol tables (Java’s various Map and Set classes.) The Game/Puzzle The game/puzzle consists of a grid of 2 rows of 5 cells each. Each cell contains a number between 0 and 9 inclusive. The object of the game/puzzle is to arrange all the numbers in the cells in order. The top row should have the numbers 0-4 in order left to right and the bottom row should have the numbers 5-9 in order left to right. You move the numbers around by making one of the following nine possible moves:
• 1: Shift the numbers in the top row to the right one position (the right-most number “wraps around” to the left-most position.
• -1: Shift the numbers in the top row to the left one position (the left-most number “wraps around” to the right-most position.
• 2: Shift the numbers in the top bottom to the right one position (the right-most number “wraps around” to the left-most position.
• -2: Shift the numbers in the bottom row to the left one position (the left-most number “wraps around” to the right-most position.
• 3-7: Swap the positions of the 2 numbers in the given column. The columns are numbered 3 through 7 from left to right. The player continues to make moves by indicating the move number (-2, -1, 1, 2, 3, 4, 5, 6, or 7) until either they win by arranging the numbers so that they appear in the cells in order, or they lose by repeating a board position. This is probably easier to understand via a demonstration. A demonstration of how the game is played will be given in class, so please make sure to take a look at the lecture recording if you did not attend the class meeting where the demonstration was given.
Deliverable #2 The second deliverable has two related components. You must implement the Solver class. you are allowed to define other classes to help you (as well as use “built-in” Java classes). For example, the Board class from part 1 of the project can be especially useful, after a few additions/changes. The point of the solver class is the solve method which takes a 2-by-5 array of bytes containing the numbers 0-9 that represent the initial state of the puzzle board (in the same way that a 2-by-5 array can be passed to the Board(byte[][] b) constructor from deliverable #1) and which returns an array of ints representing a sequence of moves that can be made to solve the puzzle. For the solution to be considered correct, not only must the sequence of moves when made in the order they appear in the array lead to the solved puzzle state (the numbers appearing in sorted order in the puzzle), but there must not be a solution that uses fewer moves. If given a completely clear board as input, the solution requires no moves and an array of size 0 must be returned. The class also has a no argument constructor that will be called to construct/initialize the solver object. It’s up to you what this constructor does. (There are valid solutions to the project where the constructor does absolutely nothing, but there are also solutions where some preprocessing work done in the constructor allows the solve method to be much faster.)
Please answer each of the questions below.. Make sure you provide a concise answer, and like the homework videos, PLEASE AVOID explaining your code line by line. Instead, make sure you explain the idea.
WHY did you choose to do what you do?
If your answer to one of the questions includes the use of a data structure we discussed in class, explain which one, and why/how you are using it. Please Avoid explain what the data structure itself does or how it works. For example, if you use a BinarySearchST, do not explain to me how binary search works, how insertion works, etc. Instead, explain, what are the keys, what are the values, and why/how you using the symbol table in your solution. Breadth-first search is done on a graph.
What is the graph being searched in your solution?
What are the vertices of the graph and when is there edge between two vertices?
During breadth first search, you need to loop over all neighbors of a given vertex. Show me where and how your code does this. How does your code know who the neighbors of a given vertex are?
Breadth-first search requires that you mark vertices as you encounter them to keep track of the vertices you have already seen. The book’s code uses an array to execute this .
How did you keep track of marked vertices?
Don’t forget to show me the part of the code that does this. To be able to recover the solution path, breadth-first search requires that for each vertex, you keep track of what vertex you came from when you first encountered it (edgeTo array). How do you keep track of that in your solution?
Don’t forget to show me the part of the code that does this. Assuming your breadth-first search has already been performed, how is the solution itself recovered?
Again, avoiding explaining line by line. Instead, explain what has been stored in the various fields/variables by the BFS, and how that information is used to construct a solution. Make sure that you show me the code that constructs/extracts the solution from the stored information. (Note that there could be some overlap between this question and previous question.) If your solution does only a single breadth-first search at the beginning, regardless of the number of times solve is called, how did you do it?
be based on how fast your code runs on my computer. For reference, when I use my first solution where I was trying to be efficient the Timing test finishes in 8 seconds. I then coded up another solution where I tried to duplicate exactly the book’s BFS algorithm, and that one took 75 seconds. Using these solutions as a baseline is recommended.
Tips when my tests fail: The name of each test includes an indication of how many moves the solutions will require. The body of each test includes calls of the form: stringToByteArray(“1634052789”); This call creates the starting position for the puzzle. The digits in the string appear in the same order that they will appear on the puzzle board. The first five are the five numbers in the top row and the second five are the five in the bottom row. You can use this to make your own test (or main) that you can debug independently of the Junit tests. For example, you could make a main that creates a 2D byte array with the numbers in the order they appear in the String and then calls your solve method with that array.
Example:
Below and to the left is a figure representing the puzzle we want to solve. Below and to the right is a Java program that would call your Solver.solve method to solve the puzzle and print out the answer.
37194147
The solution with the fewest number of moves is to swap the 6 and the 2 (4 move), and then shift the top row to the right (1 move). So the print statement at the end of the main should display [4, 1] For this particular example, any other output would be wrong and would result in the test failing. Of course, the Junit tests do not print solutions. They only verify that the solutions your code produces are correct.
The Solver.java,P2TimingTest.java,P2Test.java are all in the Word document below