413 - PurelyFunctional.tv Newsletter

00 Minimum steps to palindrome.md

Minimum steps to palindrome

A string is a palindrome if it is equal to its reverse.

(= "racecar" (str/reverse "racecar")) ;=> true, so palindrome

Your task is to write a function that adds a minimum of letters to the end of a string to make it a palindrome.

Examples

(->palindrome "race") ;=> "racecar"
(->palindrome "mad") ;=> "madam"
(->palindrome "mirror") ;=> "mirrorrim"

Note: the generated string does not have to be a real English word.

Thanks to this site for the challenge idea where it is considered Expert in JavaScript. The problem has been modified from the original.

Please submit your solutions as comments on this gist.

(ns tst.demo.core
  (:use tupelo.core tupelo.test)
  (:require
    [schema.core :as s]
    [tupelo.string :as str]))

(s/defn palindome? :- s/Bool
  [arg :- s/Str] (= arg (str/reverse arg)))

(dotest
  (is (palindome? "racecar"))
  (isnt (palindome? "racecar9")))

(s/defn ->palindrome :- s/Str
  [orig :- s/Str]
  (loop [cnt 0]
    (let [extra-chars (str/join (reverse (take cnt orig)))
          candidate   (str orig extra-chars)]
      (if (palindome? candidate)
        candidate
        (recur (inc cnt))))))

(dotest
  (is= (->palindrome "race") "racecar")
  (is= (->palindrome "mad") "madam")
  (is= (->palindrome "mirror") "mirrorrim"))

Today I (and my entire company) learned about reductions

Refactoring some other solutions to use transducers:

(defn ->palindrome [s]
  (let [r (str/reverse s)]
    (first (sequence (comp (map #(str (subs s 0 %) r))
                           (filter #(str/starts-with? % s))
                           (take 1))
                     (range (count s))))))

(defn palindrome? [w] (= (seq w) (reverse w)))
(defn ->palindrome [w]
  "Return `w` with minimum number of letters added to end to make it a palindrome"
  (let [possible-endings (->> (range (count w))
                              (map #(take % w))
                              (map reverse))
        possible-palindromes (->> possible-endings
                                  (map (partial concat w))
                                  (map (partial apply str))
                                  (filter palindrome?))]
    (first possible-palindromes)))

Somewhat reduced:

(defn palindrome? [w] (= (seq w) (reverse w)))
(defn ->palindrome [w]
   (->> (reductions conj '() w)
        (map #(concat w %))
        (filter palindrome?)
        (first)
        (apply str)))

A little late to this one, but similar to the others above:

(defn palin? [s]
  (= (seq s) (reverse s)))

(defn ->palindrome [s]
  (->> s reverse rest (reductions str s) (filter palin?) first))

;; (->palindrome "race") ;; => "racecar"
;; (->palindrome "mad") ;; => "madam"
;; (->palindrome "mirror") ;; => "mirrororrim"

(defn ->palindrome [string]
  (->> (range 1 (count string))
       (map #(str string (str/reverse (subs string 0 %))))
       (some #(#{%} (str/reverse %)))))