Homework SourseFull Board is an interactive oneperson puzzlegame by LightFo
“Full Board” is an interactive one-person puzzle/game by LightForce played on a rectangular grid. You can play the game here.
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.
Download edu.sbcc.cs145.fullboardri into lib folder of your project.
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)
Solution
Main.java
package fullboard;
import java.io.*;
import java.util.*;
import org.apache.commons.io.*;
import org.apache.commons.lang3.*;
public class Main {
public static void main(String[] args) throws IOException {
// Check if file exists
File file = new File(args != null ? args[0] : \"\");
if (!file.exists()) {
System.out.println(\"File not found.\ Complete\");
return;
}
// START - PROCESS FILE\'S MAPS
String[] maps = StringUtils.substringsBetween(FileUtils.readFileToString(file), \"map\", \"endmap\");
ArrayList<Board> emptyBoards = new ArrayList<Board>(maps.length);
for (int i = 0; i < maps.length; i++)
emptyBoards.add(new Board(maps[i].trim()));
// END
// START - FILL QUEUES WITH STARTING POSITIONS
for (Board b : emptyBoards) {
// START - BUILD SETUP
Queue<Board> remainingUnsolved = new LinkedList<Board>();
for (int i = 0; i < b.getSize(); i++)
for (int j = 0; j < b.getSize(); j++)
if (b.getSpaceAt(i, j) == Space.EMPTY)
remainingUnsolved.add(new Board(b).setStart(i, j));
// END
// START - SOLVE BOARD
ArrayList<Board> winningBoards = new ArrayList<Board>();
while (!remainingUnsolved.isEmpty()) {
Board popped = remainingUnsolved.remove();
if (popped.isSolved()) {
popped.setFinish(popped.getX(), popped.getY());
winningBoards.add(new Board(popped));
} else if (popped.isSolvable()) {
for (Direction d : Direction.values()) {
Board nextMove = new Board(popped).move(d);
if (nextMove != null)
remainingUnsolved.add(nextMove);
}
}
}
// END
// START - PRINT & SORT BOARD
Collections.sort(winningBoards);
System.out.println(\"map\");
if (winningBoards.isEmpty()) {
System.out.println(\"No solution\");
System.out.println(b);
} else {
int leastMoves = Integer.MAX_VALUE;
for (Board board : winningBoards)
if (board.getMoves() < leastMoves)
leastMoves = board.getMoves();
System.out.println(leastMoves + \" moves\");
for (Board board : winningBoards) {
System.out.println(\"solution\");
System.out.println(board);
System.out.println(\"endsolution\");
}
}
System.out.println(\"endmap\");
// END
}
System.out.print(\"Complete\");
}
}
Board.java
package fullboard;
import java.util.*;
import org.apache.commons.lang3.*;
public class Board implements Comparable<Board> {
private char[][] spaces = null;
private int moves = 0, x = 0, y = 0, size = 0;
public Board(String map) {
String[] rows = StringUtils.split(map, \"\ \ \");
size = rows.length;
spaces = new char[rows.length][rows[0].length()];
for (int i = 0; i < rows.length; i++)
for (int j = 0; j < rows[i].length(); j++)
spaces[i][j] = rows[i].charAt(j);
}
public Board(Board other) {
char[][] copying = new char[other.spaces.length][other.spaces.length];
for (int i = 0; i < other.spaces.length; i++)
copying[i] = Arrays.copyOf(other.spaces[i], other.spaces.length);
spaces = copying;
moves = other.moves;
x = other.x;
y = other.y;
size = other.size;
}
public Board move(Direction d) {
switch (d) {
case UP:
for (int i = (x - 1); i >= 0; i--) {
if (spaces[i][y] != Space.EMPTY)
return null;
spaces[i][y] = Space.ARROW_UP;
if (spaces[i - 1][y] != Space.EMPTY) {
x = i;
break;
}
}
break;
case DOWN:
for (int i = (x + 1); i <= size; i++) {
if (spaces[i][y] != Space.EMPTY)
return null;
spaces[i][y] = Space.ARROW_DOWN;
if (spaces[i + 1][y] != Space.EMPTY) {
x = i;
break;
}
}
break;
case LEFT:
for (int i = (y - 1); i >= 0; i--) {
if (spaces[x][i] != Space.EMPTY)
return null;
spaces[x][i] = Space.ARROW_LEFT;
if (spaces[x][i - 1] != Space.EMPTY) {
y = i;
break;
}
}
break;
case RIGHT:
for (int i = (y + 1); i <= size; i++) {
if (spaces[x][i] != Space.EMPTY)
return null;
spaces[x][i] = Space.ARROW_RIGHT;
if (spaces[x][i + 1] != Space.EMPTY) {
y = i;
break;
}
}
break;
}
moves++;
return this;
}
public Board setStart(int xPos, int yPos) {
spaces[xPos][yPos] = Space.START;
x = xPos;
y = yPos;
return this;
}
public Board setFinish(int xPos, int yPos) {
spaces[xPos][yPos] = Space.FINISH;
x = xPos;
y = yPos;
return this;
}
@Override
public int compareTo(Board other) {
return this.toString().compareTo(other.toString());
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder(\"\");
for (int i = 0; i < spaces.length; i++) {
for (int j = 0; j < spaces[i].length; j++)
sb.append(spaces[i][j]);
if (i != (spaces.length - 1))
sb.append(\"\ \");
}
return sb.toString();
}
public boolean isSolvable() {
if (spaces[x - 1][y] != Space.EMPTY && spaces[x + 1][y] != Space.EMPTY && spaces[x][y - 1] != Space.EMPTY
&& spaces[x][y + 1] != Space.EMPTY)
return false;
return true;
}
public boolean isSolved() {
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
if (spaces[i][j] == Space.EMPTY)
return false;
return true;
}
public char getSpaceAt(int xPos, int yPos) {
return spaces[xPos][yPos];
}
public int getMoves() {
return moves;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getSize() {
return size;
}
}
Direction.java
package fullboard;
public enum Direction {
UP, DOWN, LEFT, RIGHT;
};
Space.java
package fullboard;
public class Space {
public static final char EMPTY = 32, FINISH = 70, START = 83, ARROW_LEFT = 0x2190, ARROW_UP = 0x2191,
ARROW_RIGHT = 0x2192, ARROW_DOWN = 0x2193, WALL = 0x2593;
}
smallmaps.txt
map
endmap
map
endmap
map
endmap
map
endmap
map
endmap
map
endmap
map
endmap
map
endmap
map
endmap
map
endmap
map
endmap
map
endmap
map
endmap
largemaps.txt
map
endmap
map
endmap
smallmaps_expected_out.txt
map
No solution
endmap
map
9 moves
solution
S
F
endsolution
endmap
map
9 moves
solution
S
F
endsolution
endmap
map
12 moves
solution
SF
endsolution
endmap
map
10 moves
solution
S
F
endsolution
endmap
map
10 moves
solution
F
S
endsolution
solution
F
S
endsolution
solution
F
S
endsolution
endmap
map
9 moves
solution
F
S
endsolution
endmap
map
11 moves
solution
F
S
endsolution
solution
F
S
endsolution
endmap
map
10 moves
solution
FS
endsolution
solution
F
S
endsolution
endmap
map
15 moves
solution
S
F
endsolution
solution
F
S
endsolution
endmap
map
10 moves
solution
S
F
endsolution
endmap
map
No solution
endmap
map
18 moves
solution
F
S
endsolution
endmap
Complete
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();
}
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()));
}
}
