Project Euler #4 in Haskell

Question

Project Euler #4 asks:

Find the largest palindrome made from the product of two 3-digit numbers.

The code is as follows:

module Main where
import Data.List (sortBy)
import Data.Ord (comparing)
palindromes :: [Integer]
palindromes = [calcPalindrome a b c | a <- [1..9], b <- [0..9], c <- [0..9]]
 where
 calcPalindrome a b c = 100001 * a + 10010 * b + 1100 * c
is3Digit :: Integer -> Bool
is3Digit n = n >= 100 && n <= 999
isDiv :: Integer -> Integer -> Bool
isDiv n d = n `mod` d == 0
-- returns all multiples of 2 3-digit numbers
-- for palindromes
isMultiple :: Integer -> Bool
isMultiple n = not $ null threeMultiples
 where
 multiples :: [(Integer, Integer)]
 multiples = do
 d <- [10..99]
 if n `isDiv` (d * 11)
 then return (d * 11, n `div` (d * 11))
 else []
 threeMultiples :: [(Integer, Integer)]
 threeMultiples = filter (\ (m, n) -> is3Digit m && is3Digit n) multiples
problem4 :: Integer -> Integer
problem4 n =
 head $ filter isMultiple $ sortBy (flip compare) $ filter (< n) palindromes
main :: IO ()
main = do
 _ <- getLine
 contents <- getContents
 let cases = map read $ lines contents
 let results = map problem4 cases
 mapM_ print results

I'd appreciate comments on isMultiple and problem4 as they seem rather messy. Any other general comments are welcome too.

Answer 1

Proof technique

I was pleasantly surprised at the speed of this algorithm (generating all 6-digit palindromes, then taking the largest one with two 3-digit factors), as compared to the alternative approach (multiplying all 3-digit pairs, then finding the largest product that is a palindrome). I would have expected the latter to be faster, as factoring is normally a more expensive operation — but you take advantage of a clever shortcut. That, I suppose, is part of the point of Project Euler questions.

On the other hand, I would consider the program to be slightly incomplete. The property that the palindrome is divisible by 11 only holds if it contains an even number of digits. As a counterexample, 101 ∙ 101 = 10201 is a number within the parameters of the question (a palindrome that is the product of two 3-digit numbers) that is not divisible by 11. Your palindromes function only generates 6-digit candidates for consideration. While there is no need for your program to produce a result that requires no human interpretation, it would be desirable to note the assumption (or proof) of the existence of a 6-digit result, at least as a comment.

Implementation

I am puzzled by your boilerplate main function. Reading an input number as an upper bound on the palindrome candidates seems superfluous. An excessively large input won't scale the problem to cover 4-digit ×ばつ 4-digit products, either, as your palindromes function is hard-coded to produce 6-digit candidates only. So, this would have sufficed:

problem4 :: Int 
problem4 = head $ filter isMultiple $ sortBy (flip compare) $ palindromes
main :: IO ()
main = do
 print problem4

Integer is overkill. The numbers involved fit very comfortably under maxBound::Int.

sortBy (flip compare) is just the same as reverse. But why reverse anything at all, when you could just generate the palindrome candidates in descending order in the first place?

palindromes :: [Int]
palindromes = [calcPalindrome a b c | a <- [9,8..1], b <- [9,8..0], c <- [9,8..0]]
 where
 calcPalindrome a b c = 100001 * a + 10010 * b + 1100 * c

is3Digit is fine, though I would find is3Digit n = 100 <= n && n < 1000 more aesthetically pleasing.

isMultiple could be better named, and the do ... return would be better written as a list comprehension. (See Do notation considered harmful.)

isProductOfThreeDigitNumbers :: Int -> Bool
isProductOfThreeDigitNumbers n = not $ null threeDigitFactors
 where
 -- All palindromes with an even number of digits are divisible by 11
 factors = [(d, n `div` d) | d <- [11, 22 .. 99 * 11], n `isDiv` d]
 threeDigitFactors = filter (\ (m, n) -> is3Digit m && is3Digit n) factors

Then, problem4 would just be

problem4 :: Int
problem4 =
 head $ filter isProductOfThreeDigitNumbers $ palindromes

• wei2912: Thanks for the comments! I'll follow the changes you recommended.
• user2858451: Nice. I went for the other approach. I'm wondering how much faster this is. Maybe I'm wrong but I would have thought the less efficient approach reflects the level of difficulty of Euler # 4....

Answer 2

I went for simplicity. Here's my attempt

import Data.List
isPalindromic::Int -> Bool
isPalindromic n = (==) n' (reverse n')
 where n' = show n
euler4::Int
euler4 = maximum [p | x <- [999,998..100], y <- [999,998..100], let p = x * y, isPalindromic p]

As stated by the previous reviewer not as efficient as yours but in my opinion clearer and the right level of complexity :-)

• Mast: There is no 'right' level of complexity for Euler, IMO. All questions can be as over-engineered as you want. One prefers, scalability, others prefer speed while a third group would want to keep the complexity down. All are fine. It's Euler after all: practice what YOU want to practice.
• wei2912: Usually, I'd write a working program with as little complexity as possible, then try to optimize for time, since writing simple programs gets boring (and unsustainable in later Euler problems). :)