#!/usr/bin/Rscript coins.available <- c(200, 100, 50, 20, 10, 5, 2, 1) ways_to_split_money <- function(cents,lastcoin=0) { if(!lastcoin) { cache <<- matrix(0,cents,length(coins.available)) lastcoin <- cents } use_cache <- function(cents,lastcoin,value=0) { if(! lastcoin || ! lastcoin %in% coins.available) return(value) if(value) cache[cents,which(coins.available==lastcoin)] <<- value return(cache[cents,which(coins.available==lastcoin)]) } if(cents < 2) return(1) if(use_cache(cents,lastcoin)>0) return(use_cache(cents,lastcoin)) coins <- coins.available coins <- coins[which(cents>=coins)] coins <- coins[which(lastcoin>=coins)] return(use_cache(cents,lastcoin,sum(sapply(coins, function(coin) ways_to_split_money(cents-coin, coin))))) } split_money <- function(cents,lastcoin=cents,path=NULL) { res <- list(NULL); res[[1]] <- NULL # initialize a empty list if(cents == 0) return(list(path)) for(coin in coins.available) { if(cents >= coin && lastcoin >= coin) { for(sequence in split_money(cents-coin, coin, c(path, coin))) res[[length(res)+1]] <- sequence } } return(res) } format_output <- function(data) { res <- list(NULL); res[[1]] <- NULL for(coins in data) { output <- character() coins.rle <- rle(coins) coins.data <- data.frame(coin = coins.rle$values, count = coins.rle$lengths) for(i in 1:length(coins.data$count)) output <- c(output, paste(c(coins.data$coin[i], coins.data$count[i]), collapse=" cent x ")) res[[length(res)+1]] <- output } return(res) } for(i in as.numeric(commandArgs(TRUE))) { if(i<50) print(format_output(split_money(i))) else print(ways_to_split_money(i)) }