;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Problem 2: Raising a Number to a Power 
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define slow-exptmod
  (lambda (a b n)
    (if (= b 0)
        1
        (*mod a (slow-exptmod a (- b 1) n) n))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Problem 4: Prime Numbers
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define test-factors
  (lambda (n k)
    (cond ((>= k n) #t)
          ((= (remainder n k) 0) #f)
          (else (test-factors n (+ k 1))))))

(define slow-prime?
  (lambda (n)
    (if (< n 2)
        #f
        (test-factors n 2))))
                                 


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Problem 7: RSA
;;
;; Converting message strings to and from
;; integers.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(define (join-numbers list radix)
  ; Takes a list of numbers (i_0 i_1 i_2 ... i_k)
  ; and returns the number 
  ;    n = i_0 + i_1*radix + i_2*radix2 + ... i_k*radix^k + radix^(k+1)
  ; The last term creates a leading 1, which allows us to distinguish
  ; between lists with trailing zeros.
  (if (null? list)
      1
      (+ (car list) (* radix (join-numbers (cdr list) radix)))))

; test cases
;(join-numbers '(3 20 39 48) 100) ;-> 148392003
;(join-numbers '(5 2 3 5 1 9) 10) ;-> 1915325
;(join-numbers '() 10) ;-> 1


(define (split-number n radix)
  ; Inverse of join-numbers.  Takes a number n generated by
  ; join-numbers and converts it to a list (i_0 i_1 i_2 ... i_k) such
  ; that
  ;    n = i_0 + i_1*radix + i_2*radix2 + ... i_k*radix^k + radix^(k+1)
  (if (<= n 1)
      '()
      (cons (remainder n radix)
            (split-number (quotient n radix) radix))))

; test cases
;(split-number (join-numbers '(3 20 39 48) 100) 100) ;-> (3 20 39 48)
;(split-number (join-numbers '(5 2 3 5 1 9) 10) 10)  ;-> (5 2 3 5 1 9)
;(split-number (join-numbers '() 10) 10) ; -> ()


(define chars->bytes
  ; Takes a list of 16-bit Unicode characters (or 8-bit ASCII
  ; characters) and returns a list of bytes (numbers in the range
  ; [0,255]).  Characters whose code value is greater than 255 are
  ; encoded as a three-byte sequence, 255 <low byte> <high byte>.
  (lambda (chars)
    (if (null? chars)
        '()
        (let ((c (char->integer (car chars))))
          (if (< c 255)
              (cons c (chars->bytes (cdr chars)))
              (let ((lowbyte (remainder c 256))
                    (highbyte  (quotient c 256)))
                (cons 255 (cons lowbyte (cons highbyte (chars->bytes (cdr chars)))))))))))

; test cases
;(chars->bytes (string->list "hello")) ; -> (104 101 108 108 111)
;(chars->bytes (string->list "\u0000\u0000\u0000")) ; -> (0 0 0)
;(chars->bytes (string->list "\u3293\u5953\uabab")) ; -> (255 147 50 255 83 89 255 171 171)


(define bytes->chars
  ; Inverse of chars->bytes.  Takes a list of integers that encodes a
  ; sequence of characters, and returns the corresponding list of
  ; characters.  Integers less than 255 are converted directly to the
  ; corresponding ASCII character, and sequences of 255 <low-byte>
  ; <high-byte> are converted to a 16-bit Unicode character.
  (lambda (bytes)
    (if (null? bytes)
        '()
        (let ((b (car bytes)))
          (if (< b 255)
              (cons (integer->char b)
                    (bytes->chars (cdr bytes)))
              (let ((lowbyte (cadr bytes))
                    (highbyte (caddr bytes)))
                (cons (integer->char (+ lowbyte (* highbyte 256)))
                      (bytes->chars (cdddr bytes)))))))))

; test cases
;(bytes->chars '(104 101 108 108 111)) ; -> (#\h #\e #\l #\l #\o)
;(bytes->chars '(255 147 50 255 83 89 255 171 171)) ; -> (#\u3293 #\u5953 #\uabab)



(define (string->integer string)
  ; returns an integer representation of an arbitrary string. 
  (join-numbers (chars->bytes (string->list string)) 256))

; test cases
;(string->integer "hello, world")
;(string->integer "")
;(string->integer "April is the cruelest month")
;(string->integer "\u0000\u0000\u0000")


(define (integer->string integer)
  ; inverse of string->integer.  Returns the string corresponding to
  ; an integer produced by string->integer.
  (list->string (bytes->chars (split-number integer 256))))

; test cases
;(integer->string (string->integer "hello, world"))
;(integer->string (string->integer ""))
;(integer->string (string->integer "April is the cruelest month"))
;(integer->string (string->integer "\u0000\u0000\u0000"))
;(integer->string (string->integer "\u3293\u5953\uabab"))