mmahmoudian/which_square_of_sums.R

## which_square_of_sums.R
################################################################################
## 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                                                              ##
##                                                                            ##
## 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                           ##
################################################################################


#-------[ 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"))

}
	################################################################################
	## 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 ##
	## ##
	## 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 ##
	################################################################################


	#-------[ 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"))

	}