CmpSci 187 HW2 Professor Lehnert
Spring 2011
Introduction
Section 3.5.3 describes a type of word puzzle called a summation puzzle. Read the book’s description of summation puzzles now. For this homework you will write a recursive program that solves summation puzzles. This problem has a natural solution using both recursion and linked lists, so we will work up to it with a couple “warm-up” exercises.
Exercise 1
Pascal’s Triangle is a “ragged array” whose rows become longer as we move from the top to the bottom. Pascal’s Triangle is actually an infinite structure with an infinite number of rows, but we’ll stick to representations that are limited to a finite number of rows.
The first 4 rows are:
1 1
1 1 1 1
1 2 1 1 2 1
1 3 3 1 ( or ) 1 3 3 1
where each interior term is defined recursively:
n i,k = n i-1, k-1 + n i-1, k
Implement a class called Pascal with a constructor Pascal(n) that creates the first n rows of Pascal’s Triangle. Build your triangle as a single linked list that contains additional linked lists for each row (just as a 2-D array can be represented as a 1-D array containing other 1-D arrays). This code will be easy to write if you take advantage of the LinkedList class found in java.util to create your linked lists, and then fill each row of the triangle using recursion.
Write a constructor Pascal(n) that creates a triangle containing n rows (e.g. the triangle shown above contains 4 rows.
Implement an instance method getRow(n). This methods should use 0-origin indexing. E.g. getRow(2) should return a linked list containing 1 2 1.
Implement an instance method getElt(n,m). This method should use 0-origin indexing. E.g. getRow(2,3) should return 3.
Exercise 2
Now we’ll design a recursive program that generates all the permutations of a string. The structure of this code is illustrated in Figure 3.26 on page 154. Study that figure and make sure you understand it before you continue.
Implement a class named SumPuzzle that includes a null constructor (a constructor definition that takes no arguments). The SumPuzzle class should also contain an instance method named permute(String str, LinkedList<Character> lst). The permute method pulls characters from lst in order to grow permutation strings inside str and it uses both iteration and recursion. Your base case should test for an empty lst argument, in which case you can store the str argument in a SumPuzzle attribute that collects all the permutations for you. You don’t need to know how many permutations you’ll be collecting if you use a linked list to collect them all.
The permute method doesn’t have to be a public method. In fact, it should probably be private. The permute method just a workhorse to be used by a public method named allPermutations(string). A call to allPermutations(string) should return a LinkedList containing all possible permutations of the argument string.
Be careful when you test your code – do not try it on strings that are very long. The number of permutations for a string of length n is factorial(n).
Exercise 3
Once you have running code for Exercise 2, you are very close to having a program that solves summation puzzles. Note that any string contains an implicit mapping between the characters of the string and the integers representing the indices for those characters. If the string contains no duplicates, this is a one-to-one mapping with a unique numeric value for each character. For example, the string “pig” maps ‘p’ to 0, ‘i’ to 1, and ‘g’ to 2.
So each permutation of an alphabet string yields unique numeric values for the characters in that string, and one such permutation may represent the solution to a Summation puzzle (see section 3.5.3 again).
In Exercise 2 we generated all possible permutations for a string. For a summation puzzle we can stop as soon as we find a permutation that solves the puzzle or we can look for all possible solutions. For this exercise, we want you to solve a puzzle by checking all the possible permutations on the puzzle alphabet and finding all possible solutions. Add an instance method to the SumPuzzle class named solve(s1, s2, s3). Use this method to solve summation puzzles of the form
s1 + s2 = s3.
A call to solve(s1,s2,s3) should return a LinkedList containing all possible permutations on an appropriate alphabet string which satisfy the puzzle requirements for s1 + s2 = s3. If your alphabet contains n characters, your permutations should all be strings of length n.
Once you have the solve method running correctly, define a method superSolve(s1,s2,s3) which searches a larger search space for summation puzzle solutions. If your alphabet string contains exactly n characters, each permutation generated by the solve method will give you maps onto the integers in [0, … , n-1]. But if n is less than 10, that means you won’t find maps involving all 10 values [0, … , 9] because your permutations only cover the values [0, … , n-1]. What if you want to draw from all 10 possible numeric values [0, … , 9] even if n is less than 10? For example, your puzzle solution may only need 5 values but you want them to be 1, 4, 5, 8, 9. How can you adjust your alphabet string to allow for all 10 possible numeric values? Make this adjustment to your alphabet string so superSolve(s1,s2,s3) will find all the puzzle solutions for s1 + s2 = s3 using all the values in [0, …. , 9].
Exercise 3 Reality Check
If your code is running correctly, solve(“girl”,”boy”,”baby”) should return 8 solutions and superSolve(“girl”,”boy”,”baby”) should return 168 solutions.
Huh?
The basic search for solutions will be accomplished by the code you wrote for Exercise 2 to generate permutations on a string. For each puzzle specified by the actual arguments handed to the solve method, you need to set up an appropriate alphabet string so you can generate permutations for that alphabet. Then to solve a summation puzzle, you just generate permutations on that alphabet, checking each one to see if that particular mapping from characters to integers solves the given summation puzzle. You will need to write some extra code to (1) create the alphabet string, and (2) test a given permutation to see if it satisfies the required arithmetic relation. But you wrote the main workhorse code (the code that generates all the permutations) in Exercise 2.
This type of algorithm is called a generate and test algorithm. First you generate all the possible permutations and then you test each one looking for a solution. Exercise 2 gave you the basic generating part of your code, and Exercise 3 wrapped it up with the testing part.
How We’re Going to Grade HW2
We’re going to load your source code, compile it, and run it on some test cases. Your code can fail at our end in two ways.
Compiler Errors: If we get a compiler error, your code will fail in a huge way because we won’t be able to run it on any test cases. Compiler errors result in a 0 for your project grade. Note that it is possible for your code to compile correctly at your end and then fail to compile at our end under certain circumstances. But don’t despair --- there are steps you can take steps to make sure this won’t happen.
Runtime Errors: A fatal runtime error is a huge error because it can prevent us from running your code on all of our test cases. Again, there are steps you can take to minimize the risk of a fatal runtime error. If your code runs but produces some wrong results, you will lose points for that, but at least we’ll be able to get your code through all the test cases.
You want your code to run without any huge errors when we test it, and there are steps you can take to make sure we don’t encounter huge errors when we test your code. Please read through the following instructions to make sure you get the grade you deserve on your HW2 project.
Avoiding Compiler Errors
This is a nightmare scenario. You spend 20 hours on HW2, it’s running perfectly at your end, you get it in on time, you wait a week to get your grade, and then you get a nice fat 0 for all your efforts. It’s enough to make you hate 187, hate computer science, and hate UMass. Let’s try to avoid this.
> Avoiding Syntactic Compiler Errors
Before we can avoid them, we need to understand what they are. In Exercise 2 we ask you to write a method named allPermutations but you name your method allpermutations. That’s a compiler error (case matters). Or you misspell it as allPermitations. That’s another compiler error.
And there are more possibilities. Suppose we ask for
permute(String str, LinkedList<Character> lst)
and you define it this way:
permute(LinkedList<Character> lst, String str)
That’s a compiler error.
Any time we try to run a method using a specified name and syntactic form, the compiler expects to see that exact same name and syntax. If you deviate from the expected specs, your code will fail to compile, we won’t be able to run it at all, and you will get a 0 for your submission.
But here’s the good news. There is an EASY way to avoid syntactic compiler errors! All you have to do is implement an interface. We’ll go over that below where we talk about interface requirements.
> Avoiding Visibility Compiler Errors
It is possible for you to test your code in a main method that can “see” a private method in a class because the main method is contained inside that same class. If we try to execute the exact same method inside a different class (e.g. one that we’ve written to test your code) we’ll get a compiler error.
Again, this is easy to avoid if you follow our instructions for how your code should be organized. We’ll go over that below when we talk about your code structure.
> Avoiding Compiler Errors Due to Missing Code
This can happen pretty easily. You have a workspace that contains about 10 class definitions. One of them contains a handy little utility class that you use in your HW code. But when you submit your code, you forget to include that class in your submission. Since we won’t have that class definition at our end, and your code relies on it, we’ll get a fatal compiler error. You can avoid this (see the section below on code organization).
Avoiding Runtime Errors
A runtime error is fatal if it crashes your code. It’s obviously a good idea to avoid these, but there’s always a chance that we might test your code on some input that you never tried yourself and your code blows up for some reason. It could be an array out of bounds error. It could be a null pointer exception.
Some of these are easy to avoid. Almost of them can be avoided with additional effort. For the easy ones, be careful with your method arguments. For example, in Exercise 3 we ask you to define a method solve(s1, s2, s3). Which solves puzzles of the form s1 + s2 = s3. If you write your method to solve puzzles of the form s2 + s3 = s1, that could possibly end badly with a fatal runtime error. At the very least, it will give you a wrong result (another type of runtime error).
You also need to make sure you have method definitions for all the methods we expect to see, even if you were not able to produce working code for all of those methods. For example, suppose you were able to define the solve method correctly, but you couldn’t get superSolve to work. You should still define a superSolve method that meets the syntactic specifications in order avoid fatal runtime errors:
public ArrayList<String> superSolve(String s1, String s2, String s3){
return new ArrayList<String>(); // returns an empty list
}
To avoid runtime errors you need to follow HW instructions carefully. Pay attention to details in our HW descriptions, double check your code after you’ve written it, and then reread our instructions at least 3 times over to make sure you’ve got all the details right. That’s the easy part.
The part that takes a little more effort involves testing your code. Don’t stop after one or two test cases. Make up a lot of test cases when you check your code to make sure it’s running correctly. Pick some oddball cases to see if your code can handle everything. Try to anticipate all the possible things we might do when we run your code. You can’t really know what we’re going to do, but you should try to put your code through as many tests cases as you can. That will greatly reduce the chances of a runtime error when we try out your code on our test cases.
Avoiding Compiler Errors with Proper Code Organization
If everyone structures their code correctly, we don’t have to see any compiler errors due to visibility problems or missing code problems. Here’s the proper code organization:
You will give us a file named Pascal.java that contains a public class named Pascal (exercise 1)
You will give us a file named SumPuzzle.java that contains a public class named SumPuzzle (exercises 2 and 3).
You do not need to identify any additional classes for HW2. But if your code does rely on any additional classes, you must make sure those classes appear as inner classes inside the Pascal class or the SumPuzzle class as needed.
Note that the LinkedList class is part of the Java API. To access it, you will need an import statement such as
import java.util.*
at the beginning of your source code file. The LinkedList class will also be available at our end as long as your code contains the proper import statement. This sort of class dependency is not likely to be a problem since your code won’t run properly at your end if you haven’t imported the class from the API as needed. This is not one of those situations where it might run at your end but it doesn’t run at our end.