#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) (if (zero? c)
                          (reverse res)
                          (append (list c) (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))))))
      (let ([max-len (max (length as) (length bs))])
        (addN (append (for/list ([i (in-range (- max-len (length as)))]) 0) as)
              (append (for/list ([i (in-range (- max-len (length bs)))]) 0) bs)))))

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

(define (subN as bs)
  (let ([bits (max (length as) (length bs))])
    (reverse (take (reverse (addN as (complementN bs bits))) bits))))

(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))))
      (let ([max-len (max (length as) (length bs))])
        (eqN (append (for/list ([i (in-range (- max-len (length as)))]) 0) as)
             (append (for/list ([i (in-range (- max-len (length bs)))]) 0) bs)))))

(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 (toN n)
  (let rec ([x n] [res (list)])
    (if (zero? x)
        (append (list 0) res)
        (rec (floor (/ x 2)) (append (list (modulo x 2)) res)))))

(define (verbose-fibN x)
  (let ([n (toN x)])
    (format "~a : ~a" x (fromN (fibN n)))))