8.7.4. Free Response - Route Cipher B

The following is a free response question from 2011. It was question 4 on the exam. You can see all the free response questions from past exams at https://apstudents.collegeboard.org/courses/ap-computer-science-a/free-response-questions-by-year.

Question 4. In this question you will write two methods for a class RouteCipher that encrypts (puts into a coded form) a message by changing the order of the characters in the message. The route cipher fills a two-dimensional array with single-character substrings of the original message in row-major order, encrypting the message by retrieving the single-character substrings in column-major order.

For example, the word “Surprise” can be encrypted using a 2-row, 4-column array as follows.

../_images/routeCipherFig.png

An incomplete implementation of the RouteCipher class is shown below.

public class RouteCipher
{
    /**
     * A two-dimensional array of single-character strings, instantiated in the
     * constructor
     */
    private String[][] letterBlock;

    /** The number of rows of letterBlock, set by the constructor */
    private int numRows;

    /** The number of columns of letterBlock, set by the constructor */
    private int numCols;

    /**
     * Places a string into letterBlock in row-major order.
     *
     * @param str the string to be processed Postcondition: if str.length() <
     *     numRows * numCols, "A" in each unfilled cell if str.length() > numRows *
     *     numCols, trailing characters are ignored
     */
    private void fillBlock(String str)
    {
        /* to be implemented in part (a) */
    }

    /**
     * Extracts encrypted string from letterBlock in column-major order.
     * Precondition: letterBlock has been filled
     *
     * @return the encrypted string from letterBlock
     */
    private String encryptBlock()
    {
        /* implementation not shown */
    }

    /**
     * Encrypts a message.
     *
     * @param message the string to be encrypted
     * @return the encrypted message; if message is the empty string, returns the
     *     empty string
     */
    public String encryptMessage(String message)
    {
        /* to be implemented in part (b) */
    }

    // There may be instance variables, constructors, and methods that are not
    // shown
}

Part b. Write the method encryptMessage that encrypts its string parameter message. The method builds an encrypted version of message by repeatedly calling fillBlock with consecutive, non-overlapping substrings of message and concatenating the results returned by a call to encryptBlock after each call to fillBlock. When all of message has been processed, the concatenated string is returned. Note that if message is the empty string, encryptMessage returns an empty string.

The following example shows the process carried out if letterBlock has 2 rows and 3 columns and encryptMessage("Meet at midnight") is executed.

../_images/routeCipherFig2.png

In this example, the method returns the string “Mte eati dmnitgAhA”.

Assume that fillBlock and encryptBlock methods work as specified. Solutions that reimplement the functionality of one or both of these methods will not receive full credit.

8.7.4.1. How to Solve This

9-13-1: Explain in plain English what your code will have to do to answer this question. Use the variable names given above.

This section contains a plain English explanation of one way to solve this problem as well as problems that test your understanding of how to write the code to do those things. Click on the buttons to reveal the questions.

To solve this problem, you have a message that you need to process and concatenate. Do you need to use a loop for this?

Below is a mixed up version of the correct solution hinted at by the previous questions.

8.7.4.2. Solve Part B

Complete method encryptMessage below.

8.7.4.3. Alternate Recursive Solution

Instead of using loops, this problem can be solved using recursion. If you are unfamiliar with recursion do not worry if the recursive solution does not make immediate sense. It is not necessary that you understand recursion at this point however, once you have completed unit 10 which covers the basics of recursion, feel free to return to this question to practice working through the recursive solution.

If you still feel unsure of the recursive solution, it is recommended that you return to the recursion unit to do some more practice as this problem is quite challenging to solve recursively.

You have attempted of activities on this page