1 What is This Assignment’s Purpose?🔗

This assignment gives you experience working with a “combinatorial” problem: one where there are lots of combinations of to wrestle with. It also gives you a well-defined task but without any hint on how to solve it. Finally, it asks you to wrestle with making a solution faster.

2 Theme Song🔗

Call Me Maybe by Carly Rae Jepsen

3 Background🔗

When people pay for each phone call they make, a “toll-free” number is one where the callee, rather than the caller, pays. In the USA, these phone numbers were originally given the “area” code 800, and hence are sometimes called “800 numbers”.

As these became widespread, it became common for entities to get “memorable” numbers, often called “vanity numbers”.This is similar to trying to grab a memorable domain name, memorable email address, OG user handle, etc. These are numbers that correspond to one or more meaningful words, sometimes also called phonewords.

4 Assignment🔗

We provide you a dictionary of words. You are welcome to use smaller dictionaries for testing purposes, but please use only this dictionary in your final program/submission/reporting, so that we can compare answers.

This list of words is copied from the Education First Web site. You may be a bit surprised by some “words” there…

We will assume the standard US phonepad, which maps 2 through 9 to sets of letters but doesn’t map 0 or 1.

Your job is to find all the “vanity numbers” of a given digit length, and for each number, the set of all word sequences that “spell out” that number. For instance, given the number 276, we can construct it in the above dictionary as ARM, A-SO, and A-PM. Note that this assignment doesn’t require the word combinations to be “meaningful”; to us, AS-A-A-AIR is a legal 7-digit vanity number (and might be meaningful in some setting!).

The input is the number of digits. Because this is a combinatorial problem, at least your early solutions may take quite a while; debugging and testing on small values will make this task more tolerable. (As a hint: for size 3, we find 212 different numbers. This is the total number of sequences that can be formed from 3 digits, not the number of unique 3 digit numerical sequences.)

In the output, the keys of the dictionary are numbers represented as strings (e.g., 276 would be represented as "276"); their length must be the same as the number provided to words-for. The keys map to a set of strings like [set: “arm”, “a-so”, “a-pm”], with the words in multi-word solutions separated by “-”es. While it’s conventional to write vanity numbers in upper-case, all the words in the dictionary are in lower-case, and you should leave them that way.

Your ultimate task is to make words-for run as fast as you possibly can. You should be able to come up with a clean, correct, but slow solution based on what you know. We want you to then work on optimizing it to the extent you can. As you do this, consider having the correct-but-slow version to test against!

We expect you to have done at least three variants: an “obvious” but potentially very slow first implementation, and two attempts to improve it (either two separate ones or one on top of the other). You should also consider other algorithmic strategies for maximum exploration. You never know which approach will work best until you’ve tried it!

Ultimately, we want you to keep track of everything you’ve tried. We want you to turn in [Handing In] a “lab notebook” of your experiments: what did you start with, what did you try, why did you try it, and what was the outcome. Rinse and repeat…

5 Language Use🔗

You can use any libraries you have used this semester. You can also use any functions you have written; when you do, please credit the earlier assignment solution. You are also welcome to use any code from the textbook; again, credit it.

Do note that you are still required to produce clean, readable code to the extent possible. The only exceptions would be if not doing so enabled you to obtain a notable speedup; that should then be clear from your lab journal.

You do not have to use mutation. If you do, document in your lab journal why and how you used it, what impact you thought it would have, and what impact it actually had.

You will want to use the Pyret timing library.

6 Starter🔗

Template

7 Handing In🔗