Mr. Meinzen - Computer Science Competitions and Practice

List of Competitions & Rules

Rules for In-School Competitions

• Questions will come from the Archived Questions at the University of Evansville
  • Generally, questions will require String manipulation, numeric calculations, cryptography, and matrix/array manipulation
• Timelimit will be 60 minutes.
• For each problem, each student or team must submit a single application (i.e. needs a main() method) that is:
• console-based (i.e. System.out, System.in)
• written in Java
• saved/submitted with the file name "Problem-X-LastName-FirstName.java"
• Scoring
  • First place is based on the greatest number of Correct Solutions submitted within the timelimit allowed
  • For students or teams with the same number of Correct Solutions, the matrix/array problem will be tie-breaker followed by numeric calculation, String manipulation, then finally cryptography.
  • Final tie-breaker is whichever team turns in their first Correct Solution in terms of time.

Strings

Practice on CodingBat.com

• Medium Difficulty:

• String-2 > doubleChar

• String-2 > bobThere

• String-2 > zipZap

• Harder Difficulty:

• String-3 > gHappy

• String-3 > mirrorEnds

• String-3 > sumDigits

• String-3 > maxBlock

Common String manipulation Problems:

• 1) Reverse a String with or without recursion

  2) check if string is palindrome

  3) How to count occurrence of word in String Array

  4) Java program to compute all permutation of String
  5) How to determine if String has all unique characters

  6) Java Program to Find Lexicographically Smallest and Largest substring of Length K

  7) Check if String is Null or Empty

  8) Break the string after certain length

Useful String methods:

• String [] split(String delimiter) - separates out individual words or characters based on delimiter...see below for examples
• char[] toCharArray() - converts this string to a new character array.
• String toUpperCase() - changes every character to equivalent upper-case letters.
• String toLowerCase() - changes every character to equivalent lower-case letters.
• int compareToIgnoreCase(String str) - Compares two strings lexicographically, ignoring case differences.
• int indexOf(int ch, int fromIndex) - returns the index within this string of the first occurrence of the specified character, starting the search at the specified index.
• String trim() - returns a copy of the string, with leading and trailing whitespace omitted.
• String subString(int startIndex, int endIndex) - returns a copy of a section of the string starting at startIndex and ending at endIndex, inclusive. If endIndex is not specified, copies to the end of the string. Example "unhappy".subString(2) returns "happy". "unhappy.subString(0,3) returns "unh".

Other useful classes and methods (mostly static)

• boolean Character.isDigit(char ch) tests if a char is one of the chars '0', '1', .. '9'. Throws an Exception if ch is not one of the numeric digits.
• int Integer.parseInt(String str) converts a string to an int. If str cannot be converted, this throws an Exception

Parsing of Strings using the split() method:

Definitions:

• parsing - dividing a string into tokens based on the given delimiters

• token - one piece of information, a single "word"

• delimiter - one (or more) characters used to separate tokens (i.e. words)

• When we have a situation where strings contain multiple pieces of information (for example, when reading in data from a file on a line-by-line basis), then we will need to parse (i.e., divide up) the string to extract the individual pieces (tokens) using some character (delimiter) to separate the individual words. Common delimiters are spaces, tabs or line breaks (often called "whitespace").

• Note: The following example code uses the following delimiters: periods, commas, question marks, and exclamation point. If we wanted to include other unusual characters such as quotes as delimiters, must use an escape sequence.

  String str = "This is a sentence. This is a question, right? Yes! It is.";
  String delims = "[ .,?!]" // define a string containing all the delimiters desired
  String[] tokens = str.split(delims);

  for(String token : tokens) System.out.println(token);

  //One per line: "This", "is", "a" ...."is"

   

  Other possible or common delimiters for simple mathematics:

  Note: subtraction versus a negative number cannot easily be distinguished.

  String myString= "a+b-c*d/e";

  String delims = "(?<=[-+*/=])|(?=[-+*/=])";
  String[] tokens = myString.split(delims);

  for(String token : tokens) System.out.println(token);

   

  The following are common "escaped" characters useful as delimiters.

  \t tab character

  \b backspace character

  \n newline character

  \r carriage return

  \f formfeed

  \' single quote character

  \"double quote character

  \\ backslash character

  \[ left square bracket

Concatenating an ArrayList of strings into a single String...assumes you can import java.util.ArrayList

• import java.util.*;

  ArrayList<String> list = new ArrayList<>();
  list.add("abc");
  list.add("DEF");
  list.add("ghi");

  // Join with an empty delimiter to concat all strings...result="abcDEFghi"
  String result = String.join("", list);

arrays

Practice on CodingBat.com

• Medium Difficulty:

• Array-2 > sum13

• Array-2 > isEveryWhere

• Array-2 > fizzBuzz

• Array-2> centeredAverage

   

• Harder Difficulty:

• Array-3 > maxSpan

• Array-3 > maxMirror

• Array-3 > squareUp

numeric

Practice on CodingBat.com

• Logic-2 > makeChocolate

• Logic-2 > noTeenSum

• AP-1 > scoresAverage

• AP-1 > sumHeights

• AP-1 > dividesSelf

• Recursion-1 > bunnyEars2

File and Console Input/Output (I/O)

Practice

List of useful classes and methods:

• Scanner.java - allows use and parsing of various types of input from keyboard (i.e. console), files, networks, and String variables

• String next() // gets the next String token in the input. Note: each String "token" is typically a single word that is separated from other words whitespace (i.e. spaces, tabs, end of lines, etc.)

• String nextLine() // returns a full line as a single String including whitespace. Does not break up individual words.

• int nextInt(), long nextLong(), double nextDouble(), etc. // gets the next primitive value specified in the input.

• boolean hasNext() // determines if the input has more information to be read in or not.

• boolean hasNextLine() // determines if the input has another line of input or not...useful for files

• boolean hasNextInt(), boolean hasNextLong(), boolean hasNextDouble(), etc. // determines if the input has another primitive value available in the scanner.

• FileReader.java - opens an already-existing file to be read in as a series of characters (as opposed to binary data)

• BufferedReader.java - converts a series of characters (i.e. stream) into text such as Strings, arrays of characters, and lines.

• FileWriter.java - allows output to be written to file as a series of characters (as opposed to binary data). Whether or not a file is available or may be created depends upon the underlying platform.

• BufferedWriter.java - writes text to a character-output stream, buffering characters so as to provide for writing of single characters, arrays, and strings.

• PrintWriter.java - writes text and objects (via toString() method) to a character-output stream using formatted output. Similar to BufferedWriter.

Sample Code for Console Input/Output:

          
/** Example of Java console I/O using Scanner class */

import java.util.Scanner;

class IOexample
{
   public static void main(String argv[])
   {
      String s;
      int    i;
      double d;

      Scanner in = new Scanner (System.in);
	  
      // Read a string
      System.out.print("Enter a string without spaces: ");
      s = in.next();

      // Read an integer
      System.out.print("Enter an int: ");
      i = in.nextInt();

      // Read a double
      System.out.print("Enter a double: ");
      d = in.nextDouble();

      // Print out results
      System.out.println("The string is: " + s);
      System.out.println("The integer is: " + i);
      System.out.println("The double is: " + d);
   }  // end main
}  // end IOexample

Sample Code for File Input/Output:

/** Example of Java File I/O using Scanner class */
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.*;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.*;          

public class FileTester {           
     public static void main(String[] args) {           
          String fileInputName  = "testReadData.txt";
          String fileOutputName = "testWriteData.txt";
          Scanner sc = null;           
          try {
              sc = new Scanner(new BufferedReader(new FileReader(fileInputName)));
              while (sc.hasNextLine()) {           
 
                  // for reading Strings
                  String line = sc.nextLine();
                  System.out.println("read string = "+line);           
                  
                  // for reading integers
                  int i = sc.nextInt();
                  System.out.println("read integer = "+i);
              }
          }
          catch (FileNotFoundException e) {
              e.printStackTrace();
          }
          finally {
              if (sc != null)
                  sc.close();  // regardless we need to close the scanned file.
          }           
          
          // printing output to a file
          BufferedWriter out = null;
          try {
              out = new BufferedWriter(new FileWriter(fileOutputName));
              out.write(Double.toString(3.141592)+'\n'); //added an end-of-line character
              out.write(Integer.toString(7));            // so that this line is outputted
              out.write("help");                         // on the next line.
              out.close();
          }
          catch(IOException e) {
              e.printStackTrace();
          }
      }
}

Try Outs

Rules :

• Complete the following problems (in any order) by yourself during the assigned timeframe (usually 50 min).

• After verifying with your teacher your correct solution, mark on the front board the following three items:

  • 1) your name
  • 2) problem number you solved and
  • 3) the time stamp when you solved it (at the time you reached the board).

• The students who correctly complete the FEWEST problems at the end of the given timeframe are subject to being "cut."

• In case of a "tie" for fewest completed problems, the following steps will be used to determine who is subject to being "cut."

  • 1. The student who completes the FEWEST DIFFERENT TYPES of problems are subject to being "cut." (i.e. if Student A completed 2 String problems while Student B completed 1 String and 1 Array problem, Student A is subject to being "cut.")

  • 2. The student who finished their last completed their problem FIRST (as time-stamped on front board).

  • 3. If the last time-stamps are within 5 minutes of each other, then either a random flip of coin or Rock-Paper-Scissors (method decided by teacher) will be use to determine the student to be cut.

Problems :

see the following table