Objective: To gain experience with 1D and 2D arrays and to review network concepts.
PostOffice
Patty the postwoman became bored one night, and to break the monotony of the night shift, she carried out an experiment with a row of mailboxes in the post office. These boxes were numbered 1 through 150. She started by closing all the doors, beginning with mailbox 1. Then, beginning with mailbox 2, she opened the doors of every second mailbox. Next, beginning with mailbox 3, she went to every third mailbox, opening its door if it was closed and closing it if it was open. Then she repeated this procedure with every fourth mailbox, then every fifth, and so on. When she was finished, she was surprised at the distribution of closed mailboxes. In this lab, you will write code to determine which ones these were.
Represent the mailboxes with an array of booleans. If you wish, you may use an array of length 151 and ignore element 0. In this array, use the values true and false to indicate that the corresponding mailbox is open and closed, respectively. Here are some suggestions on how to proceed:
Task 1: Write a closeBoxes method to initialize all the mailboxes to be closed.
Task 2: Write a displayClosedBoxes method that prints out the mailboxes that are closed. When done, run your program to test that it works. You should see that all the mailboxes are closed.
Task 3: Write a changeBoxes method to carry out the opening and closing of the mailboxes as described above. You will find it helpful to use nested loops for your solution. When done, run your program to test that it works. What do you observe about the mailboxes at the end? How can you reason about this result?
Turn in a printout of your source code, as well as sample output showing that your code works correctly. Along with your sample output, include a sentence or two that explains the result. I.e., what is special about the numbers of the mailboxes that are closed? Can you explain what's going on?
Palindromes
Palindromes are words or phrases that read the same forward and backward. In this problem we represent words and phrases by an array of characters and we will explore different techniques for identifying palindromes. Save the file Palindromes.java to your hw09 directory and open it in DrJava. In the code you see an array defined (testMatrix) that stores six different words or phrases that are potential palindromes. Note that testMatrix is a two-dimensional array of characters. Each row of the array stores one word or phrase. For a given row, the columns of the array store the individual characters of a word or phrase. Note further that the array is initialized with six different potential palindromes.
Task 1: Carefully study the code provided. Compile the program, and run it using the command java Palindromes. The program will display the words and phrases to be tested as palindromes, and (wrongly) indicate that none of them is a palindrome.
Which potential palindromes are indeed palindromes? Study the display and processAll methods and understand them fully. In particular, pay attention to the indexing of the two-dimensional array and the way that the array is passed as a parameter. Note that the processAll method invokes a method pal1(char[] a) that returns a boolean value indicating whether or not a passed one-dimensional array is a palindrome. In the code there are three method stubs (pal1, pal2, pal3). Each one uses a different technique for calculating a palindrome.
Task 2: Write the body of the pal1 method. It calculates whether or not a word or phrase is a palindrome by comparing the first and last characters of the word or phrase, the second and second-to-last characters of the word or phrase, the third and third to last characters of the word or phrase and so on. If all pairs of characters are equal, then the word or phrase is a palindrome and the method returns true. Otherwise, the word or phrase is not a palindrome and the method returns false. Test your code with java Palindromes.
Task 3: Write the body of the pal2 method. It calculates whether or not a word or phrase is a palindrome by comparing the word or phrase to itself in reverse. If the two are equal, then the word or phrase is a palindrome and the method returns true. Otherwise, the word or phrase is not a palindrome and the method returns false. Test your code.
Task 4: Write the body of the shorterA method. It accepts an array a as an input parameter and returns a subarray of a that consists of the original array a minus its first and last characters. This method is called shorterA because this subarray will be shorter than the original array by 2 characters. Note that this method returns an array.
Task 5: Write the body of the pal3 method. It calculates the palindrome recursively and makes use of the shorterA method. Test your code. Now, all three pal methods should return the same correct answer.
Turn in a printout of your source code, as well as sample output.
Cellular Automata
A Cellular Automaton is a grid of black and white cells in which the color of each cell depends on the colors of its neighbors. Read the description of cellular automata at Wolfram MathWorld. We will implement a cellular automaton in which the color of a cell depends on the color of the three neighboring cells in the row above it.For example, a simple rule would be that the current cell is black if at least one of the three cells above it is black. (This rule is called "rule 254" - for an explanation, see the above webpage.) If we start with a single black cell in the first row, rule254 would result in a black triangle:
public static boolean rule254(boolean left, boolean middle, boolean right) {
return left || middle || right;
}
public static boolean rule126(boolean left, boolean middle, boolean right) {
return !((left && middle && right) || (!left && !middle && !right));
}
You are given a skeleton CellularAutomaton.java that you should complete to implement a cellular automaton. This program takes the number of rows and columns as command-line arguments, and use these values to create a 2D boolean array with the specified number of rows and columns. Starting with a single black cell in the center of the first row, the program should use a fixed rule to evolve the pattern row by row, and then print out the resulting pattern, row by row.
Task 1: Save the file CellularAutomaton.java in your hw09 directory, and carefully study the code provided. Start by completing the beginning of the main method: allocate the array, and initialize the middle cell in first row to be black.
Task 2: Complete the printRow method, and call it for each row of the array from the main method. At this point you can compile and test your code, for example using the command java CellularAutomaton 16 33. It should print a grid of dots, with a "#" in the middle of the first row. The first row would look like:
................#................
Task 3: Complete the evolveRow method, and call it for each pair of consecutive rows of the array from the main method. Use the rule254 method initially. Test your program. Once it works, substitute the rule126 method.
Task 4: Complete the methods rule90 and rule30, and test each of them to make sure you get the same patterns as on Wolfram's Rule 90 and Rule 30 pages.
Turn in a printout of your source code, as well as output for each of rule90 and rule30, showing that your code works correctly.
Extra Credit: Write a version of CellularAutomaton that takes the rule number as a third command-line argument, instead of "hard-coding" the rule into your program. You'll need to read the Wolfram MathWorld webpage on Cellular Automata to see how the rule encoding works. Basically, the binary encoding of each number from 0 to 255 determines the corresponding rule.