LR-task

gistfile1.clj

(ns lr-task.ad-hoc
  (:use clojure.test))

;;; http://dolzhenko.blogspot.com/2012/09/blog-post.html

;; Любая последовательность операторов длины в точности n позволяет
;; получить все числа [-2^n+1 2^n]

;; Индукция по n

;; Будем доказывать более сильное утв.
;; А именно все пары (x, y) имеют след структуру
;; если x > 0 то y = x - 2^k соотв. x [0 .. 2^n] (a)

;; База индукции:
;; n=1 (0, 1) верно

;; Шаг индукции:
;; Пусть для n <= k утв. верно
;; Рассмотрим пары для шага k+1
;; Для каждого числа x > 0 x <= 2^(k+1) необходимо показать, что есть
;; пара полученная не пред шаге, и применение одного из двух операторов
;; позволит получить пару с компонентом равным x (те сделав k+1 шаг) и
;; условием на связь x и y (a)

;; случай а)
;; Если x > 0 and x <= 2^k (те x мало) то, по предположению индукции есть пара с соотв. x
;; и можно применить один из операторов сохраняющий соотв. компонент.
;; Остается проверить, связь (a)

;; Без огр. общности x - первый компонент (иначе аналогично с заменой операторов)
;; R(x,y) = (x,2y-x)
;; x1 = x
;; y1 = 2y-x

;; y1 = 2y-x = 2(x-2^k) - x = 2x - 2^(k+1) - x = x - 2^(k+1)
;; утв. выполнено

;; случай б)
;; x > 2^k но тогда y = x - 2^k т.е. в данном случае y подпадает под предположение индукции.
;; и проводя абсолютно аналогичные расссуждения получим искомое.

(defn L [[a b]] [(- (* 2 a) b) b])

(defn R [[a b]] [a (- (* 2 b) a)])

;;; Task description

;;; Given two operators L and R and starting point (0 1)
;;; There is a sequence of applications of L and R to staring point (a b)
;;; such than a == N or b == N

;;; Find minimal length of such sequence for given N

;;; Limitations:
;;; N [ -2^31 2^31-1 ]
;;; Time o(log(N))
;;; Space o(1)

(defn power-of-two
  "Returns maximal k such that 2^k <= n. Assumed n >= 0"
  [n]
  (letfn [(helper [n result]
            (if (< n 2)
              result
              (recur (quot n 2)
                     (inc result))
              )
            )]
    (helper n 0)
    )
  )

(defn Q [n]
  (cond   
   (zero? n) 0
   (= n Integer/MIN_VALUE) 32
   :else (+ (power-of-two (Math/abs n))
      (if (and (> n 0) (zero? (bit-and n
                                       (dec n))))
        0
        1
        )
      )
   )
  )

; Answer (Q n)

(deftest power-of-two-test
  (are [n answer]
       (= answer (power-of-two n))
       1 0
       2 1
       3 1
       4 2
       )
  )

(deftest Q-tests
  (are [n c]
       (= c (Q n))
       -8 4
       -7 3
       -6 3
       -5 3
       -4 3
       -3 2
       -2 2
       -1 1
       0 0
       1 0
       2 1
       3 2
       4 2
       5 3
       6 3
       7 3
       8 3
       9 4
       21 5
       (Integer/MAX_VALUE) 31
       (Integer/MIN_VALUE) 32
       )
  )