Project Euler — problem 8
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
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.
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.
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.
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.