## Coding Bat Recursive Problems – Day 1

Today, we are looking at a primer for recursion using problems in CodingBat in Computer Science 2. We looked at 3 different problems from CodingBat.

#### Bunny Ears

http://codingbat.com/prob/p183649

Here is the setup of the problem:

We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).

```public int bunnyEars(int bunnies) {
if (bunnies == 0){
return 0;
} else {
return 2 + bunnyEars(bunnies-1);
}
}```

Let’s use an input of 6. With this, we would anticipate the output to be 12, since each bunny has 2 ears.

Line 3 will not be run since the condition set in line 2 is FALSE. Currently, bunnies is set to 6.

So, we move on to line 4, which is the start of the default case, and is executed on line 5. So with bunnies set to 6, we return a 2 and then add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #5.

Now, bunnies = 5, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #4.

Now, bunnies = 4, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #3.

Now, bunnies = 3, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #2.

Now, bunnies = 2, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #1.

Now, bunnies = 1, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is 0.

Now, bunnies = 0, so line 2 is now TRUE, so we return a 0 and exit the loop.

We now add the following together:

• 0 from when bunnies = 0 (cumulative total = 0)
• 2 from when bunnies = 1 (cumulative total = 2)
• 2 from when bunnies = 2 (cumulative total = 4)
• 2 from when bunnies = 3 (cumulative total = 6)
• 2 from when bunnies = 4 (cumulative total = 8)
• 2 from when bunnies = 5 (cumulative total = 10)
• 2 from when bunnies = 6 (cumulative total = 12)

The total is returned as 12 ears.

#### Bunny Ears 2

http://codingbat.com/prob/p107330

Here is the setup of the problem:

We have bunnies standing in a line, numbered 1, 2, … The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we’ll say have 3 ears, because they each have a raised foot. Recursively return the number of “ears” in the bunny line 1, 2, … n (without loops or multiplication).

```public int bunnyEars2(int bunnies) {
if (bunnies == 0){
return 0;
} else if (bunnies % 2 != 0){
return 2 + bunnyEars2(bunnies-1);
} else{
return 3 + bunnyEars2(bunnies-1);
}
}```

For this one, let’s use an input of 5. We would expect the output to be 12 since bunnies 1, 3, & 5 have a total 6 ears and bunnies 2 & 4 have a total of 6 ears.

Line 3 will not be run since the condition set in line 2 is FALSE. Currently, bunnies is set to 5.

So, we move on to line 4. This condition is looking to see if we are working with an even numbered or odd numbered bunny. We have set the condition to use the modulus of 2 of the integer of bunnies. If the modulus is NOT 0, then the statement is TRUE and therefore it is an ODD numbered bunny.

Line 6 is the start of the default case which is used if we are working with an EVEN numbered bunny.

Now, bunnies = 5, so line 2 is FALSE, and line 4 is TRUE. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #4.

Now, bunnies = 4, so line 2 is FALSE, line 4 is FALSE, so we run the default case at line 6. We return a 3 and add that to the number of bunny ears from the next bunny (bunnies -1), which is bunny #3.

Now, bunnies = 3, so line 2 is FALSE, and line 4 is TRUE. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #2.

Now, bunnies = 2, so line 2 is FALSE, line 4 is FALSE, so we run the default case at line 6. We return a 3 and add that to the number of bunny ears from the next bunny (bunnies -1), which is bunny #1.

Now, bunnies = 1, so line 2 is FALSE, and line 4 is TRUE. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is 0.

Now, bunnies = 0, so line 2 is now TRUE, so we return a 0 and exit the loop.

We now add the following together:

• 0 from when bunnies = 0 (cumulative total = 0)
• 2 from when bunnies = 1 (cumulative total = 2)
• 3 from when bunnies = 2 (cumulative total = 5)
• 2 from when bunnies = 3 (cumulative total = 2)
• 3 from when bunnies = 4 (cumulative total = 10)
• 2 from when bunnies = 5 (cumulative total = 12)

The total is returned as 12 ears.

#### Triangle

http://codingbat.com/prob/p194781

Here is the setup of the problem:

We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

```public int triangle(int rows) {
if (rows == 0){
return 0;
} else {
return rows + triangle(rows - 1);
}
}```

Here, we are building something that looks like this:

Like the cases before it, line 2 is a condition looking for when we are to row 0. If line 2 is FALSE, we will move to line 4. For this example, let’s use rows = 4. With this, the output should be 10 as there are 10 cubes needed to complete a 4 row triangle.

So, we start with rows = 4. Line 2 is FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is row #3.

We are returning the row number as that is equal to the number of cubes of each row (e.g. row 7 = 7 cubes, row 4 = 4 cubes, etc…).

We now move to rows = 3. Line 2 if FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is row #2.

We now move to rows = 2. Line 2 if FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is row #1.

We now move to rows = 1. Line 2 if FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is 0.

Now, rows = 0, so line 2 is now TRUE, so we return a 0 and exit the loop.

We now add the following together:

• 0 from when rows = 0 (cumulative total = 0)
• 1 from when rows = 1 (cumulative total = 1)
• 2 from when rows = 2 (cumulative total = 3)
• 3 from when rows = 3 (cumulative total = 6)
• 4 from when rows = 4 (cumulative total = 10)

## A Real Final Exam: Computer Science

Well, since entering K-12 education in the 2004/2005 school year, I have now written and administered my first “real” semester exams!

While I have always given exams at the conclusion of the semesters, I have never really given a genuine exam “experience”. There would be a test. That test usually consisted of 50 questions. 25 of the questions were True/False and 25 were Multiple Choice. The students were given a single sentence review guide of “Always Be True to Yourself”.

Now, with that as the review guide, I think you could safely guess that the answers were “B” and “True”. Your guess would be correct. Sadly, I did have students fail that test.

The test was not a “give-me grade” since there was usually a major end-of-year project that the majority of their semester grade was based upon. This final was created so we could simply check a box that said we gave a paper final.

This year, I opted to write and administer a genuine rigorous exam as I was not using any major end-of-year projects.

Computer Science (EOY) Final Exam – Test

Computer Science (EOY) Final Exam – Answer Key

As you can see, this is a bit more rigorous of a test. In fact, all of the questions require a calculated answer.

Once the tests are completed, I will analyze student performance in another post.

## 2-Dimensional Arrays in Java

Today, we started to cover 2-dimensional arrays in Java. I decided to start with something very easy:

We have an array with 2 rows and 3 columns. Like all things in Java, we start counting our indices at 0.

As such, the value of [0][0] is Vanilla and [1][0] is Ice Cream. Note that the first number in the reference points to the row and the second number in the reference points to the column.

```import java.util.*;
public class TwoDArrays {
public static void main(String[] args){
String[][] myBigArray = new String [][] {
{"Vanilla ", "Chocolate ", "Strawberry "},
};
System.out.println(myBigArray[0][0] + myBigArray[1][0]);
System.out.println(myBigArray[0][1] + myBigArray[1][0]);
System.out.println(myBigArray[0][2] + myBigArray[1][0]);

System.out.println(myBigArray[0][0] + myBigArray[1][1]);
System.out.println(myBigArray[0][1] + myBigArray[1][1]);
System.out.println(myBigArray[0][2] + myBigArray[1][1]);

System.out.println(myBigArray[0][0] + myBigArray[1][2]);
System.out.println(myBigArray[0][1] + myBigArray[1][2]);
System.out.println(myBigArray[0][2] + myBigArray[1][2]);
}
}```

Line 4 is where we created the 2-dimensional array named “myBigArray”.

Lines 5 and 6 are where we populated the array. Note that line 5 is the first row and line 6 is the second row.

Lines 8 through 18 are where we are outputting text that is “fed” by the 2-D array.

Line 8 concatenates [0][0] with [1][0] which is Vanilla and Ice Cream.

Line 9 concatenates [0][1] with [1][0] which is Chocolate and Ice Cream.

Line 10 concatenates [0][2] with [1][0] which is Strawberry and Ice Cream.

Line 12 concatenates [0][0] with [1][1] which is Vanilla and Cookie.

Line 13 concatenates [0][1] with [1][1] which is Chocolate and Cookie.

Line 14 concatenates [0][2] with [1][1] which is Strawberry and Cookie.

Line 16 concatenates [0][0] with [1][2] which is Vanilla and Candy.

Line 17 concatenates [0][1] with [1][2] which is Chocolate and Candy.

Line 18 concatenates [0][2] with [1][2] which is Strawberry and Candy.

## Flipping Stacks

We are now going to look at how to flip a stack. As was discussed previously, a stack is an ideal method for holding items in a queue such as an incoming call center.

Let’s say the following calls come into a call center. They are time-stamped for reference.

Call 5 – (469)382-1285 – 2017-02-13 / 08:02:57
Call 4 – (682)552-3948 – 2017-02-13 / 08:02:45
Call 3 – (214)233-0495 – 2017-02-13 / 08:01:55
Call 2 – (817)927-3849 – 2017-02-13 / 08:01:22
Call 1 – (972)828-1847 – 2017-02-13 / 08:01:13

In this case, the call that has been placed on hold the longest is “Call 1”, which came in at 8:01:13. However, recall that in a stack I can only interact with the item on the TOP of the stack. In this case, that is “Call 5”.

So, we are going to create a system that “flips” this stack over, pulls the new top item off and then returns to stack to its original order so additional calls can go in the place they should.

So, assuming that we have a stack already created for the numbers, we will need to create an empty temporary stack to hold the items. As we move the items over, the temporary stack will look like the following:

Call 1 – (972)828-1847 – 2017-02-13 / 08:01:13
Call 2 – (817)927-3849 – 2017-02-13 / 08:01:22
Call 3 – (214)233-0495 – 2017-02-13 / 08:01:55
Call 4 – (682)552-3948 – 2017-02-13 / 08:02:45
Call 5 – (469)382-1285 – 2017-02-13 / 08:02:57

As you can now see, “Call 1” is at the top of the stack and could be routed to the next available individual. However, if another new call were to come in, the stack would look like the following:

Call 6 – (512)231-1933 – 2017-02-13 / 08:03:19
Call 2 – (817)927-3849 – 2017-02-13 / 08:01:22
Call 3 – (214)233-0495 – 2017-02-13 / 08:01:55
Call 4 – (682)552-3948 – 2017-02-13 / 08:02:45
Call 5 – (469)382-1285 – 2017-02-13 / 08:02:57

To avoid our call queue getting mixed-up, immediately following the retrieval of the top item on the stack, we need to move the items from the temporary stack back to the original stack as follows:

Call 5 – (469)382-1285 – 2017-02-13 / 08:02:57
Call 4 – (682)552-3948 – 2017-02-13 / 08:02:45
Call 3 – (214)233-0495 – 2017-02-13 / 08:01:55
Call 2 – (817)927-3849 – 2017-02-13 / 08:01:22

Now, when “Call 6” comes in, it will go where it is supposed to go (following “Call 5”).

Let’s analyze the code for this problem.

```//Program Name: Flipped Stacks
//Programmer Name: Eric Evans, M.Ed.
//Programmer Organization: Ferris High School
//Program Date: Spring 2017
import java.util.*;
public class flippedstacks {
public static void main(String args[]){
int count, myStackSize, myTempStackSize;
Stack myStack = new Stack();
for (count = 1; count <=10; count++){
myStack.push(count);
}
myStackSize = myStack.size();
Stack myTempStack = new Stack();
for (count = 1; count <=myStackSize; count++){
myTempStack.push(myStack.pop());
}
System.out.println("Current Caller is " + myTempStack.pop());
myTempStackSize = myTempStack.size();
for (count = 1; count <=myTempStackSize; count++){
myStack.push(myTempStack.pop());
}
}
}```

Lines 1 – 4 are the general header information. Lines 5 – 7 are the imports and creation of the class and main object.

Line 8 creates 3 uninitialized integer variables: count, myStackSize, and myTempStackSize.

Line 9 creates a new empty stack named “myStack”.

Lines 10 – 12 push content into the “myStack” stack. It pushes numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, & 10 into the stack.

Line 13 initializes the value of the myStackSize variable as the size of “myStack” using the size function of stacks.

Line 14 is like line 9, but it creates an empty stack named “myTempStack”. This will be the stack that temporarily holds our stack of information so we can get the first record.

Lines 15 – 17 push the content into the “myTempStack” stack by popping each record in the “myStack” stack. The for loop know how many times to do this by using the myStackSize variable that was declared on line 8 and initialized on line 13.

Line 18 displays which caller is the current caller by popping it from the top of the “myTempStack” stack.

Line 19 is like line 13 in that it initializes the value of the myTempStackSize variable as the size of “myTempStack” using the size function of stacks.

Line 19 is also the beginning of the process of reverting the stack back to its original order with the first (oldest) entry removed.

Lines 20 – 22 are similar to lines 15 – 17 but the reverse process. They push content into the “myStack” stack by popping each record in the “myTempStack” stack. The for loop knows how many times to do this by using the myTempStackSize variable that was declared on line 8 and initialized on line 19.

Line 24 & 25 close out lines 7 & 6 respectively.

## Arrays with Keyboard Interactivity

Today, we discussed how to create an array with keyboard interactivity. The user will be asked to enter how many numbers they will be entering and then they will be asked to enter numbers separated by a space.

```//Program Name: Arrays with Keyboard Input
//Programmer Name: Eric Evans, M.Ed.
//Programmer Organization: Ferris High School
//Program Date: Spring 2017

import java.util.*;
import java.lang.*;
import java.io.*;

public class arrayKeys {
public static void main(String args[]){
Scanner count = new Scanner(System.in);
System.out.print("How Many Numbers Do You Want to Enter?: ");
int arraySize = count.nextInt();
int myArray[] = new int[arraySize];
Scanner nums = new Scanner(System.in);
System.out.println("Enter Your " + arraySize + " numbers each separated by a space and press enter when done.");
for(int counter = 0; counter < arraySize; counter++){
myArray[counter] = nums.nextInt();
}
System.out.println(Arrays.toString(myArray));
}
}```

Following the header information (lines 1 through 4) and the imports (lines 6 through 8), we get to the actual application code.

On line 12, we declare a scanner object named “count” which will receive input from the keyboard.

On line 13, we ask the user to enter the number of items they will be entering. Lines 14 assigns the value that is entered as an integer variable named “arraySize”.

Line 15 creates an empty array named “myArray” which is initialized as the size of the “arraySize” variable declared on line 14.

Line 16 declares a second scanner object named “nums” which will receive the integers to the recorded from the keyboard.

On line 17, we ask the user to enter the integers they want recorded separated by a space.

Line 18 opens a for loop. The loop initialization creates an integer variable named “counter” with the value of 0. The loop condition is to run while the variable “counter” is less than the variable “arraySize”, which was declared on line 14. Each pass through the loop increments the value of the variable “counter” by 1.

Each pass through the loop executes line 19, which assigns the next integer in the sequence of numbers from the “nums” scanner to “myArray” in the index (position) declared by the “counter” variable.

Finally, on line 21, we output the contents of “myArray” as a string.

## Coding Bat – rotateLeft3

This exercise requires that the program look at an array with 3 integers and shift their positions one index to the left (down) and place first integer (index 0) at the end.

```public int[] rotateLeft3(int[] nums) {

}```

As you can see, we start with an empty integer array named “nums”.

```public int[] rotateLeft3(int[] nums) {
int[] rotatedArray = new int[]{nums[1],nums[2],nums[0]};
return rotatedArray;
}```

This solution creates a new integer array named “rotatedArray” and assigns it the values of each index from the original array. (Line 2)

We return the new array on line 3 to solve the problem.

## Coding Bat – posNeg

This exercise requires that the program look at two given integers and a boolean. If the Boolean is TRUE AND both integers are negative, then TRUE is returned. If the Boolean is FALSE only 1 integer can be negative for to return TRUE.

```public boolean posNeg(int a, int b, boolean negative) {

}```

As you can see, we start with 2 integer variables named “a” and “b” and a boolean named “negative”.

```public boolean posNeg(int a, int b, boolean negative) {
if (negative){
if (a < 0 && b < 0){
return true;
} else {
return false;
}
} else if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
return true;
} else {
return false;
}
}```

This solution utilizes a nested if/then structure. Starting on line 2, we say IF the Boolean negative is TRUE, then proceed to line 3. If it is FALSE, we would jump to line 8.

On line 3, we now check to see if both “a” AND “b” are negative (less than 0). If they are, TRUE is returned (line 4). If they are not, FALSE is returned (lines 5-7).

Line 8 is executed if the Boolean on line 3 is FALSE. Line 8 looks to see if “a” is negative and “b” is positive OR “a” is positive and “b” is negative. If either case is TRUE, then TRUE is returned (line 9). If neither statement on line 8 is TRUE, then FALSE is returned (lines 10-12).

Coding Bat presents the following as their solution:

```public boolean posNeg(int a, int b, boolean negative) {
if (negative) {
return (a < 0 && b < 0);
}
else {
return ((a < 0 && b > 0) || (a > 0 && b < 0));
}
}```

In this solution, line 2 is identical to our line 2. However, their line 3 is shorter version of our lines (3-7). If both “a” AND “b” are not negative, then a FALSE is returned, otherwise a TRUE is returned.

Their lines 5-7 are our lines 8-12 and work the same way.

## Coding Bat – Arrays Cluster 1

Today, while I was attending meetings, I assigned my students to complete 4 Coding Bat logic exercises.

#### CODING BAT – COMMONEND

This exercise requires that the program return TRUE if the first integers or last integers of two given arrays are the same, otherwise, FALSE will be returned.

```public boolean commonEnd(int[] a, int[] b) {

}```

```public boolean commonEnd(int[] a, int[] b) {
int arrayALength = a.length;
int arrayBLength = b.length;
int lastA = a[arrayALength - 1];
int lastB = b[arrayBLength - 1];
int firstA = a[0];
int firstB = b[0];
if(firstA == firstB || lastA == lastB){
return true;
}
return false;
}```

The solution above starts by calculating the length of each array (lines 2 and 3). Remember, whenever you are asked to do anything with the “end” or “last” items, you will almost always need to calculate the length.

On lines 4 & 5, we are establishing variables to hold the last index of each array and lines 6 & 7 are holding the first index of each array.

Finally, lines 8 through 10 are a conditional statement comparing the first indices of each array and the last indices of each array. If either of them are equal, a TRUE is returned. However, if neither is TRUE, then FALSE is returned.

#### CODING BAT – MAKELAST

This exercise requires that the program calculate the length of a given array and create a new array that is double that length populated with zeros with the exception of the last index. The last index is to populated with the last index of the first array.

```public int[] makeLast(int[] nums) {

}```

```public int[] makeLast(int[] nums) {
int arrayLength = nums.length;
int arrayFinalLength = arrayLength * 2;
int arrayLast = nums[arrayLength - 1];
int[] num = new int[arrayFinalLength];
num[arrayLength - 1] = arrayLast;
return num;
}```

As always, since we are asked to do some operation with the “last” or “end”, we must calculate the length of the array. This is done on line 2.

On line 3, we created a variable to hold the length of the new array, which is double the length of the original array.

Line 4 is where we capture the last index of the original array.

On line 5, we create a new integer array named “num” which has a size assigned by the variable that was created on line 3.

On line 6, we replace the last index of the new array with the value of the variable created on line 4.

Finally, on line 7, we return the new array.

#### CODING BAT – MAKEPI

This exercise requires that the program return the first 3 digits of PI in an array.

```public int[] makePi() {

}```

```public int[] makePi() {
int pi[] = {3,1,4};
return pi;
}```

The solution above starts by creating a new integer array named “pi” which is assigned the integers of 3, 1, and 4 on line 2.

On line 3, the array is returned.

Many students struggle to make this problem more challenging than it needs to be. Some try to take the Math.PI constant and populate the array one index at a time. However, this is not necessary and is not outlined as a requirement in the problem.

## Coding Bat – firstLast6

This exercise requires that the program analyze an array of integers and return TRUE if either the first or last integer is a 6. The array is guaranteed to have a minimum length of 1.

```public boolean firstLast6(int[] nums) {

}```

As you can see, we have a single integer array named nums.

```public boolean firstLast6(int[] nums) {
int first = nums[0];
int last = nums[nums.length-1];
if (first == 6 || last == 6){
return true;
}
return false;
}```

This solution utilizes a conditional if with the Boolean OR to solve the problem.

We start my declaring an integer variable named “first” to retrieve the value of index 0 (line 2).

We then declare an integer variable named “last” to retrieve the value of the last letter (Line 3)

As was the case when working with strings, to retrieve the last index of the array, we must first calculate its length and then subtract 1 from the total length. This will give us the value of the last index of the array.

Lines 4 through 6 are the conditional Boolean OR looking to see if either the first or last number are 6. If the Boolean is TRUE, then TRUE is returned.

## Coding Bat – sameFirstLast

This exercise requires that the program analyze an array of integers and return TRUE if the array has a length greater than 1 and the first index is the same as the last index.

```public boolean sameFirstLast(int[] nums) {

}```

As you can see, we have a single integer array named nums.

```public boolean sameFirstLast(int[] nums) {
if (nums.length >= 1){
int first = nums[0];
int last = nums[nums.length-1];
if (first == last){
return true;
}
return false;
}
return false;
}```

We start on line 2 checking to see if the array has a minimum length of 1. If is does not, we skip to line 10 and return FALSE. If the Boolean on line 2 is true, we proceed to line 3.

We then declare an integer variable named “first” to retrieve the value of index 0 (line 3).

We then declare an integer variable named “last” to retrieve the value of the last letter (Line 4)

As was the case when working with strings, to retrieve the last index of the array, we must first calculate its length and then subtract 1 from the total length. This will give us the value of the last index of the array.

Lines 5 through 7 are the conditional Boolean looking to see if the first and last index are the same value. If the Boolean is TRUE, then TRUE is returned.