|Just another Perl shrine|
Re: (Golf) mobile phone numbers - wordsby tachyon (Chancellor)
|on May 29, 2001 at 18:14 UTC||Need Help??|
Hi, I don't know about in the US but in AUS we have 10 digit moblile numbers. Given that each number has 3 possible letters you might use in round numbers the search space is 59049 letter combinations per number
Unfortunately the generation of the test keys is not *particularly* straight forward. Using my ten digit scenario for each of the 59049 test cases we might have:
one word (a) where a=10 letters
two words (a,b) where a+b=10 letters,
three words (a,b,c) where a+b+c = 10 letters
ten words (a..j) where a+b+c+d+e+f+g+h+i+j=10 letters If you remember the binomial expansion (as I vaguely do - it was a while ago) you will remember the pyramid:
What this shows us is that while there is obviously only one test case for a ten letter match there are 9 possibilities for an a+b=10 letter match, 36 possibilities for an a+b+c=10 letter match....
Adding this up we find that there are 512 possibilities we need to consider for each of the 59049 10 letter combinations. The total search space is 30,233,088. I thought this might take a long time but that was when I thought it would be a somewhat larger search space. Should be doable in under a minute of CPU time.
more to follow...