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.
1Can the valid Scrabble word dictionary be hardcoded as well? – Lynn – 2015-05-15T13:17:06.770
2Also, what if my program is
print"FOO18\nBAR15\nBAZ42\n...\n1523"
? – Lynn – 2015-05-15T13:20:29.5172
@Mauris Hardcoding the output is a banned loophole.
– Geobits – 2015-05-15T13:24:44.2831@Geobits he says you can though. "alternatively, you can hard-code the values". – Tim – 2015-05-15T13:25:22.327
3@Tim The OP is referring to the input. – Martin Ender – 2015-05-15T13:25:50.747
1@Geobits It's not that simple though. There are many forms of "hardcoding" (like simplifying the search space if you already know what you'll find). Or you could write a really elaborate code to find the optimal solution, and then replace it by a brute force for golfing. – Martin Ender – 2015-05-15T13:26:53.460
@MartinBüttner Yea, my reply was to bare hardcoding, as Mauris was suggesting here.
– Geobits – 2015-05-15T13:28:58.773@Mauris you can if you want...? I'd rather you read it from a file, though, to make the code more readable. And, yes, hardcoding your output is a banned loophole. – sirpercival – 2015-05-15T13:35:14.843
And if someone posts a golfed brute-force, I hope they'll also post the algorithm that led to their solution. – sirpercival – 2015-05-15T13:45:57.763
As far as I know, the normal rule for [code-challenge] is that the code you post must generate the output you post. If someone posts a brute force that is obviously unfeasible to run within years, along with an optimized output, I think the people here are smart enough to see through that. – Geobits – 2015-05-15T14:07:02.187
@Geobits: Speak for yourself. :P – Alex A. – 2015-05-15T14:39:49.257
3Pro tip: Be careful with how you handle the full Scrabble dictionary. I was working on a solution in R and merging the words with their scores used all available memory and crashed my computer. – Alex A. – 2015-05-15T16:17:58.097
Question about the scoring: "A" scores 1 * 1 = 1, while "ABC" scores (1 + 3 + 3) * 3 = 21? Is this correct? – 2012rcampion – 2015-05-17T17:33:15.183
yes, that's correct. – sirpercival – 2015-05-17T17:45:31.867