StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Final Edit: <strong>Solved!</strong> Here is a solution.</p> <pre><code>GNAWN|jOULE RACHE|EUROS IDIOT|STEAN PINOT|TRAvE TRIPY|SOLES -----+----- HOWFF|ZEBRA AGILE|EQUID CIVIL|BUXOM EVENT|RIOJA KEDGY|ADMAN </code></pre> <p>Here's a photo of it constructed with my scrabble set. <a href="http://twitpic.com/3wn7iu" rel="noreferrer">http://twitpic.com/3wn7iu</a></p> <p>This one was easy to find once I had the right approach, so I bet you could find many more this way. See below for methodology.</p> <hr> <p>Construct a prefix tree from the dictionary of 5 letter words for each row and column. Recursively, a given tile placement is valid if it forms valid prefixes for its column and row, and if the tile is available, and if the next tile placement is valid. The base case is that it is valid if there is no tile left to place.</p> <p>It probably makes sense to just find all valid 5x5 boards, like Glenn said, and see if any four of them can be combined. Recursing to a depth of 100 doesn't sound like fun.</p> <p>Edit: Here is version 2 of my code for this.</p> <pre><code>#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> typedef union node node; union node { node* child[26]; char string[6]; }; typedef struct snap snap; struct snap { node* rows[5]; node* cols[5]; char tiles[27]; snap* next; }; node* root; node* vtrie[5]; node* htrie[5]; snap* head; char bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2}; const char full_bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2}; const char order[26] = {16,23,9,25,21,22,5,10,1,6,7,12,15,2,24,3,20,13,19,11,8,17,14,0,18,4}; void insert(char* string){ node* place = root; int i; for(i=0;i<5;i++){ if(place->child[string[i] - 'A'] == NULL){ int j; place->child[string[i] - 'A'] = malloc(sizeof(node)); for(j=0;j<26;j++){ place->child[string[i] - 'A']->child[j] = NULL; } } place = place->child[string[i] - 'A']; } memcpy(place->string, string, 6); } void check_four(){ snap *a, *b, *c, *d; char two_total[27]; char three_total[27]; int i; bool match; a = head; for(b = a->next; b != NULL; b = b->next){ for(i=0;i<27; i++) two_total[i] = a->tiles[i] + b->tiles[i]; for(c = b->next; c != NULL; c = c->next){ for(i=0;i<27; i++) three_total[i] = two_total[i] + c->tiles[i]; for(d = c->next; d != NULL; d = d->next){ match = true; for(i=0; i<27; i++){ if(three_total[i] + d->tiles[i] != full_bag[i]){ match = false; break; } } if(match){ printf("\nBoard Found!\n\n"); for(i=0;i<5;i++){ printf("%s\n", a->rows[i]->string); } printf("\n"); for(i=0;i<5;i++){ printf("%s\n", b->rows[i]->string); } printf("\n"); for(i=0;i<5;i++){ printf("%s\n", c->rows[i]->string); } printf("\n"); for(i=0;i<5;i++){ printf("%s\n", d->rows[i]->string); } exit(0); } } } } } void snapshot(){ snap* shot = malloc(sizeof(snap)); int i; for(i=0;i<5;i++){ printf("%s\n", htrie[i]->string); shot->rows[i] = htrie[i]; shot->cols[i] = vtrie[i]; } printf("\n"); for(i=0;i<27;i++){ shot->tiles[i] = full_bag[i] - bag[i]; } bool transpose = false; snap* place = head; while(place != NULL && !transpose){ transpose = true; for(i=0;i<5;i++){ if(shot->rows[i] != place->cols[i]){ transpose = false; break; } } place = place->next; } if(transpose){ free(shot); } else { shot->next = head; head = shot; check_four(); } } void pick(x, y){ if(y==5){ snapshot(); return; } int i, tile,nextx, nexty, nextz; node* oldv = vtrie[x]; node* oldh = htrie[y]; if(x+1==5){ nexty = y+1; nextx = 0; } else { nextx = x+1; nexty = y; } for(i=0;i<26;i++){ if(vtrie[x]->child[order[i]]!=NULL && htrie[y]->child[order[i]]!=NULL && (tile = bag[i] ? i : bag[26] ? 26 : -1) + 1) { vtrie[x] = vtrie[x]->child[order[i]]; htrie[y] = htrie[y]->child[order[i]]; bag[tile]--; pick(nextx, nexty); vtrie[x] = oldv; htrie[y] = oldh; bag[tile]++; } } } int main(int argc, char** argv){ root = malloc(sizeof(node)); FILE* wordlist = fopen("sowpods5letters.txt", "r"); head = NULL; int i; for(i=0;i<26;i++){ root->child[i] = NULL; } for(i=0;i<5;i++){ vtrie[i] = root; htrie[i] = root; } char* string = malloc(sizeof(char)*6); while(fscanf(wordlist, "%s", string) != EOF){ insert(string); } free(string); fclose(wordlist); pick(0,0); return 0; } </code></pre> <p>This tries the infrequent letters first, which I'm no longer sure is a good idea. It starts to get bogged down before it makes it out of the boards starting with x. After seeing how many 5x5 blocks there were I altered the code to just list out all the valid 5x5 blocks. I now have a 150 MB text file with all 4,430,974 5x5 solutions.</p> <p>I also tried it with just recursing through the full 100 tiles, and that is still running.</p> <p>Edit 2: Here is the list of all the valid 5x5 blocks I generated. <a href="http://web.cs.sunyit.edu/~levyt/solutions.rar" rel="noreferrer">http://web.cs.sunyit.edu/~levyt/solutions.rar</a> </p> <p>Edit 3: Hmm, seems there was a bug in my tile usage tracking, because I just found a block in my output file that uses 5 Zs.</p> <pre><code>COSTE ORCIN SCUZZ TIZZY ENZYM </code></pre> <p>Edit 4: Here is the final product.</p> <pre><code>#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> typedef union node node; union node { node* child[26]; char string[6]; }; node* root; node* vtrie[5]; node* htrie[5]; int score; int max_score; char block_1[27] = {4,2,0,2, 2,0,0,0,2,1,0,0,2,1,2,0,1,2,0,0,2,0,0,1,0,1,0};//ZEBRA EQUID BUXOM RIOJA ADMAN char block_2[27] = {1,0,1,1, 4,2,2,1,3,0,1,2,0,1,1,0,0,0,0,1,0,2,1,0,1,0,0};//HOWFF AGILE CIVIL EVENT KEDGY char block_3[27] = {2,0,1,1, 1,0,1,1,4,0,0,0,0,3,2,2,0,2,0,3,0,0,1,0,1,0,0};//GNAWN RACHE IDIOT PINOT TRIPY //JOULE EUROS STEAN TRAVE SOLES char bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2}; const char full_bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2}; const char order[26] = {16,23,9,25,21,22,5,10,1,6,7,12,15,2,24,3,20,13,19,11,8,17,14,0,18,4}; const int value[27] = {244,862,678,564,226,1309,844,765,363,4656,909,414,691,463,333,687,11998,329,218,423,536,1944,1244,4673,639,3363,0}; void insert(char* string){ node* place = root; int i; for(i=0;i<5;i++){ if(place->child[string[i] - 'A'] == NULL){ int j; place->child[string[i] - 'A'] = malloc(sizeof(node)); for(j=0;j<26;j++){ place->child[string[i] - 'A']->child[j] = NULL; } } place = place->child[string[i] - 'A']; } memcpy(place->string, string, 6); } void snapshot(){ static int count = 0; int i; for(i=0;i<5;i++){ printf("%s\n", htrie[i]->string); } for(i=0;i<27;i++){ printf("%c%d ", 'A'+i, bag[i]); } printf("\n"); if(++count>=1000){ exit(0); } } void pick(x, y){ if(y==5){ if(score>max_score){ snapshot(); max_score = score; } return; } int i, tile,nextx, nexty; node* oldv = vtrie[x]; node* oldh = htrie[y]; if(x+1==5){ nextx = 0; nexty = y+1; } else { nextx = x+1; nexty = y; } for(i=0;i<26;i++){ if(vtrie[x]->child[order[i]]!=NULL && htrie[y]->child[order[i]]!=NULL && (tile = bag[order[i]] ? order[i] : bag[26] ? 26 : -1) + 1) { vtrie[x] = vtrie[x]->child[order[i]]; htrie[y] = htrie[y]->child[order[i]]; bag[tile]--; score+=value[tile]; pick(nextx, nexty); vtrie[x] = oldv; htrie[y] = oldh; bag[tile]++; score-=value[tile]; } } } int main(int argc, char** argv){ root = malloc(sizeof(node)); FILE* wordlist = fopen("sowpods5letters.txt", "r"); score = 0; max_score = 0; int i; for(i=0;i<26;i++){ root->child[i] = NULL; } for(i=0;i<5;i++){ vtrie[i] = root; htrie[i] = root; } for(i=0;i<27;i++){ bag[i] = bag[i] - block_1[i]; bag[i] = bag[i] - block_2[i]; bag[i] = bag[i] - block_3[i]; printf("%c%d ", 'A'+i, bag[i]); } char* string = malloc(sizeof(char)*6); while(fscanf(wordlist, "%s", string) != EOF){ insert(string); } free(string); fclose(wordlist); pick(0,0); return 0; } </code></pre> <p>After finding out how many blocks there were (nearly 2 billion and still counting), I switched to trying to find certain types of blocks, in particular the difficult to construct ones using uncommon letters. My hope was that if I ended up with a benign enough set of letters going in to the last block, the vast space of valid blocks would probably have one for that set of letters.</p> <p>I assigned each tile a value inversely proportional to the number of 5 letter words it appears in. Then, when I found a valid block I would sum up the tile values, and if the score was the best I had yet seen, I would print out the block.</p> <p>For the first block I removed the blank tiles, figuring that the last block would need that flexibility the most. After letting it run until I had not seen a better block appear for some time, I selected the best block, and removed the tiles in it from the bag, and ran the program again, getting the second block. I repeated this for the 3rd block. Then for the last block I added the blanks back in and used the first valid block it found.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload