Optimize the Scralphabet Scralphabet
A normal bag of Scrabble tiles contains the following letters (? is a blank tile, which can stand for any other letter):
AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??

The letters have the following value:
{&quot;A&quot;: 1,&quot;B&quot;: 3,&quot;C&quot;: 3,&quot;D&quot;: 2,&quot;E&quot;: 1,&quot;F&quot;: 4,&quot;G&quot;: 2,&quot;H&quot;: 4,&quot;I&quot;: 1,&quot;J&quot;: 8,&quot;K&quot;: 5,&quot;L&quot;: 1,&quot;M&quot;: 3,&quot;N&quot;: 1,&quot;O&quot;: 1,&quot;P&quot;: 3,&quot;Q&quot;: 10,&quot;R&quot;: 1,&quot;S&quot;: 1,&quot;T&quot;: 1,&quot;U&quot;: 1,&quot;V&quot;: 4,&quot;W&quot;: 4,&quot;X&quot;: 8,&quot;Y&quot;: 4,&quot;Z&quot;: 10,&quot;?&quot;: 0}

Given a normal bag of Scrabble tiles, construct the highest-scoring set of non-intersecting words (i.e., individual words, not on a Scrabble board) given the following conditions:

The score for each word is sum(letter_values) * length(word).
You may only include a maximum of one word starting with each letter of the alphabet (so, a maximum of 26 words).
Only valid Scrabble words (from this dictionary) may be included. You may read the dictionary from a file, hard-code it (ugh), or scrape it from the website.
You need not use every tile, but all unused tiles form a single word, scored the same way, which subtracts from your score.

If you wish, your code may accept two inputs: the bag contents as a string, and the letter values in some format similar to a python dict (as above); alternatively, you can hard-code the bag contents and letter values. It should output the words in your set, their respective scores, and your total score, in some reasonable format.
Highest scoring set of words wins, with ties going to first posted.
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 &lt;stdio.h&gt;
#include &lt;stdint.h&gt;
#include &lt;string.h&gt;
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 &lt; 16 ? a.lo &lt;&lt; 4 : a.hi) &gt;&gt; 4*(l&amp;15) &amp; 15; }
int matches_val(uint64_t a, uint64_t b) {
    uint64_t mask = 0x1111111111111111ll;
    return !((a - b ^ a ^ b) &amp; mask);
}
int matches(struct lc all, struct lc a) { return matches_val(all.hi,a.hi) &amp;&amp; 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&lt;27; i++) if (count(cur, i) &amp;&amp; pts[i]&gt;1) return;
    for (i = 0; i &lt; n10; i++) if(!(used &amp; (1 &lt;&lt; (w10[i].w[0] &amp; 31))) &amp;&amp; matches(w10[i].lc, cur)) {
        for (c = 0; c&lt;level; c++) printf("%s ",w15[picks[c]].w);
        printf("%s\n",w10[i].w);
    }
    return;
    }
    for (i = 0; i &lt; 26;i++) if (count(cur,fs[i])) break;
    must = fs[i];
    for (c = 0; c &lt; w15c[must]; c++) { i = w15l[must][c]; if(!(used &amp; (1 &lt;&lt; (w15[i].w[0] &amp; 31))) &amp;&amp; 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 &lt;&lt; (w15[i].w[0] &amp; 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-&gt;w,s);
    for (;*s;s++)
    if (*s&amp;16) w-&gt;lc.hi += 1ll &lt;&lt; 4*(*s&amp;15); else w-&gt;lc.lo += 1ll &lt;&lt; 4*(*s&amp;15) - 4;
    if (c) for (i = 0; i &lt; 27;i++) if (count(w-&gt;lc,i)) f[i]++, w15l[i][w15c[i]++] = w-w15;
}
int main() {
    int i;
    char s[20];
    while(scanf("%s ",s)&gt;0) {
    if (strlen(s) == 15) ins(w15 + n15++,s,1);
    if (strlen(s) == 10) ins(w10 + n10++,s,0);
    }
    for (i = 0; i &lt; 26;i++) fs[i] = i+1;
    qsort(fs, 26, sizeof(int), cmpfs);
    try(pool, 0, 0);
}


Usage:

$time ./scrab &lt;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 &lt; 27; i++) if (count(a, i) &gt; 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) &amp; 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.