FRQ Route Cipher A and B

Section 4.54 FRQ Route Cipher A and 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 Past AP CSA Exams.

🔗

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.

🔗

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
     */
    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
}

Subsection 4.54.1 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.

🔗

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.

🔗

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

🔗

str.substring(k, k + 1)

🔗

Subsection 4.54.2 Route Cipher A Scaffolding

Activity 4.54.1.

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

🔗

Activity 4.54.2.

You will need to access each element in the letterBlock array. What type of loop should you use?

🔗

for each
We need to utilize elements by indexing them so a for each loop will not work
if
This is not a type of loop
for
Correct!
while
Although this could would, we would need some kind of tracker variable to allow use to count indexes which would be more easily accomplished by a different loop.
switch
This would not work in this situation.

🔗

Activity 4.54.3.

The letterBlock array has two dimensions.How many loops should you use?

🔗

1
This would not correctly iterate through the 2D array
2, nested
Correct!
2, un-nested
This would not correctly iterate through the 2D array
3, un-nested
This would not correctly iterate through the 2D array

🔗

Activity 4.54.4.

What can you use to set the outer bound while you iterate through your 2D array?

🔗

numRows
Correct!
numCols
No, numCols finds the width and we are iterating through this in row-major order.
str.length()
This finds us the length of the string but the array is not based on the string length.
str[0].length()
Strings aren’t defined under the ’[]’ operator and str is not a 2D array so this would return an error.

🔗

Activity 4.54.5.

What can you use to set the inner bound while you iterate through your 2D array?

🔗

numRows
No, numRows finds the width and should not be used as the inner bound because we are iterating through the array in row-major order.
numCols
Correct!
str.length()
This finds us the length of the string but the array is not based on the string length.
str[0].length()
Strings aren’t defined under the ’[]’ operator and str is not a 2D array so this would return an error.

🔗

Activity 4.54.6.

Which String method can you use to access partial or full strings within another string?

🔗

str.length()
This does not return a string
str(lowerbound, upperbound)
This is not a valid string method
str.subsection(lowerbound, upperbound)
This is not a valid string method
str.substring(lowerbound, upperbound)
Correct!

🔗

Activity 4.54.7.

What is the formula for obtaining a single-character string at position k of the string str?

🔗

str.substring(k, k)
This will not return the correct char correctly
str.substring(k + 1, k + 1)
This will not return the correct char correctly
str.substring(k, k + 1)
Correct!
str.substring(k + 1, k)
This will not return the correct char correctly

🔗

Activity 4.54.8.

How can one find the aforementioned k? (this is hard to visualize, try drawing out some examples)

🔗

str.substring(c + r * this.numCols, 1 + c + r * this.numCols)
Correct!
str.substring(c - r * this.numCols, 1 + c - r * this.numCols)
Try using this formula to find a given character of one of the example strings. Does it work? Try coming up with some of your own examples to figure out the forumla for k.
str.substring(c + r, 1 + c + r)
Try using this formula to find a given character of one of the example strings. Does it work? Try coming up with some of your own examples to figure out the forumla for k.
str.substring(c - r, 1 + c - r)
Try using this formula to find a given character of one of the example strings. Does it work? Try coming up with some of your own examples to figure out the forumla for k.

🔗

Activity 4.54.9.

What conditional can you write to make sure trailing characters are ignored?

🔗

if (str.length() < (c + (r * this.numCols)))
This will not return the correct boolean
if (str.length() > (c + (r * this.numCols)))
Correct!
if (str.length() > numRows * numCols)
We need to determine whether or not to ignore trialing character at each step, not just check for it once at the beginning.
if (str.length() < numRows * numCols)
We need to determine whether or not to ignore trialing character at each step, not just check for it once at the beginning.

🔗

Activity 4.54.10.

The method fillBlock below contains the correct code for one solution to this problem, but it is mixed up. Drag the needed code from the left to the right and put them in order with the correct indention so that the code would work correctly.

🔗

public void fillBlock(String str)
{
  int pos = 0;
---
  for (int r = 0; r < this.numRows; r++ )
  {
---
      for (int c = 0; c < this.numCols; c++ )
      {
---
          if (pos < str.length())
          {
---
              String subStr = str.substring(pos, pos+1);
              this.letterBlock[r][c] = subStr;
              pos++;
---
          } else
          {
              this.letterBlock[r][c] = "A";
          } // end else block
---
      } // end inner for
  } // end outer for
} // end method

🔗

Subsection 4.54.3 Try And Solve FRQ Route Cipher A

Activity 4.54.11.

Complete the method fillBlock below.

🔗

public class RouteCipher
{
    /**
     * A two-dimensional array of single-character strings, instantiated in the
     * constructor
     */
    public 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;

public RouteCipher(int r, int c)
    {
        this.letterBlock = new String[r][c];
        this.numRows = r;
        this.numCols = c;
    }

}

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

/**
     * 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)
    {
        return "";
    }

public static void main(String[] args)
    {

boolean test1 = false;
        RouteCipher ciph = new RouteCipher(3, 3);

ciph.fillBlock("There's 1");

if ((ciph.letterBlock[0][2]).equals("e")
                && (ciph.letterBlock[2][1]).equals(" "))
            test1 = true;
        else
            System.out.println(
                    "Oops! Looks like your code doesn't properly insert the given"
                        + " String.\n");

if (test1)
            System.out.println("Looks like your code works well!");
        else
            System.out.println("Make a few changes, please.");
    }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{

@Test
    public void testMain() throws IOException
    {
        String output = getMethodOutput("main");
        String expect = "Looks like your code works well!\n";

boolean passed = getResults(expect, output, "Expected output from main");
        assertTrue(passed);
    }

@Test
    public void test1()
    {
        RouteCipher ciph = new RouteCipher(3, 4);

ciph.fillBlock("Lady Bugs");

String result =
                String.valueOf(
                        (ciph.letterBlock[0][2]).equals("d")
                                && (ciph.letterBlock[2][2]).equals("A"));
        boolean passed = getResults("true", result, "method fillBlock works");
        assertTrue(passed);
    }
}

🔗

Subsection 4.54.4 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.

🔗

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.

🔗

Subsection 4.54.5 Route Cipher B Scaffolding

Activity 4.54.12.

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

🔗

Activity 4.54.13.

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?

🔗

while
Correct!
if
You would need a loop.
for
For this problem, a while loop would be easier to use.
switch statement
You would need a loop.

🔗

Activity 4.54.14.

What should your while statement conditional be?

🔗

while (message.substring(k, k + 1) < 0)
You do not need to apply that formula here.
while (message.substring(k, k + 1) > 0)
You do not need to apply that formula here.
while (message.length() < 0)
The inequality is backwards.
while (message.length() > 0)
Correct!

🔗

Activity 4.54.15.

How can you determine how large the “chunk size” should be?

🔗

int chunkSize = this.numRows * this.numCols;
Correct!
int chunkSize = this.numRows + this.numCols;
This does not give you the correct result.
int chunkSize = this.numRows - this.numCols;
This does not give you the correct result.
int chunkSize = this.numRows / this.numCols;
This does not give you the correct result.

🔗

Activity 4.54.16.

If chunkSize is greater that message.length(), what should you set chunkSize to?

🔗

chunkSize = message.substring(chunkSize);
This does not give you the correct result.
chunkSize = += encryptBlock();
This does not give you the correct result.
chunkSize = message.length();
Correct!
chunkSize = fillBlock(message);
This does not give you the correct result.

🔗

Activity 4.54.17.

What method needs to be called on message before you can call “encryptBlock()”?

🔗

encryptMessage(message);
This is the method we are trying to write!
fillBlock(message);
Correct!
RouteCipher(message);
RouteCipher is the class of the method we are currently writing.
encryptBlock(message);
We need to call a different method before we call encryptBlock()

🔗

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

🔗

Activity 4.54.18.

The method encryptMessage below contains the correct code for one solution to this problem, but it is mixed up. Drag the needed code from the left to the right and put them in order with the correct indention so that the code would work correctly.

🔗

public String encryptMessage(String message)
{
  String encryptedMessage = "";
  int chunkSize = this.numRows * this.numCols;
---
  while (message.length() > 0)
  {
---
    if (chunkSize > message.length())
    {
      chunkSize = message.length();
---
    } // end if
---
    fillBlock(message);
    encryptedMessage += encryptBlock();
    message = message.substring(chunkSize);
---
  } // end while
---
  return encryptedMessage;
---
} // end method

🔗

Subsection 4.54.6 Solve Route Cipher Part B

Complete the method encryptMessage below.

🔗

Activity 4.54.19.

Complete the method encryptMessage 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;

private int counter = 0;

public RouteCipher(int r, int c)
    {
        letterBlock = new String[r][c];
        this.fillBlock("Meet at midnight");
        this.numRows = r;
        this.numCols = c;
    }

/**
     * 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)
    {
        int pos = 0;
        for (int r = 0; r < this.numRows; r++)
        {
            for (int c = 0; c < this.numCols; c++)
            {
                if (pos < str.length())
                {
                    this.letterBlock[r][c] = str.substring(pos, pos + 1);
                    pos++;
                }
                else
                {
                    this.letterBlock[r][c] = "A";
                } // end else block
            } // end inner for
        } // end outer for
    }

public static void main(String[] args)
    {

RouteCipher ciph = new RouteCipher(2, 3);
        if (ciph.encryptMessage("Meet at midnight")
                .substring(0, 6)
                .equals("Mte ea"))
            System.out.println("Looks like your code works well!");
        else System.out.println("Oops! Make a few changes to your code, please.");
    }
}
====
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{

@Test
    public void testMain() throws IOException
    {
        String output = getMethodOutput("main");
        String expect = "Looks like your code works well!\n";

boolean passed = getResults(expect, output, "Expected output from main");
        assertTrue(passed);
    }

@Test
    public void test1()
    {
        RouteCipher ciph = new RouteCipher(2, 3);

String result =
                String.valueOf(
                        ciph.encryptMessage("Meet at midnight").substring(0, 6).equals("Mte ea"));

boolean passed = getResults("true", result, "method encryptMessage works");
        assertTrue(passed);
    }
}

🔗

Subsection 4.54.7 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.

🔗

Activity 4.54.20.

What is your base case?

🔗

if (message.length() == 0) { return ""; }
Correct!
if (message.length() <= this.numRows * this.numCols) { return encryptBlock(); }
This would not work in this situation.
return "";
This would not work in this situation.
return encryptBlock();
This would not work in this situation.

🔗

Activity 4.54.21.

What kind of recursion will you use?

🔗

Head
The recursive call is not the first statement in the method hence it is not head recursive.
Tail
Correct!
Tree
We do not make multiple recursive calls so the method is not tree recursive.
Body
This is not a term that describes recursion.

🔗

Activity 4.54.22.

What is your tail recursive call?

🔗

return "";
This is the return statement of the base case.
return (encryptMessage(message.substring(this.numRows * this.numCols)));
This does not return the correct results
return (encryptBlock());
This is the return statement of one of the conditional base cases.
return (encryptBlock() + encryptMessage(message.substring(this.numRows * this.numCols)));
Correct!

🔗

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.

🔗

Activity 4.54.23.

🔗

public String encryptMessage(String message)
{
---
  if (message.length() == 0)
  {
      return "";
  }
---
  fillBlock(message);
---
  if (message.length() <= this.numRows * this.numCols)
  {
      return encryptBlock();
  }
---
  return (encryptBlock() +
         encryptMessage(message.substring(
            this.numRows * this.numCols)));
---
} // end method

🔗

You have attempted of activities on this page.

🔗

Prev Top Next