<![CDATA[
Problem #1
108 [5, 10, 14]
8 [5, 10, 14]
20 8
first 2 lines are 2 points
third line is 1 point
-1 per incorrect token on a given line
-0 for quotes
-1 off the top if a non-quote formatting error (underscores okay for spaces)
-------------------------------------------------------------------------------
Problem #2:
Original List Final List
--------------------------------------------------------------
{4, 1, 3} {4, 1, 2}
{2, 1, 3, 2} {2, 1, 2, 4}
{3, 6, 2, 9, 5} {3, 6, 2, 4, 6}
{1, 1, 1, 1, 8} {1, 1, 2, 1, 6}
{1, 3, 4, 6, 2, 9} {1, 3, 2, 4, 2, 8}
2 points for each answer
-1 for each wrong number
-1 for each missing number
curly braces and commas are not required if sequence is clear
any given answer can't go negative
-------------------------------------------------------------------------------
Problem #3:
a c a c
a 1 c 1 a 1 d 1
b 2 c 2 c 2 c 2
1/2 point each (half points okay in final score)
-0 if spaces are not obvious (e.g., "a1" versus "a 1")
-1 off the top if any formatting error (quotes, labels, commas, etc)
-1 if first row appears as last row
-2 if values transposed
boxes/lines/grid/arrows are all okay because they are clearly not output
-------------------------------------------------------------------------------
Problem #4
Solutions:
public static void reportScore(Scanner input) {
int score = 0;
int count = 0;
while (input.hasNextInt()) {
int next = input.nextInt();
String type = input.next();
count += next;
if (type.equals("*")) {
score = score + next;
} else {
score = score - next;
}
}
String name = input.next();
System.out.println(name + " got " + score + " of " + count);
}
public static void reportScore(Scanner input) {
int numStar = 0;
int numMinus = 0;
while (input.hasNextInt()) {
int next = input.nextInt();
String type = input.next();
if (type.equals("*")) {
numStar += next;
} else {
numMinus += next;
}
}
String name = input.next();
System.out.println(name + " got " + (numStar - numMinus) + " of "
+ (numStar + numMinus));
}
1 header (non-void return type ok if consistent with a return statement)
3 while loop that reads number/type pairs
1 loop attempt (some kind of hasNextSomething)
1 reading attempt (2 variables, 2 calls on nextSomething)
1 correct: loop test is hasNextInt(), correct types for variables, correct
order, nextInt()/next(), always reads 2 tokens on each loop iteration
4 score and count properly initialized/updated
1 reasonable attempt for 3 of the following:
* initialize a count to 0 before loop
* initialize a score to 0 before loop
* increment overall count by next or equivalent (see 2nd solution)
* test against "*" or "-" (test with == is okay)
* increment score by next for "*"
* decrement score by next for "-" or equivalent (see 2nd solution)
1 at least 4 of the previous correct
1 correct comparison (String comparison using equals against "*" or "-")
1 all correct ignoring == vs equals (two counters properly initialized,
count incremented by count each time through loop, score incremented or
decremented by count depending on */-)
1 reads name with next() after loop
1 correct println after loop (print is not okay); assume variables have correct
values, can get this point even if it is in the loop if they lost a point for
reading name with next() being inside the loop
-------------------------------------------------------------------------------
Problem #5
Solution:
public static void reverseAndFlip(Scanner input) {
while (input.hasNextLine()) {
String first = input.nextLine();
if (input.hasNextLine()) {
String second = input.nextLine();
for (int i = second.length() - 1; i >= 0; i--) {
System.out.print(second.charAt(i));
}
System.out.println();
}
System.out.println(first);
}
}
1 header (non-void return type ok if consistent with a return statement)
1 correct while loop (while hasNextLine)
5 reading and printing lines assuming even number of lines (only the 5th point
requires a loop)
1 reasonable attempt to read two lines
1 reasonable attempt to print both lines in flipped order (can be print)
1 reasonable attempt to print a line in reverse order
1 correctly prints some line in reverse order (requires a println)
1 overall loop structure is correct: always reads two lines in a loop and
prints them in flipped order and attempts to print second line reversed
(requires println for non-reversed line, but reversed line just requires
attempt)
2 works for odd number of lines (requires a loop, generally atomic, but ask the
question leader if you think someone is close)
-------------------------------------------------------------------------------
Problem #6
Solutions:
// start at index 0 and compare list[i]/list[i+1], adding 2 to i
// requires "list.length - 1" or equivalent in test to handle odd case
public static boolean isPairwiseSorted(int[] list) {
for (int i = 0; i < list.length - 1; i += 2) {
if (list[i] > list[i + 1]) {
return false;
}
}
return true;
}
// start at index 0 and compare list[i]/list[i+1], adding 1 to i
// requires test on i % 2 == 0 so they don't test all pairs
// requires "list.length - 1" or equivalent in test to handle odd case
public static boolean isPairwiseSorted(int[] list) {
for (int i = 0; i < list.length - 1; i++) {
if (i % 2 == 0 && list[i] > list[i + 1]) {
return false;
}
}
return true;
}
// start at index 1 and compare list[i]/list[i-1], adding 2 to i
// does NOT require special adjustment to length test
public static boolean isPairwiseSorted(int[] list) {
for (int i = 1; i < list.length; i += 2) {
if (list[i] < list[i - 1]) {
return false;
}
}
return true;
}
// start at index 0 and compare list[2*i]/list[2*i+1], adding 1 to i
// requires testing list.length/2, but no special test for odd length
public static boolean isPairwiseSorted(int[] list) {
for (int i = 0; i < list.length / 2; i++) {
if (list[2 * i] > list[2 * i + 1]) {
return false;
}
}
return true;
}
1 header
5 loop that compares adjacent pairs for an even length array
1 loop attempt (some for loop over array length)
1 comparison attempt (comparing list[i]/list[i+1] or list[i]/list[i-1]) or
equivalent
1 correct comparison (must be adjacent pair, must test that the first is
greater than the second)
2 correct structure to compare each successive pair exactly once (mostly
atomic, but ask question leader for possible -1 if they are close)
2 handles odd length case
1 some attempt to test or adjust for a possible odd length array or they
had an approach like using list.length/2 that doesn't require adjustment)
1 correctly handles odd length array without throwing an exception
(requires that they are comparing adjacent elements and that an odd
element at the end does not lead to an extra comparison, but no double
jeopardy with test correctness)
2 true/false/return structure: correctly returns true/false based on a test in
a loop (requires some kind of test in a loop, but assume test works). This
is generally atomic but can be worth 1 point for solutions that are close.
For example, if their only error is that they forgot "return true" after the
loop, they get 1 point. Or their only error might be to fail to return true
for an array of length less than 2, in which case they get 1 point. If they
switch true/false or if they prematurely return true, they lose both points.
Ask the question leader if you see something that might be close.
-------------------------------------------------------------------------------
Problem #7
Solutions:
public static void reverse3(ArrayList<Integer> list) {
for (int i = 0; i < list.size() - 2; i += 3) {
int n1 = list.get(i);
int n3 = list.get(i + 2);
list.set(i, n3);
list.set(i + 2, n1);
}
}
public static void reverse3(ArrayList<Integer> list) {
for (int i = 0; i < list.size() - 2; i += 3) {
list.add(i, list.remove(i + 2));
list.add(i + 2, list.remove(i + 1));
}
}
1 header (return type ok if consistent with a return statement, parameter must
be ArrayList<Integer>)
4 loop over triples (ignore errors introduced by reversing code)
1 attempt (some kind of loop from the start of the list to list.size())
1 correct number of iterations (iterates exactly n times where n is the
number of complete triples or uses something like an if to exclude an
incomplete triple)
2 increments an index variable by 3 each time or equivalent
4 reverses each triple (using an index variable, they are manipulating a group
of 3 adjacent elements of the list--for this just grade whether it works for
that tiny neighborhood of 3 values without thinking about loop correctness):
1 reasonable attempt to perform one of the required steps
a call on get and set that makes sense
a call on both add and remove that makes sense
an array-style assign that makes sense
1 reasonable attempt to perform a second required step
a call on get and set that makes sense
a call on both add and remove that makes sense
note: here an array-style assign is not okay
2 correct (any combination that works)
1 correct combination of loop and reversal (in other words, they got all of
those correctness points AND the pieces fit together properly)
Notes:
Saying list.size without parens or using brackets (list.get[i], list.remove[i])
are syntax mistakes. They get one free syntax mistake, max -2 for syntax.
-2 for calling set/add/get without saying "list." (only apply this rule if
their score goes up)
extra data structure goes to question leader
Problem #8
Solution:
public class Ferret extends Critter {
private int infectCount;
private Random r;
public Ferret() {
r = new Random();
}
public Action getMove(CritterInfo info) {
if (infectCount > 0) {
infectCount--;
}
if (info.getFront() == Neighbor.OTHER) {
infectCount = 5;
return Action.INFECT;
} else if (info.getFront() == Neighbor.EMPTY) {
return Action.HOP;
} else {
int choice = r.nextInt(2);
if (choice == 0) {
return Action.LEFT;
} else {
return Action.RIGHT;
}
}
}
public Color getColor() {
if (infectCount > 0) {
return Color.RED;
} else {
return Color.BLUE;
}
}
public String toString() {
return "I=" + infectCount;
}
}
1 correct class header
3 declaring fields and constructor
1 field to count moves since infect (declared, modified somewhere)
1 field for Random object (declared, used somewhere)
1 they have a constructor with a correct header that correctly initializes
a Random object and that includes any other initialization to non-default
values
4 correctly updates state
1 reasonable attempt to set count to 5 when infecting
1 reasonable attempt to decrement count when not infecting
1 reasonable attempt to stop decrementing count when count gets back to 0
(requires a test for this case)
1 all correct (must update ALL fields properly, including display field)
2 toString
1 reasonable attempt to return "I=" + count (okay to do this with a display
field that is updated)
1 all correct (correct header, returns "I=0" initially, works correctly
assuming count/display field is updated properly)
3 getMove
1 correct header
1 has cases for returning INFECT, HOP, LEFT, RIGHT
1 correct move (INFECT when enemy in front, HOP when front is clear,
otherwise randomly choose between LEFT and RIGHT)
2 getColor
1 reasonable attempt to return either Color.RED or Color.BLUE
1 all correct (correct header, starts with blue, correctly returns red/blue
assuming count/display field is updated correctly)
notes:
-1 if they have code after a return (e.g., setting a field)
-1 if any field is not private
-1 if they update any fields outside of getMove
-1 if they make a field static
-------------------------------------------------------------------------------
Problem #9
Solutions:
public static int[] splice(int[] list, int from, int to) {
int[] result = new int[list.length];
int index = 0;
// copy "after sublist" part
for (int i = to; i < list.length; i++) {
result[index] = list[i];
index++;
}
// copy sublist part
for (int i = from; i < to; i++) {
result[index] = list[i];
index++;
}
// copy "before sublist" part
for (int i = 0; i < from; i++) {
result[index] = list[i];
index++;
}
return result;
}
public static int[] splice(int[] list, int from, int to) {
int[] result = new int[list.length];
// copy "before sublist" part
for (int i = 0; i < from; i++) {
result[result.length - from + i] = list[i];
}
// copy sublist part
for (int i = from; i < to; i++) {
result[result.length - to + i - from] = list[i];
}
// copy "after sublist" part
for (int i = to; i < result.length; i++) {
result[i - to] = list[i];
}
return result;
}
public static int[] splice(int[] list, int from, int to) {
int[] result = new int[list.length];
// copy "after sublist" part
for (int i = 0; i < list.length - to; i++) {
result[i] = list[to + i];
}
// copy sublist part
for (int i = 0; i < to - from; i++) {
result[list.length - to + i] = list[from + i];
}
// copy "before sublist" part
for (int i = 0; i < from; i++) {
result[list.length - from + i] = list[i];
}
return result;
}
1 header
2 constructing the new array of appropriate size
1 attempt (construct some new array mostly ignoring syntax)
1 correct (array of int, size correct)
3 setting low range of result ("after sublist" part)
for (int i = to; i < list.length; i++)
result[i - to] = list[i];
for (int i = 0; i < list.length - to; i++)
result[i] = list[to + i];
1 reasonable attempt:
* separate loop or if/else branch for this case
* assignment and/or index range indicates that they are solving this
part of the problem (must be copying from list to result)
1 correct number of iterations: list.length - to
1 correct copy (-1 if obob or otherwise close)
* alignment--first one is copied correctly: result[0]
* delta is correct: list.length - to
4 setting middle range (sublist part)
for (int i = from; i < to; i++)
result[i + list.length - to - from] = list[i];
for (int i = 0; i < to - from; i++)
result[i + list.length - to] = list[i + from];
for (int i = list.length - to; i < list.length - from; i++)
result[i] = list[i + from + to - list.length];
1 reasonable attempt:
* separate loop or if/else branch for this case
* assignment and/or index range indicates that they are solving this
part of the problem (must be copying from list to result)
1 correct number of iterations: to - from
2 correct copy (-1 if obob or otherwise close)
* alignment--first one is copied correctly: result[list.length - to]
* delta is correct: from + to - list.length
4 setting high range ("before sublist" part)
for (int i = 0; i < from; i++)
result[i + list.length - from] = list[i];
for (int i = list.length - from; i < list.length; i++)
result[i] = list[i + from - list.length];
1 reasonable attempt:
* separate loop or if/else branch for this case
* assignment and/or index range indicates that they are solving this
part of the problem (must be copying from list to result)
1 correct number of iterations: from
2 correct copy (-1 if obob or otherwise close)
* alignment--first one is copied correctly: result[list.length - from]
* delta is correct: from - list.length
1 returns their answer (requires construct attempt)
Notes:
ArrayList solutions or extra data structures solutions go to question leader
Syntax errors are capped at -2.
Problem #10, 6-point option
solution:
public static boolean isMatch(String pattern, String text) {
if (text.length() != pattern.length()) {
return false;
}
for (int i = 0; i < pattern.length(); i++) {
char ch1 = pattern.charAt(i);
char ch2 = text.charAt(i);
if (ch1 != '.' && ch1 != ch2) {
return false;
}
}
return true;
}
1 header
2 looping over one string and returning false for strings of unequal length
1 reasonable attempt for both or correct for one
1 correct for both
2 attempt to compare corresponding characters
1 reasonable attempt to return false if 2 chars don't match
1 reasonable attempt to avoid this test if pattern char is a dot
1 works correctly in all cases when string lengths match
Problem #10, 10-point option
Solutions:
// correct solution using Java's regex matcher
public static boolean isMatch(String pattern, String text) {
return text.matches(pattern.replace("*", ".*"));
}
// solution that manipulates i and j at the same time
public static boolean isMatch(String pattern, String text) {
int i = 0;
int j = 0;
while (i < pattern.length() && j < text.length()) {
if (pattern.charAt(i) == '*') {
int diff = text.length() - pattern.length() + 1;
if (diff < 0) {
return false;
} else {
i++;
j += diff;
}
} else if (pattern.charAt(i) != '.' &&
pattern.charAt(i) != text.charAt(j)) {
return false;
} else {
i++;
j++;
}
}
// special case for '*' as last char of pattern
if (i == pattern.length() - 1 && pattern.charAt(i) == '*') {
i++;
}
return i == pattern.length() && j == text.length();
}
// correct solution that loops over the pattern
int j = 0;
for (int i = 0; i < pattern.length(); i++) {
char ch1 = pattern.charAt(i);
if (ch1 == '*') {
int diff = text.length() - pattern.length() + 1;
if (diff < 0) {
return false;
} else {
j += diff;
}
} else {
if (j >= text.length()) {
return false;
}
char ch2 = text.charAt(j);
j++;
if (ch1 != '.' && ch1 != ch2) {
return false;
}
}
}
return j == text.length();
// solution that uses substring to handle the star first
public static boolean isMatch(String pattern, String text) {
int star = pattern.indexOf("*");
if (star != -1) {
int diff = text.length() - pattern.length() + 1;
if (diff < 0) {
return false;
} else {
pattern = pattern.substring(0, star) +
pattern.substring(star + 1);
text = text.substring(0, star) + text.substring(star + diff);
}
} else if (pattern.length() != text.length()) {
return false;
}
for (int i = 0; i < text.length(); i++) {
char ch1 = pattern.charAt(i);
char ch2 = text.charAt(i);
if (ch1 != '.' && ch1 != ch2) {
return false;
}
}
return true;
}
// another substring solution based on star index that replaces the star
// with a sequence of dots
public static boolean isMatch(String pattern, String text) {
int star = pattern.indexOf("*");
int count = 0;
for
for (int i = star + 1; i < text.length(); i++) {
char ch1 = pattern.charAt(star + 1 + i);
char ch2 = text.charAt(i);
if (ch1 != '.' && ch1 != ch2) {
return false;
}
}
if (star != -1) {
pattern = pattern.substring(0, star) + pattern.substring(star + 1);
while (pattern.length() < text.length()) {
pattern = pattern.substring(0, star) + "." +
pattern.substring(star);
}
}
if (pattern.length() != text.length()) {
return false;
}
return true;
}
// solution that has two loops to check characters before and after star
public static boolean isMatch(String pattern, String text) {
int star = pattern.indexOf("*");
// have to handle funky edge cases where pattern has too many chars
if (star == -1 && pattern.length() != text.length() ||
star != -1 && pattern.length() - 1 > text.length()) {
return false;
}
// check forwards
for (int i = 0; i < star; i++) {
char ch1 = pattern.charAt(i);
char ch2 = text.charAt(i);
if (ch1 != '.' && ch1 != ch2) {
return false;
}
}
// check backwards
for (int i = 1; i < pattern.length() - star; i++) {
char ch1 = pattern.charAt(pattern.length() - i);
char ch2 = text.charAt(text.length() - i);
if (ch1 != '.' && ch1 != ch2) {
return false;
}
}
return true;
}
Send back to round 1 any solution that doesn't have an approach to the star
problem that can succeed:
* use of substring to eliminate a portion of the string
* incrementing an index for star using the difference of the string lengths
Deductions
-3 major error
-2 medium error
&& vs ||
need to delete nontrivial code of theirs
-1 minor error
OBOB (you can fix code by changing one expression by +1 or -1)
charAt or length instead of s.charAt, s.length
testing whether character is null instead of ' '
fails for star at beginning or end of string
-0 minor syntax errors
String result = s.charAt(0);
String new = ... (reserved word)
s.length vs s.length()
string/char confusion (==, .equals)
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011