Assignment 1

Harvey Mudd College
Computer Science 60
Assignment 1, Due Monday, January 31, by 11:59pm

Making a Racket!

In this homework you will have the chance to hone your recursive-thinking skills using Racket, in which recursion is the primary form of computational control. Racket is considered a very "clean" language, very consistent, and with minimal syntax: few punctuation and formatting rules. (Some might argue it's too minimal!) Regardless, Racket is one of the best examples of a language whose focus is supporting computation itself, as opposed to intricate data structuring. In this assignment you'll implement some useful and some silly but fun functions to familiarize yourself with Racket's lists, strings, and characters, but most of all to re-familiarize yourself with recursion!

Pair and individual problems

This week, Part 1 should be in a file named hw1pr1.rkt and should be written by each person individually.

Part 2 may also be completed individually, but you are welcome -- and encouraged -- to work with a partner on those functions. If you do work in a pair, be sure to follow pair-programming practices as are detailed on the course syllabus. Either way, you should submit part two in a file named hw1pr2.rkt.

Design, testing, commenting, and formatting!

All of these are important! 25-30% of the assignment's points will be based on these. A few details:

Design matters! Be sure the use small helper functions to maintain a modular, "Racket-clean" style for your solutions.
Testing matters! Be sure to use our tests, as well as at least one -- and perhaps more -- of your own for all of your functions.
Include a top-of-function comment for all functions you write, including helper functions. Have a brief description of what the function does and the format/meaning of its inputs and output.
Include a top-of-file comment with your name(s), roughly how much time the assignment took, and any other comments you'd like to share with us or the grutors.
Comments are not necessary within function bodies, unless something tricky is going on. Particularly if you are writing many small functions (instead of fewer, larger ones), the top-of-function comment is most often enough.
Do format your code to make it easy to understand. Choose a formatting and indentation style that is clear and stick with it! Formatting also includes coding style: clean and clear structure, meaningful variable and function names, ample use of spacing, and indenting that reflects code structure.

Submitting your work

Be sure to submit your hw1pr1.rkt and hw1pr2.rkt files to the submission site! If you pair-programmed in the second part, you need only submit one file (but do be sure to indicate your partner).

The Problems

Part 1

Start with this hw1pr1.rkt starter file, which helps by having the function signatures and the provided test cases already in place... .

Remember that these functions should be done individually. As always, you can seek out help from instructors, grutors, and fellow students, but the work submitted should be your own.

Function 1: `remove-all`

In class, you saw how (remove e L) works: it returns a list identical to L, except with the first top-level instance of e removed. For this problem, write (remove-all, which should return a list identical to L, except that all top-level instances of e have been removed. For example,

(check-expect (remove-all "i" '("a" "l" "i" "i" "i" "e" "n")) '("a" "l" "e" "n"))
(check-expect (remove-all "i" '( ("a" "l" "i") "i" "i" "e" "n")) '(("a" "l" "i") "e" "n"))
(check-expect (remove-all 0 '(1 0 1 0 1 0))  '(1 1 1))

(Here we're using strings instead of symbols just to show that it will work either way... .)

Function 2: `prefix?`

Write the Racket function that begins

(define (prefix? P L)

in which P and L are both lists. Then, prefix? should output #t if and only if the list P is identical to the initial elements of the list L, i.e., P is the prefix of L. You should consider the empty list as a prefix of any list L.

Here are a couple of tests to help illustrate prefix?:

(check-expect (prefix? '() '(s p a m))   #t)
(check-expect (prefix? '(s p) '(s p a m))   #t)
(check-expect (prefix? '(s m) '(s p a m))   #f)
(check-expect (prefix? '(p a) '(s p a m))   #f)

Function 3: `sublist?`

Write the Racket function that begins

(define (sublist? S L)

in which S and L are both lists. Then, sublist? should output #t if and only if the list S is identical to the some set of consecutive elements of the list L, i.e., S is a sublist of L. You should consider the empty list to be a sublist of any list. However, no non-empty list is a sublist of the empty list.

Here are a couple of tests to help illustrate sublist?:

(check-expect (sublist? '() '(s p a m))   #t)
(check-expect (sublist? '(s p) '(s p a m))   #t)
(check-expect (sublist? '(s m) '(s p a m))   #f)
(check-expect (sublist? '(p a) '(s p a m))   #t)

Hint: use prefix? to do most of the work here!!

Run-time analysis: In a comment in your code, describe an example of a three-element list S and a six-element list L that require (sublist? S L) to do the most work (the most equality-comparisons). In other words, what inputs cause the largest number of equality-comparisons between elements to be made? Also, suppose that -- in general -- the inputs to sublist? are of length N and 2N, respectively. In this case, what is the resulting worst-case big-O running time of your sublist? function?

Function 4: `number`

Write the Racket function that begins

(define (number L)

in which L is a list. The output should be a list identical to L, except that each element from the original input is now the second element of a sequentially numbered list, starting from 0. These examples will help clarify this:

(check-expect (number '(jan feb mar apr)) '((0 jan) (1 feb) (2 mar) (3 apr)))
(check-expect (number '(0 I II III IV V VI)) '((0 0) (1 I) (2 II) (3 III) (4 IV) (5 V) (6 VI)))
(check-expect (number '())  '())

Hint: create a helper function with more arguments than number. Then, call the helper function with a reasonable default value!

Aside: Association lists, or "a-lists" for short, are always lists of lists. For example, the above function, number-each outputs association lists. Association lists are one way to store data values that can be looked up by a "key": here, the first element of each sublist is the key and the rest of each sublist is the corresponding value. We'll use association lists again in the scrabble-scoring functions, below.

Be sure to submit hw1pr1.rkt at the submissions site!

Part 2

For this part, start a new Racket file, named hw1pr2.rkt. Be sure to include a top-of-file-comment after the set-up lines:

#lang racket
(require htdp/testing)

Remember that these functions may be done individually or in a pair... .

Function 5: `subbag?`

Write the Racket function that begins

(define (subbag? S B)

in which S and B are both lists. Then, subbag? should output #t if and only if the list B contains all of the elements in S in quantities at least as large. In contrast to sublist?, however, the order of the elements makes no difference. So, if S contains three 42's, then B would have to contain at least three 42's in order for S to be a subbag of B. (By the way, a bag is a methematical term for a set in which there may be more than one of the same kind of element.)

Here are a couple of tests to help illustrate subbag?:

(check-expect (subbag? '() '(s p a m s))   #t)
(check-expect (subbag? '(s s) '(s p a m s))   #t)
(check-expect (subbag? '(s m) '(s p a m s))   #t)
(check-expect (subbag? '(p a) '(s p a m s))   #t)
(check-expect (subbag? '(a m a) '(s p a m s))   #f)

Function 6: `superreverse`

Write a function that begins

(define (superreverse L)

superreverse will be a variant of reverse. Its input L will be a list that will only contain lists as elements. superreverse should output a list identical to L, except that all of its top-level lists should be reversed. No deeper structures should be altered. You may (and should!) use the built-in reverse function in your implementation of superreverse.

Here are two examples. In the first, we use Racket's single-character datatype, just to emphasize that it differs from both symbols 'symbol and strings "string".

(check-expect (superreverse '( (1 2 3) (4 5 6) (#\k #\o #\o #\l) (#\a #\m) ))
    '( (3 2 1) (6 5 4) (#\l #\o #\o #\k) (#\m #\a) ) )
(check-expect (superreverse '( (1 2 3) (4 5 6 (7 8) 9 ) ))
    '( (3 2 1) (9 (7 8) 6 5 4) ) )

Function 7: `duperreverse`

Next, define a function

(define (duperreverse L)

which returns a list whose structure is a complete reversal of L's. Note that L does not need to have only lists as elements!

(check-expect (duperreverse '( (1 2 3) (4 5 6) 42 ("k" "o" "o" "l") ("a" "m") ))
    '(  ("m" "a") ("l" "o" "o" "k") 42 (6 5 4) (3 2 1) ) )
(check-expect (duperreverse '( (1 2 3) (4 5 6 (7 8) 9 ) ))
    '( (9 (8 7) 6 5 4) (3 2 1) ) )

Remember that you can use the Racket predicate (list? x) to determine whether or not x is a list! You might use the memAny example from class as a guide... .

Problem 8: `tail-fib`

Write a tail-recursive function

(define (tail-fib N)

that takes in a nonnegative integer N and outputs the Nth fibonacci number. The fibonacci numbers are the series that begins 1 1 and then forms each subsequent element by adding the last two:

Fibonacci numbers:  1 1 2 3 5 8 13 21 ...
Their indices, N:   0 1 2 3 4 5  6  7 ...   (for this problem)

For the purposes of this problem, the initial Fibonacci number will correspond to an input N of 0. As a refrence, here is a non-tail-recursive version of fib:

(define (fib N)
  (if (< N 2)
      1
      (+ (fib (- N 1)) (fib (- N 2)))
    ))

Here is an example test for tail-fib:

(check-expect (tail-fib 8)  34)

Note that the class's examples called the helper function tail-range, tail-power, etc. Here, we're using tail-fib as the name of the 1-input function. (I guess you'll get to choose a more creative helper-function name!)

Hint! For tail-fib it will be simplest to create a helper function that has two accumulator arguments! You might start them out at 1 and 1... .

In a comment near your tail-fib, estimate the big-O running time of (tail-fib N) in terms of N, the value of the input.

Using the built-in time function, include a comment that tells the smallest value of N for which (time (tail-fib N)) takes over 1 second to run, using the first output number that time provides. You can round N to the nearest thousand, if you like. Also, indicate the smallest value of N for which (time (fib N)) takes over 1 second of time to run. (But this latter one should be the exact value of N: it'll be much smaller)

The cpu-time is the first value that time reports, in milliseconds. In order to avoid seeing the (possible very large) value that is returned by the function call, you can use the following to do your timing:

(begin (time (tail-fib 50000)) '())

In Racket, begin simply returns the last one of the expressions it's given as input. But all the printing is still done along the way, so you'll see the results of time.

Function 9: `tail-reverse`

Write a tail-recursive Racket function

(define (tail-reverse L)

that takes in a list L and returns the reverse of that list. For example,

(check-expect (tail-reverse '(6 7 1 2))  '(2 1 7 6))

In a comment near this function, estimate the big-O runtime of your tail-reverse and of the "ordinary" (non-tail-recursive) reverse here:

(define (reverse L)
  (if (null? L)
      '()
      (append (reverse (rest L)) (list (first L)))
      ))

In analyzing this "ordinary" reverse, use the fact that append runs in time O(N), where N is the length of the first input to append. (This is counting cons.)

Problem 10: Scrabble!

Overview: This problem asks you to implement a set of Racket functions that computes the highest-scoring (or "best") Scrabble word, given a particular rack of letters rack and a list of legal words WL. Here would be the definition line:

(define (best-word rack WL) ;; rack is a string; WL is a list of strings

The output of best-word should be a two-element list in which the first element is the best word and the second element is the score of that best word. If there are ties, best-word may return any one of the best.

Here are a few examples:

(check-expect (best-word "academy" '("ace" "ade" "cad" "cay" "day"))  '("cay" 8))
(check-expect (best-word "appler" (list "peal" "peel" "ape" "paper")) '("paper" 9))
(check-expect (best-word "paler" (list "peal" "peel" "ape" "paper"))  '("peal" 6))

Note that "paper" could not be made in the third example, because the rack had only a single #\p.
In general, there may be more than one best-scoring word -- in that case, we will make sure to run tests similar to the following:

(check-expect (second (best-word "bcademy" '("ace" "ade" "cad" "cay" "bay"))) 8)

In this case, either "cay" or "bay" would produce that best score.

You're welcome to design this best-word function completely on your own. You should, however, make sure that you decompose this computation into a number of small, helper functions. Below are some details that will help with the set-up and will suggest at least some pieces that could help with best-word.

In this problem we will use an association-list to score information about scrabble tiles. The following Scheme statement defines an association-list that provides all of the letter scores. It also includes the number of times each tile appears in an official Scrabble set -- this is only for the optional extra-credit problem. You should copy this code into your hw1pr2.rkt file:

;; scrabble-tile-bag  
;;   letter tile scores and counts from the game of Scrabble
;;   the counts aren't needed (until the ex. cr.) they're obtained from
;;   http://en.wikipedia.org/wiki/Image:Scrabble_tiles_en.jpg
;;
(define scrabble-tile-bag
  '((#\a 1 9) (#\b 3 2) (#\c 3 2) (#\d 2 4) (#\e 1 12)
   (#\f 4 2) (#\g 2 3) (#\h 4 2) (#\i 1 9) (#\j 8 1)
   (#\k 5 1) (#\l 1 4) (#\m 3 2) (#\n 1 6) (#\o 1 8)
   (#\p 3 2) (#\q 10 1)(#\r 1 6) (#\s 1 4) (#\t 1 6)
   (#\u 1 4) (#\v 4 2) (#\w 4 2) (#\x 8 1) (#\y 4 2)
   (#\z 10 1) (#\_ 0 2)) ) 
;; end define scrabble-tile-bag
;;
;; The underscore will be used to represent a blank tile, which is a wild-card

The notation #\a is Scheme's way of representing single-character literals.

The function (assoc e A) takes in an association-list A (remember that A contains lists of lists) and returns the element of A whose own first element is equal to e. For example:

   (assoc 3 '((0 jan) (1 feb) (2 mar) (3 apr)))   ==>  (3 apr)
   (assoc 5 '((1 jan) (2 feb) (3 mar) (4 apr)))   ==>  #f

As the second example shows, assoc returns #f when e does not appear as a first element of any of A's sublists. This assoc function will help look up letters and their scores.

score-letter As a possible helper function, you might construct a function named score-letter that determines the score for its argument, which will be a character. Use assoc. For example,

(check-expect (score-letter '#\w) 4)

score-word As another possible helper, you might construct a function score-word that determines the score for a string of letters. Note that strings in Scheme are not the same as symbols, nor are characters the same as strings (as they are in Python). Strings are doubly quoted. The built-in functions string->list and list->string, which convert from strings to lists of characters and vice-versa, may be of use. Here are examples of them in action:

(check-expect (string->list "hi") '(#\h #\i))
(check-expect (list->string '(#\h #\i)) "hi")

Here are three tests of score-word:

(check-expect (score-word "zzz")  30)
(check-expect (score-word "fortytwo") 17)
(check-epxect (score-word "twelve")  12)

Other hints Be sure to plan out your strategy for this problem before diving in to the coding! In our solution, we used the subbag? predicate from earlier in this assignment... .

Be sure to submit hw1pr2.rkt at the submission site.

Optional extra-credit challenges...

For totally optional extra credit of up to 8 points each, include the following functions in your hw1pr2.rkt file.

Extra-credit function 1: `hard-scrabble`

For this extra-credit problem, implement a more realistic version of best-word, named hard-scrabble:

(define (hard-scrabble rack WL)

As with best-word, hard-scrabble should return a 2-element list including the best makable word and its score. In this case, however, it should allow the use of wild-card "blank" characters, which can act as any letter, and it should check that the rack does not have more of a particular letter than are available in the game! We will use #\_, the underscore character, to represent the blank. If the rack is impossible, the output should be '("no cheating!" 0). The blanks do not have to appear in the output word, but they should be accounted for.

(check-expect (hard-scrabble "iazby_q" '("biz" "jazz" "qi" "quiz"))
              '("quiz" 21)) ; 
(check-expect (hard-scrabble "iazzjaq" '("biz" "jazz" "qi" "quiz"))
              '("no cheating! 0))

Extra-credit function 2: `reachable?`

For this extra-credit problem, we will use an association list as a graph, a general-purpose representation of relationships by connectivity. For example, the association list

(define Graph1 '(  (a b) (b c) (c d) (d e) (e c) ))

would represent this graph:

In particular, this challenge is to implement the predicate reachable?:

(define (reachable? x y G)

in which x and y are nodes in the graph, G. Then, reachable? should return #t if there is a path, perhaps through some number of intermediate nodes, from node x to node y within graph G. If there is no such path from x to y, the predicate reachable? should return #f. We consider any node reachable from itself, even if it's not in the graph.

Here are a couple of examples that use Graph1:

(check-expect (reachable? 'a 'a Graph1)  #t)
(check-expect (reachable? 'z 'z Graph1)  #t)
(check-expect (reachable? 'a 'b Graph1)  #t)
(check-expect (reachable? 'a 'e Graph1)  #t)
(check-expect (reachable? 'e 'd Graph1)  #t)
(check-expect (reachable? ''e 'a Graph1)  #f)

Harvey Mudd College Computer Science 60 Assignment 1, Due Monday, January 31, by 11:59pm

Making a Racket!

Pair and individual problems

Design, testing, commenting, and formatting!

Submitting your work

The Problems

Part 1

Function 1: remove-all

Function 2: prefix?

Function 3: sublist?

Function 4: number

Part 2

Function 5: subbag?

Function 6: superreverse

Function 7: duperreverse

Problem 8: tail-fib

Function 9: tail-reverse

Problem 10: Scrabble!

Optional extra-credit challenges...

Extra-credit function 1: hard-scrabble

Extra-credit function 2: reachable?

Harvey Mudd College
Computer Science 60
Assignment 1, Due Monday, January 31, by 11:59pm

Function 1: `remove-all`

Function 2: `prefix?`

Function 3: `sublist?`

Function 4: `number`

Function 5: `subbag?`

Function 6: `superreverse`

Function 7: `duperreverse`

Problem 8: `tail-fib`

Function 9: `tail-reverse`

Extra-credit function 1: `hard-scrabble`

Extra-credit function 2: `reachable?`