Project Euler Problem 4

Problem 4

16 November 2001

 

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

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

 

Answer: 906609

 

Solution in Perl

 

 

sub isPalindrome {
 my ($str) = @_;
 my $to = length($str) / 2;
 for ( my $i = 0 ; $i <= $to ; $i++ ) {
  if ( substr( $str, $i, 1 ) != substr( $str, length($str) - 1 - $i, 1 ) )
  {
   return 0;
  }
 }
 return 1;

}

sub problem4 {
 my $max = 0;
 for my $i ( 100 .. 999 ) {
  for my $j ( 100 .. 999 ) {
   my $p = $i * $j;
   if ( isPalindrome($p) ) {
    $max = $p if ($p > $max);
   }
  }
 }
 print $max;
}

problem4();

 

 

Python

 

def isPalindrome(value):   
    to = len(value) / 2
    for i in xrange(0, to):
        if value[i] != value[len(value) - 1 - i]:
            return 0;
    return 1;

def problem4():
    maxP = 0;
    for i in xrange( 100, 999 ):
        for j in xrange( 100, 999 ):
            p = i * j
            if isPalindrome(str(p)):
                if p > maxP: maxP = p
    print maxP;

 

 

Go

 

func isPalindrome(value string) bool {
 to := len(value) / 2
 for i := 0; i < to; i++ {
  if value[i] != value[len(value)-1-i] {
   return false
  }
 }
 return true
}

 

func problem4() {
 maxP := 0
 for i := 100; i <= 999; i++ {
  for j := 100; j <= 999; j++ {
   p := i * j
   if isPalindrome(strconv.Itoa(p)) {
    if p > maxP {
     maxP = p
    }
   }
  }
 }
 fmt.Println(maxP)
}

 

func main() {
 problem4()
}

C++

bool isPalindrome(string value) {
    int to = value.size() / 2;
    for (int i = 0; i < to; i++) {
        if (value[i] != value[value.size()-1-i]) {
            return false;
        }
    }
    return true;
}

void problem4() {
    int maxP = 0;
    for (int i = 100; i <= 999; i++) {
        for (int j = 100; j <= 999; j++) {
            int p = i * j;
            char strP[10];
            _itoa_s(p, strP, 10);
            if (isPalindrome(strP)) {
                if (p > maxP) {
                    maxP = p;
                }
            }
        }
    }
    cout << maxP << endl;
}

 

Bash (very slow)

 

function isPalindrome {
    local str=$1
    local len=${#str}
    let 'to = len / 2'
    local i=0
    while ((i <= to)); do
        if (( ${str:$i:1} != ${str:${#str}-1-i:1} )); then
            return 1
        fi
        let 'i++'
    done
    return 0
}

function problem4 {
    local max=0
    local i=100
    while ((i <= 999)); do
        local j=100
        while ((j <= 999)); do
            let 'p = i * j'
            if isPalindrome $p; then
                if ((p > max)); then let 'max = p'; fi
            fi
            let 'j++'
        done
        let 'i++'
    done
    echo $max
}

problem4

Javascript

var isPalindrome = function(value) {
    var to = value.length / 2;
    for (var i = 0; i < to; i++)
        if (value[i] != value[value.length-1-i]) return false;
    return true;
}

var problem4 = function() {
    var maxP = 0;
    for (var i = 100; i <= 999; i++)
        for (var j = 100; j <= 999; j++) {
            var p = i * j;
            if (isPalindrome(p.toString())) if (p > maxP) maxP = p;
        }
    return maxP;
}

problem4()

Racket

 

(define (string-reverse s)
  (list->string (reverse (string->list s))))

(define (palindrome? str)
  (string=? str (string-reverse str)))

(define (problem4)
  (define maxP 0)
  (for* ([i (in-range 100 1000)]
         [j (in-range 100 1000)])
    (define p (* i j))
    (when (palindrome? (number->string p)) (set! maxP (max maxP p))))
  (display maxP))
(problem4)

---

; using equal?

#lang racket

(define (palindrome? str)

  (let ([s (string->list str)])

    (equal? s (reverse s))))

(define (problem4)

  (define maxP 0)

  (for* ([i (in-range 100 1000)]

         [j (in-range 100 1000)])

    (define p (* i j))

    (when (palindrome? (number->string p)) (set! maxP (max maxP p))))

  (display maxP))

(problem4)

 

#lang racket
; using SRFI 13: String Libraries
(require srfi/13)
(define (problem4)
  (define maxP 0)
  (for* ([i (in-range 100 1000)]
         [j (in-range i 1000)])
    (let* ([p (* i j)]
           [str (number->string p)])
      (when (and (> p maxP) (string=? str (string-reverse str))) (set! maxP p))))
  (display maxP))
(problem4)

 

 

; faster version

#lang racket
;(define (palindrome? str)
;  (let ([s (string->list str)])
;    (equal? s (reverse s))))

(define (palindrome? str)
  (define len (string-length str))
  (define pal true) 
  (for ([k (in-range 0 (/ len 2))])
    #:break (not pal)
    (unless (eq? (string-ref str k) (string-ref str (- len k 1)))
      (set! pal false)))
  pal)

(define (problem4)
  (define maxP 0)
  (for* ([i (in-range 999 99 -1)]
         [j (in-range 999 (sub1 i) -1)])
    (define p (* i j))
    (when (and (> p maxP) (palindrome? (number->string p))) (set! maxP p)))
  (display maxP))

(problem4)

 

 

Haskell

 

import Data.List

answer1 = maximum [p |x <- [999,998..100], y <- [999,998..x], let p = x * y, let s=show p, s==reverse s]

maxFilter filter1 lst temp =

    case lst of

        [] -> temp

        (x:xs) ->

            if x > temp

                then if filter1 x

                    then maxFilter filter1 xs x

                    else maxFilter filter1 xs temp

                else maxFilter filter1 xs temp

answer2 = maxFilter (\x->let s = show x in s==reverse s) [x*y|x <- [999,998..100], y <- [999,998..x]] 0

answer3 = foldl' (\x y->if y > x && palindrome y then y else x) 0 [x*y|x <- [999,998..100], y <- [999,998..x]]

    where palindrome p = let s=show p in s==reverse s

main = do

    print answer1

    print answer2

    print answer3

* newLISP

(setq maxP 0)
(for (i 100 999)
  (for (j 100 999)
    (setq p (* i j))
    (setq ps (string p))
      (when (= ps (reverse (copy ps)))
        (setq maxP (max maxP p)))))
(println maxP)

 

* Clojure

 

(defn problem4 []
  (println
    (apply
      max
      (filter #(let [s (str %)] (= s (apply str (reverse s))))
              (for [i (range 100 1000)
                    j (range i 1000)]
                (* i j))))))

 

(defn problem4b []
  (let [max-p (atom 0)]
    (doseq [i (range 100 1000)
            j (range i 1000)]
      (let [p (* i j), s (str p)]
        (when (and (= s (apply str (reverse s))) (> p @max-p)) (reset! max-p p))))
  (println @max-p)))

 

C

#include <stdio.h>
#include <string.h>

int isPalindrome(char *value) {
  int len=strlen(value),
    to = len / 2,
    i;
  for (i = 0; i < to; i++) {
    if (value[i] != value[len-1-i]) {
      return 0;
    }
  }
  return 1;
}

int main() {
  int maxP = 0, i, j;
  for (i = 100; i <= 999; i++) {
    for (j = i; j <= 999; j++) {
      int p = i * j;
      char strP[10];
      sprintf(strP, "%d", p);
      if (isPalindrome(strP)) {
        if (p > maxP) {
          maxP = p;
        }
      }
    }
  }
  printf("%d\n", maxP);
}

 

Emacs Lisp

 

(defun reverse/str (a)
  (apply #'string (reverse (string-to-list a))))

 

(setq maxP 0)
(setq i 100)
(while (<= i 999)
  (setq j i)
  (while (<= j 999)
    (setq p (* i j)
          ps (number-to-string p))
    (when (string= ps (reverse/str ps))
      (setq maxP (max maxP p)))
    (setq j (1+ j)))
  (setq i (1+ i)))
(print maxP)

 

Common Lisp

;1

(let ((maxp 0))
  (loop for i from 100 to 999 do
       (loop for j from i to 999 do
        (let* ((p (* i j))
           (ps (write-to-string p))
           (len (length ps))
           (to (floor (/ len 2)))
           (pal t)
           (k 0)
           (k2 (1- len)))
          (loop while (< k to) do
           (unless (eql (elt ps k) (elt ps k2))
             (setq pal nil)
             (return))
           (setq k (1+ k))
           (setq k2 (1- k2)))
          (when pal
        (when (> p maxp)
          (setq maxp p))))))
  (print maxp))

 

; 2

(defun palindromep (x)

  (let ((str (write-to-string x)))

    (string= str (reverse str))))

(loop with maxp = 0

  for x from 999 downto 100

  do

  (loop for y from x downto 100

    for p = (* x y)

    if (and (> p maxp) (palindromep p)) do (setf maxp p))

  finally (return maxp))