(Golf) mobile phone numbers -> words

[mischief]

I've been fiddling around with mobiles recently and playing with perl to get it to give me a list of possible words I could use instead of the number. Who can come up with the shortest sub that would calculate the possible combinations for a given number, check them against /usr/share/dict/words, and return the possibles as a list?

I have to say, my attempt is pitiful and it's not worth posting, but I'd be interested to see other people's.

BTW, just in case anyone's wondering, this is not a homework assignment or anything - I just think it's an interesting puzzle.

[jmcnamara]

This is a program rather than a sub. It is 160 chars without unnecessary whitespace. I don't know what you are supposed to do with 1 and 0. Get another phone number I guess. ;-)

#!/usr/bin/perl -snl

BEGIN{
    for ($N) {
        s/[10]//g;
        s/2/[abc]/g;
        s/3/[def]/g;
        s/4/[ghi]/g;
        s/5/[jkl]/g;
        s/6/[mno]/g;
        s/7/[pqrs]/g;
        s/8/[tuv]/g;
        s/9/[wxyz]/g
    }
}

/^$N$/oi&&print

You can run it like this:     phonenum -N=7375 /usr/dict/words
I tried this with most of my friends' and family's phone numbers and none of them generated any words. :-(

John.
--

[MeowChow]

I really like this "inverted" regex method. As a sub, it can be brought down to 105 characters:

sub n{
$n=shift;@l=('','',qw([abc] [def] [ghi] [jkl] [mno] [pqrs] [tuv] [wxyz
+]));$n=~s/./$l[$&]/ge;grep/^$n$/,@_
}

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print

[Masem]

And as a starting solution, here's mine at 133 characters:

my @d = qw( respect strength ); # yeah, weak dictionary, sue me!
my $n = "7377328";
my %a = ( 1=>[],
          2=>['a','b','c'],
          3=>['d','e','f'],
          4=>['g','h','i'],
          5=>['j','k','l'],
          6=>['m','n','o'],
          7=>['p','q','r','s'],
          8=>['t','u','v'],
          9=>['w','x','y','z']
    );

my @r = words( $n, \%a, \@d );
print join ",",@r;
print "\n";

sub words{
#234567890123456789012345678901234567890123456789012345678901234567890
+123456789012345678901234567890123
my($n,$a,$d,@l,@b,$c,$e)=@_;@b=split//,$n;@a=('');for(@b){$c=$_;@a=map
+{$e=$_;map{$e.$_}@{$a->{$c}}}@a};
grep{$c=$_;grep{$c eq$_}@$d}@a
}

Note that if %a was an array, it would only change a set of curly braces to square ones, and would not change the character count.

update ok, this only handles the case of matching exactly one word from the dictionary; more work would be needed to find any word combo.

---

Dr. Michael K. Neylon - [e-mail] || "You've left the lens cap of your mind on again, Pinky" - The Brain

[the_slycer]

Here's my entry at 113, note that all we pass is the wordlist and the key to search for:

sub num{
$k=shift;for(@_){chomp;$n=lc;$n=~y/abcdefghijklmnopqrstuvwxyz/22233344
+455566677778889999/;push@{$h{$n}},$_;$h{$k}
}

Update: I believe that I can add 5 (score:118) and get all possibilities.

sub num{
#23456789_123456789_123456789_123456789_123456789_123456789_123456789_
[phone]_123456789_123456789_123456789_12345678
$k=shift;for(@_){$n=$_;chomp;lc;y/abcdefghijklmnopqrstuvwxyz/222333444
[phone]/;push@{$h{$k}},$n if$k=~$_}$h{$k}
}

Update #2: Now down to 107 with all possibilities, now returns an array instead of ref to array

sub num{
$k=shift;for(@_){chomp;lc;$n=$_;y/abcdefghijklmnopqrstuvwxyz/222333444
[phone]/;push@h,$n if$k=~$_}@h
}

Returns a reference to all single words found.
ie: pass it 7825 and /usr/dict/words and it will return pub,puck,qua,rub,sub,suck etc.. (not including single letters).

[Masem]

Not a solution, just helping others to solve the problem:

I would assume that the dictionary is already stored as @d. Also, the number to letters translation matrix is stored as a hash of arrays:

my %a = ( 1 => [],
          2 => [a,b,c],
          3 => [d,e,f],  
          etc... );

This should help everyone start from the same footing.

---

Dr. Michael K. Neylon - [e-mail] || "You've left the lens cap of your mind on again, Pinky" - The Brain

[tilly]

I think there is room for creativity here...

%d=map{($_,int((-90+ord)/3.14))}"a".."p","r".."y";

[Masem]

The only critique I have on that is that some phones do have 'q' and 'z' (on the 7 and 9 respectively). While chances are that for the problem at hand, adding q and z won't increase the word set that much, there's still a possiblity of doing so.

Though I find it rather interesting that PI comes into play, though that's probably a rementent from the rotary phone era.

---

Dr. Michael K. Neylon - [e-mail] || "You've left the lens cap of your mind on again, Pinky" - The Brain

[mischief]

You could also store it as an array:

my @letters = (
        undef,
        undef,
        ['a', 'b', 'c'],
        ['d', 'e', 'f'],
        ['g', 'h', 'i'],
        ['j', 'k', 'l'],

etc.

[bobione]

As it's a Golf, you should use $[=1 or 2 to change array's indice.
BTW: I don't really understand your problem.

Update: thanks mischief, for yor explanation.

BobiOne KenoBi

[tachyon]

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:

                    1
                  1   1
                1   2   1
              1   3   3   1
            1   4   6   4   1
          1   5   10  10  5   1
        1   6   15  20  15  6   1
      1   7   21  35  35  21  7   1
    1   8   28  56  70  56  28  8   1
  1   9   36  84  126 126 84  36  9   1

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...

tachyon

[tye]

The number of possible letter arrangements is 3**10, or 59,049, not anywere near 3e10! But even if there were 3e10 possible arrangements, that doesn't matter. You need to search the dictionary so instead of generating some huge list of possible words and then searching the dictionary to see if any of them are in it, instead go through the dictionary and see if any of the words would match the phone number!

        - tye (but my friends call me "Tye")

[tachyon]

Hi tye, lost the plot in the translation from 3exp10 as I wrote to decimal. Register error. I failed to register my error!

To absolve myself from moronicity I will have to code a respnse now. Damn you (red baron)! I just hate it when people point out my calculations are a *mere* 50805 orders of magnitude off.

Despite that fundamental error the basic binomial point is valid. For any ten digit number we are most likely to find a solution from several small words rather than one big word:

For example, here are some 10 letter possibilities:

Colt Firearms: very-big-gun; rat-a-tat-tat; you-are-dead;

Perl Security: the-perl-kid; perl-hacker; naughty-boy; the-perl-man; perl-secure; now-at-intel; perl-busted; lawyer-crap; in-hot-water; im-ok-for-now; just-call-us; dont-foobar; we-know-perl;

Perl lyrics: p-p-p-p-p-p-perl; shes-my-baby;.....p-p-p-perl, I don't mean maybe.

Losing the plot: sleep(rand*28800)

tachyon