[R] expand.grid game

[baptiste auguie]

Hi,

Thanks for the link, I guess it's some kind of a classic game. I'm a
bit surprised by your timing, my ugly eval(parse()) "solution"
definitely took less than one hour with a machine not so different
from yours,

system.time( for (i in 10000079:11000079) if (sumdigits(i)==17) {idx<-c(idx,i)})
   user  system elapsed
 34.050   1.109  35.791

I'm surprised by idx<-c(idx,i), isn't that considered a sin in the R
Inferno? Presumably growing idx will waste time for large N.

Thanks,

baptiste

2009/12/19 David Winsemius <dwinsemius at comcast.net>:
>
> On Dec 19, 2009, at 1:36 PM, baptiste auguie wrote:
>
>> 2009/12/19 David Winsemius <dwinsemius at comcast.net>:
>>>
>>> On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
>>>
>>>> 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?
>>>
>>> And are you considering the number "00000089" to be in the acceptable
>>> set?
>>> Or is the range of possible numbers in 10000079:98000000 ?
>>>
>>
>> The latter, the first digit should not be 0. But if you have an
>> interesting solution for the other case, let me know anyway.
>>
>> I should also stress that this is only for entertainment and curiosity's
>> sake.
>
> The sequence of numbers whose digit sum is 13 is one of the ATT integer
> sequences:
>
> http://www.research.att.com/~njas/sequences/A143164
>
> No R implementations there, only Maple and Mathematica. Rather than doing
> strsplit()'s, I thought that a mathematical approach would be faster for a
> sumdigits function:
>
> sumdigits <- function(x) { s=0; for (i in 1:(1+floor(log(x, base=10))) ){
>                                         s<-s+x%%10; x<-x%/%10}
>                            return(s) }
>
> # what follows would be expected to take roughly 1/100th  and 1/50th of the
> time of a complete enumeration but is useful for estimating the size of the
> result and the time of an exhaustive search:
>
>> system.time( for (i in 10000079:11000079) if (sumdigits(i)==17)
>> {idx<-c(idx,i)})
>   user  system elapsed
>  30.997   3.516  34.403
>
>> system.time( for (i in 10000079:12000079) if (sumdigits(i)==17)
>> {idx<-c(idx,i)})
>   user  system elapsed
>  55.975   2.433  58.218
>
>> head(idx)
> [1] 10000079 10000088 10000097 10000169 10000178 10000187
>
>> length(idx)
> [1] 31572
>
> So it looks as though an exhaustive strategy would take a bit under an hour
> on my machine (a 2 year-old device) and be a vector around 1578600 elements
> in length. (Takes very little memory, and would undoubtedly be faster if I
> could use more than one core.)
>
>>
>> baptiste
>
> David Winsemius, MD
> Heritage Laboratories
> West Hartford, CT
>
>