425 PurelyFunctional.tv Newsletter

00 Closest Palindrome Integer.md

Closest palindrome integer

An integer is a palindrome if it is written with the same decimal digits forward and backward. Your job is to write a function that takes an integer and returns the closes palindrome integer to it. The closest one could be larger or smaller than the given integer.

Examples

(closest-palindrome 100) ;=> 99 (return the smaller in case of tie)
(closest-palindrome 887) ;=> 888
(closest-palindrome 888) ;=> 888

Note: If two palindromes are equidistant from the given integer, return the smallest. If the given integer is itself a palindrome, return it.

Thanks to this site for the problem idea, where it is rated Hard in Ruby. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

(defn palindrome? [s]
 (= (seq (str s)) (reverse (str s))))

(defn closest-palindrome [n]
  (loop [inc-n n
         dec-n n]
   (cond
     (palindrome? dec-n) dec-n
     (palindrome? inc-n) inc-n
     :else (recur (inc inc-n) (dec dec-n)))))

(defn not-palindrome? [n]
  (let [x' (str n)]
    (not (= x' (clojure.string/reverse x')))))

(defn closest-palindrome [n]
  (->> (mapcat #(vector (- n %) (+ n %)) (range))
       (drop-while not-palindrome?)
       (first)))

For large numbers, brute force searching may not be viable. Here is a solution which uses string manipulation instead of searching:

(defn abs [n]
  (if (neg? n) (- n) n))

(defn closest-smallest-integer [n xs]
  (apply min-key #(abs (- n % 0.1)) xs))

(defn closest-palindrome [n]
  (if (< n 10)
    n
    (let [s (str n)
          low-digits-length (quot (count s) 2)
          n-high-digits (read-string (subs s 0 (- (count s) low-digits-length)))
          palindromes (for [high (take 3 (iterate inc (dec n-high-digits)))
                            :let [high' (if (zero? high) "" (str high))
                                  low' (clojure.string/reverse (subs (str high' "9") 0 low-digits-length))]]
                        (read-string (str high' low')))]
      (closest-smallest-integer n palindromes))))

Not the most efficient solution possible, but was playing around with lazy-seqs and it felt fun.

(defn interleave-all [& colls]
  "Interleave collections yielding the first from each collection,
   then the second, ect. until all collections are exhausted."
  (lazy-seq
   (cond (empty? colls) '()
         (empty? (first colls)) (apply interleave-all (rest colls))
         :else (cons (ffirst colls)
                     (apply interleave-all
                      (conj (vec (rest colls))
                            (rest (first colls))))))))

(defn reverse-num [x]
  "Reverse digits of a number preserving sign."
  (loop [num x, agg 0]
    (if (= num 0) agg
        (recur (quot num 10)
               (+' (*' agg 10) (rem num 10))))))

(defn palindrome? [x]
  (and (<= 0 x) (= x (reverse-num x))))

(defn numbers-around [x]
  (interleave-all [x]
                  (iterate dec (dec x))
                  (iterate inc (inc x))))

(defn closest-palindrome [x]
  (->> (numbers-around x)
       (filter palindrome?)
       (first)))

(defn palindrome? [x] (let [s (seq (str x))] (= s (reverse s))))

(defn closest-palindrome
  ([x] (if (palindrome? x) x (closest-palindrome (dec x) (inc x))))
  ([x y] (if-let [p (first (drop-while (comp not palindrome?) [x y]))]
           p
           (closest-palindrome (dec x) (inc y)))))

(defn closest-palindrome [n]
  (letfn [(pn? [n] (= (seq (str n)) (reverse (str n))))
          (pnpr? [[a b]] (cond (and (pn? a) (pn? b)) (min a b)
                               (pn? a) a (pn? b) b))]
    (first (keep pnpr? (iterate (fn [[a b]] [(dec a) (inc b)]) [n n])))))

Sorry for the length - but implementing digitization with a transducer was fun:

(defn until [pred]
  (fn [rf]
    (completing 
     (fn 
       ([acc x]
        (if (pred x)
          (reduced acc)
          (rf acc x))))
     rf)))

(defn descending-divisors [limit]
  (->> 1 (iterate (partial * 10))
       (into () (until #(< limit %)))))

(defn digits [n]
  (->> (or (and (pos? n) n) (- n)) 
       descending-divisors 
       (reduce (fn [[digs r] q]
                 [(conj digs (quot r q)) 
                  (rem r q)])
               [[] n])
       first))

(defn palindrome? [xs]
  (if (> 2 (count xs))
    true
    (let [fx (first xs) 
          lx (last xs)]
      (and (= fx lx) 
           (palindrome? (-> xs rest butlast))))))

(defn palindrome-int? [n]
  (palindrome? (digits n)))

(defn closest-palindrome [n]
  (->> n (repeat 2) 
       (iterate (juxt #(dec (first %)) 
                      #(inc (second %))))
       (reduce (fn [_ [low hi]]
                 (cond 
                   (palindrome-int? low) 
                   (reduced low)
                   (palindrome-int? hi)
                   (reduced hi)
                   :else nil))
               nil)))

(defn palindrome
  "Accepts a number, returning it back if it's palindromic. Otherwise, returns nil."
  [el]
  (let [el' (seq (str el))]
    (when (= el' (reverse el')) el)))

(defn closest
  ([sole] (closest sole sole))
  ([a  b] (or (palindrome a)
              (palindrome b)
              (recur (dec a) (inc b)))))

(defn palindrome? [n]
 (= (seq (str n)) (reverse (seq(str n)))))

(defn small-palindrome [n]
  (if (palindrome? n)
    n
    (small-palindrome (dec n))))

(defn large-palindrome [n]
  (if (palindrome? n)
    n
    (large-palindrome (inc n))))

(defn closest-palindrome [n]
  (let [small (small-palindrome n)]
  (let [large (large-palindrome n)]
    ;large is always > n and small is always < n
    ;return small in case of tie
    (if (<= 
          (- n small)
          (- large n))
      small
      large))))

I felt like there should be an easy way to do this without needing to defn large-palindrome and small-palindrome, but I didn't see it.

That was a fun exercise!

(require '[clojure.string :as str])

(defn palindrome? [a]
   (= (str a) (str/reverse (str a))))

(defn closest-palindrome [x]
  (let [greater (iterate inc x)
        less (rest (iterate dec x))]
    (->> (interleave greater less)
         (filter palindrome?)
         (first))))

Here's an ugly but pretty fast implementation using Java interop and string manipulation. Try timing with some tests like (closest-palindrome 128180) ==> 127721

(defn closest-palindrome [n]
  (let [abs (fn [x] (if (neg? x) (- x) x))
        guess (fn [n]
                (let [s (str n)
                      sb (StringBuilder. s)
                      hlen (quot (.length sb) 2)]
                  (Long/parseLong (-> sb .reverse
                                      (.replace 0 hlen (subs s 0 hlen)) .toString))))]
      (let [g (guess n)
            diff (- g n)]
        (if (zero? diff)
          n
          (let [g2 (guess (- n diff))
                ad (abs diff)
                ad2 (abs (- g2 n))]
            (if (= ad ad2)
              (min g g2)
              (if (< ad ad2) g g2)))))))

(defn palindrome? [n]
  (let [n (Math/abs n)
        s (str n)]
    (= (seq s) (reverse s))))

(defn numbers-up [n]
  (iterate inc (inc n)))

(defn numbers-down [n]
  (iterate dec (dec n)))

(defn closest-palindrome [n]
  (if (palindrome? n)
    n
    (let [f1 (future  (first (filter palindrome? (numbers-up   n))))
          f2 (future  (first (filter palindrome? (numbers-down n))))]
      (->> [@f1 @f2]
           (map (fn [v] [(Math/abs (- n v)) v])) ; => [[distance-from-n palindrome]]
           sort
           first
           second))))

Another approach without reversing strings, and trying to be as lazy as possible:

(defn palin? [^Long n]
  (loop [reminder n, reversed 0]
    (if (zero? reminder)
      (= reversed n)
      (recur (quot reminder 10) (+ (* reversed 10) (mod reminder 10))))))

(defn closest-palindrome [^Long n]
  (let [ascending  (drop n (range))
        descending (concat (range (dec n) -1 -1) (repeat nil))]
    (->> (interleave ascending descending)
         (remove nil?)
         (filter palin?)
         first)))

;; (closest-palindrome 100) ;; => 99
;; (closest-palindrome 887) ;; => 888
;; (closest-palindrome 888) ;; => 888

ascending is a range of numbers starting at n, and descending is the list of n-1, n-2 ... until 0 then nil repeated over and over. I interleave both so check for palindromes on n, n-1, n+1, n-2, n+2 ... and so on. We don't want to check palindromes on negative numbers but we need to try ascending numbers even after the descending sequence reaches 0, so I append nils which are removed after the interleave.

(defn palindrome? [i]
  (let [digits (seq (str i))]
    (= digits (reverse digits))))

(defn closest-palindrome [i]
  (->> (interleave (iterate dec i) (iterate inc i))
       (drop-while (complement palindrome?))
       first))