This assignment has two parts.
In the first part, This problem asks you to write several Racket functions: together, they will implement a "unit-calculator" or unicalc application. A complete application will be able to convert any unit quantity to any compatible quantity by using an association list as a database of known conversions.
The second part gives you practice with Racket's higher-order functions (those that take other functions as inputs or yield them as outputs) and with tail recursion.For this assignment, you should type (and test!) your programs in two files:
You should submit your files in the usual way at the CS 42 Submission Site.
Keep in mind
that you may submit multple times -- only the final submission before
the deadline will be graded.
As with assignment 1, design, formatting and testing will account for roughly a quarter of the credit for each function or program you complete. The commenting and code-formating guidelines carry over from homework #1. Here, however, there will also be consideration for algorithm design and modularity, especially in problem 1:
Be sure that you name your functions as specified in each problem --
this
helps enormously with the grading! Helper
functions may have any names appropriate for their operation.
unicalc.rkt -- The source file template.unicalc-db.rkt -- The
database of units (updated 2pm, Friday, September 9)unicalc-tests.rkt
(updated 4pm, Saturday September 10)This is the first part of a 3-part assignment. Unicalc is a calculator
that includes physical and other units, rather than just numbers.
Units are important to computation because they eliminate an
element sometimes left to human interpretation. In the area of
engineering, failure to interpret numbers without their units specified
has been known to lead to failure of space missions for example. In the wikipedia article about NASA’s Mars Climate Orbiter,
it is stated:
“The Mars Climate Orbiter was intended to enter orbit at an altitude of 140–150
km (460,000-500,000 ft.) above Mars. However, a navigation error caused the
spacecraft to reach as low as 57 km (190,000 ft.). The spacecraft was destroyed
by atmospheric stresses and friction at this low altitude. The navigation error
arose because a NASA subcontractor (Lockheed Martin) used Imperial units
(pound-seconds) instead of the metric system.”
A little closer to home, you will have to do many unit conversions and
operations in your other classes here at HMC. It is our hope
that this calculator will prove useful in those classes.
Ultimately, Unicalc will be a complete language, sort of like
Racket,
Java, or any programming language, though with a very specialized
function.
Over the next 3 weeks you will be writing
the back-end (or
Application Programming Interface--API), the evaluator and the parser.
This week you will begin by implementing the back-end functionality for
simple unit calculations. In doing so, you will be
implementing an API (Abstract Programming Interface), which is simply a
library of visible functions that others can use. In this
case, you will
be using those functions in the coming weeks when implementing your
language.
The API is a set of functions that you will construct, as described
below, along with other helper functions. To describe our functions, we
need a couple more definitions. A symbol that is defined in the
database (as the first element of an element of the association list)
is called a defined unit. A symbol that is not defined is called a
basic unit. Examples of defined units are: mile, day, pound. Examples
of basic units are: kg, second, meter. Defined units can be expanded
into equivalent Quantities consisting of only basic units in one or
more steps. (You can assume for now that there are no circular
definitions in the database.) Also, basic units can be converted into
quantities by making them the only element in the numerator list,
accompanied by a multiplier of 1 and an empty denominator list.
A Quantity is called normalized provided that the following two
conditions are true:
• The numerator and denominator consist of only basic units.
• The numerator and denominator are sorted in ascending
alphabetic order.
Note that the sort function takes two arguments: a list and a comparitor function of two
arguments. You might find the built-in Racket function string-ci<? useful here. Here are some examples of string-ci<? in action:
> (string-ci<? "aaaa" "zz")
#t
> (string-ci<? "fun!" "unicalc")
#t
> (string-ci<? "fun!" "dentist")
#f
We don’t require the user to provide normalized Quantities,
but it helps make processing more efficient if internally use only normalized quantities.
Here are the functions you need to provide in the API. Note that divide effectively achieves conversion from one kind of normalized Quantity to
another:
| Function Call Form | Meaning |
(normalize-unit
Unit) |
Returns a normalized Quantity corresponding to 1 in the given unit (where this Unit is a single unit such as 'mile or 'kg or 'second) |
(normalize
Quantity) |
Converts any Quantity to a normalized Quantity. |
(multiply
Quantity1 Quantity2) |
Multiplies two normalized Quantities, returning a normalized Quantity. |
(divide
Quantity1 Quantity2) |
Divides normalized Quantity1 by normalized Quantity2, returning a normalized Quantity. |
(add Quantity1 Quantity2) |
Adds normalized Quantity1 to normalized Quantity2, returning a normalized Quantity, provided the quantities are interconvertible. Returns (error "illegal add" Quantity1 Quantity2) value if not. |
(subtract
Quantity1 Quantity2) |
Subtracts normalized Quantity2 from normalized |
(power Quantity1 p) |
Raises normalized Quantity1 to the integer power p returning
a normalized Quantity. You may assume that p will be an integer
(though it may be positive, negative or 0). |
unicalc-db, is global and used by these functions behind the scenes,
rather than being passed as an argument.Although we have provided test cases, you should also include at least
one more test case for each of the functions specified above.
Include these test cases in your unicalc.rkt source file.
We will also test your code on additional cases not provided.
; Provided test casesThis will make it easier for the graders to find your new test cases. (Being nice to the graders is an important skill to learn early!)
(check-expect (subbag '(1 2 2 3) '(1 2 2 3)) #t)
(check-expect (subbag '(1 2 2 3) '(1 2 3)) #f)
(check-expect (subbag '(1 2 2 3) '(2 1 3 2 2 1 1)) #t)
(check-expect (subbag '("h" "m" "c") '("c" "h" "a" "r" "m")) #t)
; MY OWN TESTS
(check-expect (subbag '(3 2 1) '(1 2 3)) #t)
review of recursion For this problem define a function, named subbag, taking two list arguments, L1 and L2. Each of these lists is to be considered a mathematical "bag" of elements, that is, a set in which duplicates are allowed. Then, subbag should return #t in the case that all of the elements of L1 appear in L2 at least as many times as they appear in L1. Otherwise, this function should return #f. Here are some examples:
(check-expect (subbag '(1 2 2 3) '(1 2 2 3)) #t)Note that subbag needs only work with elements at the "top level."
(check-expect (subbag '(1 2 2 3) '(1 2 3)) #f)
(check-expect (subbag '(1 2 2 3) '(2 1 3 2 2 1 1)) #t)
(check-expect (subbag '("h" "m" "c") '("c" "h" "a" "r" "m")) #t)
The function
(define (log2 N)
(cond
[ (< N 2) 0 ]
[ else (+ 1 (log2 (quotient N 2)))]
))
computes an integer approximation to the base-2 logorithm of its input N. For example, (log2 8) returns 3, because 2 to the 3rd power is 8.
Write (tail-log2 N), tail-recursive code that produces the same answer.
Recall that to be tail-recursive, tail-log2 (and/or helper functions!) should do no work after any recursive calls. tail-log2 should return the largest integer less than or equal to the log-base-2 of the input, N. N will always be a positive integer. For example,
(check-expect (tail-log2 2) 1)
(check-expect (tail-log2 3) 1)
(check-expect (tail-log2 4) 2)
(check-expect (tail-log2 10) 3)
(check-expect (tail-log2 1000) 9)
Write a tail-recursive function (tail-fib N) that takes in a positive integer N and outputs the Nth fibbonacci number, i.e., the appropriate term of the series in which the first and second elements are 1 and subsequent elements are the sum of the previous two:
1 1 2 3 5 8 13 21 ...Thus,
(check-expect (tail-fib 8) 21)
Write a tail-recursive function (tail-range low high) where low and high are two
integers. The output
should be the empty list if low ≥ high.
Otherwise, the output should be the list (low low+1 low+2
... high-1), that is from low up to but not including high. For example,
(check-expect (tail-range 3 3) '())Using higher-order functions
(check-expect (tail-range 40 50) '(40 41 42 43 44 45 46 47 48 49))
For the rest of this assignment (Problem 2.5 and Problem 2.6), you should not use any explicit recursion at all in their implementation. Rather, your solutions should rely on Scheme's higher-order functions, i.e., functions that take other functions as input or yield them as output. Thus, constructs such as map, foldr, filter, and lambda will be the most important building blocks.
This problem asks you to write two functions. First, implement (superreverse L), whose functionality is almost identical what it was in hw1. In this case, however, you may assume that the input L will be a list that contains zero or more lists (and only lists) as elements. (Remember to use no raw recursive calls.)
(check-expect (superreverse '( () (1 2 3) ((c b) a))) '( () (3 2 1) (a (c b))))
Second, implement (indivisible k L), where k is a positive integer and L is a list of positive integers. Then, indivisible should return a list of the elements of L that are not evenly divisible by k. They should appear in the same order as they do in L. For instance,
(check-expect (indivisible 3 '( 2 3 4 5 6 7 8 9 10 )) '(2 4 5 7 8 10))
This problem is the same as last week's problem, but for this
assignment,
you need to use higher-order functions (and lambda)
rather than raw recursion in solving it. The only exception to this
rule is that you may use the subbag function you wrote for problem 2.1,
even if you implemented it recursively.
Define a function best-word as follows:
(define (best-word rack wordList) ...)where best-word takes two inputs: a string of letters rack and a list of legal strings named wordList. Then, best-word should return a list of two elements: the return value's first element should be the highest-scoring word from wordList that can be made from the letters in rack. The return value's second element should be the score of that highest-scoring word. If there is a tie, any one of the strings in the wordList with maximal score may be returned. When we test your code, we will make sure that the highest-scoring word in each test case is unique.
(best-word 'academy (list 'ace 'ade 'cad 'cay 'day)) ==> ('cay 8)
(best-word 'appler (list 'peal 'peel 'ape 'paper")) ==> ('paper 9)
(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. ;; scrabble-tile-bag
;;
;; letter tile scores and counts from the game of Scrabble
;; the counts aren't needed (but don't hurt)
;; 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
Hint: planning out your strategy for this problem before diving in to the coding is a good thing! In particular, you will want to define and use a number of helper functions to keep your definition of best-word simple and elegant. You'll want to keep your helper functions short, as well! As a guide, consider the lotto example we looked at in class on Thursday.
The extra credit problem in this assignment ask you to
implement functions that manipulate binary search trees in a variety
of ways. Recall that the representation of a binary search tree that we
are using is either null? (the empty list) or a
list of three elements: first the root of the tree; second, the
left-hand subtree;
and third, the right-hand subtree. Also, all elements of a left-hand
subtree
are strictly less than the value of the root. All elements of a
right-hand
subtree are strictly greater than the root. Finally, no value may be
repeated in the tree.
For example,
(define BT1 '( 42 (20 (7 (1 () ()) (8 () ())) (31 () (41 () ()))) (100 (60 () ()) ()) ))We will use binary search trees of only integers for the following three problems.
First, write a function (height BT) whose input is a binary search tree and whose output is the length of the longest path from the root of BT to any one of its leaves, i.e., the height of the binary search tree. For instance,
(check-expect (height BT1) 4) ;; using the tree defined above
Next, write a function (find-min BT) whose input is a
non-empty binary search tree and whose output
is the value of the smallest node in that binary search tree.
For instance,
(check-expect (find-min BT1) 1) ;; using the tree defined above
Write a function (flatten-tree BT) whose input is any binary search tree and whose output is a list of all of the elements, in order, of the input. For example,
(check-expect (flatten-tree BT1) '(1 7 8 20 31 41 42 60 100)) ;; using the tree defined above
The final binary search tree exercise this week is to write a function (delete value BT) whose inputs are a numeric argument, value, and a binary search tree, BT. If value does not appear in BT, then a binary search tree identical to BT is returned. On the other hand, if value does appear in BT, then a tree similar to BT is returned, except with the node value deleted.
If the value to delete has zero children, it is straightforward to delete. Similarly, if it has only one non-empty child, it is replaced by that child. When the value to be deleted has two non-empty children, however, it is not clear which of its children (or descendants) are to take its place. For the sake of this problem, the node that should take value's place should be the smallest value in BT that is larger than value. Here are two examples:
(check-expect (delete 20 BT1) '(42 (31 (7 (1 () ()) (8 () ())) (41 () ())) (100 (60 () ()) ())))
(check-expect (delete 42 BT1) '(60 (20 (7 (1 () ()) (8 () ())) (31 () (41 () ()))) (100 () ())))