Homework Assignment 5

A medley of recursive methods

Overview

This lab assignment will introduce you to thinking recursively. You will implement four short recursive methods. You are allowed to use iterative structures (for loops, while loops, etc), but the purpose of this lab is recursive thinking, and your solutions must exemplify this. You may work with a partner, if you choose to, for this lab (see the note at the bottom of this page).

Objectives

Pho-new-words (Phone Words)

Take out your cell phone right now (or look at the picture below). Next to each number key (except for the 1 key), there are three or four letters.

A Phone Keypad


Each digit can be thought of as one of its corresponding letters. Given a (10 digit) phone number, we want to generate all possible words that this phone number can be interpreted as (we don't care if they aren't English words). For example, the phone number "7466396737" can be read as "phonewords" (check this out for yourself). Actually, we want to be able to generate all corresponding words for a phone number of any length. So, "228" can be read as "cat" and "bat", as well as many other words.

Write the method 

public Set<String> generateAllPhoneWords(String phonenumber)
that returns the set of all words (in lowercase) generated by the given phone number.

Hints:

  • How many words can be generated from a phone number of length n? Why? How does this reasoning help us construct an algorithm to actually generate all the words?
  • You may find it helpful to use helper method(s) to solve this problem. You can do whatever you want as long as your solution is a recursive one (i.e. you can call a recursive helper method).

    Solving Maze

    Write a recursive method that finds a path in a given maze. A maze consists of open spaces (represented by 1s) and walls (repesented by 0s). So, we can represent a maze with a 2-dimensional array of 0s and 1s. The goal is to get from the top left corner to the bottom right, following a path of 1's.

    You will implement methods in Maze.java to solve such a maze using recursion. You will be given a maze and will return the solved maze (using 2s to mark the path) or null if there is no solution.

    For example, the following maze:

    1 1 1 1 1
    1 0 0 0 0
    1 1 1 1 1
    0 1 0 0 1
    1 1 1 0 1

    Has the following solution:

    2 1 1 1 1
    2 0 0 0 0
    2 2 2 2 2
    0 1 0 0 2
    1 1 1 0 2

    Hints:

  • Use the construction of the maze (i.e. rectangular, constant starting and ending points, etc) to your advantage.
  • You are allowed to modify the contents of the maze if that aids in a solution - the only requirement is that you return a properly solved maze. It might be helpful to keep track of which spaces you've already visited.
  • Under what conditions is there a path from a given open space to the bottom-right space?

    Flat World

    Write a recursive method to determine the number of organisms in a table that is defined as a 2D array of cells. The 2D array of cells can be of any size. Each cell can be either empty or occupied by a "*". An organism consists of *-cells that are connected directly to that one via up, down, left, and right movements. Given the following matrix, how many organisms are there?

    * *           *    
      *           *    
                * *    
      *     * * *      
      * *   *   *   *  
      * *   * * * * * *
    *               *  
                    *  
          * * *     *  
              *     *  

    There are 5 organisms as shown below:

    1 1           5    
      1           5    
                5 5    
      2     5 5 5      
      2 2   5   5   5  
      2 2   5 5 5 5 5 5
    3               5  
                    5  
          4 4 4     5  
              4     5  

    Write a recursive method 

    public int numOrganisms(boolean[][] world)
    that accepts a 2D array of boolean values (true means a *-cell and false means an empty cell) and returns the number of organisms on the board. Note, a board does not wrap around, this is a flat world.

    Arrangements

    Suppose we have a collection (i.e. a set) of numbers: 
    1, 2, 3, 4
    and we want to find all possible arrangements of these numbers. We'll define an arrangement of our set as a list of numbers consisting of every member of our set exactly once. So, 
    1, 2, 4, 3
    and 
    2, 3, 4, 1
    are valid arrangements. However, 
    2, 2, 4, 3
    and 
    5, 1, 2, 3
    are not valid arrangements. For our purposes, we'll treat our set of numbers as a Set of Integers and each specific arrangement as an array of ints.

    Write the method 
    public Set<int[]> generateAllArrangements(Set<Integer> set)
    that returns the set of all possible arrangements of the given set of Integers.

    Hints:

  • How many valid arrangements are there for a set of size n? Why? How does this reasoning help us construct an algorithm to actually generate all the arrangements?
  • How would you solve this problem yourself by hand? How do you know you got the right answer?
  • You may find it helpful to use helper method(s) to solve this problem. You can do whatever you want as long as your solution is a recursive one (i.e. you can call a recursive helper method).
  • You are allowed to modify the input set if that helps you solve this problem, but you aren't required to.

    Starter Code:

    Download the following files

    Once you finish implementation, you must turn in the above four files.

    Grading:

    Your assignment will be graded first by automated testing. After that, we will read your code to determine whether requirements were satisfied, as well as judge the overall style of your code. Programs will be graded both on correctness as well as the style. Points will be deducted for poor design decisions and un-commented, or un- readable code.

    For this lab specifically, you will also be graded on your recursive thinking. Make sure you are solving the problems recursively.

    Here is the point breakdown: