gistfile1.rkt

#lang scheme

(require racket/sequence)

(provide positions)
(provide lowers)
(provide count)
(provide let->int)
(provide int->let)
(provide shift)
(provide table)
(provide percent)
(provide freqs)
(provide char-range)
(provide int-range)
(provide zip)
(provide chisqr)
(provide rotate)

(provide encode)
(provide crack)

(define (positions x xs)
  (define (equal-x pair)
    (equal? x (first pair)))

  (let ([n (- (length xs) 1)])
    (map second
         (filter equal-x
                 (zip xs (int-range 0 n))))))

(define (lowers str)
   (length (filter char-lower-case? (string->list str))))

(define (count c str)
  (define (equal-c x)
    (equal? c x))

  (length (filter equal-c (string->list str))))

(define (let->int c)
  (- (char->integer c) (char->integer #\a)))

(define (int->let n)
  (integer->char (+ (char->integer #\a) n)))

(define (shift n c)
  (if (char-lower-case? c)
      (int->let (modulo (+ n (let->int c)) 26))
      c))

(define (encode n str)
  (list->string (map (lambda (x) (shift n x))
                     (string->list str))))

; table of letter frequency for English
(define table '(8.2 1.5 2.8 4.3
                12.7 2.2 2.0 6.1
                7.0 0.2 0.8 4.0
                2.4 6.7 7.5 1.9
                0.1 6.0 6.3 9.1
                2.8 1.0 2.4 0.2
                2.0 0.1))

(define (percent n m)
  (* 100.0 (/ n m)))

(define (char-range sc ec)
  (map integer->char
       (sequence->list (in-range (char->integer sc)
                                 (+ 1 (char->integer ec))))))

(define (int-range sc ec)
  (sequence->list (in-range sc
                            (+ 1 ec))))

(define (freqs str)
  (let ([n (lowers str)])
    (define (calc x)
      (percent (count x str) n))

    (map calc (char-range #\a #\z))))

(define (zip l1 l2)
  (define (zip-iter a b r)
    (cond [(or (empty? a) (empty? b)) r]
          [else (zip-iter (cdr a)
                          (cdr b)
                          (cons (list (car a) (car b))
                                r))]))

  (reverse (zip-iter l1 l2 '())))

(define (chisqr os es)
  (define (chi pair)
    (let ([o (first pair)]
          [e (second pair)])
      (/ (expt (- o e) 2.0) e)))

  (let ([chis (map chi (zip os es))])
    (foldl + 0 chis)))
    
(define (rotate n xs)
  (let ([start (drop xs n)]
        [end (take xs n)])
    (append start end)))

(define (crack str)
  (let ([str-table (freqs str)])
    (define (apply-chisqr n)
      (chisqr (rotate n str-table) table))

    (let ([chitab (map apply-chisqr (int-range 0 25))])
      (let ([factor (car (positions (foldl min
                                           (first chitab)
                                           chitab)
                                    chitab))])
        (encode (- factor) str)))))