Instantly share code, notes, and snippets.

# ericnormand/00 Minimum steps to palindrome.md

Created February 9, 2021 15:29
Show Gist options
• Save ericnormand/bf1178a04c7b28cdaf26e0fb3257defe to your computer and use it in GitHub Desktop.

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 "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.

```(defn ->palindrome
"Returns a string with the minimum number of letters appended to make s a
palindrome."
[s]
(->> (reductions #(str %2 %1) "" s)
(map (partial str s))
(filter #(= % (str/reverse %)))
first))```

```(defn ->palindrome [s]
(->> (reductions conj '() s)
(map (partial concat (seq s)))
(some #(when (= % (reverse %)) (apply str %)))))```

### steffan-westcott commented Feb 9, 2021

```(require '[clojure.string :as st])

(defn ->palindrome [s]
(->> (reductions str "" s)
(map #(str % (st/reverse s)))
(filter #(st/starts-with? % s))
first))```

### steffan-westcott commented Feb 9, 2021

@jgoodhcg you may want to take another look, in particular the example `mirror`

### jgoodhcg commented Feb 9, 2021

@jgoodhcg you may want to take another look, in particular the example `mirror`

Oh no! How embarrassing 😬
I thought I was so clever for not having to use `reductions`. I'll update my entry.

### diavoletto76 commented Feb 9, 2021

```(defn ->palindrome
([xs] (->palindrome xs 0))
([xs n]
(let [xs' (apply str (concat xs (reverse (take n xs))))]
(if (= xs' (clojure.string/reverse xs'))
xs'
(recur xs (inc n))))))```

### cloojure commented Feb 9, 2021

```(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 "mirror") "mirrorrim"))```

### SneakyPeet commented Feb 10, 2021

Today I (and my entire company) learned about `reductions`

### miner commented Feb 10, 2021

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"
```(defn ->palindrome [string]