*** I NEED HELP*** PEASE Game Description (Here is tester and required file file
ID: 3834577 • Letter: #
Question
*** I NEED HELP*** PEASE
Game Description
(Here is tester and required file file: https://drive.google.com/open?id=0B2gb5h869g2aR2V4Zko4VTlBckk )
The game starts with a board of M rows by N columns with some grid squares marked as “obstacles” (drawn as black dots). The player chooses a starting position to place a ball (marked “S” in the figure to the right) and chooses a direction to advance (left, right, up, or down). Once a direction is chosen, the ball will advance in that direction until it hits an obstacle, the boundary of the game board, or a square that the ball has already been through. The player then chooses another direction, and the ball will advance in the same manner. The game ends when no legal move can be made. The player wins if and only if the ball has traveled through all the empty grid squares on the board.
Tasks
You are to write a program that finds all of the paths that have a minimum number of steps needed to the game.
The program is similar to Rock and Roll Countdown in that it must have a main() method. When the unit tester is run,
The tester will invoke Main.main().
The tester will send your program the name of a file containing maps via the console.
Here is an example file. Each spot on a map is either an obstacle (, unicode "u2593") or an empty space. The maxium dimensions of a map is 60 x 60.
Your program must read in the filename, then read the file, then parse and analyze each map. For each map, your program should output the following items (also note the example output listed below):
A line with the word map on it
A line with the minimum number of moves (or No solution, if there is none) required to win the game.
(if there is at least one solution).
A line with the word solution on it
The solved map. This includes an S where the solution starts, arrows that indicate the movement, and an F where the solution finishes. Note that the arrows must be , , , (unicode "u219x", where x is 0, 1, 2, 3).
A line with the word endsolution on it.
If there is more than one solution, the next solution starts on the line after the previous solution's endsolution. Each solution is enclosed in solution/endsolution lines (see map 8 below).
Note: If there is more than one solution, sort the solutions lexicographically (a.k.a. alphabetically) in ascending order. To do this, you can simply convert each solution's 2D map into a 1D string (row major). Then sort the solutions in the same order as the strings would be sorted.
A line with the word endmap on it.
A line with the word Complete on it.
Formatting is important for the unit tester to function properly - no extra lines or spaces. Punctuation and capitalization matter.
If the filename the tester sends cannot be found, your program must print out:
File not found.
Complete
Before You Start Programming
On windows computers, the block character - -used in maps has to be saved as UTF-8. Solve this by going to: Window -> Preferences -> General -> Workspace : Text file encoding
Suggestions
One approach to consider is to envision the set of possible board configurations as existing in a game tree, and to use a queue to keep track of configurations that haven't been investigated yet.
Non-Functional Requirements
NOTE: Naming is critical in the tasks and requirements described below. If the names don't match those described below exactly, your project will not compile and can't be graded.
Create a copy of the Java SE Project Template. The project name must follow this pattern: {FLname}_FullBoard_{TERM}, where {FLname} is replaced by the first letter of your first name plus your last name, and {TERM} is the semester and year. E.g. if your name is Maria Marciano and it's Spring of 2015, your project name must be MMarciano_FullBoard_S15.
Create a new package in the src folder called fullboard.
Main class:
Create a Main class in the fullboard package. It must have a public static void main(String[] args). The unit tester will invoke this function when it tests your code.
Testing
Create a new package in the src folder called sbccunittest.
Download FullBoardTester.java into the sbccunittest package.(Here is tester and required file file: https://drive.google.com/open?id=0B2gb5h869g2aR2V4Zko4VTlBckk )
Download edu.sbcc.cs145.fullboardri into lib folder of your project.(Here is tester and required file file: https://drive.google.com/open?id=0B2gb5h869g2aR2V4Zko4VTlBckk )
Right-click on edu.sbcc.cs145.fullboardri, then select Build Path | Add to Build Path.
Sample Input and Output (input is blue, output is black)
S )Explanation / Answer
FullBoardTester.java
package sbccunittest;
import static junit.framework.Assert.*;
import static org.apache.commons.io.FileUtils.*;
import static org.apache.commons.lang3.StringUtils.*;
import java.io.*;
import java.util.*;
import org.junit.*;
import fullboard.*;
public class FullBoardTester {
public static int totalScore = 0;
public static int extraCredit = 0;
public static InputStream defaultSystemIn;
public static PrintStream defaultSystemOut;
public static PrintStream defaultSystemErr;
public static String newLine = System.getProperty("line.separator");
@BeforeClass
public static void beforeTesting() throws Exception {
totalScore = 0;
extraCredit = 0;
String fbSrc = readFileToString(new File("src/fullboard/Main.java"));
if (fbSrc.contains("fullboardri"))
throw new Exception("Reference to fullboardri found");
}
@AfterClass
public static void afterTesting() {
System.out.println("Estimated score (w/o late penalties, etc.) = " + totalScore);
}
@Before
public void setUp() throws Exception {
defaultSystemIn = System.in;
defaultSystemOut = System.out;
defaultSystemErr = System.err;
}
@After
public void tearDown() throws Exception {
System.setIn(defaultSystemIn);
System.setOut(defaultSystemOut);
System.setErr(defaultSystemErr);
}
@Test
public void testFileNotFound() throws Exception {
sendToStdinOfTestee("blah.txt ");
final ByteArrayOutputStream myOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(myOut));
Main.main(null);
String output = myOut.toString();
System.setOut(defaultSystemOut);
StringBuilder sb = new StringBuilder("File not found.");
sb.append(newLine + "Complete" + newLine);
String expectedOutput = sb.toString();
// Convert to common end-of-line system.
output = output.replace(" ", " ");
expectedOutput = expectedOutput.replace(" ", " ");
assertEquals(expectedOutput, output);
totalScore += 5;
}
@Test
public void testSmallMapsFile() throws IOException {
String filename = "smallmaps.txt";
generateSmallMapsFile(filename);
sendToStdinOfTestee(filename);
final ByteArrayOutputStream myOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(myOut));
Main.main(null);
String output = myOut.toString();
System.setOut(defaultSystemOut);
// Expected output
sendToStdinOfTestee(filename);
final ByteArrayOutputStream expectedOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(expectedOut));
fullboardri.Main.main(null);
String expectedOutput = expectedOut.toString();
System.setOut(defaultSystemOut);
// out.println(expectedOutput);
// Convert to common end-of-line system.
output = output.replace(" ", " ");
writeStringToFile(new File("smallmaps_out.txt"), output);
expectedOutput = expectedOutput.replace(" ", " ");
writeStringToFile(new File("smallmaps_expected_out.txt"), expectedOutput);
// Go through outputs, map by map
String[] oMaps = substringsBetween(output, "map ", "endmap ");
String[] eMaps = substringsBetween(expectedOutput, "map ", "endmap ");
assertEquals("The number of maps doesn't match.", eMaps.length, oMaps.length);
totalScore += 5;
// Verify that the # of moves is correct for all maps
for (int ndx = 0; ndx < eMaps.length; ndx++) {
String[] olines = oMaps[ndx].split(" ");
String[] elines = eMaps[ndx].split(" ");
assertTrue("Each map must have a least one line defined in it.", olines.length > 0);
assertEquals("The minimum number of moves doesn't match", elines[0].trim(), olines[0].trim());
}
totalScore += 10;
// Verify all maps match.
assertEquals(expectedOutput, output);
totalScore += 10;
}
@Test(timeout = 120000)
public void testLargeMapsFile() throws IOException {
String filename = "largemaps.txt";
generateLargeMapsFile(filename);
sendToStdinOfTestee(filename);
final ByteArrayOutputStream myOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(myOut));
Main.main(null);
String output = myOut.toString();
System.setOut(defaultSystemOut);
writeStringToFile(new File("largemaps_out.txt"), output);
// Expected output
sendToStdinOfTestee(filename);
final ByteArrayOutputStream expectedOut = new ByteArrayOutputStream();
System.setOut(new PrintStream(expectedOut));
fullboardri.Main.main(null);
String expectedOutput = expectedOut.toString();
System.setOut(defaultSystemOut);
// Convert to common end-of-line system.
output = output.replace(" ", " ");
expectedOutput = expectedOutput.replace(" ", " ");
// Verify that the number of maps is correct
String[] oMaps = substringsBetween(output, "map ", "endmap ");
String[] eMaps = substringsBetween(expectedOutput, "map ", "endmap ");
assertEquals("The number of maps doesn't match.", eMaps.length, oMaps.length);
totalScore += 5;
if (oMaps.length == eMaps.length) {
boolean numMovesCorrect = true;
String message = null;
// Verify that the number of moves is correct
for (int ndx = 0; ndx < eMaps.length; ndx++) {
String[] expectedLines = eMaps[ndx].split(" ");
String[] outputLines = oMaps[ndx].split(" ");
if (!outputLines[1].trim().equals(expectedLines[1].trim())) {
numMovesCorrect = false;
message = "For large map " + (ndx + 1) + " the number of moves do not match.";
}
}
assertTrue(message, numMovesCorrect);
totalScore += 5;
}
// Verify that all output is as expected.
assertEquals(expectedOutput, output);
totalScore += 10;
}
private void generateLargeMapsFile(String filename) throws IOException {
int vfi = (int) (Math.random() * 2);
StringBuilder sb = new StringBuilder();
for (int ndx = 0; ndx < 2; ndx++) {
int n = (int) (30 * Math.random() + 20);
String map;
if (ndx != vfi)
map = generateMap(n, n, 5);
else
map = generateLargeValidMap(n);
sb.append("map").append(newLine);
sb.append(map);
sb.append("endmap").append(newLine);
}
writeStringToFile(new File(filename), sb.toString());
}
private String generateLargeValidMap(int n) {
StringBuilder sb = new StringBuilder(generateMap(n, n, 0));
int pos = (int) (4 * Math.random());
switch (pos) {
case 0:
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2, '');
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2 + 1, '');
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2 + 2, '');
break;
case 1:
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2, '');
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2 + 1, '');
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2 + 2, '');
break;
case 2:
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2, '');
sb.setCharAt((n / 2 + 1) * (n + newLine.length()) + n / 2, '');
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2, '');
break;
case 3:
sb.setCharAt((n / 2) * (n + newLine.length()) + n / 2 + 2, '');
sb.setCharAt((n / 2 + 1) * (n + newLine.length()) + n / 2 + 2, '');
sb.setCharAt((n / 2 + 2) * (n + newLine.length()) + n / 2 + 2, '');
break;
}
return sb.toString();
}
/**
* Works for numRows, numCols up to about 10, then too slow
*
* @param numRows
* @param numCols
* @param numBlocks
* @param numMaps
* @param numNoSolution
* @param filename
* @throws IOException
*/
public void generateSmallMapsFile(String filename) throws IOException {
boolean done = false;
int numMaps = (int) (Math.random() * 4) + 10;
int numNoSolution = (int) (Math.random() * 2) + 1;
StringBuilder sb = new StringBuilder();
int validCount = 0;
List<Integer> noSolutionIndices = new ArrayList<>(numMaps);
for (int i = 0; i < numMaps; i++)
noSolutionIndices.add(i);
Collections.shuffle(noSolutionIndices);
noSolutionIndices = noSolutionIndices.subList(0, numNoSolution);
int noSolutionCount = 0;
boolean saveSolution = false;
boolean isANoSolution = false;
while (!done) {
int numRows = (int) (Math.random() * 4) + 7;
int numCols = numRows;
int numBlocks = 5;
String map = generateMap(numRows, numCols, numBlocks);
fullboardri.Main checker = new fullboardri.Main(true);
String result = checker.processMap(map);
isANoSolution = result.contains("No solution");
boolean needNoSolution = false;
saveSolution = false;
if (numNoSolution > 0) {
if (noSolutionCount < numNoSolution) {
if ((noSolutionIndices.contains(validCount))) {
needNoSolution = true;
}
}
}
if (isANoSolution) {
if (needNoSolution)
saveSolution = true;
} else
saveSolution = true;
if (saveSolution) {
sb.append("map").append(newLine);
sb.append(map);
sb.append("endmap").append(newLine);
if (needNoSolution)
noSolutionCount++;
validCount++;
if (validCount >= numMaps)
done = true;
}
}
writeStringToFile(new File(filename), sb.toString());
}
public String generateMap(int numRows, int numCols, int numBlocks) {
char[][] map = new char[numRows][numCols];
for (int c = 0; c < numCols; c++)
map[0][c] = '';
for (int r = 1; r < numRows - 1; r++) {
map[r][0] = '';
for (int c = 1; c < numCols - 1; c++)
map[r][c] = ' ';
map[r][numCols - 1] = '';
}
for (int c = 0; c < numCols; c++)
map[numRows - 1][c] = '';
// Place blocks. Note: this is n^2 if numBlocks is of the order of numRows*numCols.
int blocksPlaced = 0;
while (blocksPlaced < numBlocks) {
int r = (int) (Math.random() * (numRows - 2)) + 1;
int c = (int) (Math.random() * (numCols - 2)) + 1;
if (map[r][c] != '') {
map[r][c] = '';
blocksPlaced++;
}
}
// Convert to string
StringBuilder sb = new StringBuilder(numRows * (numCols + newLine.length()));
for (int r = 0; r < numRows; r++) {
for (int c = 0; c < numCols; c++)
sb.append(map[r][c]);
sb.append(newLine);
}
return sb.toString();
}
public void sendToStdinOfTestee(String message) {
System.setIn(new ByteArrayInputStream(message.getBytes()));
}
}
Main.java
package fullboard;
import java.io.*;
import java.util.*;
public class Main {
private static String OBSTACLE = "u2593";
private static String ARROWUP = "u2190";
private static String ARROWDOWN = "u2191";
private static String ARROWRIGHT = "u2192";
private static String ARROWLEFT = "u2193";
private static String START = "S";
private static String END = "F";
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String fname = in.next();
in.close();
ArrayList<String> maps = parseMaps(new File(fname));
if (maps == null) {
System.out.println("File not found.");
System.out.println("Complete.");
return;
}
for (String m : maps) {
System.out.println("map");
ArrayList<String> solutions = solveBoard();
for (String s : solutions) {
int numMoves = 0;
System.out.println(numMoves + " moves");
System.out.println("solution");
System.out.println(s);
System.out.println("endsolution");
}
System.out.println("endmap");
}
System.out.println("Complete.");
}
static private ArrayList<String> parseMaps(File f) {
Scanner in;
String current;
ArrayList<String> answer = new ArrayList<String>();
try {
in = new Scanner(f);
} catch (FileNotFoundException e) {
return null;
}
while (in.hasNextLine()) {
current = in.nextLine();
if (current.equals("map")) {
answer.add("");
}
if (!current.equals("endmap")) {
answer.set(answer.size() - 1, answer.get(answer.size() - 1) + current);
}
}
in.close();
System.out.println("endmap");
return null;
}
static private ArrayList<String> solveBoard() {
return null;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.