Exercise 151 - Designing an editor

Exercise 151: Design the function create-editor.

The function consumes two strings  and produces an Editor. The first string is the text to the left of the cursor and the second string is the text to the right of the cursor. The rest of the section relies on this function.

First up, I wanted to roll my own rev function instead of going off the one in the book. This was a fairly short question and so needed some padding to make it interesting!

; Lo1s -> Lo1s
; produce a reverse version of the given list

(check-expect
 (rev (cons "a" (cons "b" (cons "c" empty))))
  (cons "c" (cons "b" (cons "a" empty))))

(define (rev l)
  (cond ((empty? l) l)
        ((cons? l) (add-to-end (first l) 
                               (rev (rest l)))))) 


Now we need our wish-list function 'add-to-end'.
I didn't read this section of the manual as I wanted to come up  with the solution to this on my own.
I had issues at this point as I kept wanting to use 'cons' to join the two lists together - this of course results in a nested list (which is not what we want). eg;

(cons (list "a" "b") (cons "a" empty)) 
  => (list (list "a" "b") "a")


After I discovered the 'append' function, this function shrank away to almost nothing. The only reason we need it now, is to save creating the second list with item and empty in the main function.

; adds an item to the end of the given list
(define (add-to-end item l)
   (append l (cons item empty)
  ))


(check-expect (add-to-end "a" empty) (list "a"))
(check-expect (add-to-end "c" (list "a" "b")) 
              (list "a" "b" "c"))


Now, for the actual question - we need to make an Editor. This function consumes two strings and produces an Editor.

; An Editor is (make-editor Lo1S Lo1S)
; An Lo1S is one of:
; - empty
; - (cons 1String Lo1S)
(define-struct editor (pre post))

This method really seems overkill (or I'm not doing something I  should be doing... it seems we've cut down on typing by 2 characters (the difference between m-a-k-e and c-r-e-a-t-e)

Perhaps my possible lack of comprehension will become clearer later on in exercise 152, but for now, this is what I think they are after ...

(define (create-editor left-string right-string)
  (make-editor left-string right-string))


All these constants below are given by the question - I'm just pasting them here for completeness

; constants
(define HEIGHT 20) ; the height of the editor
(define WIDTH 200) ; its width
(define FTSZ 11) ; the font size
(define FTCL "black") ; the font color

; graphical constants - also supplied directly by the question
(define MT (empty-scene WIDTH HEIGHT))
(define CU (rectangle 1 HEIGHT "solid" "red"))


; Editor -> Image
; render an editor as an image of the two texts separated by the cursor
; (supplied directly from the question)
(define (editor-render e)
  MT)

; Editor KeyEvent -> Editor
; deal with a key event, given some editor
; (supplied directly from the question)
(define (editor-kh ed ke)
  ed)


; main : String -> Editor
; launch the editor given some initial string
; (supplied directly from the question)
(define (main s)
   (big-bang (create-editor s "")
             (on-key editor-kh)
             (to-draw editor-render)))

At this point we can actually call our editor, but it doesn't do anything interesting yet. (Or anything at all really!)

(make-editor (make-editor "Hello" "World") "")

The first two test statements are supplied by the question. The rest are what we need to come up to answer the question.

; This first checks to make sure that when you press 'e' you
; create an editor displaying e
(check-expect (editor-kh (create-editor "" "") "e")
              (create-editor "e" ""))


; This checks that when you type 'e', it's added at the 
; cursor point
; (rather than the beginning or end of the editor)
(check-expect (editor-kh (create-editor "cd" "fgh") "e")
              (create-editor "cde" "fgh"))


; check that pushing backspace deletes text from the 
; correct location
(check-expect (editor-kh (create-editor "Bob" "Dylan") "\b")
              (create-editor "Bo" "Dylan"))


(check-expect (editor-kh (create-editor "" "") "\b")
              (create-editor "" ""))


; check we can use the cursor to move to the left
(check-expect (editor-kh (create-editor "Bob" "Dylan") "left")
              (create-editor "Bo" "bDylan"))


(check-expect (editor-kh (create-editor "" "Dylan") "left")
              (create-editor "" "Dylan"))


; check we can use the cursor to move to the right
(check-expect (editor-kh (create-editor "Bob" "Dylan") "right")
              (create-editor "BobD" "ylan"))


(check-expect (editor-kh (create-editor "Bob" "") "right")
              (create-editor "Bob" ""))
                         

Exercise 150 - Transposing a Matrix

Mathematics teachers may have introduced you to matrix calculations by now. Numeric programs deal with those, too. Here is one possible data representation for matrices:

; A Matrix is one of:

; – empty

;; – (cons LN Matrix)

; An LN is one of:

; – empty

;; – (cons Number LN)

; interp. a matrix is a list of rows, a row is a list of numbers

; constraint: all rows are of the same length

Study it and translate the two-by-two matrix consisting of the numbers 11, 12, 21, 22 into this data representation.

They don't make it 100% clear how this should translate to a matrix (eg horizontally or vectically), but common sense would be to divide it into two horizontal rows

(require racket/base)

(define MATRIX (list (list 11 12)

(list 21 22)))

; define an extra couple of Matrix's to use for testing.

(define MATRIX2 (list (list 11 12)

(list 21 22)

(list 31 32)))

(define MATRIX3 (list (list 11 12 13)

(list 21 22 23)

(list 31 32 33)))

Study it and translate the two-by-two matrix consisting of the numbers 11, 12, 21, 22 into this data representation.

The following function implements the important mathematical operation of transposing the entries in a matrix. To transpose means to mirror the entries along the diagonal, that is, the line from the top-left to the bottom-right.

; Matrix -> Matrix

; transpose the items on the given matrix along the diagonal

;(check-expect (transpose mat1) tam1)

(define (transpose lln)

  (cond

    [(empty? (first lln)) empty]

    [else (cons (first* lln) (transpose (rest* lln)))]))

The definition assumes two auxiliary functions:

first*, which consumes a matrix and produces the first column as a list of numbers;;

rest*, which consumes a matrix and removes the first column. The result is a matrix.

Even though you lack definitions for these functions, you should be able to understand how transpose works. You should also understand that you cannot design this ;function with the design recipes you have seen so far. Explain why.

Design the two “wish list” functions. Then complete the design of the transpose with some test cases. 

I am not at all sure how transpose works at this point! (My maths-fu is weak). From reading the code, it seems to work thru a list of lists of numbers, taking the first column and then creating a new list by adding this first column back onto the start of the matrix (which has just had the first column removed!

(An example here would have gone a long way.)

Even if this is transposing the colums, it seems it would be working in complete columns, so I'm not sure how it could ever produce a diagonal transposition.

To confound things further, they say "You cannot design this function". then without explaining anything further, they tell us to go design this function!

I'm not sure if i'm meant to be able to do this or not, but we'll have a try... If we can run the code and it does what they say, perhaps seeing it in process may make things clearer!

The function first* is not too hard - it's the standard recursive scheme function. If the matrix is empty, return empty, otherwise build up a new list consisting of the first number in the list, and the result of calling this on the *rest* of the rows in the matrix

;first* consumes a matrix and produces the first column as a 

;list of numbers

; Matrix -> LN

(define (first* lln)

  (cond ((empty? lln) empty)

        ((cons? lln) (cons (first (first lln)) 

                           (first* (rest lln))))))  

(check-expect (first* MATRIX) (list 11 21))

(check-expect (first* MATRIX2) (list 11 21 31))

This is basically the inverse of first* - this time we want to grab the rest of each list and return that.

;Matrix -> Matrix

(define (rest* lln)

  (cond ((empty? lln) empty)

        ((cons?  lln) (cons (rest (first lln))

                            (rest* (rest lln))))))

(check-expect (rest* MATRIX) (list (list 12) 

                                   (list 22)))

(check-expect (rest* MATRIX2) (list (list 12) 

                                    (list 22) 

                                    (list 32)))

(check-expect (rest* MATRIX3) (list (list 12 13)

                                    (list 22 23) 

                                    (list 32 33)))

Now to test the transposing - in theory, this function should turn our matrix from this:

; 11 12 13

; 21 22 23

; 31 32 32

into this:

; 11 21 31

; 12 22 32

; 13 23 33

(check-expect (transpose MATRIX3) (list (list 11 21 31)

                                        (list 12 22 32)

                                        (list 13 23 33)))

The test passes, so the transpose function does what it is meant to – but why?!?! 

Let's add a  debugging method to try and work out what's going on.

(define (print-matrix mat)

  (cond ((empty? mat) 

         (fprintf (current-output-port) " *** \n"))

        (else (fprintf (current-output-port) 

                       " ~a\n" 

                       (first mat))

              (print-matrix (rest mat)))))

If you put this into the (transpose) function, you can see that transpose does rip the matrix apart into columns. Once the columns have been removed, these get cons'd together horizontally (as rows) to become the new Matrix. This automatically 'mirrors' each half along the diagonal without needing to work on diagonal sections of the matrix.

For example, originally if you had:

; (list (list 2 5)

;       (list 8 9))

This would get ripped into the two colums (list 2 8) and (list 8 9) and then assembled as;

; (list (list 2 8)

;       (list 8 9))

Exercise 149: Design a BSL program that simulates the Unix command wc

Exercise 149: Design a BSL program that simulates the Unix command wc.

The purpose of the command is to count the number of characters (1Strings),
words, and lines in a given file. That is, the command consumes the name of
a file and produces a value that consists of three numbers.


(require racket/base)
(require 2htdp/batch-io)


First, create a function to count the chars 


; calculates the number of chars in a string
; Spaces count as a character
; String->Number
(define (count-chars string)
  (count-chars-helper (explode string) 0))


; List-of-Characters->Number
(define (count-chars-helper loc count)
  (cond ((empty? loc) count)
        ((cons? loc) (count-chars-helper 
                      (rest loc) 
                      (add1 count)))))


(check-expect (count-chars "") 0)
(check-expect (count-chars "This is a string") 16)


Second stage - create a function to count the words

This part is mildy tricky - there are three cases we need to deal with:

1.  if llos is currently a string, its just a   string and we can recursively iterate on it til the end simply
2. it's an empty list - ie, a blank line. We need to just skip this  item and move on. If we try and count it, we'll get #void and it will make add1 very unhappy
3.  it's a populated list - ie, one or more populated lines.  In this case we need to call count-words-helper on it   twice - once to get the count for the first line, and again to get the count for all the remaining lines. The result of the  first count feeds into the second call as we don't know how to    maintain variable state yet... I found this part very difficult    to grok

; calculates the number of words in a list of lists
; of strings
; List-Of-Lists-Of-String->Number
(define (count-words llos)
  (count-words-helper llos 0))


; Does the actual work of getting the count
; - llos -> empty - returns the count
; - (rest llos) is a string - count it, and recurse
; - (rest llos) is a cons, we're on a new line, so just recurse
; List-Of-Lists-Of-String->Number
(define (count-words-helper llos count)


  (cond ((empty? llos) count)
        ((cons? llos) 
  
       (cond ((string? (first llos)) 
              (count-words-helper (rest llos) (add1 count)))
             ((empty? (first llos)) 
              (count-words-helper (rest llos)  count))
             ((cons? (first llos))
              (count-words-helper 
               (first llos) 
               (count-words-helper (rest llos) count)))))))
     


Some tests to make sure we didn't mess that up!


; basic case - an empty list
(check-expect (count-words empty) 0)
; a list of strings
(check-expect (count-words 
               (list "This" "is" "a" "string")) 
              4)
; a list of lists of strings
(check-expect (count-words (list 
                            (list "line" "one") 
                            (list "line" "two")))
              4)
; make sure we handle new lines (empty lists) okay
(check-expect (count-words (list (list "line" "one") 
                                 empty (list "line" "two"))) 
              4)




Finally - last method - count the lines.


; calculates the number of lines in list of lists of strings
; this method is very straight forward - just counting the number of 
; items present in our list
; basically just counting the lists
; List-of-Strings->Number
(define (count-lines los)
  (count-lines-helper los 0))


(define (count-lines-helper los count)  
  (cond ((empty? los) count)
        ((cons? los) (count-lines-helper (rest los) 
                                         (add1 count)))))


  
(check-expect (count-lines empty) 0)
(check-expect (count-lines (list "This is a string")) 
              1)
(check-expect (count-lines (list (list "line one") 
                                 (list "line two"))) 
              2)
(check-expect (count-lines (list (list "line one")
                                 empty 
                                 (list "line two")))
              3)


; finally, wrap it all up with a function that
; calls all 3 of our new methods and produces a list
; character, word and line counts
; String->List-of-Numbers
(define (wc filename)
  (list
   (count-chars (read-file filename))
   (count-words (read-words/line filename))
   (count-lines (read-lines filename))
  ))

Exercise 148: Design a program that encodes text files numerically.

Exercise 148: Design a program that encodes text files numerically.
Each letter in a word should be encoded as a numeric three-letter string with a value between 0 and 256. Here is our encoding function for letters:



; 1String -> String
; auxiliary for stating tests
;(define (code1 c)
;  (number->string (string->int c)))
; 
;(check-expect (encode-letter "\t") 
;              (string-append "00" (code1 "\t")))
;(check-expect (encode-letter "a") 
;              (string-append "0" (code1 "a")))
;(check-expect (encode-letter "z") (code1 "z"))
; 
;(define (encode-letter s)
;  (cond
;    [(< (string->int s) 10) (string-append "00" (code1 s))]
;    [(< (string->int s) 100) (string-append "0" (code1 s))]
;    [else (code1 s)]))


; Before you start, explain this function. Also recall how
; a string can be converted into a list of 1Strings.
; Again, use read-words/line to preserve the organization of
; the file into lines and words.  




They don't specify in the question what they want you to do with the  output, so I'm going to return it as a plain string with no padding between the groups.


(require racket/base)
; 1String -> String
; convert the given 1string into a three-letter numeric string

; 1String -> String
; auxiliary for stating tests
(define (code1 c)
  (number->string (string->int c)))

(check-expect (encode-letter "\t") 
              (string-append "00" (code1 "\t")))
(check-expect (encode-letter "a")
              (string-append "0" (code1 "a")))
(check-expect (encode-letter "z") 
              (code1 "z"))

(define (encode-letter s)
  (cond
    [(< (string->int s) 10) (string-append "00" (code1 s))]
    [(< (string->int s) 100) (string-append "0" (code1 s))]
    [else (code1 s)]))




Explaining how it works is straight forward. code1 calls string->int, which will convert the char passed in into an int.  (Presumably it's ascii code decimal equivilant). This is then converted to  a string and returned. 
As this will be a straight int (eg, no leading zero's) the function encode-letter will prepend "00" if the number is less than 10, or prepend "0" if the number is greater than 10 but less than 100.


; encode a list of numbers - returns a list of strings of 
; encoded chars
; 1String -> String
(define (process-word loc)
  (cond ((empty? loc) "")
        ((cons? loc) (string-append (encode-letter (first loc))
                                    (process-word (rest loc))))))


(check-expect (process-word (list "t" "h" "e")) "116104101")


; Process the entire line of words into integer codes. Note the
; use of the 'explode' function here. I was originally trying
; to use string->list which will not work!
; List-of-Strings->String
(define (process-line los)
  (cond ((empty? los) 
         "")
        ((cons? los) 
         (string-append (process-word (explode (first los)))
                        (process-line (rest los))))))


(check-expect (process-line (list "the" "cat" "in" "the" "hat"))
              "116104101099097116105110116104101104097116")

Excercise 147 - Removing articles from a text file

Exercise 147: Design a program that removes all articles from a text file.

The program consumes the name n of a file, reads the file, removes the articles, and writes
the result out to a file whose name is the result of concatenating "no-articles-" with n.
For this exercise, an article is one of the following three words: "a", "an", and "the".

Use read-words/line so that the transformation retains the organization of the
original text into lines and words. When the program is designed, run it on the
Piet Hein poem.


; these requires let us print out debugging info 
; and read/write the files to disk
(require racket/base)
(require 2htdp/batch-io)


; the list of articles we are going to strip
(define ARTICLES (list "a" "the" "an"))


  
; String -> Boolean
; Returns true of false if a word is permitted (eg it is not in
; our list of ARTICLES)
; articles is a List-of-Strings
; word is a String
(define (permitted? articles word)
  (cond ((empty? articles) #true)
        ((string=? (first articles) word) #false)
        ((cons? articles) (permitted? (rest articles) word))))


; test our permitted? function is working as expected
(check-expect (permitted? ARTICLES "bob") #true)
(check-expect (permitted? ARTICLES "the") #false)

Racket includes a filter method, which does basically 90% of this exercise, but we don't want to use it as then we're not learning anything! So . . . lets roll our own.

; List-of-Strings -> List-of-Strings
; 
; Returns a list of strings with the ARTICLES filtered out
; We need to call this function my_filter (or something other
; than filter) as filter is defined by racket/base 
;
; A List-of-Strings is one of:
; – empty
; – (cons String List-of-Strings)

(define (my_filter los)
   (cond ((empty? los) empty)
        ((cons? los) 
          (fprintf (current-output-port) "filter: ~a permit: ~a\n" 
                   (first los)
                   (permitted? ARTICLES (first los)))
         (cond ((permitted? 
                 ARTICLES (first los)) 
                (cons (first los) 
                      (my_filter (rest los))))
               (else (my_filter (rest los)))))))





I thought there was a string->word-list type function that I could use here, but apparently not. I probably should have written a quick one, but this will do for now


; Test we are correctly stripping out the non-permitted words
; from our list

(check-expect (my_filter (list "a" "quick" "brown" "fox" 
                               "is" "an" "elephant") )
              (list "quick" "brown" "fox" "is" "elephant"))





; processes a list of List-of-Strings, filtering each list in turn
; returns a List-of-Lists-of-Strings

(define (process llos)
  (cond ((empty? llos) empty)
        ((cons? llos) (cons (my_filter (first llos)) 
                            (process (rest llos))))))



; test our process function is removing the items from our list as
; we'd expect
(check-expect (process (list (list "a" "cat")
                             (list "a" "quick" "brown") 
                             (list "fox" "is" "an" "elephant")))
              (list (list "cat") 
                    (list "quick" "brown") 
                    (list "fox" "is" "elephant")))




And now we're pretty much finished - we can actually run the program that they asked for. We still have to convert the List of Lists of Strings that process-file is returning to a String that write-file can use, but luckily we just wrote a couple of functions that did exactly that....


; wrap this round a read/write block and add in our new file name

(define (process-file filename)
  (write-file (string-append "no-articles-" filename) 
              (collapse-lines (process (read-words/line 
                                        filename)))))





; These last two functions are taken from my answer to 
; exercise 146


; List-of-List-of-Strings -> String
; collapses a list of lists of strings into a single string.
(define (collapse-lines llos)
    (cond ((empty? llos) "")
        ((cons? llos) (string-append 
                       (collapse-los (first llos)) "\n" 
                       (collapse-lines (rest llos))))))






; List-of-Strings -> String
; collapses a 1 dimensional list of tokens into a string
; (eg NOT a list of lists of strings, just a list of strings

(define (collapse-los los)

  (cond ((empty? los) "")

        ((= 1 (length los)) (first los))

        ((cons? los) (string-append 

                      (first los)

                      " " 

                      (collapse-los (rest los))))))

Finally - lets run it and see what we get:



> (process-file "ttt.txt")
  "no-articles-ttt.txt"

dgs@dgs-netbook:~/code/htdp$ cat ttt.txt 

TTT

Put up in a place

where it's easy to see

the cryptic admonishment

T.T.T.

When you feel how depressingly

slowly you climb,

it's well to remember that

Things Take Time.

Piet Hein

dgs@dgs-netbook:~/code/htdp$ cat no-articles-ttt.txt 

TTT

Put up in place

where it's easy to see

cryptic admonishment

T.T.T.

When you feel how depressingly

slowly you climb,

it's well to remember that

Things Take Time.

Piet Hein

Success!

Exercise 144 - Phone Numbers

Exercise 144: Here is one way to represent a phone number:

    (define-struct phone (area switch four))
    ; An Phone is a structure:
    ; (make-addr Three Four)
    ; A Three is between 100 and 999.
    ; A Four is between 1000 and 9999. 

Design the function replace. It consumes a list of Phones and produces one.
It replaces all area codes 713 with 281.



The question itself doesn't seem to make sense (at least to me). make-addr is not defined. Is it
meant to be area? Why does it define Three and Four and use switch and four in the
struct...  I think this stuff is probably irrelevant for the question though...

(require racket/base)
(define-struct phone (area switch four))
(define OLD_CODE 713)
(define NEW_CODE 281)


; replaces a section of a struct within a list of phone numbers
(define (replace alop) 
  (cond ((empty? alop) empty)
        ((cons? alop) (cons (helper (first alop)) 
                            (replace (rest alop))))))




(define (helper phone)
  (make-phone
   (substitute (phone-area phone))
   (phone-switch phone)
   (phone-four phone)))


; swaps the area codes if they match
(define (substitute area)
  (cond ((= area OLD_CODE) NEW_CODE)
        (else area)))


; this test is failing, but a visual eyeball of the results show that 
; expected and actual results are identical - not sure if it's some weirdness
; to do with comparing structs.... but not going to waste too much time trying
; to track down whats up...
(check-expect (replace (list (make-phone 123 456 789)
                             (make-phone 713 456 8753)
                             (make-phone 281 432 234)))
              (list (make-phone 123 456 789)
                             (make-phone 281 456 8753)
                             (make-phone 281 432 234)))
                     

;

Execise 146 - Covert List Of Lines into a String

Exercise 146: Design a program that converts a list of lines into a string.
The strings should be separated by blank spaces (" ").
The lines should be separated with a newline ("\n").

Challenge: Remove all extraneous white spaces in your version of the Piet Hein poem. When you are finished with the design of the program, use it like this:

    (write-file "ttt.dat" (collapse (read-words/line "ttt.txt")))

The two files "ttt.dat" and "ttt.txt" should be identical.

(require 2htdp/batch-io)
(define FILE "ttt.txt")




; read-words/line reads the content of file f and produces it as 
; a list of lists,
; one per line; each line is represented as a list of white-space 
; separated tokens .
(define (collapse a) 
  (collapse-lines (read-words/line FILE)))


; List-of-Strings -> String
(define (collapse-lines llos)
    (cond ((empty? llos) "")
        ((cons? llos) (string-append (collapse-los (first llos)) "\n" (collapse-lines (rest llos))))))


; List-of-Strings -> String
; collapses a 1 dimensional list of tokens into a string
; (eg NOT a list of lists of strings, just a list of strings
; A List-of-Strings is one of:
; – empty
; – (cons String List-of-Strings)
(define (collapse-los los)
  (cond ((empty? los) "")
        ((= 1 (length los)) (first los))
        ((cons? los) (string-append (first los) " " (collapse-los (rest los))))))






(check-expect (collapse-los empty) "")
(check-expect (collapse-los (cons "slowly" (cons "you" (cons "climb" empty))))
              "slowly you climb")