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")
My solutions to the scheme text "How to Design Programs 2nd ed". (Or htdp2e) I aim to complete as many as these as I can - please feel free to comment on my solutions/answers!
Tuesday, 27 September 2011
Tuesday, 20 September 2011
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)
; 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
Finally - lets run it and see what we get:
> (process-file "ttt.txt")
"no-articles-ttt.txt"
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))))))
> (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!Thursday, 15 September 2011
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)))
;
(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")
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")