Out: Monday, October 20, 2014
Due: Monday, October 27, 2014 at 600pm local time.
The goal of this problem set is to give you practice using context arguments and invariants.
Remember that you must follow the design recipe, and write invariants (as WHERE clauses) whenever an argument represents context information.
You must use DrScheme's HtDP Intermediate Student Language with Lambda. Use list abstractions like filter, fold, and map whenever they are helpful. As before, you will be penalized for failing to use these when they are "obviously" applicable.
As usual, the rubric for grading is here. You should also refer to the more detailed guidelines here.
Starting with this problem set, we will not run automated testing on programs that do not pass the qualification tests.
1 The first section 1.1 A subsection with no subsections 1.2 Another subsection 1.2.1 This is a subsection of 1.2 1.2.2 This is another subsection of 1.2 1.3 The last subsection of 1 2 Another section 2.1 More stuff 2.2 Still more stuff
We could represent such an outline as a list with one element per section or subsection. Each element of the list consists of two members: the section number, represented as a list of natural numbers, and a string.
In this representation, the outline above would be represented as
(((1) "The first section") ((1 1) "A subsection with no subsections") ((1 2) "Another subsection") ((1 2 1) "This is a subsection of 1.2") ((1 2 2) "This is another subsection of 1.2") ((1 3) "The last subsection of 1") ((2) "Another section") ((2 1) "More stuff") ((2 2) "Still more stuff"))(where we're using the "write" representation of lists).
We'll call this the flat-list representation.
A different representation would represent an outline as a list of sections, where a section contains a title, which is a string, and a list of subsections.
Under this representation, the outline above would be represented as
(("The first section" ("A subsection with no subsections") ("Another subsection" ("This is a subsection of 1.2") ("This is another subsection of 1.2")) ("The last subsection of 1")) ("Another section" ("More stuff") ("Still more stuff")))
We'll call this the nested-list representation.
Write a program called "outlines.rkt" that converts from the nested representation to the flat representation.
Your program should use the following data definition:An Sexp is one of the following -- a String -- a NonNegInt -- a ListOfSexp A ListOfSexp is one of -- empty -- (cons Sexp ListOfSexp)
First, write data definitions for NestedRep and FlatRep. Each of these will be subsets of Sexp. Be sure to include whatever invariants are applicable.
An outline may be an empty document, in which case both the NestedRep and FlatRep would be the empty list.
Then, provide the following functions:
nested-rep? : Sexp -> Boolean GIVEN: an Sexp RETURNS: true iff it is the nested representation of some outline nested-to-flat : NestedRep -> FlatRep GIVEN: the representation of an outline as a nested list RETURNS: the flat representation of the outline
You should switch to the "write" output representation in DrRacket (Choose Language > Show Details > Output Style > 'write') so that your output will look exactly like the ones above. With this output representation, your interaction should look like
> (nested-to-flat '(("The first section" ("A subsection with no subsections") ("Another subsection" ("This is a subsection of 1.2") ("This is another subsection of 1.2")) ("The last subsection of 1")) ("Another section" ("More stuff") ("Still more stuff")))) (((1) "The first section") ((1 1) "A subsection with no subsections") ((1 2) "Another subsection") ((1 2 1) "This is a subsection of 1.2") ((1 2 2) "This is another subsection of 1.2") ((1 3) "The last subsection of 1") ((2) "Another section") ((2 1) "More stuff") ((2 2) "Still more stuff")) >
There should be no structs in your input or output, just lists.
As usual, before you turn in your solution, make sure it passes the tests in ps06-outlines-qualification.rkt. As before, download this file, save it in your set06 directory, and run it to qualify your program for grading. Be sure to commit this file to repository so we know that you've done this correctly.
For what it's worth, my solution to this problem was 117 lines, not including tests, and in one recent semester the median reported time for this problem was 8.65 hours.
(define-struct sum-exp (exprs)) (define-struct mult-exp (exprs)) ;; An Expr is one of ;; -- Integer ;; -- (make-sum-exp NELOExpr) ;; -- (make-mult-exp NELOExpr) ;; Interpretation: a sum-exp represents a sum and a mult-exp ;; represents a multiplication. ;; A LOExpr is one of ;; -- empty ;; -- (cons Expr LOExpr) ;; A NELOExpr is a non-empty LOExpr.
Your task is to write a program called pretty.rkt that contains a pretty-printer for Exprs. More precisely, you are to provide a function
expr-to-strings : Expr NonNegInt -> ListOfString GIVEN: An expression and a width RETURNS: A representation of the expression as a sequence of lines, with each line represented as a string of length not greater than the width.
The rules for rendering the expression as a list of lines are as follows:
(+ expr1 expr2 ... exprN)and similarly for multiplication expressions.
In addition, you must provide make-sum-exp, sum-exp-exprs, make-mult-exp, and mult-exp-exprs.
In order to help you debug your program, we have provided in extras.rkt the function:
display-strings! : ListOfString -> Void GIVEN: a list of strings EFFECT: displays the strings on separate lines RETURNS: no value Example: > (display-strings! "xyz" "abc") xyz abc >
Be sure to download a fresh copy of extras.rkt containing this function.
Here is a sample interaction:
> hw-example-1 (make-sum-exp (list 22 333 44)) > (expr-to-strings hw-example-1 15) (list "(+ 22 333 44)") > (expr-to-strings hw-example-1 10) (list "(+ 22" " 333" " 44)") > > (define (display-expr expr n) (display-strings! (expr-to-strings expr n))) > (display-expr hw-example-1 25) (+ 22 333 44) > (display-expr hw-example-1 10) (+ 22 333 44) > (display-expr hw-example-1 5) not enough room > hw-example-2 (make-sum-exp (list (make-mult-exp (list 22 3333 44)) (make-mult-exp (list (make-sum-exp (list 66 67 68)) (make-mult-exp (list 42 43)))) (make-mult-exp (list 77 88)))) > (display-expr hw-example-2 100) (+ (* 22 3333 44) (* (+ 66 67 68) (* 42 43)) (* 77 88)) > (display-expr hw-example-2 50) (+ (* 22 3333 44) (* (+ 66 67 68) (* 42 43)) (* 77 88)) > (display-expr hw-example-2 20) (+ (* 22 3333 44) (* (+ 66 67 68) (* 42 43)) (* 77 88)) > (display-expr hw-example-2 15) (+ (* 22 3333 44) (* (+ 66 67 68) (* 42 43)) (* 77 88)) >
As usual, before you turn in your solution, make sure it passes the tests in ps06-pretty-qualification.rkt. As before, download this file, save it in your set06 directory, and run it to qualify your program for grading. Be sure to commit this file to repository so we know that you've done this correctly.
Here are some hints on this problem.
My solution to this problem took 175 lines, exclusive of tests, and the last time I gave this problem, the median reported time was 16.3 hours.
Last modified: Sun Oct 19 11:26:29 Eastern Daylight Time 2014