Dear list,
In a little numbers game, I've hit a performance snag and I'm not sure
how to code this in C.
The game is the following: how many 8-digit numbers have the sum of
their digits equal to 17?
The brute-force answer could be:
maxi <- 9 # digits from 0 to 9
N <- 5 # 8 is too large
test <- 17 # for example's sake
sum(rowSums(do.call(expand.grid, c(list(1:maxi), rep(list(0:maxi),
N-1)))) == test)
## 3675
Now, if I make N = 8, R stalls for some time and finally gives up
with:
Error: cannot allocate vector of size 343.3 Mb
I thought I could get around this using Reduce() to recursively apply
rowSum to intermediate results, but it doesn't seem to help,
a=list(1:maxi)
b=rep(list(0:maxi), N-1)
foo <- function(a, b, fun="sum", ...){
switch(fun,
'sum' = rowSums(do.call(expand.grid, c(a, b))),
'mean' = rowMeans(do.call(expand.grid, c(a, b))),
apply(do.call(expand.grid, c(a, b)), 1, fun, ...)) # generic
case
}
sum(Reduce(foo, list(b), init=a) == test)
## 3675 # OK
Same problem with N=8.
Now, if N was fixed I could write a little C code to do this
calculation term-by-term, something along those lines,
test = 0;
for (i1=1, i1=9, i1++) {
for (i2=0, i2=9, i2++) {
[... other nested loops ]
test = test + (i1 + i2 + [...] == 17);
} [...]
}
but here the number of for loops, N, should remain a variable.
In despair I coded this in R as a wicked eval(parse()) construct, and
it does produce the expected result after an awfully long time.
makeNestedLoops <- function(N=3){
startLoop <- function(ii, start=1, end=9){
paste("for (i", ii, " in seq(",start,", ",end,")) {\n", sep="")
}
first <- startLoop(1)
inner.start <- lapply(seq(2, N), startLoop, start=0)
calculation <- paste("test <- test + (", paste("i", seq(1, N),
sep="", collapse="+"), "==17 )\n")
end <- replicate(N, "}\n")
code.to.run <- do.call(paste, c(list(first), inner.start,
calculation, end))
cat(code.to.run)
invisible(code.to.run)
}
test <- 0
eval(parse(text = makeNestedLoops(8)) )
## 229713
I hope I have missed a better way to do this in R. Otherwise, I
believe what I'm after is some kind of C or C++ macro expansion,
because the number of loops should not be hard coded.
Thanks for any tips you may have!
Best regards,
baptiste
