# Unit 4C - Free Response - Route Cipher A and B

Each coding exercise has its own folder. Open its `.java` file and press **Run** to try it. **Run Tests** checks every graded exercise in this lesson at once.

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 [Past AP CSA Exams](https://www.savemyexams.com/ap/computer-science/college-board/a/past-papers/).

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.

![Route Cipher Fig](images/routeCipherFig.png)

An incomplete implementation of the `RouteCipher` class is shown below.

```java
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
     */
    public 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
}
```

## Route Cipher A Description

**Part a.** Write the method `fillBlock` that fills the two-dimensional array `letterBlock` with one-character strings from the string passed as parameter `str`.

The array must be filled in row-major order—the first row is filled from left to right, then the second row is filled from left to right, and so on, until all rows are filled.

If the length of the parameter `str` is smaller than the number of elements of the array, the string “A” is placed in each of the unfilled cells. If the length of `str` is larger than the number of elements in the array, the trailing characters are ignored.

For example, if `letterBlock` has 3 rows and 5 columns and `str` is the string “Meet at noon”, the resulting contents of `letterBlock` would be as shown in the following table.

![Route Cipher Table](images/routeCipherTable.png)

If `letterBlock` has 3 rows and 5 columns and `str` is the string “Meet at midnight”, the resulting contents of `letterBlock` would be as shown in the following table.

![Route Cipher Table2](images/routeCipherTable2.png)

The following expression may be used to obtain a single-character string at position `k` of the string `str`.

```java
str.substring(k, k + 1)
```

## Route Cipher A Scaffolding

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

> Discuss this with your class, or answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routeciphera_short

> Check your understanding: You will need to access each element in the `letterBlock` array. What type of loop should you use? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routeciphera_1bMC

> Check your understanding: The `letterBlock` array has two dimensions.How many loops should you use? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routeciphera_1cMC

> Check your understanding: What can you use to set the outer bound while you iterate through your 2D array? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routeciphera_2MC

> Check your understanding: What can you use to set the inner bound while you iterate through your 2D array? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routeciphera_3MC

> Check your understanding: Which `String` method can you use to access partial or full strings within another string? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routeciphera_4MC

> Check your understanding: What is the formula for obtaining a single-character string at position `k` of the string `str`? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routeciphera_5MC

> Check your understanding: How can one find the aforementioned `k`? (this is hard to visualize, try drawing out some examples) — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routeciphera_5bMC

> Check your understanding: What conditional can you write to make sure trailing characters are ignored? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routeciphera_6MC

> Check your understanding: The method fillBlock below contains the correct code for one solution to this problem, but it is mixed up. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#RouteCipherA

## Try And Solve FRQ Route Cipher A

### Exercise 1

Complete the method `fillBlock`.

> Open the `01-FRQRouteCipherA` folder and edit `RouteCipher.java`. Press **Run** to try it; **Run Tests** checks it (2 tests).

## Route Cipher B

**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.

![Route Cipher Fig2](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.

## Route Cipher B Scaffolding

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

> Discuss this with your class, or answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#routecipherb_short

> Check your understanding: To solve `encryptMessage`, you have a message that you need to process and concatenate. What type of loop could you use to solve this problem? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#FRQRouteCipherB_1bMC

> Check your understanding: What should your while statement conditional be? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#FRQRouteCipherBnorm_1

> Check your understanding: How can you determine how large the “chunk size” should be? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#FRQRouteCipherBnorm_2

> Check your understanding: If chunkSize is greater that message.length(), what should you set chunkSize to? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#FRQRouteCipherBnorm_3

> Check your understanding: What method needs to be called on message before you can call “encryptBlock()”? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#FRQRouteCipherBnorm_4

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

> Check your understanding: The method encryptMessage below contains the correct code for one solution to this problem, but it is mixed up. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#RouteCipherB

## Solve Route Cipher Part B

### Exercise 2

Complete the method `encryptMessage`.

> Open the `02-routecipherbCoding` folder and edit `RouteCipher.java`. Press **Run** to try it; **Run Tests** checks it (2 tests).

## 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 learned about recursion, feel free to return to this question to practice working through the recursive solution.

> Check your understanding: What is your base case? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#FRQRouteCipherBrecur_1

> Check your understanding: What kind of recursion will you use? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#FRQRouteCipherBrecur_2

> Check your understanding: What is your tail recursive call? — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#FRQRouteCipherBrecur_3

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.

> Check your understanding: The method encryptMessage below contains the correct code for one solution to this problem, but it is mixed up. — answer it on CS Awesome: https://runestone.academy/ns/books/published/csawesome2/routeCipher.html#RouteCipherB_recurpar