Skip to content

Instantly share code, notes, and snippets.

@miner
Created October 2, 2018 20:30
Show Gist options
  • Save miner/0c8ccad10cb8018ab6e49e3de2825d54 to your computer and use it in GitHub Desktop.
Save miner/0c8ccad10cb8018ab6e49e3de2825d54 to your computer and use it in GitHub Desktop.
find longest palindromic substring using Clojure
(ns miner.pal
(:require [criterium.core :as crit]
[clojure.string :as str]))
;; An exercise from Apropos Clojure #18 video cast:
;; https://www.youtube.com/watch?v=elF9BPa0Np4
;;
;; Their solution is something like this...
(defn palindrome? [s]
(= (seq s) (reverse s)))
(defn substrings [s]
(let [mx (inc (count s))]
(for [start (range mx)
end (range (inc start) mx)]
(subs s start end))))
(defn longest-palindrome [s]
"Return the longest substring of s that is a palindrome"
(apply max-key count (filter palindrome? (substrings s))))
;; First improvement: build the strings in length order by slightly rearranging the `for`
;; comprehension.
(defn substrings1 [s]
(let [cnt (count s)]
(for [len (range cnt 0 -1)
start (range (inc (- cnt len)))
:let [end (+ start len)]]
(subs s start end))))
;; The first palindrome found is known to be the longest as the candidates are generated in
;; length order, longest first. The `filter` and `substrings1` are lazy so the process
;; terminates as soon the first palindromic substring is generated. The smaller substrings
;; are not realized.
(defn longest-palindrome1 [s]
"Return the longest substring of s that is a palindrome"
(first (filter palindrome? (substrings1 s))))
;; Second improvement: Use a faster test. It's not obvious but `clojure.string/reverse` is
;; pretty fast (due to Java interop) and beats using Clojure sequences of characters.
(defn palindrome2? [s]
(= s (str/reverse s)))
(defn longest-palindrome2 [s]
(first (filter palindrome2? (substrings1 s))))
;; The fastest implementation is to use Java interop to access characters within the
;; original string without creating new strings. Only the longest palindromic substring
;; needs to be realized. The ^String type annotations help the Clojure compiler pick the
;; correct Java methods.
(defn substr-pal? [^String s start end]
(loop [front start back (dec end)]
(or (>= front back)
(and (= (.charAt s front) (.charAt s back))
(recur (inc front) (dec back))))))
;; fastest
(defn longest-palindrome3 [^String s]
(let [cnt (.length s)]
(first (for [len (range cnt 0 -1)
start (range (inc (- cnt len)))
:let [end (+ start len)]
:when (substr-pal? s start end)]
(subs s start end)))))
(defn smoke-test [palfn]
(let [aman "amanaplanacanalpanama"
junkman (str "aabbccddeeef" aman "xyz")]
(assert (= "a" (palfn "a")))
(assert (= "aba" (palfn "abax")))
(assert (= aman (palfn junkman)))
aman))
(defn demunge [fnx]
(let [s (str fnx)
at (str/last-index-of s "@")
fname (if at (subs s 0 at) s)]
(clojure.main/demunge fname)))
(defn run-benchmarks []
(doseq [palfn [longest-palindrome longest-palindrome1 longest-palindrome2
longest-palindrome3]]
(println "---------------------------")
(println "Testing" (demunge palfn))
(println)
(crit/quick-bench (smoke-test palfn)))
(println "---------------------------"))
@miner
Copy link
Author

miner commented Oct 2, 2018

Criterium benchmarking library is here: https://github.com/hugoduncan/criterium

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment