Last active
December 16, 2019 13:56
-
-
Save mmahmoudian/32dbd85442e74e93b733d4fe48beda1e to your computer and use it in GitHub Desktop.
Revisions
-
mmahmoudian revised this gist
Dec 16, 2019 . 1 changed file with 209 additions and 58 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -2,6 +2,10 @@ ## This code is in response to the following tweet of "Fermat's Library" ## ## https://twitter.com/fermatslibrary/status/1180837639915819008?s=20 ## ## ## ## It is also corresponsing to the following entry in the On-Line ## ## Encyclopedia of Integer Sequences (OEIS): ## ## https://oeis.org/search?q=A104113 ## ## ## ## Author: Mehrad Mahmoudian ## ## License: GPL3 ## ## ## @@ -22,78 +26,225 @@ ################################################################################ #-------[ load packages ]-------# { library("parallel") library("foreach") library("doParallel") } #-------[ initial settings ]-------# { ## what range of numbers should it cover lower_bound <- 10 upper_bound <- 100000000 # how many tasks should we push to each CPU core (this depends on the processing # power of each core and the total available memory, so don't set it too high jumps <- 250 setwd("~/tmp/A104113/") } #-------[ internal functions ]-------# { func_cutter <- function(x, cuts){ ## Description: ## A function to cut a string at given points ## ## Arguments: ## x: A character vector of length 1 ## cuts: a numeric vector of length smaller than nchar(x) # create a collective variable final <- c() # go through all the cutting points that is provided to the function for(i in seq_along(cuts)){ # if the index is 1 if(i == 1){ # append the first few chracters as an item to the collective vector final <- c(final, substr(x = x, start = 1, stop = cuts[i])) } # if we got to the end of the cutting points list if(i == length(cuts)){ # set the ending to be the end of the string tmp_end_index <- nchar(x) }else{ # using the next cutting point as the ending position tmp_end_index <- cuts[i+1] } final <- c(final, substr(x = x, start = cuts[i]+1, stop = tmp_end_index)) } return(final) } chunk2 <- function(x,n){ ## source: https://stackoverflow.com/a/16275428/1613005 ## ## Description: ## A function to break the provided vector into n equal smaller vectors ## ## Arguments: ## x: a vector that you want to cut into chunks ## n: number of chunks split(x, cut(seq_along(x), n, labels = FALSE)) } } #-------[ ininital setup ]-------# { # set the number to maximum possible but leave one out for the grace parallel.cores <- parallel::detectCores() - 1 ## register parallel backend cl <- parallel::makeCluster(parallel.cores, outfile = "") doParallel::registerDoParallel(cl) } #-------[ main ]-------# { # create an empty vector to be filled in the loop below final <- c() # initiate the start of i in the loop i_low <- lower_bound ## initiate the result file with a separator tagged with date and time header_txt <- paste0("[ ", format(Sys.time(), "%Y%m%d-%H%M%S"), " ]") padding_length <- (80 - nchar(header_txt)) / 2 header_txt <- paste0(paste(rep.int("-", ceiling(padding_length)), collapse = ""), header_txt, paste(rep.int("-", floor(padding_length)), collapse = "")) cat(header_txt, file = "result.txt", sep = "\n", append = T) # run as long i is less than the upper bound while(i_low <= upper_bound){ # define how high we want to go in this round of while i_high <- i_low + (parallel.cores * jumps) # if the hight we defined is larger than the user-defined upper bound if(i_high > (upper_bound + 1)){ # trim it to be as high as upper bound +1 (+1 is to make the while loop break) i_high <- upper_bound + 1 } # break the distance between i_low to i_high to equal chunks where chunk count is equal to parallel.cores chunks <- chunk2(i_low:i_high, parallel.cores) cat(i_low, ":", i_high, ":: ") # got through the numbers between the lower and upper limits of this round of while tmp_final <- foreach(ii = chunks, .inorder = TRUE, .combine = c) %dopar% { tmp_outer_collective <- c() for(i in ii){ tmp_inner_collective <- c() # iterate through the possible number of cuts we can have to the string for(j in seq_len(nchar(i) - 1)){ # generate all possible combination of cutting positions considering the # constraint on total number of cuts allowed combinations <- apply(combn(x = nchar(i) - 1, m = j), 2, function(a){ func_cutter(x = i, cuts = a) }) # go through all generated pieces and do the math for(k in 1:ncol(combinations)){ # select this specific combination x <- as.character(combinations[, k]) # turn this combination into numbers x_numeric <- as.numeric(x) # if the square of sums was equal to the number we are testing if((sum(x_numeric)^2) == i){ tmp_success <- paste0("(", paste0(x, collapse = "+"), ")^2") tmp_inner_collective <- c(tmp_inner_collective, tmp_success) } } } # if the collective variable was not empty if(length(tmp_inner_collective)){ # retusn a character vector of length 1 with correct desired format tmp_inner_collective <- paste0(paste0("[", format(Sys.time(), "%Y%m%d-%H%M%S"), "]\t"), i, "\t::\t", paste(tmp_inner_collective, collapse = ", ")) }else{ tmp_inner_collective <- NULL } tmp_outer_collective <- c(tmp_outer_collective, tmp_inner_collective) } return(tmp_outer_collective) } # append to the global collective1 variable final <- c(final, tmp_final) if(!is.null(tmp_final)){ cat(length(tmp_final), "\n") cat(tmp_final, file = "result.txt", sep = "\n", append = T) }else{ cat("0\n") } # put the highest I we covered to be the lowest to get ready for the next round of while loop i_low <- i_high invisible(gc()) } parallel::stopCluster(cl) invisible(gc()) } #-------[ save the results ]-------# { comment(final) <- paste("From", lower_bound, "to", upper_bound) saveRDS(object = final, file = paste0(paste(format(Sys.time(), "%Y%m%d-%H%M%S"), "final", lower_bound, "to", upper_bound, sep = "_"), ".RDS")) } -
Nov 8, 2019 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,99 @@ ################################################################################ ## This code is in response to the following tweet of "Fermat's Library" ## ## https://twitter.com/fermatslibrary/status/1180837639915819008?s=20 ## ## ## ## Author: Mehrad Mahmoudian ## ## License: GPL3 ## ## ## ## Description: ## ## The in the aforementioned tweet it is mentioned that 81 is the only ## ## number that has (8+1)^2=81 feature. I thought it is a nice morning ## ## coding challenge. From that tweet either of these conditions can be ## ## deduced: ## ## - if you treat the number as a string and cut it in half, the square ## ## of sums should be equal to the number. ## ## - if you treat the number as a string and split it into individual ## ## digits, the square of sums should be equal to the number ## ## - if you treat the number as a string and break it at some point(s), ## ## the square of sums should be equal to the number. ## ## ## ## I realized the last one is the most complex one and also it contains the ## ## other two in itself, so I challenged myself :D ## ################################################################################ func_cutter <- function(x, cuts){ ## Description: ## A function to cut a string at given points ## ## Arguments: ## x: A character vector of length 1 ## cuts: a numeric vector of length smaller than nchar(x) # create a collective variable final <- c() # go through all the cutting points that is provided to the function for(i in seq_along(cuts)){ # if the index is 1 if(i == 1){ # append the first few chracters as an item to the collective vector final <- c(final, substr(x = x, start = 1, stop = cuts[i])) } # if we got to the end of the cutting points list if(i == length(cuts)){ # set the ending to be the end of the string tmp_end_index <- nchar(x) }else{ # using the next cutting point as the ending position tmp_end_index <- cuts[i+1] } final <- c(final, substr(x = x, start = cuts[i]+1, stop = tmp_end_index)) } return(final) } # iterate through the range for(i in 10:100000){ # iterate through the possible number of cuts we can have to the string for(j in seq_len(nchar(i)-1)){ # generate all possible combination of cutting positions considering the # constraint on total number of cuts allowed combinations <- apply(combn(x = nchar(i)-1, m = j), 2, function(a){ func_cutter(x = i, cuts = a) }) # go through all generated pieces and do the math apply(combinations, 2, function(x){ x_numeric <- as.numeric(x) # if the square of sums was equal to the number we are testing if((sum(x_numeric)^2) == i){ # print the combination cat(paste0("(", paste0(x, collapse = "+"), ")^2"), "=", i, "\n") } }) } } # (8+1)^2 = 81 # (10+0)^2 = 100 # (1+29+6)^2 = 1296 # (20+25)^2 = 2025 # (30+25)^2 = 3025 # (6+72+4)^2 = 6724 # (8+2+81)^2 = 8281 # (82+8+1)^2 = 8281 # (98+01)^2 = 9801 # (98+0+1)^2 = 9801 # (100+00)^2 = 10000 # (100+0+0)^2 = 10000 # (5+5+225)^2 = 55225 # (88+209)^2 = 88209