8 Placement 3

8.1 Language

For the following assignment, you must use Racket’s Beginning Student with List Abbreviations language. Go to the Language menu, select Choose Language, and pick the language from the Teaching Languages section.

8.2 Library

In Placement 2 you defined the function is-in?. This is built into Racket with the name member. You may use member from now on. Note that member uses equal? to perform its comparisons.

We will also be using characters, which are the atomic elements of strings. Characters are written with a #\ prefix: e.g., #\c, #\s. You can turn strings into lists of characters and vice versa using string->list and vice versa with list->string.

From now on, for the rest of the placement and the course: in every assignment, you can use any functions defined in that and any previous assignment, as well as libraries permitted in that and previous assignments, unless indicated otherwise—but no other. There may well be built-in functions that do exactly what the assignment asks for, but unless the assignment is expressly about your ability to search, we want you to demonstrate to us that you can write it with the resources we’ve asked you to use.

Some functions in this assignment would benefit from creating a helper function to handle a complex sub-task.

8.3 Reading

Read Part 2 of HtDP 2/e, specifically chapter 10.1. You can read past it if you feel the need as you’re doing the assignment.

If you find something unfamiliar, recall that we skipped reading Part 1 so you may need to peek in there to look up something.

8.4 Task

Define the following functions.

• elim-contains-char :: Char List-of-strings -> List-of-strings

  Consumes a list of strings and produces a list of the same words, in the same order, excluding those strings that contain the given character.

• valid-words :: List-of-strings List-of-chars -> List-of-strings

  Consumes a list of words (represented as strings) and a list of letters (represented as characters). Produces the list of same words, in the same order, that contain only those letters. (Imagine a game where you have to assemble words with just the letters you have.)

  For this assignment, ignore multiplicity: i.e., a word may contain more instances of a letter than the number of times the letter was present in the second parameter. Also, letters should be case-sensitive (e.g., #\A does not appear in "cat").

• unique :: List-of-any -> List-of-any

  Given a list of values, produces a list of the same values in the same order excluding duplicates. If a value is present more than once, its first instance stays and the remainder are discarded. Use equal? for comparison.

• l33t :: List-of-strings -> List-of-strings

  Consumes a list of words (represented as strings) and produces a list of the same words, in the same order, but where some of the letters have been replaced by characters that stand for numbers. Specifically, it turns #\A and #\a into #\4,Note that #\4 is a character, whereas 4 is a number. You can’t do arithmetic on the former or put the latter in a string. #\E and #\e into #\3, #\I and #\i into #\1, and #\O and #\o into #\0.

  Note: The first letter of the function name we are asking for is the letter ‘l’ (Lima), not the number ‘1’ (One). It’s pronounced “leet” and is favored in basements worldwide. If you spell it incorrectly, the grading software will not give you any credit!

• strip-vowels :: List-of-strings -> List-of-strings

  Consumes a list of words (represented as strings) and produces the same list of words, except with each vowel (#\a, #\e, #\i, #\o, or #\u, or their upper-case equivalents) removed. (If a word consists of all vowels, it reduces to the empty string but is not removed entirely.)

  Note: Be careful. There’s a simple, clean decomposition of tasks in this problem, but if you rush you may end up with a mess.

• singles :: List-of-numbers -> List-of-numbers

  Consumes a list of numbers and produces the same list, but where any “run” of numbers (i.e., consecutive numbers that are identical) is replaced by a single occurrence of that number. For instance, the list (cons 1 (cons 2 (cons 2 (cons 4 empty)))) would be transformed into (cons 1 (cons 2 (cons 4 empty))).

8.5 Grading Standards

From this assignment onward, for the rest of the placement and the course, you will be graded on both the quality and correctness of your code and on the quality and correctness of your tests. Both are important. If you didn’t pay enough attention to writing tests earlier, you should certainly start doing so now.

8.6 How We Test Tests

It’s probably useful for you to understand how we test your tests.

What’s the job of a test suite (i.e., set of tests)? It’s to find errors in a program. (Examples help you understand the problem before you start writing code, tests help you catch errors in the program as and after you write it.) In short, test suites are like sorting hats, putting programs in a “good” or “bad” bin.If you are a mathy person, you might call a test suite a classifier.

So here’s how we will test your test suites. We construct a collection of implementations for the problem. One is known to be correct (because we built it that way); we call this a wheat. The rest are known to be incorrect (because we intentionally introduced errors); we call each of these a chaff. Your test suite’s job is to separate the wheat from the chaff (if you haven’t seen that phrase before, read up). That is, we will run the wheat and each of the chaffs against your test suite and see what happens:This table is not strictly correct. During the semester, we’ll see that a correct wheat may fail for a very interesting reason. But that won’t happen during summer placement.

The quality of your test suite is then a measure of whether you passed the wheat and how many chaffs you caught. Of course, we can make the latter arbitrarily hard. For instance, we could define a chaff that always works correctly except when the given list has, say, exactly 1729 elements. We won’t do things like that, both because it’s cruel and because real implementations are very rarely buggy in this way. Instead, we will make “reasonable” mistakes (but not all of them will be easy!).

In short, we will be running your test suite against our implementation. Therefore, it is very important that when you turn in your test suite (see details below), it not be accompanied by your implementation: otherwise, when we try to load ours, DrRacket will complain.

8.7 Turnin

From now on, for the rest of placement and most of the semester, you will turn in multiple files.

One file, named p3-code.rkt, contains the five functions named above (it can contain any other helper definitions you like as well). The functions must be named exactly as above and must take parameters exactly as above.

In addition, make a copy of just the test cases for each of the required functions and put them in distinct files, named as follows:

Failure to follow any of these instructions may result in zero credit.

You will upload your work using Gradescope.