Linked List Palindrome
September 8, 2017
Our solution appends all the list items into a single string, splits the string into a list of characters, then compares the list to its reverse (we could do without the intermediate list if Scheme had a string-reverse):
(define (palindrome? strs)
(let ((cs (string->list (apply string-append strs))))
(equal? cs (reverse cs))))
Here are two examples:
> (palindrome? '("a" "bcd" "ef" "g" "f" "ed" "c" "ba"))
#t
> (palindrome? '("a" "bcd" "ef" "g" "f" "ed" "ba"))
#f
You can run the program at https://ideone.com/UIP1Ml.
You should look at the sixty-six posted solutions on the original problem page. It is astonishing to me that so many programming languages take a simple problem and make it extraordinarily complex. Well, at least the code to solve the problem is complex. Maybe it’s the programmers and not the programming languages that cause the complexity? In any event, some of those solutions are absolutely beyond belief. You will either laugh or cry, or both.
Pages: 1 2
The following should run in time linear in the input size, and is a
bit more general than needed.
(import (scheme base) (only (srfi 1) list= fold) (only (srfi 13) string-fold)) (define input-1 '("a" "bcd" "ef" "g" "f" "ed" "c" "ba")) (define (palindrome? = lst) (list= = lst (reverse lst))) ;; equivalent to (reverse (apply append (map string->list slist))) ;; but more direct. (define (string-list->rlist slist) (fold (lambda (str acc) (string-fold cons acc str)) '() slist)) (define (palindrome-string-list? lst) (palindrome? char=? (string-list->rlist lst))) (palindrome-string-list? input-1)I was asked a palindrome question yesterday, but it explicitly excluded any solution that involved reversing or flattening, as it had to execute in O(1) space.
;; Simple solution. ;; O(n) in time. (assuming amortized O(n) with-output-to-string implementation). ;; 2n space. (for string and its reverse). ;; programmer time: the time to write it, correct on the first write. (defun palindromic-list-p (list-of-strings) (flet ((list-to-string (los) (with-output-to-string (*standard-output*) (dolist (string los) (write-string string))))) (let ((string (list-to-string list-of-strings))) (string= string (reverse string))))) (assert (palindromic-list-p '("a" "bcd" "ef" "g" "f" "ed" "c" "ba"))) (assert (not (palindromic-list-p '("a" "bcd" "ef" "g" "f" "Xd" "c" "ba")))) ;; Sophisticated solution: the characters are compared in place. ;; O(n) in time ;; O(e) in space with e = (length list-of-strings), which may be much smaller than n if the strings are big. ;; programmer time: a lot; debugging and tuning. (defun palindromic-list-p (list-of-strings) (labels ((equal-palindromic-string (size a start-a b start-b) (loop :repeat size :for i :from start-a :for j :from (- (length b) start-b 1) :downto 0 :always (char= (aref a i) (aref b j)))) (equal-list-of-strings (a start-a b start-b) (cond ((endp a) (endp b)) ((endp b) nil) (t (let* ((size (min (- (length (first a)) start-a) (- (length (first b)) start-b))) (new-start-a (+ start-a size)) (new-start-b (+ start-b size))) (and (equal-palindromic-string size (first a) start-a (first b) start-b) (equal-list-of-strings (if (< new-start-a (length (first a))) a (rest a)) (if (< new-start-a (length (first a))) new-start-a 0) (if (< new-start-b (length (first b))) b (rest b)) (if (< new-start-b (length (first b))) new-start-b 0)))))))) (equal-list-of-strings list-of-strings 0 (reverse list-of-strings) 0))) (assert (palindromic-list-p '("a" "bcd" "ef" "g" "f" "ed" "c" "ba"))) (assert (not (palindromic-list-p '("a" "bcd" "ef" "g" "f" "Xd" "c" "ba")))) ;; To see how this works, let's trace equal-palindromic-string: cl-user> (palindromic-list-p '("a" "bcd" "ef" "g" "f" "ed" "c" "ba")) (equal-palindromic-string 1 "a" 0 "ba" 0) (equal-palindromic-string 1 "bcd" 0 "ba" 1) (equal-palindromic-string 1 "bcd" 1 "c" 0) (equal-palindromic-string 1 "bcd" 2 "ed" 0) (equal-palindromic-string 1 "ef" 0 "ed" 1) (equal-palindromic-string 1 "ef" 1 "f" 0) (equal-palindromic-string 1 #1="g" 0 #1# 0) (equal-palindromic-string 1 "f" 0 "ef" 0) (equal-palindromic-string 1 "ed" 0 "ef" 1) (equal-palindromic-string 1 "ed" 1 "bcd" 0) (equal-palindromic-string 1 "c" 0 "bcd" 1) (equal-palindromic-string 1 "ba" 0 "bcd" 2) (equal-palindromic-string 1 "ba" 1 "a" 0) t cl-user> (palindromic-list-p '("a" "bcd" "ef" "g" "f" "Xd" "c" "ba")) (equal-palindromic-string 1 "a" 0 "ba" 0) (equal-palindromic-string 1 "bcd" 0 "ba" 1) (equal-palindromic-string 1 "bcd" 1 "c" 0) (equal-palindromic-string 1 "bcd" 2 "Xd" 0) (equal-palindromic-string 1 "ef" 0 "Xd" 1) nil cl-user>Note: it is possible to make it O(1) in space, but this will degrade into O(e^2)+O(n) instead of O(e)+O(n) in time since we will have to traverse the list several time, by index. (with e = (length list) and n = total number of characters). It will also be O(t^2) in programmer time, with t being the time the programmer took to implement the second version above… ;-)
Prompted by John Cowan’s comment above, here is a version that is
constant space, but quadratic time.
If using SRFI-135 is considered “cheating” then we could impagine we
have included code from portable implementation from that SRFI. (We
could also use “istrings” from SRFI 140 or Kawa, etc.)
;; Tested with Larceny Scheme (import (scheme base) (scheme write) (only (srfi 1) fold) (only (srfi 135) text text-length text-ref string->text)) (define input-1t (map string->text '("a" "bcd" "ef" "g" "f" "ed" "c" "ba"))) (define input-2t (map string->text '("a" "bcd" "f" "g" "f" "ed" "c" "ba"))) ;; An "ltext" is a list of texts, viewed as a segmented text/string. ;; ltext-ref is then analogous to text-ref, string-ref, etc. ;; Since text-ref is O(1), ltext-ref is O(n) time, O(1) space. (define (ltext-ref ltxt idx) (let ((flen (text-length (car ltxt)))) (if (< idx flen) (text-ref (car ltxt) idx) (ltext-ref (cdr ltxt) (- idx flen))))) ;; ltext analogue of text-length, string-length etc. ;; O(n) time, O(1) space. (define (ltext-length ltxt) (fold (lambda (txt c) (+ c (text-length txt))) 0 ltxt)) ;; An array-style palindrome-check. ;; Given above, it is O(n^2) time, O(1) space. (define (ltext-palindrome? ltxt) (let ((len (ltext-length ltxt))) (let f ((i 0)) (or (>= i (/ len 2)) (and (char=? (ltext-ref ltxt i) (ltext-ref ltxt (- len i 1))) (f (+ i 1))))))) (display (map ltext-palindrome? `((,(text)) (,(text #\a)) (,(text #\a #\a)) (,(text #\a #\b)) ,input-1t ,input-2t))) (newline) ;;;