Wellesley College, Summer 2003 Problem Set 7 Due: Thu., July 3 by 6pm

Reading

• (Fall'01 text) Chapter 6: Lists
• (Fall'01 text) Chapter 12: Strings and Things
• Diagramming List Recursions
• Study the code in the file IntListOps.java within the lec10_lists/IntLists folder.
• Study the code in the file StringListOps.java within the ps7_programs/Unjumbler folder.
• Study the code in the file Lab8Ops.java within the ps7_programs/Unjumbler folder.
• IntList Contract
• IntListOps Contract
• StringList Contract
• StringListOps Contract
• String Contract

About this Problem Set

• Task 1 is an independent problem in which you will program a buggle to eat bagels in a spiral pattern using fruitful recursion. Because it is an independent problem, you may not consult with anyone else about this particular problem.
• In Task 2 you will gain a better understanding of lists by writing many methods that manipulate lists of strings as part of implementing an "unjumbling assistant" that will help you solve "word jumble" problems.

The code for both tasks is available in the ps7_programs folder in the cs111 download directory.

The IntListList problem on change-making originally slated for Problem Set 7 will be delayed until Problem Set 8.

How to turn in this Problem Set

Hardcopy Submission

1. The cover page;
2. Your final version of SpiralEaterWorld.java from Task 1;
3. Your final version of Unjumbler.java from Task 2.

Softcopy Submission

• For Task 1, submit your final version of the SpiralEaterWorld folder to your drop folder on the cs111 server.
• For Task 2, submit your final version of the Unjumbler folder to your drop folder on the cs111 server.

Submit only softcopies of the SpiralEaterWorld and Unjumbler folders. Do not submit the dicts folder or either of the Test folders. (Some of these folders are very big and will eat up your disk quota.)

Task 1: SpiralEaterWorld (Independent Problem)

Task 1 is an independent problem (which is effectively a mini take-home exam). You may not consult with anyone else about this problem. (If you have any questions, you may of course ask Lyn or Elena; but we cannot help you to solve the problem.)

Background

Starting in the lower left corner of the grid facing East, Spiro moves forward, hugging the wall, turning left when he gets to a corner. (See the pictures below.) Whenever he encounters a bagel, he eats it, and paints the square with a specied color (blue in this example). Any square without a bagel is painted with the color of the buggle (red in this example). Spiro treats any colored cell as if it is a wall, so when he encounters his own trail, he spirals toward the center of the grid. See the pictures below showing several snaphots of the state of the grid as Spiro spirals inward toward the center of the grid.

When Spiro reaches the final cell of the spiral and can't move any farther, he steps backwards along the same spiral path he followed towards the center. He repaints to white every cell that was originally empty, but leaves a colored cell in every location that originally contained a bagel. At the final step, Spiro is in his initial position facing East, and all locations originally containing bagels have been transformed to colored cells. Here are snapshots depicting some of the intermediate states when Spiro is unwinding his way back to his initial position:

You can interactively experiment with the behavior of eat by running the SpiralEaterWorld.mcp file in the SpiralEaterWorldTest folder in the exam2_programs folder. This will create a parameter window in addition to a buggle window. After you select parameters specifying the side length of the buggle grid and the desired number of bagels, press Reset to change the side length of the grid an populate the grid with the specified number of randomly placed bagels. Press Run to have the buggle invoke the eat method the bagel color specified in the parameter window (the buggle itself will have the buggle color specified in the parameter window).

Your Task

Your task is to write an eat instance method in the SpiralEater class, which is a subclass of Buggle:

public void eat (Color c);
Assume the buggle's brush state is initially up. As described above, causes the buggle to follow a counter-clockwise spiral in which all bagels in the grid are eaten and replaced by a cell colored with the color c, which may or may not be the same as the buggle's color. The position, heading, and color of the buggle are invariant under the eat method.

Notes:

• In the SpiralEaterWorldTest folder is a test version of the program that you should play with before starting the assignment. In the parameter window, try various numbers for side and bagels and various colors for buggleColor and bagelCellColor. The recognized colors for the color parameters are red, blue,green, yellow, magenta,cyan, black, and white. Press the Reset button after any changes before pressing Run.
• Use the paintCell method to paint the cell under the buggle with any color (including white).
• Use the getCellColor method to determine the color of the cell underneath the buggle.
• Use the getColor method to determine the color of buggle.
• Do not use the setColor or setPosition methods in your code.
• Do not use any while loops or for loops in your code. Use recursion instead! In particular, the unwinding of the spiral should be accomplished by undoing on the way out of the recursion the steps used to make the spiral pattern on the way into the recursion.
• In addition to the eat method, you should define whatever additional auxiliary methods that you find useful.
• It is recommended that you solved the problem in the following stages:
  1. First, get the buggle to walk to the center of the grid in a spiral pattern by just leaving a trail of its colors. Ignore bagels in this stage.
  2. Next, modify eat to have the buggle eat bagels and color the bagel cells with the specified color as it spirals inward.
  3. Next, modify eat to have the buggle walk out of the spiral back to its original position without repainting any cells.
  4. Finally, modify eat to repaint cells appropriately as it walks out of the spiral.
• Your eat method should work for any color of buggle and any parameter color supplied to eat. Make sure to test your program with various buggle and bagel cell colors. The only color constant that your eat method may use is Color.white. You should not use any other color constants, such as Color.red or Color.blue.
• As noted in the specification of eat, your program should work even when the color parameter supplied to eat is the same as the buggle's color. That is, in this case, when the program is done, only cells originally containing a bagel should be colored with the buggle's color. The diagrams below show three intermediate steps of the process in the case when the buggle and the parameter to eat are both red.

  You can still receive most of the credit on this problem even if you do not correctly handle the case where the color parameter is the same as the color of the buggle.

• Partial credit will be awarded for an eat method that satisfies only some parts of the specification.

Task 2: Word Unjumbler

Overview

The game involves "unjumbling" English words whose letters have been reordered. For instance, the jumbled word ytikt can be unjumbled to kitty. The game can be challenging; even relatively short jumbles can be tricky to unjumble. For instance, here are the words that appeared on the March 26, 2003, version of the on-line game; can you unjumble them?:

(The last string unjumbles into two words.)

In this problem, you will create a Java program that acts as an "unjumbling assistant". Given a string, your program will first generate all possible reorderings of the letters in the string. Such reorderings are called permutations. For example, there are six reorderings of the letters in the string tra:

In general, a string with n distinct letters has n! (pronounced "n factorial") permutations. For instance, a 4-letter string has 4! = 24 permutations, a 5-letter string has 5! = 120 permutations, a 6-letter string has 6! = 720 permutations, and so on.

Next, the assistant will determine which of the permutations is an English word by looking them up in a "dictionary". You do not have to worry about how to construct such a dictionary; this has been done for you. Notes on how to use the dictionary as a "black box" can be found later in this problem description. In the case of "tra", filtering out the English words leaves:

When the string you are unjumbling contains duplicate letters, it turns out that a simple permutations generator will yield some duplicate permutations. For instance, the permutations of "dda" will generate the 3! = 6 permutations:

Filtering out the English words yields:

In such cases, the unjumbling assistant should also filter out duplicates to yield the final list:

To get a feel for what the unjumbling assistant does, you should experiment with the working unjumbler test program in the folder UnjumblerTest within the ps7_programs folder. You can use the program to help you solve the on-line Word Jumble puzzles!

Your Task

Here are some things you need to know:

• Unlike in previous assignments, you are not given skeleton method declarations that you will flesh out. Instead, you must write all of your method declarations from scratch. Write all of your definitions within the Unjumbler class in the file Unjumbler.java within the folder Unjumbler of the ps7_programs folder. Carefully read the comments at the top of the Unjumbler.java; these tell you which class methods you can use in the file without an explicit class name as a prefix.
• Unlike most previous programming assignments, which were Java applets, this assignment is a Java application. Code that you want to be executed when you run the program must be in the main method of Unjumbler.java. On a Mac, you must be sure to quit out of any previous MRJ applications before attempting to run your program again.
• Unlike in previous assignments, you are not provided with test cases for your methods. You are required to write your own testing code for this assignment. You should test each of your methods by adding appropriate testing code to the main method of the Unjumbler class, just as you did in Lab 7. Recall that the fromString class method for the StringList is a very convenient way to generate a string list. For instance fromString("[I,am,Sam]") yields a three element list containing the strings "I", "am", and "Sam".
• In many cases below, you will need a working version of one or more of the earlier methods to write a later method. In order to remove the dependency between the different methods, we have provided you with a class named UnjumblerAnswers that contains working versions of each of the nine methods. If you don't have a working method meth1, but need meth1 to define meth2, you can use UnjumblerAnswers.meth1 within your definition of meth2. This allows you to work on the nine methods below in any order, while still being able to test each method along the way.

1. public static StringList remove (String s, StringList L)
   Returns a new list in which all occurrences of s in L have been removed. The other strings in the list should have the same relative order in the resulting list as in the given list.

   Examples:
   remove("I", fromString("[I,know,that,I,said,that,I,did]")))
         returns the string list [know,that,said,that,did].
   
   remove("that", fromString("[I,know,that,I,said,that,I,did]"))
         returns the string list [I,know,I,said,I,did].
   
   remove("said", fromString("[I,know,that,I,said,that,I,did]"))
         returns the string list [I,know,that,I,that,I,did].
   
   remove("you", fromString("[I,know,that,I,said,that,I,did]"))
         returns the string list [I,know,that,I,said,that,I,did].
   

   Note: Use the equals instance method from the String class to compare two strings. For instance, "cat".equals("cat") returns true but "cat".equals("dog") returns false. You should not use == to compare two strings because it may not return what you expect. For instance, while "cat" == "dog" is guaranteed to return false, "cat" == "cat" and "cat" == ("c" + "at") are not guaranteed to return true. They may return true in some implementations and some circumstances, but you cannot rely on this behavior.

2. public static StringList removeDuplicates (StringList L)
   Returns a list containing each string in L exactly once. The order of the elements in the returned list should be the relative order of the first occurrence of each element in L.

   Examples:
   removeDuplicates(fromString("[I,know,that,I,said,that,I,did]"))
         returns the string list [I,know,that,said,did].
   
   removeDuplicates(fromString("[you,say,what,you,mean,and,mean,what,you,say]"))
         returns the string list [you,say,what,mean,and].
   
   removeDuplicates(fromString("[lists,are,cool]"))
         returns the string list [lists,are,cool].
   

   Note: The remove method from above is helpful here!

3. public static StringList mapConcat (String s, StringList L)
   Given a list L with n strings, returns a new list with n strings in which the ith string of the resulting list is the result of concatenating s to the ith element of L.

   Examples:
   mapConcat("com", fromString("[puter,plain,municate,pile]"))
         returns the string list [computer,complain,communicate,compile].
   
   mapConcat("I ", fromString("[came,saw,conquered]"))
         returns the string list [I came,I saw,I conquered].

4. public static StringList insertions (String s1, String s2)
   Given two strings s1 and s2, where s2 has n characters, returns a list of n + 1 strings that result from inserting s1 at all possible positions within s2, from left to right.

   Examples:
   insertions("*", "split")
         returns the string list [*split,s*plit,sp*lit,spl*it,spli*t,split*]

insertions("a", "bcd")
         returns the string list [abcd,bacd,bcad,bcda]

insertions("com", "pile")
         returns the string list [compile,pcomile,picomle,pilcome,pilecom]

insertions("abc", "")
         returns the string list [abc]

   Note: The Lab8Ops class contains two helper methods that are useful for defining insertions:

   1. public static String first (String s)
      Returns a string consisting of the first character of s. For example, first("computer") returns the string "c".

   2. public static String butFirst (String s)
      Returns a string consisting of all but the first character of s. For example, butFirst("computer") returns the string "omputer".

5. public static StringList insertionsList (String s, StringList L)
   Returns a list that contains all the strings that result from inserting s at all possible positions in all the strings of L.

   Examples:
   insertionsList("a", fromString("[bc,cb]"))
         returns the string list [abc,bac,bca,acb,cab,cba]

insertionsList("*", fromString"[I,am,Sam]"])
         returns the string list [*I,I*,*am,a*m,am*,*Sam,S*am,Sa*m,Sam*]

insertionsList("abc", fromString("[]"))
         returns the string list []
   

   Note: The StringListOps class contains a helper method append that is useful for defining insertionsList:

   public static StringList append (StringList L1, StringList L2)
   Returns a new string list containing all the elements of L1 followed by all of the elements of L2. For example,

   • append(fromString("[I,do]"), fromString("[not,like,green,eggs]")) returns [I,do,not,like,green,eggs]
   • append(fromString("[I,do]"), fromString("[]")) returns [I,do]
   • append(fromString("[]"), fromString("[not,like,green,eggs]")) returns [not,like,green,eggs]

6. public static StringList permutations (String s)
   Returns a list of all permutations of the string s. A permutation of a string s is any string that is formed by reordering the letters in the string s (without duplicating or deleting any letters). For a string with n distinct characters, there are exactly n! (i.e., "n factorial") permutations. If some characters in s are repeated, there are still n! permutations, but the permutations contain duplicates. The elements in the list returned by permutations may be in any order.

   Examples:
   permutations("d") returns the string list [d].
   
   permutations("cd") returns the string list [cd,dc] or the string list [dc,cd].
   
   permutations("bcd") returns (any permutation of) the string list [bcd,cbd,cdb,bdc,dbc,dcb].
   
   permutations("abcd") returns (any permutation of) the string list

         [abcd,bacd,bcad,bcda,
          acbd,cabd,cbad,cbda,
          acdb,cadb,cdab,cdba
          abdc,badc,bdac,bdca,
          adbc,dabc,dbac,dbca,
          adcb,dacb,dcab,dcba].

   
   permutations("121") returns (any permutation of) the string list [121,211,211,112,112,121]. Note that when the given string contains duplicate characters, the permutation list will contain duplicates.
   
   permutations("1231") returns (any permutation of) the string list

         [1231,2131,2311,2311,
          1321,3121,3211,3211,
          1312,3112,3112,3121,
          1213,2113,2113,2131,
          1123,1123,1213,1231,
          1132,1132,1312,1321].

   Note: There are many ways to define the permutations method, but a particularly elegant way uses the first, butFirst, and insertionsList methods from above. Be very careful in defining your base case!

7. public static StringList filterWords (StringList L)
   Returns a list of all strings in L that are English words. The resulting strings should be in the same relative order as in L.

   Examples:
   filterWords(fromString("[the,dog,barked,at,the,cat]")) returns the string list [the,dog,barked,at,the,cat].
   
   filterWords(fromString("[the,dog,barkd,ate,hte,cat]")) returns the string list [the,dog,ate,cat].
   
   filterWords(fromString("[tra,rta,rat,tar,atr,art]")) returns the string list [rat,tar,art].
   

   Note: To determine if a string is an English word, you should use the class method isWord that is already defined for you in the Unjumbler class:

   public static boolean isWord (String s)
   Returns true if s is a word in the default English dictionary, and false otherwise.

   The default dictionary (which can be changed within the Unjumbler class) contains 22641 English words (all lower case, no proper nouns) of up to 8 characters in length. It is not a "perfect" dictionary: there are some perfectly acceptable English words that are not in the dictionary.

   You can change the default dictionary to one that contains 45425 English words without a length restriction, but this takes longer to load. For details on how to do this, see the comments near the end of Unjumbler.java.

8. public static StringList unjumble (String s)
   Returns a list of all the permutations of s that are English words (as determined by the default dictionary). The order of elements in the resulting list does not matter, but each word in the resulting list should listed only once.

   Examples:
   unjumble("tra") returns the string list [rat,tar,art].
   
   unjumble("tras") returns the string list [rats,arts,star]
         (the default dictionary doesn't recognize tars or tsar as words).
   
   unjumble("argle") returns the string list [glare,large,lager,regal].
   
   unjumble("sbso") returns the string list [sobs,boss].
   
   unjumble("xzzy") returns the string list [].
   

   Note: You should only remove duplicates after performing filterWords. It turns out that performing removeDuplicates on a large lists (such as the output of permutations) can take a very long time. (To understand why this is so, take CS230!)

9. public static void unjumbleInteractively()
   Launches an interactive session in the Java Console that repeatedly prompts the user for a string and displays the list of unjumbled English words for that string. The interactive session ends when the user enters the empty string.

   Example: Below is a sample session of unjumbleInteractively(). The text typed by the program is in italics, while the text typed by the user is in bold:

   Enter a string to unjumble and press Return (enter the empty string to quit):
argle
Constructing dictionary from file ../dicts/dict8.txt.
This may take a little while...
Done! Dictionary constructed with 22641 words.
[glare,large,lager,regal]
Enter a string to unjumble and press Return (enter the empty string to quit):
eshou
[house]
Enter a string to unjumble and press Return (enter the empty string to quit):
sbos
[boss,sobs]
Enter a string to unjumble and press Return (enter the empty string to quit):

Thank you for using the unjumbler!

   Notes:

   • To read input from the Java Console, use the following class method from the Stdin class:

     public static String readLine (String s)
     Displays the prompt s in the Java Console window, and waits for the user to type a line of text. When the user presses the return key, returns the line of text that has been typed as a string.

   • In the above example, the following text is automatically displayed when the dictionary is loaded, which automatically happens when the isWord method is invoked for the first time.

     Constructing dictionary from file ../dicts/dict8.txt.
This may take a little while...
Done! Dictionary constructed with 22641 words.