Project Euler — problem 4

May 29, 2012
By

(This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers)

It’s midnight already. I’m going to bed after I type this. Now the fourth Euler problem:

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.

Mmm … Palindromic. people can tell whether a number is a palindromic easily, just by looking at the number to see whether it’s symmetric. But it needs some coding work to teach your computer to do the same thing. I could reverse the number, then compare it with the original to see whether they are identical. In R, I need strsplit(), rev(), “==”, and as.character() to coerce the number to a character object. I’ll write a helper function to test the palindromicity.
Next issue here is the products of two 3-digit numbers, e.g. 100 to 999. Using computer, I could easily generate all the products of 100-999 using the matrix multiplication. But that’s silly. Thus my plan is to generate a small fraction of the products, say 900-999. Then check their palindromicity; if these are some, pick the biggest one; otherwise move on to the other products. As one thousand numbers are between 900 and 999, the odd that there is none of palindrome in their products is slim. Here comes the code.

?View Code RSPLUS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
is.palindromic <- function(x) {
  x <- as.character(x)
  forward <- unlist(strsplit(x, split = ""))
  reverse <- rev(forward)
  flag <- all(forward == reverse)
  return(flag)
}
# calculate the products of 900:999
mat <- matrix(900:999, nrow = 1)
mat <- t(mat) %*% (mat)
candidate <- as.vector(mat)
candidate <- unique(sort(candidate, decreasing = T))
# pick the largest palindrome
pali.max <- 0
i <- 1
n <- length(candidate)
while (i <= n) {
  if (is.palindromic(candidate[i])) {
    pali.max <- candidate[i]
    break
  }
  i <- i + 1
}
cat("The result is:", pali.max, "\n")

I used to check the palindromicity on every product, which is unnecessary for searching the largest one. So I use a while loop here and it saves about 1/3 of the processing time.

To leave a comment for the author, please follow the link and comment on his blog: Tony's bubble universe » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.