Two Palindrome Exercises

October 6, 2017

Many of the people who read my blog are programming students. It is October, about the middle of the Fall Semester at many universities, and my student readers need exercises to cement their understanding of their studies. Here are two exercises about palindromes.

  1. A number like 123454321 is palindromic; it decimal digits are the same left-to-right as they are right-to-left. Write a program that determines if a given input number is palindromic.
  2. Given a list of strings, for instance {“a” “bcd” “ef” “g” “f” “ed” “c” “ba”}, write a program to determine if the individual letters of the strings form a palindrome. Note that the letters might be distributed into the individual words differently when read in opposite directions.

Your task is to write two programs that recognize palindromes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

5 Responses to “Two Palindrome Exercises”

  1. chaw said

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

  2. John Cowan said

    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, “Hägar the Horrible”, when expressed in decomposed form (as here). reverses not to “elbirroH eht ragäH” but to “elibrroH eht rag̈aH”, with the umlaut on the “g” rather than the first “a”.

  3. Globules said

    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
    
  4. Steve said
            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
    
  5. lijigang said

    (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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: