Skip to content

Instantly share code, notes, and snippets.

@skeeto
Last active September 26, 2022 13:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save skeeto/f20c47961edbee9d8c168d684fb8bcf8 to your computer and use it in GitHub Desktop.
Save skeeto/f20c47961edbee9d8c168d684fb8bcf8 to your computer and use it in GitHub Desktop.
Word lock wheel selector
// 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