phone.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <ctype.h>
   5
   6 FILE *f;
   7
   8 #define HASH_SIZE 16384
   9
  10 typedef unsigned char byte;
  11
  12 struct word {
  13   struct word *next;
  14   int len;
  15   byte w[1];
  16 };
  17
  18 struct word *htab[HASH_SIZE];
  19
  20 byte c2n[256];
  21 /*                  0      1     2      3      4     5     6     7      8      9   */
  22 byte *n2c[10] = { "OQZ", "IJ", "ABC", "DEF", "GH", "KL", "MN", "PRS", "TUV", "WXY" };
  23
  24 void init(void)
  25 {
  26   int i;
  27   byte *c;
  28
  29   for(i=0; i<10; i++)
  30     {
  31       for(c=n2c[i]; *c; c++)
  32         {
  33           c2n[*c] = '0'+i;
  34           c2n[tolower(*c)] = '0'+i;
  35         }
  36       c2n['0'+i] = '0'+i;
  37     }
  38 }
  39
  40 unsigned int hash(byte *x, int len)
  41 {
  42   int h = len;
  43
  44   while (*x && len--)
  45     h = h * 13337 + c2n[*x++];
  46   return h & (HASH_SIZE - 1);
  47 }
  48
  49 void read_it(void)
  50 {
  51   byte l[256];
  52   int h, s, c=0;
  53   struct word *w;
  54
  55   while (fgets(l, sizeof(l)-1, f))
  56     {
  57       byte *z = strchr(l, '\n');
  58       if (z)
  59         *z = 0;
  60       s = strlen(l);
  61       h = hash(l, s);
  62       w = malloc(sizeof(struct word) + s);
  63       if (!w)
  64         {
  65           perror("malloc");
  66           exit(1);
  67         }
  68       w->next = htab[h];
  69       htab[h] = w;
  70       w->len = s;
  71       strcpy(w->w, l);
  72       c++;
  73     }
  74   printf("Scanned %d words.\n", c);
  75 }
  76
  77 struct word *find(byte *x, int l)
  78 {
  79   int h = hash(x, l);
  80   struct word *w = htab[h];
  81   byte *p, *q;
  82   while (w)
  83     {
  84       if (w->len == l)
  85         {
  86           int ll = l;
  87           p = x;
  88           q = w->w;
  89           while (ll && *p++ == c2n[*q++])
  90             ll--;
  91           if (!ll)
  92             return w;
  93         }
  94       w = w->next;
  95     }
  96   return NULL;
  97 }
  98
  99 #define MAXL 128
 100
 101 struct word *last[MAXL];
 102 int best[MAXL];
 103
 104 void print(int z)
 105 {
 106   struct word *w;
 107
 108   if (!z)
 109     return;
 110   w = last[z];
 111   if (!w)
 112     {
 113       printf("!!!BUG!!!");
 114       return;
 115     }
 116   print(z - w->len);
 117   printf("%s ", w->w);
 118 }
 119
 120 void sentence(byte *z)
 121 {
 122   int l = strlen(z);
 123   int i, j;
 124   struct word *w;
 125
 126   if (l >= MAXL-1)
 127     {
 128       printf("TOO LONG.\n");
 129       return;
 130     }
 131   best[0] = 0;
 132   for(i=1; i<=l; i++)
 133     {
 134       last[i] = NULL;
 135       best[i] = -1;
 136       for(j=0; j<i; j++)
 137         if (best[j] >= 0 && (w = find(z+j, i-j)) && (best[i] < 0 || best[i] > best[j] + 1))
 138           {
 139             last[i] = w;
 140             best[i] = best[j] + 1;
 141           }
 142     }
 143   if (best[l] <= 0)
 144     printf("NO SOLUTION.");
 145   else
 146     print(l);
 147   putchar('\n');
 148 }
 149
 150 int main(int argc, char **argv)
 151 {
 152   byte l[256];
 153   byte *k;
 154
 155   if (!(f = fopen("voc", "r")))
 156     {
 157       perror("Unable to open vocabulary");
 158       return 1;
 159     }
 160   init();
 161   read_it();
 162
 163   while (fgets(l, sizeof(l), stdin) && (k = strchr(l, '\n')))
 164     {
 165       *k = 0;
 166       sentence(l);
 167     }
 168   return 0;
 169 }