exercise-70.scm (2819B)
1 (import (only (srfi :1) zip)) 2 (import (srfi :26)) 3 (import (srfi :64)) 4 (import (only (sicp utils) accumulate)) 5 (import (only (sicp solutions huffman-codes-stuff) 6 decode 7 encode 8 generate-huffman-tree 9 weight 10 make-leaf)) 11 12 (define (remove-empty-strings list-of-strings) 13 (filter (compose not 14 (cut equal? 15 "" 16 <>)) 17 list-of-strings)) 18 19 (define code-text 20 "A 2 NA 16 21 BOOM 1 SHA 3 22 GET 2 YIP 9 23 JOB 2 WAH 1") 24 25 (define songs-huffman-tree 26 (let* ([split-code-text 27 (string-split code-text 28 (string->char-set "\n "))] 29 [only-tokens-code-text 30 (remove-empty-strings split-code-text)] 31 [list-of-pairs (let loop ([code-list only-tokens-code-text]) 32 (cond 33 ((null? code-list) '()) 34 ((null? (cdr code-list)) '()) 35 (else (cons (list (string->symbol (car code-list)) 36 (string->number (cadr code-list))) 37 (loop (cddr code-list))))))] 38 [ordered-pairs-by-weight (sort list-of-pairs 39 (lambda (x y) 40 (< (cadr x) 41 (cadr y))))]) 42 (generate-huffman-tree ordered-pairs-by-weight))) 43 44 (define song-text 45 "Get a job 46 Sha na na na na na na na na 47 48 Get a job 49 Sha na na na na na na na na 50 51 Wah yip yip yip yip 52 yip yip yip yip yip 53 Sha boom") 54 55 (define only-letters-song-message 56 (remove-empty-strings 57 (string-split (string-upcase song-text) 58 (string->char-set "\n ")))) 59 60 (define song-message 61 (map string->symbol only-letters-song-message)) 62 63 (define encoded-song-message 64 (encode song-message 65 songs-huffman-tree)) 66 67 (test-begin "chapter-2-exercise-70") 68 (test-equal 69 84 70 (length encoded-song-message)) 71 (test-equal 72 992 73 (* 8 ;; Length of message in bits is a 8 bits per byte times length of message in characters. 74 (apply + ;; length of message in characters 75 (cons ;; is length of spaces 76 (- (length only-letters-song-message) ;; which is the length of message in symbols 77 1) ;; minus one to get the number of spaces between symbols 78 (map string-length 79 only-letters-song-message))))) ;; plus the number of characters in each symbol. 80 (test-end "chapter-2-exercise-70") 81 82 ;; We count consecutive whitespaces - newline and a spacey space - as a single 83 ;; space delimiting the symbols. 84 ;; We also disregard letter case and casing, which is unadvised for a 85 ;; reasonably safe journey in the land of languages.