Last active
September 26, 2022 13:20
-
-
Save skeeto/f20c47961edbee9d8c168d684fb8bcf8 to your computer and use it in GitHub Desktop.
Word lock wheel selector
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Word lock wheel selector | |
// $ cc -o wordlock wordlock.c | |
// $ ./wordlock </usr/share/dict/words | |
// Ref: https://old.reddit.com/r/algorithms/comments/xo6y6p | |
// This is free and unencumbered software released into the public domain. | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#define N 4 // number of wheels | |
#define M 10 // letters per wheel | |
#define W 20000 // maximum words to handle | |
static int cmp(const void *a, const void *b) { return *(int *)b-*(int *)a; } | |
static int cmpword(const void *a, const void *b) { return memcmp(a, b, N); } | |
int main(void) | |
{ | |
int nwords = 0; | |
static struct { char s[N]; } words[W]; | |
char line[64]; | |
while (nwords<W && fgets(line, sizeof(line), stdin)) { | |
if (strspn(line, "abcdefghijklmnopqrstuvwxyz")==N && line[N]<32) { | |
memcpy(words[nwords++].s, line, N); | |
} | |
} | |
for (int n = 0; n < N; n++) { | |
// compute and sort histogram | |
struct { int n; char c; } hist[] = { | |
{0, 0},{0, 1},{0, 2},{0, 3},{0, 4},{0, 5},{0, 6},{0, 7},{0, 8}, | |
{0, 9},{0,10},{0,11},{0,12},{0,13},{0,14},{0,15},{0,16},{0,17}, | |
{0,18},{0,19},{0,20},{0,21},{0,22},{0,23},{0,24},{0,25} | |
}; | |
for (int i = 0; i < nwords; i++) { | |
hist[words[i].s[n]-'a'].n++; | |
} | |
qsort(hist, 26, sizeof(hist[0]), cmp); | |
// build a set for the wheel | |
long result = 0; | |
for (int m = 0; m < M; m++) { | |
result |= 1L << hist[m].c; | |
} | |
for (int i = 0; i < 26; i++) { | |
if (1L<<i & result) { | |
putchar('a' + i); | |
} | |
} | |
putchar('\n'); | |
// eliminate now-invalid words | |
for (int i = 0; i < nwords; i++) { | |
long b = 1L << (words[i].s[n] - 'a'); | |
if (!(result & b)) { | |
words[i--] = words[--nwords]; | |
} | |
} | |
} | |
printf("%d words\n", nwords); | |
qsort(words, nwords, sizeof(words[0]), cmpword); | |
for (int i = 0; i < nwords; i++) { | |
printf("%.*s%c", N, words[i].s, (i%12==11)||(i==nwords-1)?'\n':' '); | |
} | |
return fflush(stdout) || ferror(stdout) || ferror(stdin); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment