Lab 5 Feedback
Marking scheme:
--------------------
1.3 / 2 -some unit tests failed; TAs, please check for errors
--------------------
TA Comments:
-there should not be a loop in either genFractal or sumSome:
public static void genFractal(List<Circle> circles, int x, int y, int radius, int n, boolean [] mode) {
if (n == 0) {
return;
}
int halfR = radius / 2;
Circle c = new Circle(x - radius, y, halfR);
circles.add(c);
c = new Circle(x + radius, y, halfR);
circles.add(c);
c = new Circle(x, y + radius, halfR);
circles.add(c);
c = new Circle(x, y - radius, halfR);
circles.add(c);
if (mode[0]) {
// generate circles to the left
RecursiveTasks.genFractal(circles, x - radius, y, halfR, n - 1, mode);
}
if (mode[1]) {
// generate circles to the right
RecursiveTasks.genFractal(circles, x + radius, y, halfR, n - 1, mode);
}
if (mode[2]) {
// generate circles above
RecursiveTasks.genFractal(circles, x, y + radius, halfR, n - 1, mode);
}
if (mode[3]) {
// generate circles below
RecursiveTasks.genFractal(circles, x, y - radius, halfR, n - 1, mode);
}
}
public static boolean sumSome(int index, int[] nums, int sum, int target) {
if (sum == target) {
return true;
}
else if (index >= nums.length) {
return false;
}
else if (sum > target) {
return false;
}
boolean hasIndex = RecursiveTasks.sumSome(index + 1, nums, sum + nums[index], target);
if (hasIndex) {
return true;
}
return RecursiveTasks.sumSome(index + 1, nums, sum, target);
}
--------------------
Style checker output:
No style errors found by checkstyle; TAs, please check for poorly named
variables, unusual programming constructs, and other style errors.
--------------------
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.011
There were 12 failures:
1) test_40_genFractal(eecs2030.lab6.RecursiveTests)
java.util.ConcurrentModificationException
2) test_41_genFractal(eecs2030.lab6.RecursiveTests)
java.util.ConcurrentModificationException
3) test_42_genFractal(eecs2030.lab6.RecursiveTests)
java.util.ConcurrentModificationException
4) test_30_genFractal(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: Circles list incorrect [mode = {true,true,true,true}; n=1]
5) test_31_genFractal(eecs2030.lab6.RecursiveTests)
java.util.ConcurrentModificationException
6) test_56_sumSome(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: sumSome(0,[],0,0) expected:<true> but was:<false>
7) test_32_genFractal(eecs2030.lab6.RecursiveTests)
java.util.ConcurrentModificationException
8) test_58_sumSome(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: sumSome(0,[10,2,2,5],0,15) expected:<true> but was:<false>
9) test_38_genFractal(eecs2030.lab6.RecursiveTests)
java.util.ConcurrentModificationException
10) test_39_genFractal(eecs2030.lab6.RecursiveTests)
java.util.ConcurrentModificationException
11) test_50_sumSome(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: sumSome(0,[2,4,8],0,10) expected:<true> but was:<false>
12) test_57_sumSome(eecs2030.lab6.RecursiveTests)
java.lang.AssertionError: Failed: sumSome(0,[10,2,2,5],0,17) expected:<true> but was:<false>
FAILURES!!!
Tests run: 47, Failures: 12
--------------------
Your submission:
package eecs2030.lab6;
import java.util.ArrayList;
import java.util.Arrays;
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.endsWith(")")) {
String result = str.substring(0, str.length() - 1);
str = RecursiveTasks.getParenthesis(result);
return str;
} else if (!str.startsWith("(")) {
String result = str.substring(1, str.length());
str = RecursiveTasks.getParenthesis(result);
return str;
} else {
return str;
}
}
/**
* 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.length() < sub.length()) {
return 0;
} else if (str.equals(sub)) {
return 1;
} else if (str.startsWith(sub)) {
String result = str.substring(sub.length(), str.length());
int sum = RecursiveTasks.numOccurrences(result, sub);
return sum + 1;
} else {
String result = str.substring(1, str.length());
int sum = RecursiveTasks.numOccurrences(result, sub);
return sum;
}
}
/**
* 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.isEmpty()) {
return true;
}
if (str.startsWith("(") && str.endsWith(")")) {
String result = str.substring(1, str.length() - 1);
boolean isit = RecursiveTasks.parenthIsNested(result);
return isit;
} else {
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) {
circles.add(new Circle(-radius, y, radius / 2));
circles.add(new Circle(radius, y, radius / 2));
circles.add(new Circle(x, -radius, radius / 2));
circles.add(new Circle(x, radius, radius / 2));
if (n > 1) {
for (Circle k : circles) {
RecursiveTasks.genFractal(circles, k.getX(), k.getY(), k.getRad(), n - 1, mode);
}
}
return;
}
/**
* 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) {
boolean result = false;
if (index >= nums.length)
return false;
else if (nums[index] == target)
return true;
sum = 0;
for (int k = index; k < nums.length; k++) {
sum += nums[k];
if (sum == target)
return true;
}
sum = 0;
for (int k = nums.length - 1 - index; k >= 0; k--) {
sum += nums[k];
if (sum == target)
return true;
}
result = RecursiveTasks.sumSome(index + 1, nums, sum, target);
return result;
}
}