15.2
(define (palindrome? sent)
(palindromic-word? (accumulate word sent)))
(define (palindromic-word? w)
(or (<= (count w) 1)
(and (equal? (first w) (last w))
(palindromic-word? (bf (bl w))))))
15.3
;;; Only if two different subsequences return the same string will
;;; there be a duplicate here. Could wrap in REMDUP if such are not
;;; desired.
(define (substrings w)
(se (every suffixes (prefixes w)) ""))
;;; All non-empty suffixes:
(define (suffixes w)
(if (empty? w)
'()
(se w (suffixes (bf w)))))
;;; All non-empty prefixes:
(define (prefixes w)
(if (empty? w)
'()
(se w (prefixes (bl w)))))
17.12
(define (flatten x)
(cond ((null? x) '())
((pair? x) (append (flatten (car x))
(flatten (cdr x))))
(else (list x))))
;;; The above is the classic definition. But if you are an efficiency
;;; freak, you'll notice that for some s-exprs it is O(n^2), since
;;; APPEND is linear in the length of its first argument.
;;; A linear time algorithm can be written by using a helper function
;;; which takes the flattened remainder of the expression and just
;;; CONSes anything it finds onto the front.
(define (flatten x)
(flatten-aux x '()))
(define (flatten-aux x flat-end)
(cond ((null? x) flat-end)
((pair? x) (flatten-aux (car x)
(flatten-aux (cdr x)
flat-end)))
(else (cons x flat-end))))
19.9
;;; This is so easy I can't bring myself to type it in!
Here is some junk mail:
You have been hired by the post office to write software that reads the bar codes bulk mailers are required to produce.
These bar codes consist of a series of long and short bars. We will call the long bars 1's and the short bars 0's.
Let's zoom in on the bar code strip itself:
| digit | code group |
|---|---|
| 1 | 0 0 0 1 1 |
| 2 | 0 0 1 0 1 |
| 3 | 0 0 1 1 0 |
| 4 | 0 1 0 0 1 |
| 5 | 0 1 0 1 0 |
| 6 | 0 1 1 0 0 |
| 7 | 1 0 0 0 1 |
| 8 | 1 0 0 1 0 |
| 9 | 1 0 1 0 0 |
| 0 | 1 1 0 0 0 |
Good: the first five digits are the zip code in the address block.
Note that there are exactly two 1s and three 0s in each five-bit group. (The decimal digit values can be computed using the column weights 7, 4, 2, 1, 0. For example, 01100 is (+ (* 0 7) (* 1 4) (* 1 2) (* 0 1) (* 0 0)) = 6. The exception to this rule is the digit 0, which would come to 11 by the above formula. If you think these bit patterns are neat, you should take a course on information theory.)
Your task is to write a Scheme procedure that takes the sentence of 0's and 1's output by the physical scanning device and returns a sentence of decimal digits.
There are many sources of error that cause incorrect or invalid readings: the labels can be torn or smudged, dust and dirt and vibration can cause the scanning device to misregister, etc. For this reason, there are a number of features built into the code to allow such errors to be detected, so the envelope can be diverted for manual processing. For example, the bit patterns above are such that a misreading of 0s as 1s, or alternatively of 1s as 0s, results in an invalid pattern.
Another such feature is that the last digit in the strip is a ``check digit.'' It is chosen so that the sum of all the digits in the strip comes to a multiple of 10. So if one wanted to encode the number 87131000199 in a bar code strip like this, one would first add the digits, 8+7+1+3+1+0+0+0+1+9+9=39, so the check digit would be a 1, because 39+1=40 which is a multiple of 10.
To give an example of all the above, in order to encode the zip code 87131, we first append a check digit, giving 871310 (8+7+1+3+1+0 = 20). Then these get converted into into five-bar codes, giving 10010 10001 00011 00110 00011 11000. Then a 1 is appended to each end, to get the final bar pattern: 11001010001000110011000011110001.
Your job is to write the procedure that will convert a sentence of bars read in, eg (1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1), into the corresponding sentence of decimal digits, eg (8 7 1 3 1).
Because of the presence of errors in the strip read in, you must be very careful to call the procedure error if there is any evidence of an incorrectly read strip! This means you must call error if the 1's at the end are not there, or if any five-bar group is invalid, or if the check digit is invalid, or if the total number of bars read doesn't come to 5n+2 for some n>0. (You cannot assume that n=5+1=6, for five-digit zip codes, because (a) sometimes 9-digit zip codes are used, as above, (b) sometimes extra information is encoded beyond this, as above, and (c) you might want to sell your program to some other country that has some other zip code length.)
The remainder of this problem set involves first writing subroutines that will be useful for this task, and finally writing the actual conversion routine.
For example, (first-n 2 '(aye bee sea dee eye eff)) yields
(aye bee).
(define (first-n n lis)
(if (= n 0)
'()
(cons (car lis)
(first-n (- n 1)
(cdr lis)))))
For example, (bf-n 2 '(aye bee sea dee eye eff)) yields
(sea dee eye eff).
(define (bf-n n lis)
(if (= n 0)
lis
(bf-n (- n 1) (cdr lis))))
Eg (bars->digit '(1 0 0 1 0)) yields 8 while
(bars->digit '(1 0 1 1 0)) calls error.
(define (bars->digit code)
(if (= (apply + code) 2)
(modulo (apply + (map * code '(7 4 2 1 0))) 11)
(error "Code group must have exactly two 1s")))
Eg (barcode->zipcode '(1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1)) yields (8 7 1 3 1).
You can assume that the sentence it is passed contains only 0's and 1's. But you must call error if there is any kind of format error, or if the check digit is incorrect. (The check digit itself should not be part of the sentence returned.)
You may find it useful to write more helper functions than just those
assigned above.
(define (barcode->zipcode strip)
(cond ((= (car strip) 0)
(error "Strip must begin with a 1"))
((= (last strip) 0)
(error "Strip must end with a 1"))
((not (= (modulo (count strip) 5) 2))
(error "Incorrect number of bars in strip"))
(else (let ((decimal (barcode-cutup (bf (bl strip)))))
(cond ((not (= (modulo (apply + decimal) 10) 0))
(error "Bad check digit"))
(else
(bl decimal)))))))
(define (barcode-cutup codes)
(if (null? codes)
'()
(cons (bars->digit (first-n 5 codes))
(barcode-cutup (bf-n 5 codes)))))
More extra credit: write barcode->zipcode3 and
barcode->zipcode4 which try to recover from a single
missing bar or a single extra inserted bar, respectively, as might
occur if the envelope were creased or torn. There might be more than
one possible correction under these circumstances, so you should
return a list of all potential correct sentences of decimal digits.
;;; exercise for the reader