Euler-sol-4

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 4

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

python by astan (traltixx)

Runtime: 2.703000 seconds

   import time, math
   start_time = time.time()
   max = 1
   factors = [0,0]
   def isPalindrome(num):
       l = str(num)
       ls = [c for c in l]
       return (ls == ls[::-1])
   for i in range(100,1000,1):
       for p in range(100,1000,1):
           if isPalindrome((i*p)) and max<(i*p):
               max = (i*p)
               factors = [i,p]
   print max
   print factors
   run_time = time.time() - start_time
   print 'Run time: %f seconds' % run_time

Caml by SanguineV

Runtime: 14.290 ms

(* Determine if an integer is a palindrome *)
let palindrome x =
  let rec reverse n acc =
    if n < 10
    then n + (10 * acc)
    else reverse (n/10) ((10 * acc) + (n mod 10))
  in
  x == reverse x 0
;;

(* Generate numbers from n down to m *)
let rec intsN2M n m =
  if n == m
  then [n]
  else n :: (intsN2M (n - 1) m)
;;

(* Generate some potential palindromes created by multiplying 2 3 digits numbers *)
let pps =
  let rec inner = function
    | [] -> []
    | x::xs -> List.append (List.map (fun z -> z * x) xs) (inner xs)
  in
  inner (intsN2M 999 900)
;;

(* Return the first integer to satisfy "f" *)
let rec first f = function
  | [] -> 0
  | x::xs ->  if f x
              then x
              else first f xs
;;

(* Print the first palindrome created by multiplying 2 3 digit numbers *)
Printf.printf "Max palindrome is: %u\n" (first palindrome pps);;

Haskell by SanguineV

Runtime: 11 ms

pal :: Integer -> Bool
pal n = n == rev 0 n
  where
    rev i n | n < 10 = 10 * i + n
    rev i n = rev ((10 * i) + mod n 10) (div n 10)

main = print (maximum (filter pal [x*y | x <- [999,998..900], y <- [999,998..900]]))

Ruby by tomchristmas

Runtime: 54ms (original), 54ms (alternate line).
No difference -- interesting...

p = []
900.upto(999){|x| 900.upto(999){|y| p << x * y if (x*y).to_s == (x*y).to_s.reverse}}
puts p.inject(0){|a,b| (b > a) ? b : a}

Alternatively, you could replace the third line with just

puts p.last

since you are generating the palindromes from the smallest to largest number pair, intuition suggests that the last palindrome generated is the largest palindrome on the list. Nevertheless, it is sound practice to do a thorough check all the same.

Java by ctd

Runtime: 442ms

public class Problem4 {
	public static void main (String[] args) {
		int largest = 0;
		for (int i = 0; i < 1000; i++)
			for (int j = 0; j < 1000; j++) {
				int num = i * j;
				if (isPalindromic(num) && num > largest)
					largest = num;
			}
		System.out.println(largest);
	}

	public static boolean isPalindromic (int num) {
		String str = "" + num;
		for (int i = 0; i < str.length()/2; i++)
			if (str.charAt(0+i) != str.charAt(str.length()-1-i))
				return false;
		return true;
	}
}
Personal tools