Pair programming is permitted on all parts of this week's assignment.
The Spampede game has been broken into three parts. You'll do Part 1 this week. In Part 1, you will extend the capabilities of your maze solver from HW7 (though you may use our solution code for that assignment if you prefer).
This week you will work on implementing bubble sort, insertion sort, and selection sort in Prolog, Java, and Racket.
To reinforce some of the sorting algorithms you've learned in CS 60, you'll be implementing these sorting algorithms in each of the three languages from CS60.
In the hw11 directory you'll find:
The Java starter file provides the following method signatures. We are using the SortingStuff class, but do not plan to make SortingStuff objects and you will write the following static methods for the class.
public static boolean bubble(int[] arr) {
public static int bubbleSort(int[] arr) {
public static void insert(int[] arr, int index) {
public static void insertionSort(int[] arr) {
public static int minIndex(int[] arr, int startIndex) {
public static void selectionSort(int[] arr) {
The Racket starter file provides approximately half of the functions necessary for sorting. The following functions are provided: selectionSort, insertionSort, and bubble. You will write the following functions:
min remove insert bubbleSort
The Prolog starter file provides approximately half of the predicates necessary for sorting. The following predicates are provided: min, remove, insert, and bubbleSort. You will write the following predicates:
selectionSort insertionSort bubble
Test cases are provided for all of the sorting [methods/functions/predicates]. Before writing the code for any of these [methods/functions/predicates] you should add at least one test case (and clearly mark it as added.) The purpose of this is to get familiar with what each of these [methods/functions/predicates] does before trying to figure out how it does that.
You can begin with the starter file that provides a working version a breadth first search (BFS) as a reference.
A common occurrence in software development is needing to go back and revise old code. This is called refactoring code and can be done to improve the style of the code, increase the code clarity, achieve a new goal, decrease the speed of the code, or make the code easier to work with.
Your assignment for this week is to refactor your maze code to provide functionality that we'll use to make the Spampede game. Specifically you're going to be providing two new methods.
Task 1: New Constructor (5 points)Your homework-12-self really wants a constructor that is easier to use!! It seems much more convenient if you could create Mazes out of an array of Strings rather than out of a single String. Please add the following method to your Maze class.
public Maze(String[] mazeStrings)Task 2: New BFS for Many Spams (15 points)
Your homework-12-self also wants to be able to get the next MazeCell along the shortest path given a start destination and the character that represents one of potentially many goals. Another thing that will be different about this method is that you should be able to search the same Maze object multiple times. (Your previous version may have left 'o's hanging around). Please add the following method to your Maze class.
public MazeCell multiBFS(MazeCell start, char destination)
Part of your goal in writing multiBFS is to break your method up into intuitive helper methods. We recommend that you'll want at least one helper method to clear all of the flags in the MazeCell[][] and probably another helper method to help you pick a random cell, when there is no "best" cell to pick. Here is some additional description of the multiBFS method.
/* * method: multiBFS * * input: a starting cell and a char to seek * * output: the maze cell that is BESIDE START and NEXT ALONG the path to the * nearest destination! * * optional: printing the path to the goal if you do, BE SURE TO CLEAR * _EVERYTHING_ OUT! before returning... * * if there is no path, this method should return an open MazeCell that is * NEXT TO START * * if there is no open MazeCell that is NEXT TO START, this method should * return any MazeCell that is next to start (and it will crash) */Task 3: Test the heck out of it! (15 points)
Please create a JUnit test case file with tests of your new constructor and your multiBFS and your String array constructor. We expect you'll need at least 9 tests. Here are some (strong) recommendations. All of your tests should be commented.
To create a MazeCell reference in MazeTest.java you'll need to use the enclosing class to specify what a MazeCell is (b/c it is internal to Maze). Here is an example of how to create a test case in MazeTest.java.
public void testSomething(){
String[] mazeStr = {"******",
"*S D*",
"******"};
Maze m1 = new Maze(mazeStr);
Maze.MazeCell start = m1.maze[1][1];
Maze.MazeCell m = m1.multiBFS(start, 'D');
assertTrue(m.getRow() == 1);
assertTrue(m.getCol() == 2);
}
Using the List class from Homework 6, implement and test:
You will turn in both List.java and ListTest.java. Half of the points will be based upon your thorough testing of the sorting method and testing any helper methods you write. Please use the following signatures. Your methods should modify the List. You shouldn't create any new ListNodes (i.e., you shouldn't call new ListNode()), but you may create additional ListNode references. You may create additoinal Lists (i.e., you can call new List()).
public void quickSort() public void bubbleSort()