;;; unjumble -- solve permuted-word puzzles by linking probable digraphs

;;; John David Stone
;;; Department of Mathematics and Computer Science
;;; Grinnell College
;;; stone@math.grin.edu

;;; Created March 8, 1998
;;; Last revised March 8, 1998

;;; A permuted-word puzzle is a string of letters that, when rearranged,
;;; form a familiar word.  The object of the puzzle is to determine the
;;; word.  For instance, the string "regano" is a permuted-word puzzle; its
;;; solution is "orange".

;;; This program constructs a short list of possible solutions to a
;;; permuted-word puzzle by applying information about which pairs of
;;; letters tend to occupy adjacent positions in English words.

;;; The UNJUMBLE procedure takes as arguments a string of lower-case
;;; letters that is a permuted-word puzzle and a non-negative number
;;; indicating how many guesses the program is allowed to make in trying to
;;; identify the word.  It returns a list containing the highest-scoring
;;; permutations of the given string, equal in length to the specified
;;; number of guesses.

;;; The basic idea is to construct a list of all the possible permutations
;;; of the letters of the given string and to give each one a score
;;; reflecting the sum of the ``plausibility scores'' of the letter-pairs
;;; that occur in it.  (For instance, the letter-pair ER is highly
;;; plausible, since it occurs in many words; the letter-pair HJ occurs in
;;; few words and therefore receives a low plausibility score.

;;; The permutations and the corresponding scores are stored in an
;;; association list, which is then sorted into descending order by score.
;;; The first few element of the sorted list are then separated off, and
;;; the scores discarded; the strings that received the highest scores are
;;; assembled into a list and returned.

(define unjumble
  (lambda (jumbled tries)
    (keys (head tries (sort (score-permutations jumbled))))))

;;; The KEYS procedure takes an association list as its argument and
;;; returns a list consisting only of the keys of that association list.
;;; The technique is simply to walk down the association list, applying CAR
;;; to each element and collecting the results.

(define keys
  (lambda (ls)
    (let loop ((rest ls)
               (result '()))
      (if (null? rest)
          (reverse result)
          (loop (cdr rest) (cons (caar rest) result))))))

;;; The HEAD procedure takes a non-negative integer SIZE and a list LS as
;;; its arguments and returns a list consisting of the first SIZE elements
;;; of LS.  (If LS contains fewer than SIZE elements, the entire list is
;;; returned.)  Again, the method is simple: Walk down LS, transferring
;;; each element to a result list, until either SIZE elements have been
;;; transferred or the end of LS has been reached.

(define head
  (lambda (size ls)
    (let loop ((remaining size)
               (rest ls)
               (result '()))
      (if (or (zero? remaining)
              (null? rest))
          (reverse result)
          (loop (- remaining 1) (cdr rest) (cons (car rest) result))))))

;;; The SORT procedure takes as argument an association list in which the
;;; values are real numbers and returns an association list containing the
;;; same key-value pairs, but arranged in descending order by value.

;;; The strategy is to select the first element of the list to serve as a
;;; ``pivot,'' and then to separate the rest of the list into a group of
;;; elements that should precede the pivot and another group that should
;;; follow it.  Each of these two groups is sorted separately by a
;;; recursive call.  Finally, the results are appended, with the group
;;; preceding the pivot placed first, then the pivot, and finally the group
;;; following the pivot.

(define sort
  (lambda (mixed)
    (if (null? mixed)
        (list)
        (let* ((pivot (car mixed))
               (parts (split pivot (cdr mixed))))
          (append (sort (car parts)) (list pivot) (sort (cdr parts)))))))

;;; The SPLIT procedure takes a pivot as its first argument and a list of
;;; key-value pairs to be classified as preceding or following that pivot
;;; as its second argument.  It walks down the list, classifying each
;;; key-value pair, and returns a pair in which the car is the list of
;;; preceders and the cdr is the list of followers.

(define split
  (lambda (pivot whole)
    (let loop ((rest whole)
               (preceders (list))
               (followers (list)))
      (if (null? rest)
          (cons preceders followers)
          (let ((item (car rest))
                (still-left (cdr rest)))
            (if (compare-by-value item pivot)
                (loop still-left (cons item preceders) followers)
                (loop still-left preceders (cons item followers))))))))

;;; The COMPARE-BY-VALUE procedure takes two key-and-value pairs, such as
;;; might be found in an association list, and determines whether the value
;;; part of the first is, or is not, greater than or equal to the value
;;; part of the second.  It assumes that both values are real numbers.

(define compare-by-value
  (lambda (pair-1 pair-2)
    (>= (cdr pair-1) (cdr pair-2))))

;;; The SCORE-PERMUTATIONS procedure takes a string of letters and
;;; constructs an association list in which the keys are all of the
;;; permutations of that procedure and the values are the scores for those
;;; permutations, as determined by SCORE-WORD.

;;; The general plan is to convert the string into a list of characters and
;;; then to select each of the characters in turn to be the first element
;;; of a permutation.  (Each of the _distinct_ characters, that is -- if a
;;; selection would duplicate a previous selection, it is skipped.)  A
;;; recursive call then generates all possible permutations of the
;;; remaining characters, and the selected character is then consed onto
;;; the front of each of those permutations.  The inner loop appends all of
;;; the resulting lists of permutations together to form one big list of
;;; permutations.  After all the possible lists of characters have been
;;; formed, the ENSTRING-AND-SCORE procedure (below) is applied to the
;;; result to convert each list back to a string, score it, and form a list
;;; of the permuted strings and scores.

(define score-permutations
  (lambda (word)
    (enstring-and-score
     (let outer ((chars (string->list word)))
       (if (null? chars)
           '(())                    ; a list containing only the null list
           (let inner ((tried '())
                       (untried chars)
                       (result '()))
             (if (null? untried)
                 result
                 (let ((first (car untried)))
                   (if (memv first tried)
                       (inner tried (cdr untried) result)
                       (inner (cons first tried)
                              (cdr untried)
                              (append (cons-onto-all first
                                                     (outer (remove first
                                                                    chars)))
                                      result)))))))))))

;;; The CONS-ONTO-ALL procedure takes two arguments, a value FIRST and a
;;; list LS of lists, and returns a list formed by adding FIRST at the
;;; beginning of each element of LS.

(define cons-onto-all
  (lambda (first all)
    (let loop ((rest all)
               (result (list)))
      (if (null? rest)
          result
          (loop (cdr rest) (cons (cons first (car rest)) result))))))

;;; The REMOVE procedure takes two arguments, a value DELEND and a list LS,
;;; and returns a list containing the same elements as LS except that one
;;; occurrence of DELEND has been removed.  If DELEND is not a member of
;;; LS, LS is returned without change.

(define remove
  (lambda (delend ls)
    (let loop ((rest ls)
               (so-far '()))
      (cond ((null? rest) ls)
            ((eqv? (car rest) delend) (append so-far (cdr rest)))
            (else (loop (cdr rest) (cons (car rest) so-far)))))))

;;; The ENSTRING-AND-SCORE procedure takes a list LS of lists of characters
;;; and returns an association list in which the keys are strings formed
;;; from the lists of characters in LS and the values are the scores of
;;; those strings (as determined by SCORE-WORD).

(define enstring-and-score
  (lambda (ls)
    (let loop ((rest ls)
               (result '()))
      (if (null? rest)
          result
          (let ((word (list->string (car rest))))
            (loop (cdr rest) (cons (cons word (score-word word))
                                   result)))))))

;;; The SCORE-WORD procedure ``scores'' a letter sequence by adding the
;;; scores for the letter-pairs that occur in it.

(define score-word
  (lambda (word)
    (let ((len (string-length word)))
      (let loop ((position 1)
                 (score (score-digraph #\$ (string-ref word 0))))
        (if (= position len)
            (+ score (score-digraph (string-ref word (- len 1)) #\$))
            (loop (+ position 1)
                  (+ score (score-digraph (string-ref word (- position 1))
                                          (string-ref word position)))))))))

;;; Finally we have reached the point at which the actual scoring mechanism
;;; for letter-pairs must be explained.

;;; The following association list gives the approximate relative frequency
;;; of letter-pairs in English words.  The keys are pairs in which each
;;; element is either a letter or the character $, indicating a word
;;; boundary.  (So, for example, the entry with the key (#\$ . #\a)
;;; indicates the frequency of the occurrence of the letter A at the
;;; beginning of a word, and the entry with the key (#\e . #\$) indicates
;;; the frequency of the occurrence of E at the end of a word.)

;;; This list was compiled by a Scheme program that actually went through a
;;; list of 29,233 English words and common names, counting each occurrence
;;; of each letter-pair.

(define digraph-frequencies
  `(((#\e . #\$) . 6563) ((#\e . #\r) . 3608) ((#\n . #\$) . 3211)
    ((#\a . #\n) . 3200) ((#\$ . #\s) . 3039) ((#\o . #\n) . 3028)
    ((#\i . #\n) . 2977) ((#\e . #\n) . 2944) ((#\l . #\e) . 2875)
    ((#\t . #\$) . 2831) ((#\$ . #\c) . 2795) ((#\r . #\e) . 2745)
    ((#\t . #\e) . 2743) ((#\y . #\$) . 2637) ((#\a . #\l) . 2380)
    ((#\a . #\r) . 2353) ((#\t . #\i) . 2329) ((#\a . #\t) . 2287)
    ((#\r . #\a) . 2279) ((#\s . #\t) . 2253) ((#\$ . #\p) . 2181)
    ((#\n . #\t) . 2142) ((#\o . #\r) . 2087) ((#\i . #\s) . 2049)
    ((#\r . #\i) . 2047) ((#\i . #\c) . 2045) ((#\$ . #\a) . 2029)
    ((#\l . #\$) . 1927) ((#\$ . #\b) . 1833) ((#\r . #\o) . 1781)
    ((#\c . #\o) . 1746) ((#\$ . #\m) . 1646) ((#\$ . #\d) . 1641)
    ((#\s . #\$) . 1635) ((#\r . #\$) . 1630) ((#\d . #\e) . 1627)
    ((#\l . #\a) . 1612) ((#\d . #\$) . 1588) ((#\l . #\i) . 1538)
    ((#\n . #\e) . 1510) ((#\i . #\t) . 1488) ((#\$ . #\t) . 1464)
    ((#\e . #\s) . 1446) ((#\u . #\n) . 1444) ((#\$ . #\r) . 1438)
    ((#\t . #\a) . 1395) ((#\m . #\a) . 1385) ((#\m . #\e) . 1349)
    ((#\e . #\l) . 1340) ((#\t . #\r) . 1308) ((#\s . #\e) . 1307)
    ((#\i . #\o) . 1280) ((#\c . #\a) . 1280) ((#\t . #\o) . 1280)
    ((#\a . #\$) . 1279) ((#\c . #\h) . 1273) ((#\u . #\s) . 1258)
    ((#\h . #\e) . 1250) ((#\n . #\d) . 1238) ((#\n . #\a) . 1238)
    ((#\$ . #\i) . 1221) ((#\$ . #\e) . 1216) ((#\e . #\t) . 1202)
    ((#\$ . #\h) . 1192) ((#\o . #\l) . 1170) ((#\c . #\e) . 1160)
    ((#\i . #\a) . 1146) ((#\o . #\u) . 1144) ((#\v . #\e) . 1132)
    ((#\d . #\i) . 1126) ((#\n . #\i) . 1110) ((#\s . #\i) . 1107)
    ((#\b . #\l) . 1085) ((#\$ . #\f) . 1085) ((#\e . #\a) . 1083)
    ((#\l . #\l) . 1079) ((#\l . #\o) . 1073) ((#\u . #\r) . 1050)
    ((#\a . #\c) . 1045) ((#\t . #\h) . 1035) ((#\p . #\e) . 1023)
    ((#\a . #\b) . 1019) ((#\h . #\a) . 1012) ((#\$ . #\g) . 1007)
    ((#\a . #\s) . 1005) ((#\o . #\m) . 998) ((#\i . #\l) . 994)
    ((#\m . #\i) . 984) ((#\$ . #\u) . 969) ((#\n . #\c) . 963)
    ((#\c . #\$) . 922) ((#\h . #\o) . 918) ((#\m . #\$) . 895)
    ((#\e . #\d) . 889) ((#\g . #\e) . 882) ((#\e . #\c) . 881)
    ((#\s . #\h) . 871) ((#\$ . #\l) . 855) ((#\s . #\s) . 851)
    ((#\h . #\$) . 833) ((#\p . #\r) . 824) ((#\n . #\g) . 812)
    ((#\m . #\o) . 800) ((#\u . #\l) . 787) ((#\a . #\m) . 781)
    ((#\p . #\a) . 776) ((#\n . #\s) . 771) ((#\p . #\o) . 770)
    ((#\c . #\t) . 768) ((#\h . #\i) . 757) ((#\a . #\d) . 744)
    ((#\e . #\m) . 742) ((#\n . #\o) . 736) ((#\b . #\e) . 727)
    ((#\r . #\t) . 727) ((#\o . #\s) . 719) ((#\r . #\y) . 711)
    ((#\i . #\d) . 704) ((#\$ . #\w) . 703) ((#\o . #\t) . 701)
    ((#\s . #\o) . 674) ((#\b . #\a) . 673) ((#\$ . #\o) . 672)
    ((#\$ . #\n) . 662) ((#\c . #\i) . 656) ((#\u . #\t) . 654)
    ((#\s . #\a) . 650) ((#\i . #\m) . 644) ((#\k . #\$) . 632)
    ((#\s . #\c) . 629) ((#\p . #\h) . 628) ((#\i . #\e) . 626)
    ((#\c . #\k) . 616) ((#\a . #\p) . 600) ((#\s . #\u) . 595)
    ((#\b . #\o) . 590) ((#\a . #\i) . 588) ((#\o . #\p) . 583)
    ((#\i . #\r) . 582) ((#\t . #\y) . 571) ((#\u . #\m) . 563)
    ((#\a . #\g) . 560) ((#\o . #\o) . 560) ((#\o . #\c) . 560)
    ((#\m . #\p) . 559) ((#\t . #\u) . 548) ((#\c . #\r) . 546)
    ((#\s . #\p) . 545) ((#\i . #\g) . 537) ((#\e . #\e) . 533)
    ((#\o . #\$) . 531) ((#\g . #\a) . 526) ((#\g . #\r) . 526)
    ((#\v . #\i) . 520) ((#\g . #\$) . 512) ((#\d . #\o) . 509)
    ((#\d . #\a) . 508) ((#\k . #\e) . 502) ((#\o . #\g) . 499)
    ((#\p . #\i) . 490) ((#\w . #\a) . 487) ((#\$ . #\v) . 486)
    ((#\p . #\l) . 481) ((#\b . #\r) . 480) ((#\r . #\d) . 480)
    ((#\r . #\u) . 478) ((#\t . #\t) . 474) ((#\e . #\p) . 474)
    ((#\c . #\u) . 471) ((#\b . #\i) . 469) ((#\i . #\v) . 456)
    ((#\a . #\u) . 455) ((#\l . #\u) . 449) ((#\o . #\d) . 448)
    ((#\f . #\i) . 445) ((#\r . #\m) . 442) ((#\r . #\s) . 432)
    ((#\v . #\a) . 425) ((#\r . #\r) . 419) ((#\b . #\u) . 418)
    ((#\s . #\m) . 418) ((#\o . #\w) . 415) ((#\p . #\$) . 414)
    ((#\f . #\o) . 413) ((#\q . #\u) . 404) ((#\$ . #\k) . 396)
    ((#\e . #\x) . 393) ((#\c . #\l) . 392) ((#\i . #\p) . 373)
    ((#\g . #\i) . 371) ((#\$ . #\j) . 358) ((#\r . #\n) . 353)
    ((#\i . #\b) . 348) ((#\f . #\e) . 348) ((#\g . #\o) . 348)
    ((#\n . #\n) . 347) ((#\u . #\c) . 347) ((#\r . #\c) . 344)
    ((#\o . #\v) . 342) ((#\d . #\r) . 334) ((#\u . #\e) . 319)
    ((#\w . #\i) . 319) ((#\e . #\g) . 316) ((#\i . #\$) . 313)
    ((#\g . #\h) . 310) ((#\a . #\y) . 304) ((#\e . #\v) . 304)
    ((#\a . #\v) . 301) ((#\r . #\g) . 300) ((#\e . #\f) . 300)
    ((#\f . #\a) . 298) ((#\u . #\i) . 298) ((#\u . #\p) . 298)
    ((#\g . #\u) . 298) ((#\e . #\i) . 297) ((#\d . #\u) . 297)
    ((#\l . #\y) . 293) ((#\l . #\t) . 293) ((#\m . #\b) . 292)
    ((#\f . #\f) . 292) ((#\i . #\f) . 291) ((#\u . #\a) . 291)
    ((#\u . #\b) . 287) ((#\h . #\y) . 286) ((#\f . #\u) . 285)
    ((#\m . #\u) . 284) ((#\u . #\d) . 282) ((#\o . #\i) . 274)
    ((#\p . #\t) . 273) ((#\l . #\d) . 272) ((#\e . #\y) . 271)
    ((#\e . #\o) . 270) ((#\f . #\l) . 270) ((#\k . #\i) . 268)
    ((#\o . #\b) . 267) ((#\p . #\u) . 266) ((#\f . #\r) . 265)
    ((#\w . #\o) . 265) ((#\o . #\a) . 262) ((#\w . #\e) . 257)
    ((#\h . #\u) . 250) ((#\a . #\k) . 246) ((#\n . #\u) . 242)
    ((#\p . #\p) . 242) ((#\e . #\w) . 239) ((#\n . #\f) . 235)
    ((#\s . #\y) . 231) ((#\g . #\l) . 230) ((#\m . #\m) . 223)
    ((#\u . #\g) . 217) ((#\h . #\r) . 216) ((#\r . #\l) . 214)
    ((#\r . #\b) . 213) ((#\z . #\e) . 212) ((#\k . #\a) . 211)
    ((#\c . #\y) . 209) ((#\w . #\$) . 209) ((#\e . #\b) . 207)
    ((#\e . #\u) . 205) ((#\h . #\t) . 203) ((#\r . #\p) . 201)
    ((#\v . #\o) . 198) ((#\s . #\l) . 190) ((#\r . #\k) . 190)
    ((#\a . #\w) . 187) ((#\n . #\k) . 186) ((#\t . #\l) . 179)
    ((#\a . #\f) . 177) ((#\s . #\k) . 176) ((#\n . #\y) . 170)
    ((#\c . #\c) . 168) ((#\i . #\u) . 167) ((#\i . #\z) . 166)
    ((#\g . #\n) . 166) ((#\d . #\y) . 164) ((#\p . #\s) . 162)
    ((#\f . #\$) . 160) ((#\o . #\f) . 160) ((#\j . #\u) . 160)
    ((#\g . #\y) . 154) ((#\o . #\k) . 153) ((#\t . #\c) . 153)
    ((#\y . #\s) . 148) ((#\x . #\$) . 145) ((#\d . #\l) . 142)
    ((#\d . #\d) . 141) ((#\n . #\v) . 140) ((#\y . #\a) . 139)
    ((#\o . #\e) . 138) ((#\w . #\h) . 137) ((#\y . #\p) . 136)
    ((#\b . #\$) . 136) ((#\y . #\l) . 134) ((#\s . #\w) . 134)
    ((#\a . #\h) . 134) ((#\r . #\v) . 134) ((#\y . #\n) . 133)
    ((#\$ . #\q) . 130) ((#\l . #\s) . 128) ((#\y . #\m) . 127)
    ((#\j . #\o) . 124) ((#\o . #\y) . 119) ((#\w . #\n) . 118)
    ((#\j . #\a) . 117) ((#\j . #\e) . 115) ((#\d . #\g) . 113)
    ((#\b . #\s) . 113) ((#\x . #\i) . 113) ((#\d . #\s) . 111)
    ((#\$ . #\y) . 111) ((#\y . #\c) . 109) ((#\b . #\b) . 108)
    ((#\t . #\s) . 108) ((#\m . #\y) . 106) ((#\l . #\m) . 105)
    ((#\f . #\t) . 102) ((#\k . #\l) . 101) ((#\x . #\t) . 100)
    ((#\k . #\y) . 100) ((#\e . #\h) . 99) ((#\f . #\y) . 99)
    ((#\p . #\y) . 98) ((#\l . #\v) . 98) ((#\u . #\$) . 96)
    ((#\y . #\r) . 96) ((#\x . #\p) . 96) ((#\g . #\g) . 95)
    ((#\y . #\e) . 95) ((#\o . #\x) . 94) ((#\n . #\h) . 94)
    ((#\y . #\o) . 93) ((#\r . #\f) . 92) ((#\a . #\z) . 92)
    ((#\h . #\m) . 91) ((#\z . #\a) . 91) ((#\l . #\f) . 90)
    ((#\i . #\k) . 89) ((#\z . #\$) . 87) ((#\b . #\y) . 86)
    ((#\k . #\o) . 85) ((#\s . #\n) . 84) ((#\a . #\e) . 83)
    ((#\t . #\m) . 82) ((#\n . #\b) . 82) ((#\n . #\l) . 82)
    ((#\t . #\w) . 81) ((#\u . #\o) . 81) ((#\n . #\r) . 81)
    ((#\l . #\k) . 79) ((#\l . #\p) . 79) ((#\r . #\h) . 79)
    ((#\l . #\c) . 77) ((#\u . #\f) . 77) ((#\e . #\q) . 76)
    ((#\l . #\b) . 76) ((#\$ . #\z) . 76) ((#\a . #\x) . 75)
    ((#\n . #\p) . 75) ((#\m . #\c) . 74) ((#\w . #\r) . 73)
    ((#\n . #\m) . 71) ((#\y . #\t) . 70) ((#\h . #\l) . 69)
    ((#\r . #\w) . 67) ((#\y . #\d) . 66) ((#\k . #\n) . 66)
    ((#\s . #\b) . 64) ((#\d . #\w) . 64) ((#\i . #\x) . 63)
    ((#\o . #\h) . 62) ((#\k . #\s) . 60) ((#\l . #\g) . 59)
    ((#\t . #\z) . 59) ((#\m . #\s) . 59) ((#\z . #\o) . 58)
    ((#\d . #\m) . 58) ((#\e . #\k) . 55) ((#\s . #\q) . 55)
    ((#\h . #\n) . 54) ((#\w . #\l) . 54) ((#\x . #\e) . 51)
    ((#\t . #\f) . 51) ((#\z . #\i) . 50) ((#\g . #\s) . 50)
    ((#\n . #\w) . 50) ((#\e . #\z) . 49) ((#\g . #\m) . 48)
    ((#\x . #\c) . 48) ((#\d . #\b) . 47) ((#\k . #\u) . 46)
    ((#\s . #\f) . 44) ((#\z . #\z) . 44) ((#\n . #\j) . 43)
    ((#\h . #\w) . 43) ((#\x . #\a) . 43) ((#\m . #\n) . 43)
    ((#\v . #\$) . 42) ((#\i . #\q) . 41) ((#\g . #\t) . 41)
    ((#\d . #\h) . 40) ((#\k . #\r) . 39) ((#\w . #\s) . 39)
    ((#\n . #\z) . 37) ((#\d . #\v) . 36) ((#\u . #\x) . 35)
    ((#\y . #\b) . 35) ((#\x . #\o) . 34) ((#\h . #\b) . 33)
    ((#\n . #\q) . 33) ((#\u . #\k) . 32) ((#\o . #\z) . 31)
    ((#\k . #\w) . 30) ((#\y . #\g) . 30) ((#\t . #\n) . 30)
    ((#\y . #\w) . 30) ((#\k . #\h) . 29) ((#\t . #\b) . 29)
    ((#\d . #\n) . 28) ((#\j . #\i) . 28) ((#\$ . #\x) . 28)
    ((#\a . #\o) . 27) ((#\d . #\f) . 27) ((#\u . #\v) . 27)
    ((#\u . #\z) . 27) ((#\l . #\h) . 27) ((#\b . #\t) . 27)
    ((#\d . #\j) . 27) ((#\s . #\r) . 26) ((#\l . #\w) . 25)
    ((#\w . #\d) . 25) ((#\s . #\d) . 25) ((#\w . #\b) . 25)
    ((#\k . #\b) . 24) ((#\d . #\t) . 24) ((#\y . #\i) . 24)
    ((#\x . #\y) . 24) ((#\i . #\i) . 24) ((#\z . #\y) . 23)
    ((#\e . #\j) . 23) ((#\p . #\m) . 23) ((#\m . #\l) . 23)
    ((#\w . #\y) . 23) ((#\z . #\l) . 22) ((#\s . #\g) . 22)
    ((#\h . #\s) . 22) ((#\a . #\a) . 22) ((#\c . #\s) . 21)
    ((#\d . #\p) . 21) ((#\c . #\q) . 21) ((#\k . #\m) . 21)
    ((#\m . #\f) . 20) ((#\v . #\y) . 20) ((#\i . #\j) . 20)
    ((#\a . #\j) . 20) ((#\h . #\f) . 20) ((#\b . #\d) . 20)
    ((#\b . #\c) . 20) ((#\w . #\m) . 19) ((#\t . #\p) . 19)
    ((#\l . #\r) . 19) ((#\d . #\c) . 19) ((#\y . #\h) . 19)
    ((#\y . #\u) . 19) ((#\k . #\t) . 18) ((#\a . #\q) . 18)
    ((#\x . #\u) . 17) ((#\s . #\v) . 17) ((#\v . #\u) . 17)
    ((#\b . #\m) . 16) ((#\t . #\g) . 16) ((#\k . #\p) . 15)
    ((#\z . #\u) . 15) ((#\p . #\b) . 15) ((#\i . #\h) . 15)
    ((#\w . #\u) . 14) ((#\w . #\k) . 14) ((#\x . #\h) . 14)
    ((#\o . #\j) . 14) ((#\b . #\j) . 14) ((#\w . #\f) . 13)
    ((#\c . #\d) . 13) ((#\o . #\q) . 13) ((#\g . #\b) . 13)
    ((#\w . #\t) . 13) ((#\y . #\z) . 12) ((#\l . #\n) . 12)
    ((#\u . #\y) . 12) ((#\c . #\n) . 12) ((#\f . #\s) . 11)
    ((#\h . #\p) . 11) ((#\k . #\d) . 11) ((#\p . #\f) . 11)
    ((#\g . #\w) . 11) ((#\u . #\h) . 10) ((#\y . #\f) . 10)
    ((#\h . #\d) . 10) ((#\r . #\z) . 9) ((#\i . #\w) . 9)
    ((#\u . #\j) . 9) ((#\m . #\w) . 9) ((#\y . #\k) . 9)
    ((#\t . #\v) . 9) ((#\v . #\r) . 9) ((#\n . #\x) . 9)
    ((#\f . #\m) . 9) ((#\g . #\d) . 9) ((#\w . #\p) . 9)
    ((#\m . #\t) . 9) ((#\g . #\f) . 9) ((#\t . #\k) . 9)
    ((#\c . #\m) . 9) ((#\b . #\n) . 9) ((#\c . #\g) . 9)
    ((#\b . #\h) . 9) ((#\k . #\k) . 8) ((#\h . #\h) . 8)
    ((#\t . #\d) . 8) ((#\g . #\p) . 8) ((#\c . #\z) . 8)
    ((#\k . #\f) . 8) ((#\p . #\n) . 8) ((#\z . #\h) . 8)
    ((#\r . #\j) . 8) ((#\m . #\h) . 8) ((#\s . #\z) . 8)
    ((#\r . #\q) . 8) ((#\p . #\w) . 8) ((#\x . #\x) . 7)
    ((#\w . #\c) . 7) ((#\p . #\k) . 7) ((#\h . #\c) . 7)
    ((#\y . #\v) . 7) ((#\b . #\p) . 7) ((#\x . #\v) . 7)
    ((#\l . #\z) . 7) ((#\p . #\d) . 7) ((#\s . #\j) . 6)
    ((#\v . #\s) . 6) ((#\m . #\r) . 6) ((#\b . #\f) . 6)
    ((#\h . #\g) . 6) ((#\i . #\y) . 6) ((#\g . #\k) . 6)
    ((#\b . #\v) . 6) ((#\r . #\x) . 6) ((#\c . #\p) . 5)
    ((#\f . #\b) . 5) ((#\m . #\d) . 5) ((#\h . #\k) . 5)
    ((#\b . #\w) . 5) ((#\p . #\c) . 5) ((#\k . #\c) . 5)
    ((#\v . #\l) . 5) ((#\u . #\q) . 5) ((#\u . #\w) . 4)
    ((#\p . #\g) . 4) ((#\d . #\z) . 4) ((#\f . #\c) . 3)
    ((#\z . #\w) . 3) ((#\x . #\w) . 3) ((#\f . #\d) . 3)
    ((#\z . #\m) . 3) ((#\f . #\h) . 3) ((#\v . #\d) . 3)
    ((#\u . #\u) . 3) ((#\k . #\j) . 3) ((#\f . #\n) . 3)
    ((#\z . #\t) . 3) ((#\q . #\$) . 3) ((#\l . #\j) . 3)
    ((#\x . #\l) . 3) ((#\k . #\v) . 3) ((#\y . #\x) . 3)
    ((#\z . #\b) . 3) ((#\f . #\g) . 3) ((#\b . #\g) . 3)
    ((#\d . #\k) . 3) ((#\g . #\c) . 2) ((#\j . #\$) . 2)
    ((#\x . #\g) . 2) ((#\g . #\z) . 2) ((#\z . #\g) . 2)
    ((#\f . #\w) . 2) ((#\z . #\r) . 2) ((#\d . #\q) . 2)
    ((#\y . #\q) . 2) ((#\z . #\v) . 2) ((#\x . #\s) . 2)
    ((#\f . #\k) . 2) ((#\b . #\x) . 2) ((#\c . #\b) . 2)
    ((#\m . #\v) . 2) ((#\c . #\f) . 2) ((#\q . #\i) . 2)
    ((#\m . #\k) . 2) ((#\m . #\q) . 2) ((#\x . #\f) . 2)
    ((#\k . #\g) . 2) ((#\q . #\a) . 2) ((#\v . #\g) . 2)
    ((#\p . #\q) . 1) ((#\z . #\d) . 1) ((#\p . #\z) . 1)
    ((#\h . #\v) . 1) ((#\w . #\g) . 1) ((#\z . #\s) . 1)
    ((#\y . #\y) . 1) ((#\j . #\m) . 1) ((#\j . #\y) . 1)
    ((#\x . #\z) . 1) ((#\w . #\z) . 1) ((#\x . #\n) . 1)
    ((#\f . #\j) . 1) ((#\z . #\n) . 1) ((#\z . #\p) . 1)
    ((#\q . #\o) . 1) ((#\x . #\q) . 1) ((#\j . #\s) . 1)
    ((#\h . #\q) . 1) ((#\j . #\n) . 1) ((#\g . #\q) . 1)
    ((#\x . #\b) . 1) ((#\v . #\t) . 1) ((#\v . #\p) . 1)
    ((#\z . #\k) . 1) ((#\v . #\v) . 1) ((#\k . #\q) . 1)
    ((#\w . #\w) . 1) ((#\p . #\j) . 1) ((#\m . #\g) . 1)
    ((#\y . #\j) . 1) ((#\v . #\k) . 1) ((#\z . #\q) . 1)
    ((#\j . #\k) . 1)))

;;; The SCORE-DIGRAPH procedure returns the relative frequency of a given
;;; letter-pair.  If the frequency is listed in the table above, that
;;; frequency is returned; otherwise, 0 is returned.

(define score-digraph
  (lambda (left right)
    (let ((table-value (assoc (cons left right) digraph-frequencies)))
      (if table-value (cdr table-value) 0))))