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 their blog: Tony's bubble universe » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, 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.

Sponsors

Mango solutions



plotly webpage

dominolab webpage



Zero Inflated Models and Generalized Linear Mixed Models with R

Quantide: statistical consulting and training

datasociety

http://www.eoda.de





ODSC

ODSC

CRC R books series





Six Sigma Online Training









Contact us if you wish to help support R-bloggers, and place your banner here.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)