<![CDATA[
Problem #1
3 [2, 3, 7]
1 [2, 3, 7]
17 7
first 2 lines are 2 points
third line is 1 point
-1 per incorrect token on a given line
-0 for quotes
-0 for {} instead of []
-1 off the top if a non-quote formatting error (underscores okay for spaces)
-------------------------------------------------------------------------------
Problem #2:
Original List Final List
--------------------------------------------------------------
{0, 2, 3} {0, 2, 5}
{1, 1, 4, 5} {1, 1, 3, 7}
{3, 1, 2, 9, 5} {3, 1, 3, 7, 5}
{5, 1, 1, 1, 8} {5, 1, 3, 7, 8}
{2, 1, 1, 2, 3, 4} {2, 1, 3, 7, 3, 7}
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:
d a d d
b 1 b 1 d 1 c 1
b 2 b 2 d 2 d 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
Solution:
public static void tallyScores(Scanner input) {
while (input.hasNext()) {
String name = input.next();
System.out.print(name + ":");
int points = 0;
int count = 0;
while (input.hasNextInt()) {
int nextPoints = input.nextInt();
points += nextPoints;
count++;
System.out.print(" " + nextPoints);
}
System.out.println();
double average = (double) points / count;
System.out.println("average = " + average);
}
}
1 header (non-void return type ok if consistent with a return statement)
2 outer while loop that prints name
1 reasonable attempt: two of the following:
while loop exists
test is hasNext()
reads one string with input.next()
prints name (doesn't require colon)
1 all four of these are correct
3 inner while loop that reads ints and prints them
1 reasonable attempt at loop (has to be a different loop than previous)
1 reasonable attempt to read and print an int
1 all correct: test is hasNextInt, reads exactly one int using nextInt,
stores value in a variable, prints value (doesn't require a space)
3 average computation
1 reasonable attempt to be able to compute the average of the scores: 3 of
the following
initialize counter to 0
initialize sum to 0
increment counter each time they read a score
increment sum by next score
1 reasonable attempt to compute average (sum / count) and print it
1 all correct other than formatting (requires conversion to double and
correct resetting of sum and count for each new student)
1 prints all three elements (name, score, average) with correct formatting:
correct use of print/println, spaces between numbers, all formatting is
correct, elements are printed in correct order
-------------------------------------------------------------------------------
Problem #5
Solution:
public static void switchNames(Scanner input) {
while (input.hasNextLine()) {
String line = input.nextLine();
if (line.equals("name:")) {
String line2 = input.nextLine();
int commaIndex = line2.indexOf(",");
String last = line2.substring(0, commaIndex);
String first = line2.substring(commaIndex + 2);
System.out.println(first + " " + last);
} else {
System.out.println(line);
}
}
}
1 header (non-void return type ok if consistent with a return statement)
3 overall structure for echoing input to output
1 correct while loop (while hasNextLine)
1 reads and stores a line using nextLine()
1 sometimes echos a line with System.out.println (requires reading point)
5 correctly handles "name:" lines
1 reasonable attempt to test for "name:" (can be ==)
1 reasonable attempt to read another line and split it into first and last
names
1 at least four of these are correct
correct test for .equals("name:")
reads a second line in that case and stores it in a variable
uses indexOf or equivalent to find index of comma
calls substring to get first and last name
substring indexes are close (within 2 for each)
substring indexes are correct
1 at least five of the previous are correct
1 all six of these are correct and it correctly prints the first name
followed by last name with a space in between and non-"name:" lines are
echoed correctly and no extraneous output (this is the nit-picky
uber-correctness point)
-------------------------------------------------------------------------------
Problem #6
Solution:
public static int minGap(int[] list) {
if (list.length < 2) {
return 0;
} else {
int min = list[1] - list[0];
for (int i = 2; i < list.length; i++) {
int gap = list[i] - list[i - 1];
if (gap < min) {
min = gap;
}
}
return min;
}
}
1 header
2 works for an array of length < 2
1 reasonable attempt to test for this
1 correct test and returns 0
3 loop that correctly computes gaps
1 reasonable attempt (some for loop over array length)
1 reasonable attempt to compute gap between adjacent elements
1 all correct: generates all relevant adjacent pairs without going out of
bounds (doesn't have to generate first pair if handled outside loop) and
gaps computed correctly
3 correctly computes min
1 reasonable attempt to initialize min to something big
1 correctly updates min inside a loop assuming gap computation is correct
1 min is intialized to first gap or Integer.MAX_VALUE
1 returns min after a loop
-------------------------------------------------------------------------------
Problem #7
Solutions:
// one loop, going forward, needs i++/i--
public static void cloneOddsRemoveEvens(ArrayList<Integer> numbers) {
for (int i = 0; i < numbers.size(); i++) {
int n = numbers.get(i);
if (n % 2 == 0) {
numbers.remove(i);
i--;
} else {
numbers.add(i, n);
i++;
}
}
}
// one loop, going backwards, doesn't need i++/i--
public static void cloneOddsRemoveEvens(ArrayList<Integer> numbers) {
for (int i = numbers.size() - 1; i >= 0; i--) {
int n = numbers.get(i);
if (n % 2 == 0) {
numbers.remove(i);
} else {
numbers.add(i, n);
}
}
}
// two loops, going forward, need i++/i--, no if required in second loop
// because remove is done first
public static void cloneOddsRemoveEvens(ArrayList<Integer> numbers) {
for (int i = 0; i < numbers.size(); i++) {
if (numbers.get(i) % 2 == 0) {
numbers.remove(i);
i--;
}
}
for (int i = 0; i < numbers.size(); i += 2) {
numbers.add(i + 1, numbers.get(i));
}
}
1 header (return type ok if consistent with a return statement, parameter must
be ArrayList<Integer>)
2 loop structure
1 loop attempt (loop using list.size() or list.length() or list.length)
1 reasonable attempt to test for odd/even (array notation okay)
3 removing even values
1 reasonable attempt to remove even values (can be "remove" instead of
"list.remove", can be at wrong index)
1 reasonable attempt to account for shifting problem when removing
(typically i-- but could also be a loop that goes backwards)
1 correct call on list.remove(i) and correctly accounts for shifting
problem when list is composed entirely of evens
3 cloning odd values
1 reasonable attempt to clone odd values (can be "add" instead of
"list.add", can be at wrong index, can use array syntax for value to add)
1 reasonable attempt to account for shifting problem when adding
(typically i++ but could also be a loop that goes backwards)
1 correct call on list.add at i or i+1 adding list.get(i) and correctly
accounts for shifting problem when list is composed entirely of odds
1 pieces fit together: odd/even test is correct (requires list.get), correctly
accounts for shifting for both odds and evens, loop has correct bounds, works
for mixture of odds and evens
Notes:
Saying list.size without parens or using brackets on method calls (list.get[i],
list.remove[i]) are syntax mistakes. They get one free syntax mistake, max -2
for syntax.
extra data structure goes to question leader
Problem #8
Solution:
public class Spider extends Critter {
private boolean south;
private int moves;
public Action getMove(CritterInfo info) {
if (info.getFront() == Neighbor.OTHER) {
return Action.INFECT;
} else if (south && info.getDirection() != Direction.SOUTH) {
return Action.LEFT;
} else if (!south && info.getDirection() != Direction.NORTH) {
return Action.LEFT;
} else if (info.getFront() == Neighbor.EMPTY) {
moves++;
return Action.HOP;
} else {
south = !south;
moves = 0;
return Action.LEFT;
}
}
public Color getColor() {
return Color.GREEN;
}
public String toString() {
if (south) {
return "S-" + moves;
} else {
return "N-" + moves;
}
}
}
1 correct class header
2 declaring fields
1 field to keep track of mode (desired direction north/south)
1 field to count hops in desired direction
-1 if any field is not private
-1 if they set field to a non-default value outside of a legal constructor
-1 if they make a field static
2 toString
1 reasonable attempt to return "N-"+hops or "S-"+hops (okay to do this with
a display field that is updated)
1 all correct (correct header, returns "N=0" initially, works correctly
assuming direction/hops fields are updated properly--if they return a
display field, then they must have code in getMove to set the display
field to either "N-" or "S-" plus hops; a call on getDirection doesn't
work)
1 getColor
5 getMove
1 correct header
1 has cases for returning INFECT, HOP, LEFT
1 correct moves when facing in desired direction (infect when enemy is in
front, otherwise hop if front is empty, otherwise turn left)
2 turns left when not facing in desired direction and no enemy to infect
(requires call on getDirection, -1 if close)
4 updating state
1 reasonable attempt to count number of hops
1 reasonable attempt to reset direction when unable to hop
1 correctly counts hops (requires resetting to 0 when updating direction)
1 correctly updates direction when unable to hop
notes:
-1 if they have code after a return (e.g., setting a field)
-1 if they update any fields outside of getMove (only take off this point
if they earned points for the code)
-------------------------------------------------------------------------------
Problem #9
Solutions:
public static int[] insert(int[] list1, int[] list2, int index) {
int[] result = new int[list1.length + list2.length];
// copy "before" part
for (int i = 0; i < index; i++) {
result[i] = list1[i];
}
// copy "middle" part--list2
for (int i = 0; i < list2.length; i++) {
result[index + i] = list2[i];
}
// copy "after" part
for (int i = index; i < list1.length; i++) {
result[list2.length + i] = list1[i];
}
return result;
}
public static int[] insert(int[] list1, int[] list2, int index) {
int[] result = new int[list1.length + list2.length];
// copy "before" part
int newIndex = 0;
for (int i = 0; i < index; i++) {
result[newIndex] = list1[i];
newIndex++;
}
// copy "middle" part--list2
for (int i = 0; i < list2.length; i++) {
result[newIndex] = list2[i];
newIndex++;
}
// copy "after" part
for (int i = index; i < list1.length; i++) {
result[newIndex] = list1[i];
newIndex++;
}
return result;
}
public static int[] insert(int[] list1, int[] list2, int index) {
int[] result = new int[list1.length + list2.length];
for (int i = 0; i < result.length; i++) {
if (i < index) { // "before"
result[i] = list1[i];
} else if (i < index + list2.length) { // "middle"
result[i] = list2[i - index];
} else { // "after"
result[i] = list1[i - list2.length];
}
}
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 ("before" sublist)
for (int i = 0; i < index; i++)
result[i] = list1[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 list1 to result)
1 correct number of iterations: index
1 correct copy (-1 if obob or otherwise close)
* alignment--first one copied correctly: result[0]
* delta is correct: 0
4 setting middle range (list2)
for (int i = 0; i < list2.length; i++)
result[i + index] = list2[i];
for (int i = index; i < index + list2.length; i++)
result[i] = list2[i - index];
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 list2 to result)
1 correct number of iterations: list2.length
2 correct copy (-1 if obob or otherwise close)
* alignment--first one copied correctly: result[index]
* delta is correct: -index
4 setting high range ("after" sublist)
for (int i = index; i < list1.length; i++)
result[i + list2.length] = list1[i];
for (int i = 0; i < list1.length - index; i++)
result[i + index + list2.length] = list1[i + index];
for (int i = index + list2.length; i < result.length; i++)
result[i] = list1[i - list2.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 list1 to result)
1 correct number of iterations: list1.length - index
2 correct copy (-1 if obob or otherwise close)
* alignment--first one copied correctly: result[index + list2.length]
* delta is correct: -list2.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.
For ArrayList, eligible for: header, loop attempt/bounds, return (max 8)
Problem #10
Solutions:
public static boolean samePattern(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j < s1.length(); j++) {
if (s1.charAt(i) == s1.charAt(j) &&
s2.charAt(i) != s2.charAt(j)) {
return false;
}
if (s2.charAt(i) == s2.charAt(j) &&
s1.charAt(i) != s1.charAt(j)) {
return false;
}
}
}
return true;
}
public static boolean samePattern(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j < s1.length(); j++) {
if ((s1.charAt(i) == s1.charAt(j)) !=
(s2.charAt(i) == s2.charAt(j))) {
return false;
}
}
}
return true;
}
public static boolean samePattern(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
for (int i = 0; i < s1.length(); i++) {
if (s1.indexOf(s1.charAt(i)) != s2.indexOf(s2.charAt(i))) {
return false;
}
}
return true;
}
public static boolean samePattern(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
String chars1 = "";
String chars2 = "";
for (int i = 0; i < s1.length(); i++) {
char ch1 = s1.charAt(i);
char ch2 = s2.charAt(i);
if (chars1.indexOf(ch1) != -1) {
if (chars1.indexOf(ch1) != chars2.indexOf(ch2)) {
return false;
}
} else {
if (chars2.indexOf(ch2) != -1) {
return false;
}
chars1 += ch1;
chars2 += ch2;
}
}
return true;
}
-------------------------------------------------------------------------------
Round 1
Can get up to 4 points for any of the following good things:
1 correct header
1 testing whether lengths are equal/unequal
1 returning false when lengths are unequal
1 for loop using string length
1 getting one char from str1 with charAt or substring(i, i + 1)
1 getting one char from str2 with charAt or substring(i, i + 1)
1 returning false in a loop for some kind of character comparison
1 returning true at the end of the method
-------------------------------------------------------------------------------
To go to round 2, a solution needs:
* a nested loop approach
* calls on indexOf
* building up strings
-------------------------------------------------------------------------------
Round 2 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 ' '
-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