ITEC 120 2010fall ibarland

home—info—lects—labs—exams—hws
tutor/PIs—Object120 + its docs—java.lang docs—java.util docs

lab09b
looping over strings

Today's lab will (again) be done individually. You'll create a class Lab09b, and submit class Lab09b.java on WebCT.

1. Complete the test cases, a stub function, and then the body for countOccurrences.

   /** Test countOccurrences */ static void testCountOccurrences() { testEqualInts( countOccurrences("abracadabra", 'a' ),      ); testEqualInts( countOccurrences("abracadabra", 'b' ),      ); testEqualInts( countOccurrences("abracadabra", 'd' ),      ); testEqualInts( countOccurrences("abracadabra", 'z' ),      ); testEqualInts( countOccurrences("AAA", 'A' ),      ); testEqualInts( countOccurrences("A", 'A' ),      ); testEqualInts( countOccurrences("A", 'b' ),      ); testEqualInts( countOccurrences("", 'b' ),      ); }

   We've used/written testEqualInts before; you can find its code below.
2. Now, complete the signature and stub function for countOccurrences.

   /** Return how many times given character occurs in a String. * @param s the string to search through * @param target the char to count. * @return how many occurrences of `target` occur in `s`. */ //Your stub here

3. Finally, we'll write the actual body of countOccurrences.

   • What should your index variable be?
     How will it be updated, each time through the list?
   • What should your accumulator (“so-far”) variable be?
     How will it be updated, each time through the list?
   You can refer back to yesterdays' lecture for the code which goes through and processes every character of a String.

4. Submit your file Lab09b.java on WebCT. (I'll only look at countOccurrences, not the ISBN problems mentioned below.)

Extra: check-sums and ISBNs

The following problems aren't required for today, but may be in the future -- or they might be for extra credit.

1. Ten-digit book numbers — ISBN-10s — have the following “checksum” property:
   the digits x₁x₂x₃…x₉x₁₀ have the property that
   (1·x₁ + 2·x₂ + 3·x₃ + … + 9·x₉ + 10·x₁₀) % 11 = 0.
   This scheme means¹that if somebody mis-types a digit, or transposes two digits, a computer can recognize that an error has been made.

   For example, for the ten digits "0306406152",

   (

   1·0

   +

   2·3

   +

   3·0

   +

   4·6

   +

   5·4

   +

   6·0

   +

   7·6

   +

   8·1

   +

   9·5

   +

   10·2

   )

   % 11

   =

   (

   0

   +

   6

   +

   0

   +

   24

   +

   20

   +

   0

   +

   42

   +

   8

   +

   45

   +

   20

   )

   % 11

   =

   165 % 11

   =

   0 (since 11 goes into 165 fifteen times with remainder 0)

   Thus "0306406152" is a valid ISBN-10.

   Test case for you to try by hand, to understand what our code will have to do:
   Which of these is a valid ISBN-10?

   • "0020300004"
   • "0010300007"
   • "0000000000"
   • "1000000000"
   • "1000000001"

   By the way, mathemeticians have a concise way of writing this sum:

   	10
   (	Σ	i·xi	)	mod 11 = 0
   	i=1

   You'll see this summation-notation if you look on (say) Wikipedia. Don't be intimidated; whenever you see a high-falutin’ “Σ”, just think about writing it out as a summation in your head. (In fact, you can think of math as being a programming-language that has a convenient syntax for loops that add.)
   
   
2. Write the following method:

   class ISBNChecker { boolean isValidISBN10( String isbn ) { return false; // stub. } }

   • From the countOccurences above, we see how to have a loop look at each character individually.
   • Remember, though, that the third digit, x₃, occurs at index 2 of the string. Similarly, x₄ occurs at index 3. In general, the ith digit x_i of a string s is s.charAt(      ).
   • One thing we need to do in this problem is to convert a char into an int from 0..9. The most idiomatic way is to do something like (int)ch - (int)'0', which works as long as ch is a character in '0' …'9'. If didn't want to rely on the slippery play between characters and their underlying representation (and the use of casting), you might make a helper function:

     int charToInt( char digit ) { return Integer.parseInt( Character.toString(digit) ); }

3. Here are some tests for isValidISBN10.

   class ISBNCheckerTester { public static void main( String[] args ) { ISBNChecker looper = new ISBNChecker(); System.out.println( "\nTest some contrived ISBNs: " ); testEqualBools( looper.isValidISBN10("0000000000"), true ); testEqualBools( looper.isValidISBN10("1000000001"), true ); testEqualBools( looper.isValidISBN10("1000000000"), false ); testEqualBools( looper.isValidISBN10("0100000002"), true ); testEqualBools( looper.isValidISBN10("0010000003"), true ); testEqualBools( looper.isValidISBN10("0001000004"), true ); testEqualBools( looper.isValidISBN10("0000000019"), true ); testEqualBools( looper.isValidISBN10("0000000027"), true ); testEqualBools( looper.isValidISBN10("2000000010"), true ); testEqualBools( looper.isValidISBN10("4000000020"), true ); testEqualBools( looper.isValidISBN10("5000000080"), true ); System.out.println( "\nTest some real and incorrect ISBNs: " ); testEqualBools( looper.isValidISBN10("0306406152"), true ); testEqualBools( looper.isValidISBN10("0306406162"), false ); testEqualBools( looper.isValidISBN10("0306406154"), false ); testEqualBools( looper.isValidISBN10("0553565699"), true ); testEqualBools( looper.isValidISBN10("1553565699"), false ); } }

4. Extra challenge: Actually, sometimes the check-digit works out to be 10. Since that won't fit into a single digit, in that case the letter 'X' is used (reminiscent of the roman numeral).

   Fix your code above so that ISBN-10s ending in the letter 'X' are also recognized. (Hint: put your change inside charToInt.)

   System.out.println( "\nTest some X-digit ISBNs: " ); testEqualBools( looper.isValidISBN10("000000000X"), false ); testEqualBools( looper.isValidISBN10("050000000X"), true ); testEqualBools( looper.isValidISBN10("000020000X"), true ); testEqualBools( looper.isValidISBN10("300000002X"), true );

5. Extra extra challenge: ISBN-10s are created by using 9 digits of “real” data, and then constructing the 10th digit so that the above property holds. The formula to compute the tenth digit² is
   
   That is, compute
   
   Your task: Write char createCheckDigit( String isbnPart ).
6. Extra extra extra challenge: Can you modify isValidISBN10 so that it is much much shorter, by having it call createCheckDigit as a helper?
7. Extra extra extra extra challenge: Read about ISBN-13, and implement a verifier isValidISBN13 for that as well.
   Then, write isValidISBN which can take a 10-digit or a 13-digit input, and return isValidISBN10 or isValidISBN13 as appropriate.

    /** If two booleans aren't equal, print an error message.
     * Intended for use as a test-helper.
     * @param act The actual boolean returned by a test call.
     * @param exp The expected boolean to be returned by a test call.
     */
    static void testEqualBools(boolean act, boolean exp) {
      if (act==exp) {
        System.out.println("(test passed)");
      }
      else {
        System.out.println( "Actual: " + act + "\nExpect: " + exp );
      }
    }
    
    /** If two ints aren't equal, print an error message.
     * Intended for use as a test-helper.
     * @param act The actual int returned by a test call.
     * @param exp The expected int to be returned by a test call.
     */
    static void testEqualInts(int act, int exp) {
      if (act==exp) {
        System.out.println("(test passed)");
      }
      else {
        System.out.println( "Actual: " + act + "\nExpect: " + exp );
      }
    }
    

    /** If two Strings aren't equal, print an error message.
     * Intended for use as a test-helper.
     * @param act The actual String returned by a test call.
     * @param exp The expected String to be returned by a test call.
     */
    static void testEqualStrings(String act, String exp) {
      if (act.equals(exp)) {
        System.out.println("(test passed)");
      }
      else {
        System.out.println( "Actual: " + act + "\nExpect: " + exp );
      }
    }

    /** If two doubles aren't (nearly) equal, print an error message.
     * Intended for use as a test-helper.
     * @param act The actual double returned by a test call.
     * @param exp The expected double to be returned by a test call.
     * @param tolerance The amount of tolerance allowed to still be considered equal
     *    (an absolute amount.)
     *    
     * BUG: the tolerance should probably be a relative to exp, at least when when exp!=0.
     */
    static void testEqualDoubles(double act, double exp, double tolerance) {
      if (  (act == exp)
         || (Math.abs(act-exp) < tolerance) 
         || (Double.isNaN(act) && Double.isNaN(exp))) {
        System.out.println("(test passed)");
      }
      else {
        System.out.println( "Actual: " + act + "\nExpect: " + exp );
      }
    }

  /** If two doubles aren't (nearly) equal, print an error message.
     * Intended for use as a test-helper.
     * @param act The actual double returned by a test call.
     * @param exp The expected double to be returned by a test call.
     */
    static void testEqualDoubles(double act, double exp) {
        testEqualDoubles(act,exp,TOLERANCE);
    }     
    
    /** default The tolerance for testEqualDoubles */
    private static double TOLERANCE = 0.000001;

home—info—lects—labs—exams—hws
tutor/PIs—Object120 + its docs—java.lang docs—java.util docs

©2010, Ian Barland, Radford University Last modified 2010.Oct.28 (Thu)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu