CS152

Homework 4

You will again use the sbt project structure

cs152 (or whereever you store your git repo)
  hw4
    src
      main
        scala
          hw4.scala (in the default package)
      test
        scala
          MyTestSuite.scala (in the default package)

All your work goes inside an

object hw4 {
  ...
}

in hw4.scala.

In the test cases given below, I don't use the hw4. prefix because my test suite starts with

import hw4._

To test that the grader will be able to run your project, clone your repo into /tmp/cs152, change to the hw4 directory, and run sbt test.

IMPORTANT: Be sure to edit your .gitignore file so that you don't upload a lot of unnecessary stuff into your repo! See the instructions for homework 3.

Reimplement the tokens function from Lecture 7 Lab Step 4. First, accept two lists of regex, the tokens that should be reported and those that should be ignored. (The latter would contain white space and comments). Next, return a pair consisting of a list of tokens that you found and an integer that indicates the index of the first error—the position in the original string where you were unable to find a match. If the entire input string matched, return -1.
Martin Odersky, the inventor of Scala likes to show off the power of Scala and functional programming with a solution of the “phone mnemonics” problem. Given a phone number, what word or word sequence spells it on a touch-tone pad? For example, given the phone number 435 569 6753, one should come up with the sequence HELLO WORLD (and maybe others).

We'll do this in a different way than he does it in his presentations. I present this as a set of discoveries. Follow along in a worksheet, then put your work together into the final deliverable, a function val phoneMnemonics = (digits: String) => ... that yields a List[String]. Note that we will use NO RECURSION. That's why all the functions are written as val.

And no constructs that we haven't covered in class. No for/yield. (Use map and flatmap instead.) No macros :-)

You don't have to turn in the answers to the various questions in the following description—just the phoneMnemonics function and the various helper functions.
1. What interesting word can you make from the number 72252? If you can't figure one out, it's ok—your program will do it for you soon enough.
2. Declare a map that maps "2" to "ABC", "3" to "DEF", and so on.
3. Actually, we want "2" to map to a List with three elements, "A", "B", "C". But we don't want to type all that by hand. Here is a handy function that turns a string into a list of its characters:
```
val characters = (s: String) => s.toList.map("" + _)
   // In Scala, a String is a Seq[Char]
```
  Transform your map by adding
```
.map(e => (e._1, characters(e._2)))
```
  Call the result letters—we'll need it in the next step.
4. Now it's trivial to find out the words that one can make with one digit, say "2". It's just letters("2"). What if you have two digits, say "2" followed by "3"? Then you want to combine all elements of letters("2") with all elements of letters("3"). That's similar to the flatMap example in Lecture 6:
```
letters("3").flatMap(y => letters("2").map(x => x + y))
```
  Try it out and see what you get. Think about why the list order is switched.
5. It is useful to write a function that solves a more general problem. Given two lists of strings, get a list of all concatenations from both of them.
```
val cats = (s: List[String], t: List[String]) => ...
```
  Implement this function.
  Test case:
```
assert(cats(letters("2"), letters("3")).toSet
  == Set("AD", "BD", "CD", "AE", "BE", "CE", "AF", "BF", "CF"))
```
6. Now write a function wordsForDigits that takes a string of digits between "2" and "9" and produces all strings that they can encode.
```
val wordsForDigits = (digits: String) => ...
```
  Hint: First map to a list of strings for each digit. Then use reduceLeft.
  Test case: assert(wordsForDigits("72252").contains("SCALA"))
7. Read in all words from /usr/share/dict/words, as we did in Lecture 6. And remove those that start with an uppercase letter (which include a bunch of junk) as well as those of length 1. Turn it into a set for efficiency. And let's make them all uppercase. And let's add in "SCALA" which is weirdly missing.
```
val words = io.Source.fromURL("http://horstmann.com/sjsu/spring2018/cs152/words").
  getLines.filter(w => Character.isLowerCase(w(0)) && w.length > 1).
  map(_.toUpperCase).toSet + "SCALA"
```
  Then improve the wordsForDigits function from the preceding step by filtering against the set.
8. Now when you run wordsForDigits("72252"), what do you get? What do you get for wordsForDigits("72253")?
9. We've made a lot of progress, but we aren't quite there. The problem is a little harder. Given an arbitrary number like 7225247386, one is supposed to find the words "SCALA", "IS", "FUN" (and whatever other word sequences there might be hidden).
  
  Let's assume we have a particular way of breaking up the numbers, say into List("72252", "47", "386"). Using wordsForDigits, we get all the words for "72252", "47", and "386". Now we want to concatenate them into a sentence.
  
  We've almost solved that problem before, when wordsForDigits called reduce with cats to glue together words. Give it a try:
```
val wordsForDigitsSequence = (seq: List[String]) =>
  seq.map(e => wordsForDigits(e)).reduceLeft(cats)
```
  What do you get for wordsForDigitsSequence(List("72252", "47", "386"))?
10. It would be easier to read the result if the words were separated by spaces. Make a copy of cats, call it catsSpaces, and make it separate the concatenated words by spaces. Then call catsSpaces instead of cats in wordsForDigitsSequence. What do you now get for wordsForDigitsSequence(List("72252", "47", "386"))?
11. We are doing good. If we know how to break up a number (such as 7225247386) into all corresponding sequences (such as 72252 47 386 and many others), then we can find the corresponding words for each sequence.
  
  Let's find all ways that a phone number can be broken up into (non-empty) sequences. For example, the phone number 1234 has 8 such decompositions: 1234, 12 34, 1 234, 1 2 34, 123 4, 12 3 4, 1 23 4, 1 2 3 4.
  
  That looks pretty random, but it's not so bad. Suppose you knew how to break up 234 (into 234, 23 4, 2 34, 2 3 4). Now you grow that by adding 1. There are two things you can do:
  - Add 1 all by itself: 1 234, 1 23 4, 1 2 34, 1 2 3 4
  - Add 1 to the first string: 1234, 123 4, 12 34, 12 3 4
  Let's do the first part.
```
val grow1 = (c: String, substringLists: List[List[String]]) => substrings.map(...)
```
  For each list s in substringLists, you prepend c (with ::) the sequence List(t.toString).
  
  What do you get for
```
grow1("1", List(List("234"),
  List("23", "4"),
  List("2", "34"),
  List("2", "3", "4")))
```
12. On to grow2. There are two inputs: a string c with a single character such as "1", and a List[List[String]] such as List(List("234"), List("23", "4"), List("2", "34"), List("2", "3", "4")). Glue the character to the front of the first element of each list s in substringLists.
```
val grow2 = (c: String, substringLists: List[List[String]]) => map(...)
```
  What do you get for
```
grow2("1", List(List("234"),
  List("23", "4"),
  List("2", "34"),
  List("2", "3", "4")))
```
13. Now define
```
val grow = (c: String, a: List[List[String]]) => ...
```
  to concatenate grow1(c, a) and grow2(c, a) (with ++).
  
  Now you should get all expected patterns from
```
grow("1", List(List("234"),
  List("23", "4"),
  List("2", "34"),
  List("2", "3", "4")))
```
14. What is the result of
```
grow("1", grow("2", grow("3", List(List("4")))))
```
15. This looks so promising. But why can't you use grow with reduceRight?
16. Ok, we'll use foldRight instead. And we want this to work for arbitrary strings s, not just "1234". Apply foldRight to the list characters(s.substring(0, s.length - 1)). What is the seed value?
17. Implement val substrings = (s: String) => .... What is substrings("2728")?
18. Note that's a list of List[String]. What do you get when you call
```
substrings("2728").map(wordsForDigitsSequence)
```
19. Ok, that's not quite what we want. We don't want lists of lists. How do you flatten them out? (Don't change substrings—just figure out what you need to do with its result.)
20. Now implement val phoneMnemonics = (digits: String) => ... that does this for any string of digits, not just "2728". What is phoneMnemonics("7225247386")?
21. Pheew! You are done. Look, ma, no recursion. Scala is fun.
22. Important: You won't get any partial credit if the test suite can't compile. If you can't get everything done, make sure you define the remaining functions. All of them happen to return lists, so define any unimplemented functions to return empty lists:
```
  val wordsForDigits = (digits: String) => Nil
  val catsSpaces = (s: List[String], t: List[String]) => Nil
  val wordsForDigitsSequence = (seq: List[String]) => Nil
  val grow = (c: String, a: List[List[String]]) => Nil
  val substrings = (s: String) => Nil
  val phoneMnemonics = (digits: String) => Nil
```