Code Analysis
 | This page is incomplete. |
- Not to be confused with Source Code.
Template:EventLinksBox Code Analysis is a Division B and Division C event that was first run as a trial event at the 2018 Virginia state tournament and at the 2019 Wisconsin state tournament. It was also run at the 2019 Massachusetts state tournament as Python Code Analysis, using Python as the target language rather than Java. At the 2020 Washington state tournament, it replaced Ping Pong Parachute. Competitors are asked to determine the output or error that a given piece of code outputs without running the code. Each team is allowed one 8.5"x11" double-sided reference sheet, or two single-sided reference sheets of the same size.
The Event
Teams are not allowed to bring electronic devices into the testing room. All code given will be in Java, but problems focus on general programming concepts as opposed to specific qualities of Java. Problems may be written in a variety of ways, such as a series of statements, a method to be called with specific arguments, or a complete program with a main() method. All inputs and values will be specified, and no external inputs are allowed. All code given will also be properly indented.
While problems may be written in different ways, there are only two types of answers that will be requested. The competitor will determine the output of the code as created by System.out.print(), System.out.printIn(), and/or System.out.format() if a problem has an output. Space will be provided for the competitor to write their answer, and if the answer depends on spacing then a grid will be given so the answer is aligned properly. However, if the code has an error, then the competitor will be asked to describe the run-time error that occurs when the code is run. The error message or exception type does not need to be reproduced, but the competitor must describe what goes wrong and how to correct it.
Subjectivity in Test Writing
Test writers are free to craft the test according to their own coding philosophies. Based on an informal survey of a half dozen 2018/2019 tests:
- some embrace obfuscation, while others stick to clean ("honest") code.
- nearly all tests have at least one problem with recursion, although this recursion often ends up being simple single-branch nesting of no more than 3 levels.
- some tests emphasize mastery of printf and precise output formatting -- \n, whitespace, ASCII, etc. Other tests simply calculate numbers and print them, one per line.
- non-descriptive variable names and method names are very common -- i, x, n, foo, etc.
- some tests use nonsensical junk code with zero practical value. Other tests are full of real, usable code -- sorting, towers of hanoi, prime number calculations, etc.
Binary
Binary is the most basic form of data used by a computer. While most programs are not written in binary, it is important to have an understanding of how binary works. Binary is a base 2 system of counting, where decimal is known as base 10. As indicated by the base, binary only uses two digits used in binary code - 0 and 1. Each number is known as a bit, and there are eight bits in a byte. Half a byte (4 bits) is also known as a nibble. Individual bits can be manipulated by bitwise operations, such as AND (&), OR (|), or XOR (^). Binary numbers are also known as bit strings, and when translated into decimal or hexadecimal numbers encode for specific data.
ASCII
ASCII is a form of character encoding, where each letter or character used corresponds to a code that is readable by the computer. ASCII encodes for 128 characters, with each character corresponding to either a printed or non-printed symbol. Printed symbols consist of the 26 letters in the English alphabet, numerals 0 through 9, and various punctuation marks like periods or exclamation points. As ASCII was originally designed for teleprinters, the other non-printing symbols (also known as control characters) were used to control the formatting of characters on a page like return or tab. Each of these characters corresponds to a decimal number, which in turn represents a hexadecimal number and a binary number. This binary number is what the computer reads in order to display the desired character. While ASCII characters were originally encoded using 7 bits, extended versions of ASCII implement additional characters using 8 bit codes. Below is a table of ASCII values:
Original Characters
|
Extended Characters
|
Operators
Java can manipulate variables in a variety of ways using operators. An operator represents an action or a process, and return the result of that action being performed on one or more operands. The operand is the value which a given action is being performed on. Some operators appear much more frequently than others, but all have their own uses.
Arithmetic Operators
In most cases, arithmetic operators are the same as they are in algebra. However, Java has a couple of additional operators not typically found in math.
| Operator | Description | Example |
|---|---|---|
| + (Addition) | Adds values on either side of the operator. | 2 + 5 returns 7. |
| − (Subtraction) | Subtracts the value on the right of the operator from the value on the left. | 2 - 5 returns -3. |
| * (Multiplication) | Multiplies values on either side of the operator. | 2 * 5 returns 10. |
| / (Division) | Divides the value on the left side of the operator by the value on the right and returns the quotient. | 10 / 5 returns 2. |
| % (Modulus) | Divides the value on the left side of the operator by the value on the right and returns the remainder. | 10 % 3 returns 1. |
| ++ (Increment) | Pre increment increases the value of the operand by 1 and returns the new value of the operand. | If i = 5, ++i returns 6. i is now equal to 6.
|
| Post increment increases the value of the operand by 1 and returns the old value of the operand. | If i = 5, i++ returns 5. i is now equal to 6.
| |
| −− (Decrement) | Pre decrement decreases the value of the operand by 1 and returns the new value of the operand. | If i = 5, --i returns 4. i is now equal to 4.
|
| Post decrement decreases the value of the operand by 1 and returns the old value of the operand. | If i = 5, i-- returns 5. i is now equal to 4.
|
Relational Operators
Relational operators show the relationships between two primitives. All relational operators return a boolean, meaning that they are either true or false. The operator must compare the same data type otherwise the program will throw a compiler error. Some of these are also found in algebra, just like the arithmetic operators.
| Operator | Description | Example |
|---|---|---|
| == (Equal To) | Returns true if both primitives are of the same value. Otherwise, it returns false. | int x = 2;
if (x == 5) { //if x is equal to 5...
System.out.println("This statement will not print since 2 == 5 is false");
} else { //otherwise
System.out.println("This statement will print instead");
}
|
| != (Not Equal To) | Returns true if both primitives are of different values. Otherwise, it returns false. |
int x = 2;
if (x != 5) { //if x is not equal to 5...
System.out.println("This statement will print since 2 != 5 is true");
} else { //otherwise
System.out.println("This statement will not print");
}
|
| > (Greater Than) | Returns true if the primitive on the left side is larger than the primitive on the right side. Otherwise, it returns false. |
int x = 2;
boolean isXGreaterThanZero = x > 5; // You can use logical operators and assign the return value to a boolean!
if (isXGreaterThanZero) { // if x is greater than 5...
System.out.println("This statement will not print since 2 > 5 is false");
} else { // otherwise...
System.out.println("This statement will print instead");
}
|
| < (Less Than) | Returns true if the primitive on the left side is smaller than the primitive on the right side. Otherwise, it returns false. |
int x = 2;
boolean isXGreaterThanZero = x < 5; // You can use logical operators and assign the return value to a boolean!
if (isXGreaterThanZero) { // if x is less than 5...
System.out.println("This statement will print since 2 < 5 is true");
} else { // otherwise...
System.out.println("This statement will not print");
}
|
| >= (Greater Than Or Equal To) | Returns true if the primitive on the left side is larger than or equal to the primitive on the right side. Otherwise, it returns false. |
int x = 2;
if (x >= 2) { // if x is greater than or equal to 2...
System.out.println("This statement will print since 2 >= 2 is true");
} else { // otherwise...
System.out.println("This statement will not print");
}
|
| <= (Less Than Or Equal To) | Returns true if the primitive on the left side is smaller than or equal to the primitive on the right side. Otherwise, it returns false. |
int x = 2;
if (x <= 5) { // if x is less than or equal to 5...
System.out.println("This statement will print since 2 <= 5 is true");
} else { // otherwise...
System.out.println("This statement will not print");
}
|
Bitwise Operators
NOTE: All bitwise evaluations are done in binary. They all return the primitive number type (int, long, byte, char) back.
| Operator | Description | Example |
|---|---|---|
| | (OR) | Compares each binary digit and if either digit is a 1, then it gives back a 1. Otherwise it gives back a 0. | 710 | 1810 = 1112 | 100102 = 101112 = 2310 |
| & (AND) | Compares each binary digit and if both digits is a 1, then it gives back a 1. Otherwise it gives back a 0. | 710 & 1810 = 1112 & 100102 = 102 = 210 |
| ^ (XOR) | Compares each binary digit and if only one of the digits is a 1, then it gives back a 1. Otherwise it gives back a 0. | 710 ^ 1810 = 1112 ^ 100102 = 101012 = 2110 |
| ~ (NOT/Complement) | For each digit, it sets each 1 to 0 and each 0 to 1. | ~1810 = ~100102 = 11012 = 1310 |
| >> (Right Shift) | Shifts all the bits to the right. Preserves the sign, meaning it keeps the same number of binary digits. | 10>>1=5 since 10102 shifted to the right 1 is 01012 which is 510. |
| >>> (Unsigned Right Shift) | Shifts all the bits to the right. This is the unsigned version of the signed right shift. It doesn't keep the same number of binary digits. | 10>>1=5 since 10102 shifted to the right 1 is 1012 which is 510. |
| << (Left Shift) | Shifts all the bits to the left. | 10<<1=20 since 10102 shifted to the left 1 is 101002 which is 2010. |
Logical Operators
Compares two boolean variables and returns a boolean.
| Operator | Short Circuit | Description | Example |
|---|---|---|---|
| | (OR) | || | Will return true if either boolean condition is true. Will return false if both conditions are false. | If bool1 is true and bool2 is false, then bool1 | bool2 is true. |
| & (AND) | && | Will return true if both boolean conditions are true. Otherwise, it will return false. | If bool1 is true and bool2 is false, then bool1 & bool2 is false. |
| ^ (XOR) | Will return true if one, but not both, of the boolean conditions is true. Will return false if both conditions are true or false. | If bool1 is true and bool2 is true, then bool1 ^ bool2 is false. | |
| ! (NOT) | Flips the boolean value. | If bool1 is false, then !bool1 is true. |
De Morgan’s Law
Given that A and B are both boolean variables, De Morgan’s Law states that
- [math]\displaystyle{ !(A \& B) == !A \| !B }[/math]
and
- [math]\displaystyle{ !(A \| B) == !A \& !B }[/math]
Short-Circuit Operators
Short circuit operators will not evaluate the second part of a boolean operation if it isn’t necessary. It is written in code as || for OR operations and && for AND operations.
An example, if the condition being evaluated is A || B and A is true, then regardless what B is, A || B will be true, so the computer doesn’t evaluate B.
For the expression A && B and A was false, then the expression would return false regardless of what B is.
The reason why a short-circuit for XOR doesn’t exist is because if you evaluate A ^ B, if A is either true or false, the value B still needs to be evaluated to see whether the expression A ^ B returns true or false.
Assignment Operators
Assignment operators allow data types to be assigned values.
| Operator | Description | Example |
|---|---|---|
| = (Assignment) | It is used to set the value to a data type. Both primitives and Objects can use this operator. |
int x; // By default, Java sets uninitialized primitives to 0 x = 10; // x is now set to 10 System.out.println(x); // This will print 10 |
| += (Increment) | It is used to add some primitive value to itself. This is similar to doing x = x + y. This can only be used with PRIMITIVES excluding booleans. |
int x = 10; x += 20; System.out.println(x); // This will print 30 |
| -= (Decrement) | It is used to subtract some primitive value to itself. This is similar to doing x = x - y. This can only be used with PRIMITIVES excluding booleans. |
int x = 10; x -= 20; System.out.println(x); // This will print -10 |
Miscellaneous Operators
Ternary Operator
The ternary operator is a way of assigning a variable a certain value based on a certain condition. It is almost identical to an if-else statement, but only assigns a value to a variable instead of running multiple lines of code.
Example:
int x = (2 > 0) ? 5: 10;
Key
The condition
The ternary operator
The value assigned to x if the condition is true
The operator to define the start of the else block
The value assigned to x if the condition is false
Control Flow Statements
Conditional
If-Else
If
An if statement allows for a block of code to run if it meets a certain boolean condition. If the conditional it skips over the block of code and continues. The syntax for an if statement is as follows:
if (/*conditional*/) {
// The block of code that runs if the conditional is true
}
If the brackets are not included with the if statement, then the statement immediately after if is the consequence.
if (/*conditional*/) // This line will run if the conditional is true // This line is not part of the if statement
Here are some examples that can be run:
This is an example that shows when the conditional is true.
// This code should print "Hello World!"
int x = 10;
if (x == 10) { // this statement is true, so it will run the code within the brackets
System.out.print("Hello ");
}
System.out.println("World!");
This is an example that shows when the conditional is false.
// This code should print "World!"
int x = 10;
if (x > 20) { // this statement is false, so it will skip the code within the brackets
System.out.print("Hello ");
}
System.out.println("World!");
This is an example of using an if statement without the brackets.
// This code should print "World!"
int x = 10;
if (x > 20) // this statement is false, so it will skip the immediate statement below
System.out.print("Hello "); // Since this line is considered as the "block" of code in the if statement, this will not run
System.out.println("World!");
Loops
Data Types
Primitive
Primitives are a data type that store their data in a certain amount of bytes. All these types can all be defined by assigning integers to them.
int
An int is one of the most fundamental types of primitives. Ints are allocated 4 bytes (32 bits) and can range from -2,147,483,648 to 2,147,483,647 in decimal. These numbers are easily accessible just by doing Integer.MIN_VALUE and Integer.MAX_VALUE respectfully.
The following code defines an int.
int x;
By default, Java sets the value of all primitives to 0. So, if x were to be printed, it would print out "0".
To initalize it, use the assignment operator. This can also be done while the int is defined.
int x = 10; // x is 10 x = 20; // x is now 20
Ints are one of a couple of primitives that can use Arithmetic Operators and Bitwise Operators along with Relational Operators and Assignment Operators which all primitives can use.
Overflow
Ints have the potential to overflow if they try to store a number larger than 2,147,483,647 (231-1). If a number does overflow, it will wrap back around and continue adding from -2,147,483,648 (-231).
So if x initially equals Integer.MAX_VALUE and 1 is added to it, it will experience overflow and wrap around to Integer.MIN_VALUE. x will then equal -231.
If we instead added 2, the final result of x is -231+1 or Integer.MIN_VALUE + 1.
Overflow can also happen if the numbers that are less than -231 are then wrapped back up to 231-1.
So if x initially equals Integer.MIN_VALUE and 1 is subtracted from it, it will experience overflow and wrap around to Integer.MAX_VALUE. x will then equal 231-1.
If we instead subtracted 2, the final result of x is 231-2 or Integer.MAX_VALUE - 1.
boolean
A boolean is a 1 bit primitive. Its purpose is to record whether something is true (1) or false (0). The following code defines a boolean.
boolean x;
By default, Java sets the value of x to false (0). So, if x were to be printed, it would print out "false".
To initalize it, use the assignment operator. This can also be done while the boolean is defined.
boolean x = true; // x is true x = false; // x is now false
Booleans are the only primitive that can use Logical Operators along with Relational Operators and Assignment Operators which all primitives can use.
char
A char is a 2 byte (16 bits) primitive that stores a integer that maps bijectively to an ASCII character.
The following code defines a char.
char x;
By default, Java sets the value of all primitives to 0.
To initalize it, use the assignment operator. This can also be done while the char is defined.
char x = 65; // x is 'A' (ASCII code 65) x = 'g'; // x is now 'g' (ASCII code 103)
Only a certain range of chars can be printed out, on the ASCII table, it notes the printable ASCII codes.
Chars are one of a couple of primitives that can also use Arithmetic Operators and Bitwise Operators. However, the primitive type that they return is an int and will need to be cast into a char if needs to be kept as a char. It can also use the Relational Operators and Assignment Operators just like the other primitives.
Object
Variables
Variables, also known as instance fields, is the way data is stored. Variables can represent different data types like primitives and objects.
When defining variables, there are 3 parts: the access modifier, the data type, and the name.
Access Modifiers
Access modifiers determine which classes are allowed to access a variable or function. It allows to maintain integrity in a program and prevents users from accessing certain properties and methods that are meant to be kept secret.
There are 3 main modifiers: public, private, and protected. Below is a table of what modifiers give to variables and functions if they are added to them.
| Modifier | Class | Package | Subclass | World |
|---|---|---|---|---|
public
|
Yes | Yes | Yes | Yes |
protected
|
Yes | Yes | Yes | No |
| no modifier | Yes | Yes | No | No |
private
|
Yes | No | No | No |
Miscellaneous Modifiers
The static modifier is a modifier that declares whether a variable can be accessed at the class level. In other words, an instance of the Object does not need to be created in order to access this variable. Functions can also have a static modifier.
The final modifier is a modifier that declares a variable as a constant value. Upon declaration, it needs to be instantiated and can not be written afterward. The name of a final variable typically follows uppercase snake case (e.g. UPPERCASE_SNAKE_CASE) compared to the typical camel case of normal variables.
Name
Naming convention for variables mostly follows camel case (e.g. camelCase) as most of Java surrounds the use of camel case. However, if a variable is declared as a final variable, then the name must be in uppercase snake case (e.g. UPPERCASE_SNAKE_CASE) as it is the way to distinguish between manipulatable variables and constant variables.
Functions
Functions are a block of code that when called will run the lines of code contained within it. Functions are often used to simplify code. One way it can simplify code is by reusing code. Instead of redundantly writing multiple lines of code, the code can be put into a function and called multiple times. Another way functions can simply code is by creating helper functions. In multiple cases when creating long and complex algorithms, helper functions are used to break the algorithm into manageable steps, allowing for easy debugging and clean code that is way to read.
Defining a Function
Functions are defined in four parts: its access modifier, its return type, its name, and its parameters. In objects, all functions have a certain level of access that is defined in the function definition. Functions, similar to variables, can be public, private, or protected. The return type refers to the primitive or object type that will be returned once the function is done executing. The name is simply the name of the function. This is the name that will be used to call the function when it needs to be executed. Finally, there are the parameters which are the values that are required for the function to run properly. These can also be known as arguments. Parameters of a function are defined within the function definition, typically stating the type of object or primitive and the name it is will be referred under. When passed into a function, primitive values follow the pass by value protocol while object values follow pass by reference. A function can have multiple parameters, but all parameters need to be filled in order for a function to execute.
public boolean isFirstGreaterThanSecond(int first, int second) { if (first > second) { return true; } return false; }
Key
The access modifier
The return type
The name of the function
The parameters
The Return statement
Functions can have a return value of void which doesn't return any value once the function completes execution. Once the function execution reaches a return statement, the function will exit out and return the value stated in the return statement. The type of value specified in the return statement must match the return value stated in the definition otherwise the code will not compile. Functions that define a return type, must return a value otherwise the function will not compile. Functions that are void can use return; to exit the function without returning any value.
Overloading
Functions can also be overload other functions. For a function to be overloaded, the overloading function needs to be defined with the same name, but either a different amount of parameters or different types of parameters. This way the compiler knows which function to call on execution. Function overloading can mostly be seen by overloading default functions like toString() as certain objects might want to return a more comprehendible string rather than a random string of characters.
Scoring
Each problem specifies its own worth. No one problem can be worth more than 20% of the total score possible.