;;
;; Note - I had this palindrome code in my files from an earlier project, but I didn't write.
;; unfortunatly, I've lost the source. This is a nice solution for O(n) time and space
;; complexity

(defn longest-palendrome
  [text]
  (letfn [(final-centers
           [n tcenters centers]
           (cond
            (<= n 1)
            centers
            :default
            (let [n (dec n)]
              (recur n
                     (rest tcenters)
                     (concat (vector
                              (min (first tcenters) n))
                             centers)))))

          (ext-centers
           [strn n centers tcenters cdist]
           (cond
            (= 0 cdist)
            #(ext-tail strn (inc n) 1 centers)
            (= (dec cdist) (first tcenters))
            #(ext-tail strn n (first tcenters) centers)
            true
            #(ext-centers strn n
                          (concat
                           (vector (min (first tcenters) (dec cdist)))
                           centers)
                          (rest tcenters) (dec cdist))))

          (ext-tail
           [strn n curr-tail centers]
           (cond
            (> n (dec (count strn)))
            #(final-centers curr-tail centers
                            (concat (vector curr-tail) centers))
            (= (- n curr-tail) 0)
            #(ext-centers strn n
                          (concat (vector curr-tail) centers)
                          centers curr-tail)
            (= (nth strn n) (nth strn (- n curr-tail 1)))
            #(ext-tail strn (inc n) (+ 2 curr-tail) centers)
            true
            #(ext-centers strn n
                          (concat (vector curr-tail) centers)
                          centers curr-tail)))

          (pal-around-centers
           [strn]
           (reverse (trampoline #(ext-tail strn 0 0 []))))]
    (pal-around-centers text)))

(defn longest-pal-str [strn seq]
  (if (empty? seq)
    ""
    (let* [len (reduce max seq)
	   pos (.indexOf (ArrayList. seq) len)
	   start (- (/ pos 2) (/ len 2))
	   end (+ (/ pos 2) (/ len 2))]
	  (subs strn start end))))

(defn find-password []
  (let [txt (slurp "./gettysburg.txt")]
    (longest-pal-str txt (longest-palendrome txt))))