CS46B Lab - Using Collections

Copyright © Cay S. Horstmann 2012
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.

A. Sets and Maps

In this part, you will write a program that reads a Java source file and makes an index of all identifiers and the line numbers, like this: (below is the output of your program)

Dict 6
Exception 8
File 1 10
Integer 12 22
Scanner 2 10 17
String 8 12 16 21 28
System 30 32 33
TreeMap 3 12
TreeSet 4 12 22 23
add 24
args 8 10
get 22 31
hasNext 19
hasNextLine 13
identifier 21 22 25
in 10 13 16
in2 17 18 19 21
index 12 22 25 28 31
 ...

To read a file, we'll use a scanner in the usual way:
```
Scanner in = new Scanner(new File(args[0]));
```
If we now keep calling in.next(), we get a sequence of words. Try it out:
```
while (in.hasNext())
{
   System.out.println(in.next());
}
```
Complete a program Dict.java and run
```
java Dict Dict.java
```
(i.e. reading your own program).

Yes, that's on the command line. Open a terminal window. Navigate to the right directory, run javac Dict.java and then the command above.

What output do you get?
Ok, that wasn't so useful. We want each Java identifier, not each word. The trick is to set the delimiter of the scanner. By default, the delimiter is a regular expression
```
[ \t\n\r]+
```
What does this regular expression match?
That's not quite what we want. For the delimiter, we want to match every character that's not a letter, digit, or underscore. What regular expression is that?
Try it out—call
```
in.useDelimiter("...");
```
before the while loop and run your program again. Now what output do you get?

Here, of course, ... should be your regular expression, not three periods.
That's nice—it gives us all the identifiers, but we don't have line numbers. To get line numbers, one must do
```
int lineNumber = 0;
while (in.hasNextLine())
{
   lineNumber++;
   String line = in.nextLine();
}
```
Now extract the identifiers from each line, by using a second scanner
```
Scanner in2 = new Scanner(line);
while (in2.hasNext()) ...
```
Print each identifier and the line number in which occurs.

What output do you get?
That's nice—but we want to it to look like an index, with all line numbers of a given identifier listed together. This is done by forming a map whose keys are the identifiers and whose values are sets of integers.
What map? A hash map or a tree map? What sets? Hash sets or tree sets? If either is ok, say so.
Declare and initialize a variable index of type ???Map<???, ???Set<???>>, filling in the ???. Do this before the outer while loop. What is your code?
Now remove the print statement. Instead, each time you read an identifier, call
```
???Set<???> lines = new ???Set<>();
lines.add(lineNumber);
index.put(identifier, lines)
```
At the end of the program, add
```
System.out.println(index);
```
Run the program again. What output do you get?
That's not really nice—you only get the last occurrence of each identifier. Why?
Time to work harder. When you read an identifier, call
```
???Set<???> lines = index.get(identifier)
```
instead of making a new set each time. (Keep the other two lines of code.) This way, you add lineNumber to the existing set of line numbers for the identifier.

Run the program. What happens?
Why?
Ok, the first time is special. How can you tell that you are about to add the first line number for a given identifier?
And what should you different in that case?
Implement that. What is the code inside the inner loop?
Run the program. What happens?
You should now have the right output, but the formatting could be nicer. Iterate over all the keys of the map. and print each key. What is your code?
Now, for each key, also fetch index.get(key) and print it.
Run the program. What's the output?
Getting there... Now, iterate over the elements in index.get(key) and print each of them, with spaces in between.
Run the program. What's the output? (Your output should look similar to that before step 1.)

Just one flaw. The output contains Java keywords such as class and if. Make a set of all Java reserved words

???<???> reserved = new ???<>(Arrays.asList("abstract", "continue", "for",
   "new", "switch", "assert", "default", "goto", "package", "synchronized",
   "boolean", "do", "if", "private", "this", "break", "double", "implements",
   "protected", "throw", "byte", "else", "import", "public", "throws", "case",
   "enum", "instanceof", "return", "transient", "catch", "extends", "int",
   "short", "try", "char", "final", "interface", "static", "void", "class",
   "finally", "long", "strictfp", "volatile", "const", "float", "native",
   "super", "while"));

Be sure not to print any of them. (Or even better, not to add any of them into the map.)

Now what is your program output?
What is the code of your program?

B. A Stack for Tree Traversal

The file system is an example of a recursive data structure. Directories can contain files or other directories, which can again contain files or directories.
In the Java API, there is a class File that can denote either files or directories. When you have an object file of class File, call
- file.isDirectory() to find out whether it's actually a directory
- file.list() to get an array of the files and directories it contains if it is in fact a directory
Suppose you are asked to print all files that occur in a directory or one of its descendants. Write pseudocode for a recursive method

printAllFiles(File dir)

Ok, it's not hard to do this with recursion. Can you do it without recursion? That's when a stack comes in.

printAllFiles(File dir)
  stk = a stack
  push dir on stk
  while stk is not empty   
    pop stack into d   
    for each f in d.list()       
      if f is a file, print it      
      otherwise push it on stk

No recursion!

Assume the following directory structure:

In which order are the files printed? (Work it out by hand.)

Now implement the method from that pseudocode:

public class Dirs
{
   public static void main(String[] args) throws IOException
   {
      File dir = new File(args[0]);
      printAllFiles(dir);
   }

   ...
}

What is the code of your class?

Download this file and run
```
cd path/to/lab10
mkdir numberquiz
cd numberquiz 
jar xvf /path/to/downloads/numberquiz.zip
cd ..
javac Dirs.java
java Dirs numberquiz    
```
(where path/to/lab10 is the directory containing Dirs.java.)

What output do you get?Your Java program is Dirs, and your input is numberquiz. You should not get any error when running these above commands.
Could you have used a queue instead of a stack? Why or why not?

C. A Queue for Solving a Number Puzzle

An addition puzzle has a form such as 2BCD+BCDE=DA01. We want to find a solution, where A, B, C, D are distinct digits, different from any digits in the puzzle. Here, a solution is 2345+3456=5801.
Solve the puzzle AB + C = BA by hand. What is a solution? How did you get it? (Remember that the letters are all different.)
That wasn't so hard because you knew that B had to be A + 1, and then you can determine C. But in a program, it's easier to just try all combinations.
Given a puzzle, we'll pick the first letter, replace it with all the numbers that aren't already present, and throw each of these simpler puzzles in a queue. For example, given 2BCD+BCDE=DA01, we'll add the following to a queue:

23CD+3CDE=DA01

24CD+4CDE=DA01

25CD+5CDE=DA01

26CD+6CDE=DA01

27CD+7CDE=DA01

28CD+8CDE=DA01

29CD+9CDE=DA01

Then we take the next one from the queue and repeat.

Eventually, we'll be left over with puzzles that have no letters left, such as

2345 + 3456 = 5801

which is a solution (so we print it)

or

2435 + 4356 = 5701

which is not (so we discard it).

In other words, the queue holds the partially finished work.

Try this for the puzzle AB + C = BA. What goes into the queue?
Now pull out the first one from the queue and add its replacements? What are they?

Let's do this with the computer instead. Use this Puzzle class. Complete

public class PuzzleSolver
{
   public static void main(String[] args)
   {
      Puzzle puzzle = new Puzzle(args[0], args[1], args[2]);
      Queue<???> q = new LinkedList<>();
      q.add(???);
      while ()
      {

      }
   }
}

What is your code?

What solution(s) do you get when you run
```
java PuzzleSolver AB C BA
```
What solution(s) do you get when you run
```
java PuzzleSolver 2BCD BCDE DA01
```
What solution(s) do you get when you run
```
java PuzzleSolver SEND MORE MONEY
```
Could you have used a stack instead of queue? Why or why not?
How could you have used recursion instead of a stack or queue? Provide pseudocode.

D. Escaping a Maze without Recursion

As you saw in the preceding two sections, you can use a stack or queue to avoid recursion. Let's try that with another recursive algorithm. Go back to your solution of the recursion lab parts A and B. Look these over again. Why was it easy to avoid the recursion (with just a loop) in part A, and why wasn't it easy in part B?
We want to solve part B without recursion.
The trick is always to put unfinished work on a stack or queue. (It doesn't matter which—the only difference is the order in which the work is broken down.) In this example, you get up to four pieces of unfinished work when you reach an intersection.

Let's use a stack here.

What work items do you push on the stack? (Hint: clone)

Now write the main method of MazeSolver to have the form

public class MazeSolver
{
   public static void main(String[] args)
   {
      Maze maze = new Maze(...);
      Robot fred = new Robot(maze, 5, 8);
      Stack<???> stk = new Stack<>();
      stk.push(???)
      while (...)
      {
         ??? = stk.pop();
         // At exit? Print getVisited()
         
         for (int i = 0; i < 4; i++)
         {
            turnRight();
            if (...can move...)
            {
               // Clone the robot
               // Make the clone move 
               stk.push(???)
            }
         }
      }
   }
}

What is your code?

What happens when you escape from the maze with cycles in Lab 4 step B4?
Add another exit to the maze so that there are two ways out. What does your program do?