The simplest (and an efficient) solution is right there in the definition of a palindrome, but it’s easy to “follow your nose” through the construction of palindromes and end up writing something more complicated. The real lesson of the sixth L-99 problem is less about lists and more about “forests” and “trees”.
The problem description immediately restricts us to a list representation, and, although it isn’t specified, I’ll assume the list must be proper. LIST-PALINDROME-P should work as follows:
(list-palindrome-p 42) ; TYPE-ERROR: 42 (list-palindrome-p '(a b c d . e)) ; TYPE-ERROR: E (list-palindrome-p '()) => T (list-palindrome-p '(a b b a)) => T (list-palindrome-p '(a b c b a)) => T (list-palindrome-p '(a b c b a b)) => NIL
First, I’ll write a utility function to construct palindrome lists:
(defparameter *alphabet* "abcdefghijklmnopqrstuvwxyz") (defparameter *alphabet-length* 26) (defun random-character () (elt *alphabet* (random *alphabet-length*))) (defun make-palindrome (length) (let ((l '())) (multiple-value-bind (quotient remainder) (floor length 2) (dotimes (i quotient) (push (random-character) l)) (let ((middle (if (plusp remainder) (list (random-character)) '()))) (append l middle (reverse l)))))) CL-USER> (make-palindrome 11) => (#\y #\i #\z #\d #\j #\y #\j #\d #\z #\i #\y)
While scratching that out, I was thinking about a point in the Wikipedia article on palindromes:
In addition, the set of palindromes may not be reliably tested by a deterministic pushdown automaton and is not LR(k)-parsable. When reading a palindrome from left-to-right, it is, in essence, impossible to locate the “middle” until the entire word has been read completely.
The middle… right! If I can find the middle of the list, I can traverse the list from both ends at once, comparing corresponding elements. If a pair of elements differs, the list is not a palindrome; otherwise, when the pointers meet or pass, I have a palindrome. Easy enough to write:
(defun list-palindrome-p (list) (do ((i 0 (1+ i)) (j (1- (length list)) (1- j))) ((or (= i j) (< j i)) t) (unless (equal (nth i list) (nth j list)) (return nil))))
(defun seq-palindrome-p (seq) (do ((i 0 (1+ i)) (j (1- (length seq)) (1- j))) ((or (= i j) (< j i)) t) (unless (equal (elt seq i) (elt seq j)) (return nil))))
To measure the performance hit of list element access, O(n) on average, I wrote a vector-based version using the SVREF vector accessor:
(defun vector-palindrome-p (vector) (do ((i 0 (1+ i)) (j (1- (length vector)) (1- j))) ((or (= i j) (< j i)) t) (unless (equal (svref vector i) (svref vector j)) (return nil))))
Here are some benchmarks under SBCL 1.0.50 on my machine:
CL-USER> (compile 'list-palindrome-p) => LIST-PALINDROME-P CL-USER> (compile 'seq-palindrome-p) => SEQ-PALINDROME-P CL-USER> (compile 'vector-palindrome-p) => VECTOR-PALINDROME-P CL-USER> (defparameter *palindrome* (make-palindrome 100001)) => ... CL-USER> (defparameter *vpalindrome* (coerce *palindrome* 'vector)) => *VPALINDROME* CL-USER> (defparameter *result* nil) => *RESULT* CL-USER> (gc :all t) => NIL CL-USER> (time (dotimes (i 1000 (setf *result* (list-palindrome-p *palindrome*))))) Evaluation took: 9.641 seconds of real time 10.133459 seconds of total run time (10.133459 user, 0.000000 system) 105.10% CPU 19,234,325,700 processor cycles 66,096 bytes consed => T CL-USER> (gc :all t) => NIL CL-USER> (time (dotimes (i 1000 (setf *result* (seq-palindrome-p *palindrome*))))) Evaluation took: 38.109 seconds of real time 39.323022 seconds of total run time (39.323022 user, 0.000000 system) 103.19% CPU 76,026,725,220 processor cycles 254,312 bytes consed => T CL-USER> (gc :all t) => NIL CL-USER> (time (dotimes (i 1000 (setf *result* (vector-palindrome-p *vpalindrome*))))) Evaluation took: 0.002 seconds of real time 0.002000 seconds of total run time (0.002000 user, 0.000000 system) 100.00% CPU 3,609,922 processor cycles 0 bytes consed => T
The list-specific accessor NTH is faster and conses less than ELT. Unsurprisingly, where repeated arbitrary element access is required, a vector is the better choice. VECTOR-PALINDROME-P runs in O(n) time and O(1) space.
However, I can write a list-based solution that is simpler and faster than LIST-PALINDROME-P. It trades space (O(n)) for speed (O(n)). As I noted above, a palindrome is a sequence that reads the same forward or backward:
(defun simple-list-palindrome-p (list) (equal list (reverse list))) CL-USER> (gc :all t) => NIL CL-USER> (time (dotimes (i 1000 (setf *result* (simple-list-palindrome-p *palindrome*))))) Evaluation took: 0.002 seconds of real time 0.002000 seconds of total run time (0.002000 user, 0.000000 system) 100.00% CPU 4,399,568 processor cycles 802,816 bytes consed