Euler 4

Largest palindrome number made from the product of two three-digit numbers

First a function that tests i a number is palindromic. Vectorized!

is_palindromic <- function(x){
  y <- as.character(x)
  y <- strsplit(y, "")
  y <- lapply(y, rev)
  y <- lapply(y, paste, collapse = "")
  y == x
}

t <- expand.grid(100:999, 100:999)
t <- t[,"Var1"] * t[,"Var2"]
answer <- max(t[is_palindromic(t)])

fra nusse.dk

I solved this more than four years ago. So I have no idea if this was the way I did it originally.

The problem is:

A palindromic number is a number that reads the same both ways. Like “A man, a plan, a canal, Panama!” just with numbers.

The problem informs us, that the largest palindrome made from the product of two two-digit numbers, is 9009.

We get that from 91 × 99. We must now find the largest palindrome, made from the product of two three-digit numbers.

First, we need to figure out how to test if a number is palindromic. There might be easier ways. But this is mine.

Convert the number to a string. Split it in individual characters reverse the string, and compare to the original.

Like this, using the stringr library:

library(stringr) rev(unlist(str_split(“9009”, ““))) == unlist(str_split(”9009”, ““))

[1] TRUE TRUE TRUE TRUE

Everything is TRUE, as it should be - lets make a function.

is_palindromic <- function(x){ all(rev(unlist(str_split(x, ““))) == unlist(str_split(x,”“))) }

is_palindromic(9009)

[1] TRUE

Only problem is that it is not vectorized

is_palindromic(c(991, 9009))

[1] FALSE

Just for the fun of it, lets write something vectorized. This is definitely not the way I did it originally.

is_palindromic <- function(x){ unlist(lapply(lapply(str_split(x,““), rev),str_c, collapse=”“)) == as.character(x) }

is_palindromic(c(991, 9009))

[1] FALSE TRUE

Nice. There are definitely faster ways of doing it.

Now I just need to generate all products made up of two three-digit numbers, test if it is palindromic, and find the largest.

I use expand.grid to generate all combinations of all three-digit numbers, transmute the product into existence, and filter out all the non-palindromic products. Then I arrange the product variable in descending order, and take the first.

library(dplyr) answer <- expand.grid(100:999, 100:999) %>% transmute(product = Var1*Var2) %>% filter(is_palindromic(product)) %>% arrange(desc(product)) %>% slice(1)

Not very fast… The main problem is that I check all 810.000 products. There is no need for that. If I instead test the products in order, from the largest, to the smallest, the first palindromic number I find, is the largest.

Let us generate a list of candidates, in descending order:

cand <- expand.grid(100:999, 100:999) %>% transmute(product = Var1*Var2) %>% arrange(desc(product)) %>% .$product

And now, for each element in the candidate-vector, if it is palindromic, set that to be the answer, and break out of the for-loop.

for(i in cand){ if(is_palindromic(i)){ answer <- i break() } }

Much faster.