On a standard telephone, the numbers 1-9 can be used to correspond to a set of letters:
1: space 2: ABC 3: DEF 4: GHI 5: JKL 6: MNO
7: PQRS 8: TUV 9: WXYZ
Using the keypad, you can 'spell' words by entering the digits that correspond to each letter of the word. For example, 'words' is spelled 96737.
For this problem, we are given a dictionary file called with no more than 100,000 words, one per line, sorted in alphabetical order. Each word is comprised of no more than 18 characters, all lowercase letters from the phone keypad. Here is a (very short!) example of a dictionary file we will use in the examples:
Your program should read a string of digits (from 2 to 9, not using 1 as space) from the console and find the words in the dictionary whose spellings contain that series of consecutive digits anywhere within the word.
• If there are no matches, print the string 'No matches'
• If there is one match, print the matching word.
• If there are n>1 matches, print the string 'n matches:' followed by the matching
words, one per line.
NOTE: To make it easier to read the examples below, these are the 'spellings' of the words in words.txt, in digits:
>>1-5
Same person and we have been trolled constantly.
Name:
Anonymous2008-02-27 12:34
haha, I remember this. I think I converted words.txt to all digits and then used a hash table.
Name:
Anonymous2008-02-27 12:58
XTREME
Name:
Anonymous2008-02-27 13:03
#!/usr/bin/env python
KEYS = {}
for i, k in enumerate(
(' ', 'abc', 'def',
'ghi', 'jkl', 'mno',
'pqrs', 'tuv', 'wxyz')):
for c in k: KEYS[c] = str(i+1)
if __name__ == '__main__':
from sys import argv
wordlist = dict((''.join(KEYS[c] for c in word), word)
for word in open(argv[1]).read().split('\n'))
match = [w for (n, w) in wordlist.iteritems() if argv[2] in n]
if match:
if len(match) > 1:
print len(match), 'matches'
for w in match:
print w
else:
print 'No matches'
Name:
Anonymous2008-02-27 13:16
>>9
Takes no less then a minute to find 223355 on the 1,000,000 word file.
What the fuck? They are giving 24 hours for the solutions of these, I thought it would be something more difficult (faggot to be participant of the 2008 challenge)
for(c = m; c; c = c->next)
{
printf("%s", c->word);
}
return 0;
}
Name:
Anonymous2008-02-27 14:42
>>18
I think they would need more than 20 to saturate an EXPERT PROGRAMMER
but well, I was going to take a drivers license test some time in the duration of this anyway.
Name:
Anonymous2008-02-27 14:57
vanilla: 8264554
O RLY?
#!/bin/perl
use feature "say";
open WORDS, '<', shift or die;
$_ = pop or die;
die if /[^2-9]/;
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;
$r = $_;
$num = @found = grep /$r/o, <WORDS>;
say "No matches" unless $num;
say "$num matches:\n" if $num > 1;
say @found;
Name:
Anonymous2008-02-27 15:03
Might have some bugs, but wrote this in around 5 minutes.
#include <stdio.h>
char words[1800000];
char wordt[1800000];
main(int argc, char **argv) {
FILE *i = fopen(argv[1],"rb");
int j=0;
char *s;
for(;;) {
switch(wordt[j]=fgetc(i)) {
case 'a': case 'b': case 'c':
words[j++] = '2';
break;
case 'd': case 'e': case 'f':
words[j++] = '3';
break;
case 'g': case 'h': case 'i':
words[j++] = '4';
break;
case 'j': case 'k': case 'l':
words[j++] = '5';
break;
case 'm': case 'n': case 'o':
words[j++] = '6';
break;
case 'p': case 'q': case 'r': case 's':
words[j++] = '7';
break;
case 't': case 'u': case 'v':
words[j++] = '8';
break;
case 'w': case 'x': case 'y': case 'z':
words[j++] = '9';
break;
case EOF:
fclose(i);
words[j] = 0;
goto done_1;
case '\n':
while(j%18) {
words[j]= wordt[j] = ' ';
j++;
}
}
}
done_1:
s = &words;
while(s=strstr(s,argv[2])) {
int a = (s-words / 18)*18;
while((a+1)%18)
putchar(wordt[a++]);
putchar('\n');
}
}
Name:
Anonymous2008-02-27 15:07
>>23
that looks suspiciously like an example from K&R
Any solution that makes a big string of enumerated digit sequences for each word and searches that string for the digit sequence is wrong. Clever, but wrong. Think about it.