current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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
share|improve this answer
    
Thanks for the comments! I'll follow the changes you recommended. –  wei2912 Dec 24 '14 at 6:22
    
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.... –  chosenbreed37 Aug 27 at 8:01
up vote 1 down vote

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 :-)

share|improve this answer
2  
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. –  Mast Aug 27 at 8:15
1  
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). :) –  wei2912 Sep 6 at 14:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.