Lab 5 Feedback
Marking scheme:
--------------------
1.6 / 2 -some unit tests failed; TAs, please check for errors
--------------------
TA Comments:
-you don't need indexOf in parenthIsNested; you can solve the problem just by
looking at the first and last characters of the string
-in parenthIsNested, you are forgetting the case where str is empty
(should return true)
-in genFractal, you should always generate 4 circles before checking mode:
public static void genFractal(List<Circle> circles, int x, int y, int radius, int n, boolean[] mode) {
if (n <= 0) {
// dont add any circles once radius too small
return;
}
// used to position left and right circles
int x1 = x - (radius);
int x2 = x + (radius);
int x3 = x;
int x4 = x;
int y1 = y;
int y2 = y;
int y4 = y + (radius);
int y3 = y - (radius);
if (radius > 2) {
// add circle to the left
circles.add(new Circle(x1, y1, radius / 2));
// add circle to the right
circles.add(new Circle(x2, y2, radius / 2));
// add circle above
circles.add(new Circle(x3, y3, radius / 2));
// add circle below
circles.add(new Circle(x4, y4, radius / 2));
}
if (mode[0])
genFractal(circles, x1, y1, radius / 2, n - 1, mode);
if (mode[1])
genFractal(circles, x2, y2, radius / 2, n - 1, mode);
if (mode[2])
genFractal(circles, x3, y3, radius / 2, n - 1, mode);
if (mode[3])
genFractal(circles, x4, y4, radius / 2, n - 1, mode);
return;
}
--------------------
Style checker output:
YOUR SUBMISSION FAILED SOME BASIC STYLE CHECKS
Here is the style checker output:
Starting audit...
RecursiveTasks.java:173:29: Must have at least one statement.
Audit done.
--------------------
Unit tester output:
YOUR SUMBISSION FAILED SOME UNIT TESTS
Here is the test output:
java -classpath .:/home/burton/work/teaching/2017F/2030/marking/lab6/_jar/* org.junit.runner.JUnitCore eecs2030.lab6.Lab6Suite
JUnit version 4.12
..E.E..E..E.E.E.E...E........E..E.....E.........E..........
Time: 0.013
There were 12 failures:
1) test_40_genFractal(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: Circles list incorrect [mode = {false,false,true,false}; n=5]
2) test_18_parenthIsNested(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: parenthIsNested("(())))") expected:<false> but was:<true>
3) test_41_genFractal(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: Circles list incorrect [mode = {false,false,false,true}; n=5]
4) test_42_genFractal(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: Circles list incorrect [mode = {false,false,false,false}; n=5]
5) test_30_genFractal(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: Circles list incorrect [mode = {true,true,true,true}; n=1]
6) test_15_parenthIsNested(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: parenthIsNested("(yy)") expected:<false> but was:<true>
7) test_31_genFractal(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: Circles list incorrect [mode = {true,true,true,true}; n=2]
8) test_32_genFractal(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: Circles list incorrect [mode = {true,true,true,true}; n=3]
9) test_38_genFractal(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: Circles list incorrect [mode = {true,false,false,false}; n=5]
10) test_39_genFractal(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: Circles list incorrect [mode = {false,true,false,false}; n=5]
11) test_23_numOccurrances(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: numOccurrences("iiijjj", "i") expected:<3> but was:<2>
12) test_17_parenthIsNested(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: parenthIsNested("((yy)))") expected:<false> but was:<true>
FAILURES!!!
Tests run: 47, Failures: 12
--------------------
Your submission:
package eecs2030.lab6;
import java.util.List;
/**
* A utility class containing several recursive methods (Lab 6, F2017)
*
* <pre>
*
* For all methods in this API, you are forbidden to use any loops, nor
* String or List based methods such as "contains", or methods that use regular expressions
* </pre>
*
* @author
*
*/
public final class RecursiveTasks {
private RecursiveTasks() {
}
/**
* getParenthesis returns the component within a given string that is enclosed
* in parenthesis
*
* <br>
* The method assumes there is only a single pair of parenthesis in the string,
* and computes the new string recursively, such that the new string is only
* made of the parenthesis and their contents.
*
* E.g.
*
* <pre>
* <code>getParenthesis("abcd(xyz)qrst")</code> will return "(xyz)"
* </pre>
*
* @param str
* the input string (with one pair of parenthesis embedded within)
* @return a string made only of the parenthesis and their contents (from str)
*/
public static String getParenthesis(String str) {
if (str.charAt(0) == '(') {
if (str.charAt(str.length() - 1) == ')') {
return str.substring(0, str.length());
}
else {
return getParenthesis(str.substring(0, str.length() - 1));
}
}
else {
return getParenthesis(str.substring(1, str.length()));
}
}
/**
* Count the number of co-occurrances of a non-empty sub-string <code>sub</code>
* within the string <code>str</code>
*
* E.g.
*
* <pre>
* <code>numOccurances("dogmonkeydog","dog")</code> will return 2
* <code>numOccurances("dogmonkeydog","mon")</code> will return 1
* <code>numOccurances("dogmonkeydog","cow")</code> will return 0
* </pre>
*
* @param str
* the given string
* @param sub
* a non-empty sub-string
* @return the number of times sub occurs in str, without overlap
*
*/
public static int numOccurrences(String str, String sub) {
if (str.equals(sub)) {
return 1;
} else if (str.length() < sub.length()) {
return 0;
} else {
if (str.substring(0, sub.length()).equals(sub)) {
return 1 + numOccurrences(str.substring(sub.length() + 1, str.length()), sub);
} else {
return 0 + numOccurrences(str.substring(1, str.length()), sub);
}
}
}
/**
* Given a string, return true if it is a nesting of zero or more pairs of
* balanced parenthesis, like "(())" or "((()))".
*
* If the parenthesis are unbalanced, or the string includes characters other
* than parenthesis, return false
*
* E.g.
*
* <pre>
* <code>parenthIsNested("(())")</code> will return true
* <code>parenthIsNested("((()))")</code> will return true
* <code>parenthIsNested("(((x))")</code> will return false
* </pre>
*
* Hint: check the first and last chars, and then recur on what's inside them.
*
* @param str
* - the string (includes zero or more pairs of parenthesis)
* @return a boolean value indicating true if the string contains nested and
* balanced parenthesis, false otherwise
*/
public static boolean parenthIsNested(String str) {
if (str.equals("()")) {
return true;
} else if (str.indexOf("(") < 0 && str.indexOf("(") < 0) {
return true;
}
else {
if (str.charAt(0) == '(') {
if (str.charAt(str.length() - 1) == ')') {
return true && parenthIsNested(str.substring(1, str.length() - 1));
} else {
return false;
}
}
return false;
}
}
/**
* Generates a list of Circles to be used in drawing a fractal pattern
*
* <pre>
* This method accepts a List of Circles (see Helper classes Circle.java and
* FractalPatterns.java To see how the list of Circles is generated, and how
* this method is envoked). You do not to perform any drawing operations in
* this task (they are done for you).
*
* The method computes the position of, and creates 4 new circles at each
* recursion step. Each circle is positioned at the vertical (top and
* bottom) and horizontal (left and right) intercepts with a imaginary
* circle (centred on x,y and with radius = <code>radius</code>). The radius
* of each circle created, is radius/2.
*
* The centre position of each newly generated circle will form the centre
* of a new set of 4 circles in the next recursive step, each with a reduced
* radius of (radius/4), and drawn on the vertical and horizontal intercepts
* of its parent circle, and so on (see diagram in lab description).
*
* </pre>
*
*
* @param circles
* a list in which to store circles as they are generated
* @param x
* the x coord of the centre of the current set of circles
* @param y
* the y coord of the centre of the current set of circles
* @param radius
* the radius of the parent circle
* @param n
* number of recursive steps to generate circles for
* @param mode
* a boolean array [left right up down] indicating which of the 4
* circles will be recursed on
*/
public static void genFractal(List<Circle> circles, int x, int y, int radius, int n, boolean[] mode) {
if (n == 0) {
/* Do nothing */
} else {
if (mode[0]) {
genCircle(circles, x, y, radius, 1); // caseNum = 1 (Used in genCircle)
genFractal(circles, x + radius * 2, y, radius / 2, n - 1, mode);
} else {
genCircle(circles, x, y, radius, 1); // caseNum = 1 (Used in genCircle)
}
if (mode[1]) {
genCircle(circles, x, y, radius, 2); // caseNum = 2 (Used in genCircle)
genFractal(circles, x - radius * 2, y, radius / 2, n - 1, mode);
} else {
genCircle(circles, x, y, radius, 2); // caseNum = 2 (Used in genCircle)
}
if (mode[2]) {
genCircle(circles, x, y, radius, 3); // caseNum = 3 (Used in genCircle)
genFractal(circles, x, y + radius * 2, radius / 2, n - 1, mode);
} else {
genCircle(circles, x, y, radius, 3); // caseNum = 3 (Used in genCircle)
}
if (mode[3]) {
genCircle(circles, x, y, radius, 4); // caseNum = 4 (Used in genCircle)
genFractal(circles, x, y - radius * 2, radius / 2, n - 1, mode);
} else {
genCircle(circles, x, y, radius, 4); // caseNum = 4 (Used in genCircle)
}
}
}
private static void genCircle(List<Circle> circles, int x, int y, int radius, int caseNum) {
Circle circle = null;
switch (caseNum) {
case 1:
circle = new Circle(x + radius * 2, y, radius);
break;
case 2:
circle = new Circle(x - radius * 2, y, radius);
break;
case 3:
circle = new Circle(x, y + radius * 2, radius);
break;
case 4:
circle = new Circle(x, y - radius * 2, radius);
break;
}
circles.add(circle);
}
/**
* Calculate and determine if there exists a sum of (some) of the elements in an
* integer array that is equal to a target value. If there exists a sum, then
* return true, otherwise false.
*
* Given an array of ints, is it possible to choose a group of some of the ints,
* such that the group sums to the given target?
*
* Assume this method is always called with a starting index of 0 and a sum of 0
* Recursion traverses the array and explores alternative sums
*
* <pre>
* e.g.
* sumSome(0, [2, 4, 8], 10) will return true
* sumSome(0, [2, 4, 8], 14) will return true
* sumSome(0, [2, 4, 8], 9) will return false
* </pre>
*
* @param index
* the current position in nums
* @param nums
* an array of integers to be considered in the sum
* @param sum
* the current sum
* @param target
* the value some of the integers in nums should add up to
* @return a boolean value indicating that a sum of some of the integers in nums
* equals the target
*/
public static boolean sumSome(int index, int[] nums, int sum, int target) {
if (index >= nums.length) {
return sum == target;
} else if (sumSome(index + 1, nums, sum + nums[index], target)) {
return true;
} else if (sumSome(index + 1, nums, sum, target)) {
return true;
}
return false;
}
}