Programming Praxis

Two Palindrome Exercises

October 6, 2017 9:00 AM

We’ve done the first task previously. One approach converts the number to a string, then compares, but it’s easy to strip off the digits of the number, one by one, comparing at the end:

(define (number-palindrome? n)
  (let loop ((x n) (z 0))
    (if (zero? x) (= n z)
      (let ((q (quotient x 10)) (r (remainder x 10)))
        (loop q (+ (* z 10) r))))))

And here are some examples:

> (number-palindrome? 123454321)
#t
> (number-palindrome? 123456789)
#f

For the second task, we convert the input strings to a list of characters and compare the list to its reverse; mappend is like map, but uses append instead of cons to assemble its output, thereby splitting multi-letter words into their individual letters:

(define (string-palindrome? xs)
  (let ((chars (mappend string->list xs)))
    (equal? chars (reverse chars))))

And here are some examples:

> (define x ‘(“a” “bcd” “ef” “g” “f” “ed” “c” “ba”))
> (string-palindrome? x)
#t
> (string-palindrome? (cdr x))
#f

You can run the program at https://ideone.com/9VdOBA.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

5 Responses to “Two Palindrome Exercises”

We can avoid separate calls to quotient and remainder by using floor/ which returns both.

By chaw on October 6, 2017 at 11:00 AM
With SRFI 13, we can eliminate converting strings to lists and back, and just say:
```
(let ((str (apply string-append xs)
  (string=? str (string->reverse str)))
```
That said, the successors of SRFI 13 do not support string-reverse, because it is only useful in artificial examples like these. In a Unicode world, “Hägar the Horrible”, when expressed in decomposed form (as here). reverses not to “elbirroH eht ragäH” but to “elibrroH eht rag̈aH”, with the umlaut on the “g” rather than the first “a”.

By John Cowan on October 6, 2017 at 11:46 AM

A Haskell version.

import Data.Bool (bool)
import Data.List (unfoldr)
import Data.Tuple (swap)
import Numeric (showInt)

-- Is a number a base-10 palindrome?  (We only consider non-negative numbers
-- because the showInt library function only supports them.)
isNumPalindrome :: Integral a => a -> Bool
isNumPalindrome n | n < 0     = False
                  | otherwise = isPalindrome (showInt n "")

-- Is the result of concatenating a list of lists a palindrome?
isConcatPalindrome :: Eq a => [[a]] -> Bool
isConcatPalindrome = isPalindrome . concat

-- Is a list a palindrome?
isPalindrome :: Eq a => [a] -> Bool
isPalindrome xs = xs == reverse xs

--------------------------------------------------------------------------------

-- An alternate way of checking whether a number is a palindrome, by explicitly
-- converting the number to a list of digits, rather than using the showInt
-- library function to convert it to a list of characters.

-- The list of a number's digits, in base b.  The least significant digits are
-- first.  The empty list represents 0.
toDigits :: Integral a => a -> a -> [a]
toDigits b = unfoldr step
  where step 0 = Nothing
        step i = Just . swap $ i `quotRem` b

-- Is a number a base-10 palindrome?  We allow negative numbers: -n is a
-- palindrome if n is.
isNumPalindrome' :: Integral a => a -> Bool
isNumPalindrome' = isPalindrome . toDigits 10

--------------------------------------------------------------------------------

test :: (Eq a, Show a) => (a -> Bool) -> a -> IO ()
test palFn x = putStrLn $ "Is " ++ show x ++ " a palindrome?  " ++
               bool "No" "Yes" (palFn x)

main :: IO ()
main = do
  test isNumPalindrome 0
  test isNumPalindrome 123
  test isNumPalindrome 12321
  
  test isConcatPalindrome ([] :: [String])
  test isConcatPalindrome ["a", "bc"]
  test isConcatPalindrome ["a", "bcd", "ef", "g", "f", "ed", "c", "ba"]

  test isNumPalindrome' (-12)
  test isNumPalindrome' (-121)
  test isNumPalindrome' 121

$ ./palin2 
Is 0 a palindrome?  Yes
Is 123 a palindrome?  No
Is 12321 a palindrome?  Yes
Is [] a palindrome?  Yes
Is ["a","bc"] a palindrome?  No
Is ["a","bcd","ef","g","f","ed","c","ba"] a palindrome?  Yes
Is -12 a palindrome?  No
Is -121 a palindrome?  Yes
Is 121 a palindrome?  Yes

By Globules on October 9, 2017 at 6:03 AM

        Klong 20170905
        f1::{[a]; a::,/:~x; a=|a}
:monad
        f2::{[a]; a::0;{x>0}{[r]; a::(r::x!10)+a*10; (x-r):%10}:~x; x=a}
:monad
        f1(["a" "bc" "def" "g" "h"])
0
        f1(["a" "bc" "def" "g" "h" "h" "g" "f" "e" "d" "c" "b" "a"])
1
        f1(["a" "bc" "def" "g" "h" "g" "f" "e" "d" "c" "b" "a"])
1
        f2(123)
0
        f2(123321)
1
        f2(12321)
1

By Steve on October 10, 2017 at 3:02 PM

(defun palindromic-p (str)
(equal (string-reverse str) str))

(defun palindromic-integer-p (n)
(palindromic-p (int-to-string n)))

(defun palindromic-list-p (list)
(palindromic-p (apply #’concat list)))

;; (palindromic-integer-p 123454321)

;; t
;; (palindromic-integer-p 1234544321)

;; nil

;; (palindromic-list-p ‘(“a” “bcd” “ef” “g” “f” “ed” “c” “ba”))

;; t
;; (palindromic-list-p ‘(“a” “bcd” “ef” “xg” “f” “ed” “c” “ba”))

;; nil

By lijigang on October 16, 2017 at 3:38 PM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

Two Palindrome Exercises

Share this:

Related

5 Responses to “Two Palindrome Exercises”

Leave a Reply