#lang racket

(define (nand-gate a b)
  (if (and (= a 1) (= b 1)) 0 1))

(define (not-gate a)
  (nand-gate a a))

(define (and-gate a b)
  (not-gate (nand-gate a b)))

(define (or-gate a b)
  (nand-gate (not-gate a) (not-gate b)))

(define (xor-gate a b)
  (or-gate (and-gate a (not-gate b))
           (and-gate (not-gate a) b)))

(define (eq-gate a b)
  (not-gate (xor-gate a b)))

(define (add1 a b c-in)
  (let ([res   (xor-gate c-in (xor-gate a b))]
        [c-out (or-gate (and-gate a b)
                        (and-gate (xor-gate a b) c-in))])
    (values res c-out)))

(define (addN as bs)
  (if (= (length as) (length bs))
      (let rec ([c 0] [a (reverse as)] [b (reverse bs)] [n (length as)] [res (list)])
        (if (zero? n) (reverse res)
            (let-values ([(res-bit c-tmp) (add1 (car a) (car b) c)])
              (rec c-tmp (cdr a) (cdr b) (- n 1) (append res (list res-bit))))))
      (error "List must have same lengths.")))

(define (complementN as)
  (addN (map (lambda (x) (not-gate x)) as)
        (let* ([len (length as)]
               [len1 (- len 1)])
          (for/list ([i (in-range len)]) (if (= len1 i) 1 0)))))

(define (subN as bs)
  (addN as (complementN bs)))

(define (eqN as bs)
  (if (= (length as) (length bs))
      (let recur ([state 1] [n (length as)])
        (if (zero? n) state
            (recur (and-gate state
                             (eq-gate (list-ref as (- n 1))
                                      (list-ref bs (- n 1))))
              (- n 1))))
      (error "List must have same lengths.")))

(define (fibN n)
  (let* ([len (length n)]
         [len1 (- len 1)]
         [zeroN (for/list ([i (in-range len)]) 0)]
         [oneN  (for/list ([i (in-range len)]) (if (= len1 i) 1 0))]
         [checkN (or-gate (eqN n zeroN) (eqN n oneN))])
    (if (= 1 checkN) n
        (let* ([n1 (subN n oneN)]
               [n2 (subN n1 oneN)])
          (addN (fibN n1) (fibN n2))))))

(define (fromN n)
  (let ([len (length n)])
    (for/sum ([i (in-range len)]) (* (list-ref n (- len i 1)) (expt 2 i)))))

(define (verbose-fibN n)
  (format "~a : ~a" (fromN n) (fromN (fibN n))))

; (verbose-fibN (list 0 0 0 1 0 1 0 1))
; => "21 : 194"