# C, 2765 (optimal)
### Edit
Now all in a single C file. This just finds all the optimal solutions. They all must have 6 words of 15 letters and one 10-letter word consisting of 8 letters of value 1 and two blanks. For that I only need to load a fraction of the dictionary and I don't have to look for 15 letter words with blanks.
The code is a simple exhaustive depth-first search.
#include <stdio.h>
#include <stdint.h>
#include <string.h>
struct w {
struct lc { uint64_t hi,lo; } lc;
char w[16];
} w15[6000], w10[40000];
int n15,n10;
struct lc pool = { 0x12122464612, 0x8624119232c4229 };
int pts[27] = {0,1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};
int f[27],fs[26], w15c[27],w15l[27][6000];
int count(struct lc a, int l) { return (l < 16 ? a.lo << 4 : a.hi) >> 4*(l&15) & 15; }
int matches_val(uint64_t a, uint64_t b) {
uint64_t mask = 0x1111111111111111ll;
return !((a - b ^ a ^ b) & mask);
}
int matches(struct lc all, struct lc a) { return matches_val(all.hi,a.hi) && matches_val(all.lo,a.lo); }
int picks[10];
void try(struct lc cur, int used, int level) {
int c, i, must;
if (level == 6) {
for (i = 0; i<27; i++) if (count(cur, i) && pts[i]>1) return;
for (i = 0; i < n10; i++) if(!(used & (1 << (w10[i].w[0] & 31))) && matches(w10[i].lc, cur)) {
for (c = 0; c<level; c++) printf("%s ",w15[picks[c]].w);
printf("%s\n",w10[i].w);
}
return;
}
for (i = 0; i < 26;i++) if (count(cur,fs[i])) break;
must = fs[i];
for (c = 0; c < w15c[must]; c++) { i = w15l[must][c]; if(!(used & (1 << (w15[i].w[0] & 31))) && matches(cur, w15[i].lc)) {
struct lc b = { cur.hi - w15[i].lc.hi, cur.lo - w15[i].lc.lo };
picks[level] = i;
try(b, used + (1 << (w15[i].w[0] & 31)), level+1);
}}
}
int cmpfs(int *a, int *b){return f[*a]-f[*b];}
void ins(struct w*w, char *s, int c) {
int i;
strcpy(w->w,s);
for (;*s;s++)
if (*s&16) w->lc.hi += 1ll << 4*(*s&15); else w->lc.lo += 1ll << 4*(*s&15) - 4;
if (c) for (i = 0; i < 27;i++) if (count(w->lc,i)) f[i]++, w15l[i][w15c[i]++] = w-w15;
}
int main() {
int i;
char s[20];
while(scanf("%s ",s)>0) {
if (strlen(s) == 15) ins(w15 + n15++,s,1);
if (strlen(s) == 10) ins(w10 + n10++,s,0);
}
for (i = 0; i < 26;i++) fs[i] = i+1;
qsort(fs, 26, sizeof(int), cmpfs);
try(pool, 0, 0);
}
Usage:
$time ./scrab <sowpods.txt
cc -O3 scrab.c -o scrab
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS LAURUSTINE
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS LUXURIATED
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS LUXURIATES
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS ULTRAQUIET
JUXTAPOSITIONAL DEMISEMIQUAVERS ACKNOWLEDGEABLY WEATHERPROOFING CONVEYORIZATION FEATHERBEDDINGS UTRICULATE
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS LAURUSTINE
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS LUXURIATED
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS LUXURIATES
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS ULTRAQUIET
JUXTAPOSITIONAL DEMISEMIQUAVERS WEATHERPROOFING ACKNOWLEDGEABLY CONVEYORIZATION FEATHERBEDDINGS UTRICULATE
OVERADJUSTMENTS QUODLIBETARIANS ACKNOWLEDGEABLY WEATHERPROOFING EXEMPLIFICATIVE HYDROGENIZATION RUBIACEOUS
OVERADJUSTMENTS QUODLIBETARIANS WEATHERPROOFING ACKNOWLEDGEABLY EXEMPLIFICATIVE HYDROGENIZATION RUBIACEOUS
real 0m1.754s
user 0m1.753s
sys 0m0.000s
Note every solution is printed twice because when adding a 15-letter 'W' word 2 orders are created because there are 2 'W' tiles.
The first solution found with the point breakdown:
JUXTAPOSITIONAL 465
DEMISEMIQUAVERS 480
ACKNOWLEDGEABLY 465
WEATHERPROOFING 405
CONVEYORIZATION 480
FEATHERBEDDINGS 390
LAURUSTINE (LAURU?TI?E) 80
no tiles left
### Edit: explanation
What makes searching the entire space possible? While adding a new word I only take into account words that have the rarest remaining letter. This letter need to be in some word anyway (and a 15 letter word since this will be a non 1-value letter, though I don't check for that). So I start with words containing `J, Q, W, W, X, Z` which have counts around `50, 100, 100, 100, 200, 500`. At lower levels I get more cutoff because some words are eliminated by the lack of letters. Breadth of the search tree at each level:
0: 1
1: 49
2: 3046
3: 102560
4: 724040
5: 803959
6: 3469
Of course a lot of cutoff is gained by not checking non-optimal solutions (blanks in 15 letter words or shorter words). So it is lucky that 2765 solution can be achieved with this dictionary (but it was close, only 2 combinations of 15 letter words give a reasonable leftover). On the other hand it is easy to modify the code to find lower scoring combinations where not all the leftover 10 letters are 1-valued, though it would be harder to prove this would be an optimal solution.
Also the code shows classic case of premature optimization. This version of `matches` function makes the code only 30% slower:
int matches(struct lc all, struct lc a) {
int i;
for (i = 1; i < 27; i++) if (count(a, i) > count(all, i)) return 0;
return 1;
}
I even figured out how to make the bit magic parallel comparison even shorter than in my original code (highest nibble cannot be used in this case, but this is not a problem, as I only need 26 out of 32 nibbles):
int matches_val(uint64_t a, uint64_t b) {
uint64_t mask = 0x1111111111111111ll;
return !((a - b ^ a ^ b) & mask);
}
But it gives zero advantage.
### Edit
Writing the explanation above I realized that most of the time is spent on scanning the list of words for those containing a specific letter not in the `matches` function. Calculating the lists upfront gave 10x speedup.