Project Euler — problem 8

June 9, 2012
By

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

The eight problem of Project Euler:

Find the greatest product of five consecutive digits in the 1000-digit number. …

The solution is as straightforward as the problem, although the 1000-digit number needs some format changes before product calculation.

?View Code RSPLUS
1
2
3
4
5
6
7
8
tmp <- scan("tmp.txt", what = "")  # store the numbers in tmp.txt
tmp <- paste(tmp, collapse = "")  # get the single number
num.lst <- strsplit(tmp, split = "")  # split it into 1-digit numbers
num.lst <- as.numeric(unlist(num.lst))
products <- num.lst[1:(n - 4)] * num.lst[2:(n - 3)] * num.lst[3:(n - 2)] * 
            num.lst[4:(n - 1)] * num.lst[5:n]
result <- max(products)
cat("The result is:", result, "\n")

I also take another method specific for this problem. I notice there are many 0′s and 1′s in this number. The numbers multiplied with 0 or 1 won’t be the largest product for sure. So I use the argument ‘split = “[0-1]“‘ in strsplit(), then remove sequences with less than five numbers. And the last step is to calculate the largest product of five consecutive numbers.

?View Code RSPLUS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
max.prod <- function(x) {  
  # helper to calculate the largest product in a give number sequence x
  lst <- strsplit(x, split = "")
  lst <- as.numeric(unlist(lst))
  n <- length(lst)
  products <- lst[1:(n - 4)] * lst[2:(n - 3)] * lst[3:(n - 2)] * 
              lst[4:(n - 1)] * lst[5:n]
  max.product <- max(products)
  return(max.product)
}
num.lst <- strsplit(tmp, split = "[0-1]")
num.lst <- unlist(num.lst)
mt <- nchar(num.lst) >= 5  # remove small number sequences
num.lst <- as.list(num.lst[mt])  # coerce to list for the next step using sapply()
result <- max(sapply(num.lst, max.prod))
cat("The result is:", result, "\n")

It sounds better than the first solution, right? The calculations are reduced as many numbers are eliminated. In fact, however, this method is almost twice slower than the first one, due to more operation on separate number sequences. 
Btw, if I only have pencil and paper, this would be my solution. Maybe I would only consider those products with 9′s.

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.