Hjælp til wordsolver

det skal nok være en database - jeg ville lave en række opslag
hvis du har fx 'aerb'
så start loop ved at slå op på første tegn
select * where ord like 'a*'
hvis der er hit, så kør loop, hvor du tjekker på 2. tegn
select * where ord like 'ae*'
select * where ord like 'ar*'
select * where ord like 'ab*'
hvor der er hit (fx ab) kører du loop med 3. tegn
select * where ord like 'abr*'
select * where ord like 'abe*'
hvor der er hit (fx abe) kører du loop med 4. tegn
select * where ord like 'aber'
og tæller op hvis hit.

Jeg har selv lavet et lignende program, så jeg kan snyde i Whirley Words på min iPhone. Hemmeligheden er at den sorterer alle input bogstaverne, og den sorterer alle ordene  i ordlisten. Derefter er det let at checke om et ord fra ordlisten er et subset af bogstaverne.

Herunder er C koden jeg lavede. Den er lavet meget hurtigt, og det er sikkert meget grimt, men det virker da ;-)


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int comparec ( const void * a, const void * b ) {
  return strcmp( (char *)a, (char *)b );
}
int compares ( const void * a, const void * b ) {
  char * c = *(char **)a;
  char * d = *(char **)b;
  int cl = strlen(c);
  int dl = strlen(d);
  return cl == dl ? strcmp( c, d ) : cl-dl ;
}

int main(int argc, char ** argv) {

  if (argc != 4) {
    printf("Usage %s: %s letters minlength /usr/share/dict/danish\n", argv[0], argv[0]);
    return 0;
  }

  char * letters = argv[1]; //"suwalr"; // letters
  int minword = atoi(argv[2]); // min word length

  int i, j;
  int llen = strlen(letters);
  for (i = 0; i < llen; ++i) if (letters[i] > 'Z' && letters[i] <= 'z') letters[i] -= 'a'-'A';
  qsort(letters, llen, 1, comparec);

  printf ("Letters: %s\n", letters);

  char * words = malloc(sizeof(char)*10000000);
  FILE * fp = fopen(argv[3], "r"); // american-english
  fread(words, 1, 10000000, fp);
  if (!feof(fp)) puts("Buffer too small, more to read.");
  fclose(fp);

  char * results[100000];
  int nresults = 0;

  char word[100];
  char * pch = strtok(words, "\n");
  while (pch != NULL) {
    int wlen = strlen(pch);
    if (wlen >= minword) {
      for (i = 0; i < wlen; ++i) if (pch[i] > 'Z' && pch[i] <= 'z') pch[i] += 'A'-'a';
      memcpy(word, pch, wlen);
      qsort(word, wlen, 1, comparec);
      for (i = 0, j = 0; j < wlen && i < llen; ++i) if (word[j] == letters[i]) j++;
      if (j == wlen) results[nresults++] = pch;
    }
    pch = strtok (NULL, "\n");
  }

  qsort(results, nresults, sizeof(char *), compares);

  for (i = 0; i < nresults; ++i) puts(results[i]);

  return 0;
}

Det kan være at det her slet ikke er effektivt nok, eller at det simpelthen er for svært at implementere.

Men måske er det en god ide at gemme summen af bogstaverne i din dictionary og samtidig sortere din dictionary efter denne sum.

I starten af din dictionary (eller et andet sted) kan du have alle de forskellige summer gemt i en sorteret liste så du kan lave en binær søgning på denne liste.

Når du har fundet den rigtige sum i listen kan du fx have en pointer som fører dig til det rigtige sted i din dictionary.

Her har du fået det hele indskrænket en del og kan begynde at søge efter ord der har de samme bogstaver som dit input.

Qobra læg et svar hvis du vil ha point

Håber det kunne bruges.