Assignment 1

Harvey Mudd College
Computer Science 60
Assignment 1, Due Tuesday, September 16, by 11:59pm

Link to the CS submission site
Back to the top-level assignments page
Back to the top-level CS 60 page

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.

In addition, a small part of this homework (8 points) asks you to complete a few functions in the Java programming language. Informally, this gives at least a brief respite from parentheses! More seriously, Java's syntax is much more complex than Racket's; we will spend the next few weeks doing just a little bit of getting used to Java each week with a little help from the wonderful CodingBat website. See the end of this assignment for details.

Now, back to Racket...

In contrast to Java, 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.

Part 3 may be completed with a partner, but if you do so - switch who is using the keyboard and mouse after each function instead of every 30 minutes.

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. As always we want you to write these functions BEFORE you write the code!
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 submission site ID (your login), 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. Here is an example of a suitably commented function: ;; problem 0 ;; len ;; inputs: L, a list of any items ;; output: the number of top-level items in the input list (define (len L) (if (null? L) 0 (+ 1 (len (rest L)))))

Submitting your work

Be sure to submit your hw1pr1.rkt, hw1pr2.rkt and Hw1pr3.java files to the submission site! If you pair-programmed you should both still submit all of the files, but also indicate the login of your partner (e.g. CS60XX).

Reminder - your assignments will be graded anonymously and you should not include your name anywhere in your submitted files.

The Problems

Part 1 (36 points)

Start with this hw1pr1.rkt starter file, which helps by having the function signatures and the provided test cases already in place... . Here it is in .txt format, in case this one is simpler to copy or download.

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))

Remember to write SIMPLE test cases to test your function before you write your code! It should help in planning and writing your code. You should write your own test cases for all of the functions in this assignment. Sometimes you'll need to write new SIMPLE test cases, sometimes you'll need to write more complex test cases.

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!!

Function 4: `enumerate`

Write the Racket function that begins

(define (enumerate 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 (enumerate '(jan feb mar apr)) '((0 jan) (1 feb) (2 mar) (3 apr)))
(check-expect (enumerate '(0 I II III IV V VI)) '((0 0) (1 I) (2 II) (3 III) (4 IV) (5 V) (6 VI)))
(check-expect (enumerate '())  '())

Hint: create a helper function with more arguments than enumerate. 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, enumerate 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 (56 points)

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... .

Also, as always, feel free to include helper functions of your own or from our class examples... .

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 mathematical 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? '(a p) '(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!

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 reference, 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)

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 or at 1 and 0... .

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))

Note that you'll need a helper function with an additional accumulator input that will do most of the work! Also, don't use Racket's reverse within tail-reverse or your helper function!

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))
(check-expect (best-word "kwyjibo" '("ace" "ade" "cad" "cay" "day"))  '("" 0))
;; Do you recognized "kwyjibo"? http://www.hulu.com/watch/29524

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 Racket statement defines an association-list that provides all of the letter scores. (Note: 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 Racket'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 Racket 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-expect (score-word "twelve")  12)

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

If you want to use any definitions from hw1pr1.rkt, you can copy / paste them into hw1pr2.rkt. This practice is not very good for software engineering (what happens if you need to change your definition of subbag??), but doing so makes it possible to grade each file separately.

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

Part 3 (CS60 Required, CS42 Optional)

Getting familiar with Java syntax (8 points)

This problem will introduce you to the Java programming language -- ot, at least, its syntax. We will consider Java's "object-oriented" design and the capabilities that make it a popular industry/enterprise language later on in CS 60.

One of CS 60's goals is that you will feel confident that you can use any new computational language effectively and efficiently -- all you'll need is a syntax reference. This problem practices exactly that skill using problems from a site named CodingBat, which has many small one-function challenges and some succinct references.

For this problem, you should... (Steps also shown in CS60 Lecture and in this video)

Download Eclipse, a programming environment for Java

You should install "Eclipse IDE for Java Developers
You can click on the link for your operating system under the header on the right "Download Links"
You might want to watch this video about getting set-up with Eclipse

Right click under "Package Explorer" to create a new Java project named "CodingBat"
Right click on your "CodingBat" project - select "New Java Class" and name it: Hw1pr3
Copy the code from Hw1pr3.java into your file with the same name
Right click on your "CodingBat" project - select "New Java Class" and name it: Hw1pr3Test
Copy the code from Hw1pr3Test.java into your file with the same name
Write the functions in the file Hw1pr3.java and test them by running the file Hw1pr3Test.java by clicking on the green Run button

If you get stuck! Go to the link showing the "Source" of that problem and click on the "Show Solution" button in CodingBat. This will give you the correct answer!! Except that our solutions have the word static in the signature line. You'll need to add that to the solution if you use it. We ask you give an earnest try for each of these problems. If you need to use the solutions after trying to answer the question on your own, you are free to do so - but if you do, we ask you to include a comment in your code for that function explaining what facet of the problem you hadn't fully understood before using the solution. After all, the goal is that you become comfortable with Java and its syntax - articulating what was new or surprising in a comment will do just that!

For example, imagine we had needed to look at CodingBat's solution to the sleepIn problem, above. In that case we could have used that solution as long as we included a comment such as the one below. Multi-line comments in Java are delimited by /* at the start and */ at the end:

/*

 I used the answers here because I didn't know that || means "or"
 in Java and that ! means "not" in Java.

 */
public boolean sleepIn(boolean weekday, boolean vacation) 
{
  if (!weekday || vacation) 
  {
    return true;
  } 
  else 
  {
    return false;
  }
}

Each one of these seven functions - plus the sleepIn function - is worth one point. These are the final 8 points of this hw1 assignment.

Be sure to submit Hw1pr3.java at the submissions site!

Good luck diving into Java!

Optional extra-credit challenges...

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

Racket 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))

Racket 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 Tuesday, September 16, by 11:59pm

Making a Racket!

Pair and individual problems

Design, testing, commenting, and formatting!

Submitting your work

The Problems

Part 1 (36 points)

Function 1: remove-all

Function 2: prefix?

Function 3: sublist?

Function 4: enumerate

Part 2 (56 points)

Function 5: subbag?

Function 6: superreverse

Function 7: duperreverse

Problem 8: tail-fib

Function 9: tail-reverse

Problem 10: Scrabble!

Part 3 (CS60 Required, CS42 Optional)

Getting familiar with Java syntax (8 points)

Optional extra-credit challenges...

Racket Extra-credit function 1: hard-scrabble

Racket Extra-credit function 2: reachable?

Harvey Mudd College
Computer Science 60
Assignment 1, Due Tuesday, September 16, by 11:59pm

Function 1: `remove-all`

Function 2: `prefix?`

Function 3: `sublist?`

Function 4: `enumerate`

Function 5: `subbag?`

Function 6: `superreverse`

Function 7: `duperreverse`

Problem 8: `tail-fib`

Function 9: `tail-reverse`

Racket Extra-credit function 1: `hard-scrabble`

Racket Extra-credit function 2: `reachable?`