/*
This is a modification of the scrabble move finder 'findmoves.c' also
in this directory.
This one however attempts to place a move on an 'upwords' board. See the
scrabble version for common comments. At the moment, it appears to
be working. The basic engine took about 2 hours to convert from the
Scrabble source, the biggest difference being that the placement loop
was changed to a recursive procedure. This allowed multiple variations
on placements at each row/col address, as was required by the choice
of placing a tile on an existing stack - or not. I'm currently adding
scoring and some tile management to actually make it play a game.
Note: upwords has a single "Qu" tile, so the easiest way to handle
this is to preprocess the word list: remove all words where a Q
is not followed by a U, then conflate all QU's to a single Q. Remember
to output any Q's as "Qu" if doing a fancy display.
There appear to be AT LEAST two sets of rules for 'upwords', so the
rules and scoring adhered to in this program will definitely not please
everyone, at least until I parameterise the game for both variations.
(One is from a US Milton Bradley 10x10 board, the other is from a UK Parker
Bros 10x10 board, travel version)
Meanwhile, let's use these rules:
http://www.backgammon.com/consumer/instruct/upwords.pdf
Note: is is almost possible to work out the score just from the
pattern of the word that is to be played at any position, ignoring
the actual letters that would be played. ('almost' is because there
is a small bonus if a "Qu" is played). It should be possible to
trim the search using this fact, so that we don't waste time
enumerating possible words for a slot if we already know that the
score can't be any higher than one we have already looked at.
This should speed up move generation considerably.
PENDING:
Scoring is not quite right yet: haven't handled "Qu" bonus yet.
Need to tidy code where bonus 20 is added for a bingo
Still to add code to reject plurals.
Need to refine code which implements this rule:
Change a word already on the board to a different word.
If a word is changed, at least one letter of the original
word must be used in the new word.
Strategy: (according to hints on the MSN gaming zone...)
Play shorter words than you might play in a Scrabble game.
Build upward (or upword!) before building outward, as you might in a
Scrabble game.
Try to place tiles on the corner squares.
Try to place the fifth (topmost) tile on a stack.
Get rid of bad tiles quickly.
Learn to identify two-letter words.
Avoid building adjacent words unless you are a master UpWords player;
your total score will be lower in the long run.
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
#include "splib.h"
#ifndef FALSE
#define TRUE (0==0)
#define FALSE (0!=0)
#endif
int spell_verbose = FALSE;
static int debug = FALSE;
#define WIDTH 10
#define HEIGHT 10
#define RACKSIZE 7
#define MAX_TILES 100
/* 1..WIDTH for board, 0 and (WIDTH+1) for tombstones */
/* these two are swapped x/y with orientation */
static char board[(HEIGHT+2)][(WIDTH+2)]; /* row, col format */
static char height[(HEIGHT+2)][(WIDTH+2)];
/* these two are recalculated on each orientation so don't need to be swapped */
static char *crosschecks[(HEIGHT+2)][(WIDTH+2)];
static int vertical_score[(HEIGHT+2)][(WIDTH+2)];
static char remaining_tiles[MAX_TILES+1];
static int score, tiles_left_in_bag;
static int tiles_held = 0;
static char tiles[RACKSIZE+1];
/* To do: when calculating crosschecks, work out how much putting a tile
on the crosscheck square will get you, from the vertical component.
Pre-compute all but the last part (i.e. the value of the placed tile) */
#define HORIZONTAL 1
#define VERTICAL 2
static NODE *dawg;
static INDEX nedges;
#define swap(a,b,temp) {temp = a; a = b; b = temp;}
/*--------------------- crosscheck code -------------------------*/
static int crosscheck_internal(
NODE *dawg, INDEX i,
char *word, char *res, char *set,
int len, int *found
)
{
int endsword, last, ch, target;
NODE node;
INDEX link;
static int wildch = '\0';
for (;;) {
node = dawg[i++];
ch = (int)((node >> V_LETTER) & M_LETTER);
last = ((node & (INDEX)M_END_OF_NODE) != 0);
endsword = ((node & M_END_OF_WORD) != 0);
link = node & M_NODE_POINTER;
res[len] = ch; res[len+1] = '\0';
target = ((int)*word)&255;
if (ch != 0) {
if (ch == target || target == '?') {
if (target == '?') {
wildch = ch;
}
if (endsword && *(word+1) == '\0') {
int i;
(*found)++;
/* Add ch to crosscheck set if not already there */
/* We just assume only 1 '?' per word, and last wildch was it */
if (strchr(set, wildch) == NULL) {
i = strlen(set);
set[i] = wildch; set[i+1] = '\0';
}
}
if (*(word+1) != '\0' && link != 0)
(void) crosscheck_internal(dawg, link, word+1, res, set, len+1, found);
}
}
if (last) break;
}
return(0==0);
}
char *convert_wildcard_to_permitted_set(NODE *dawg, char *word)
{
char result[MAX_WORD_LEN];
static char set[MAX_WORD_LEN];
int i = 0;
*set = '\0';
if (debug) fprintf(stdout, "wildcard: %s\n", word);
(void)crosscheck_internal(dawg, (INDEX)ROOT_NODE, word, result, set, 0, &i);
if (i == 0) return(NULL);
if (debug) fprintf(stdout, " -> %s\n", set);
return(set);
}
/*--------------------- placement code -------------------------*/
static void fix_upwords(
NODE *dawg, INDEX i,
char *word, char *res, char *tilesleft,
int len, int *found, int L, int n,
int hscore, int vscore, int orientation,
int word_is_flat
)
{
int endsword, last, ch, target;
NODE node;
INDEX link;
for (;;) {
node = dawg[i++];
ch = (int)((node >> V_LETTER) & M_LETTER);
last = ((node & (INDEX)M_END_OF_NODE) != 0);
endsword = ((node & M_END_OF_WORD) != 0);
link = node & M_NODE_POINTER;
res[len] = ch; res[len+1] = '\0';
target = *word; target &= 255;
if (ch != 0) {
if (ch == target) { /* matches a tile on the board already */
if (endsword && *(word+1) == '\0') {
fprintf(stdout, "play: %s at %c%d %s for %d%s\n", res, L, n,
(orientation == HORIZONTAL ? "across" : "down"),
(word_is_flat ? 2*hscore : hscore)+vscore,
(word_is_flat ? " (plus word is flat - bonus points)" : ""));
(*found)++;
}
if (*(word+1) != '\0' && link != 0) {
fix_upwords(dawg, link, word+1, res, tilesleft,
len+1, found, L, n, hscore, vscore, orientation,
word_is_flat);
}
} else if (target == '[') { /* Is this letter in our set of valid letters? */
char choices[(WIDTH * (256+2)) + 1];
char *s, *saved = word;
strcpy(choices, word+1);
s = strchr(choices, ']'); /* We assume well-formed expressions */
*s = '\0';
word = strchr(word, ']');
if (strchr(choices, ch) != NULL) {
if (endsword && *(word+1) == '\0') {
char *s;
int i;
s = strchr(tilesleft, ch);
if (s != NULL) { /* Do we have the actual tile? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
fprintf(stdout, "play: %s at %c%d %s for %d%s\n", res, L, n,
(orientation == HORIZONTAL ? "across" : "down"),
(word_is_flat ? 2*hscore : hscore)+vscore,
(word_is_flat ? " (word is flat - bonus points)" : ""));
(*found)++;
}
}
if (*(word+1) != '\0' && link != 0) {
char *s;
int i;
s = strchr(tilesleft, ch);
if (s != NULL) { /* Do we have the actual tile? */
i = *s;
*s = tilesleft[0]; tilesleft[0] = i;
fix_upwords(dawg, link, word+1, res, tilesleft+1,
len+1, found, L, n, hscore, vscore, orientation, word_is_flat);
}
}
}
word = saved;
}
}
if (last) break;
}
}
void upwords_match(
NODE *dawg, char *word, char *tiles, int L, int n, int orientation,
int word_is_flat, int hscore, int vscore)
{
int i = 0;
char result[MAX_WORD_LEN];
result[0] = '\0';
if (debug) fprintf(stdout, "match: '%s' using '%s' at %c%0d %s\n", word, tiles, L, n,
(orientation == HORIZONTAL ? "across" : "down"));
fix_upwords(dawg, (INDEX)ROOT_NODE, word, result, tiles, 0, &i, L, n,
hscore, vscore,
orientation, word_is_flat);
}
/*--------------------------------------------------------------*/
/*
Board layout is different from Scrabble.
*/
void read_board(char *fname)
{
int row, col;
int c;
FILE *sample;
sample = fopen(fname, "r");
if (sample == NULL) {
fprintf(stderr, "Cannot open board file '%s'\n", fname);
exit(0);
}
for (row = 1; row <= WIDTH; row++) {
if (debug) fprintf(stderr, "Row %02d: ", row);
for (col = 1; col <= WIDTH; col++) {
height[row][col] = 0;
c = fgetc(sample);
if (c == ' ') {
c = fgetc(sample);
}
if (isdigit(c)) {
height[row][col] = c-'0';
c = fgetc(sample);
}
if (isalpha(c)) { /* Take care with locale for other language versions */
if (height[row][col] == 0) height[row][col] = 1;
board[row][col] = tolower(c);
if (debug) fprintf(stderr, "%c", tolower(c));
} else if (debug) fprintf(stderr, " ");
}
c = fgetc(sample); /* newline */
if (c != '\n') {
fprintf(stderr, "Data format in .dat file\n");
exit(0);
}
if (debug) fprintf(stderr, "\n");
}
tiles_held = 0;
for (col = 0; col < RACKSIZE; col++) {
c = fgetc(sample);
if (c == '?') continue;
if (c == '*') c = '?';
if (isalpha(c)) c = tolower(c);
tiles[tiles_held++] = c;
}
tiles[tiles_held] = '\0';
fscanf(sample, " %d %d\n", &score, &tiles_left_in_bag);
if (debug) {
fprintf(stderr, "%0d Tiles: %s\n", tiles_held, tiles);
}
remaining_tiles[0] = '\0';
fgets(remaining_tiles, MAX_TILES+1, sample); /* Don't care if error */
fclose(sample);
}
/*--------------------------------------------------------------*/
/*
In 'upwords', you can place a letter on an existing tile, so unlike
scrabble, this procedure is not called only for blank spaces. However
if tiles are already stacked 5 deep, no more tiles may be placed
here, so the fixed tile is added to the pattern, not a restricted
wild-card set (eg "s" instead of "[s]") as no tile may be placed here.
*/
char *create_crosscheck_wildcard(int r, int c)
{
char crosscheck[(WIDTH+2)];
char *s;
int rp;
int vscore = 0;
int flat = TRUE;
/* Already tiles here 5 deep so crosscheck is meaningless */
if (height[r][c] == 5) return(NULL);
/* none above and none below? */
if ((board[r-1][c] == 0) && (board[r+1][c] == 0)) return(NULL);
rp = r-1;
while (board[rp][c] != 0) {
vscore += height[rp][c];
if (height[rp][c] > 1) flat = FALSE;
// do i need to port this bugfix that I made to scrabble?
// was getting blank as a wildcard, not as a fixed letter...
//if (*s == '?') *s = board[rp][c]; // FIX FOR BUG IN "wildcard:"
rp -= 1; /* what's above? */
}
rp += 1; /* row of 1st letter in crosscheck word */
s = crosscheck; while (rp != r) *s++ = board[rp++][c];
vscore += height[r][c];
if (height[r][c] > 0) flat = FALSE;
*s++ = '?'; /* r */
rp = r+1;
while ((*s++ = board[rp][c]) != '\0') {
vscore += height[rp][c];
if (height[rp][c] > 1) flat = FALSE;
// do i need to port this bugfix that I made to scrabble?
// was getting blank as a wildcard, not as a fixed letter...
//if (*s == '?') *s = board[rp][c]; // FIX FOR BUG IN "wildcard:"
rp += 1;
/* what's below? */;
}
if (flat) vscore = vscore * 2 + 1; /* two points per tile if flat */
vertical_score[r][c] = vscore; /* NOT including this tile */
return(strdup(crosscheck));
}
/*--------------------------------------------------------------*/
/* It should be possible to add up most of the score using only the
template from 'slot()' rather than the actual word. A small adjustment
can be made at the end for playing a "Qu" etc. */
void slot_internal(int orig_r, int orig_c,
int r, int c,
int still_to_place, int placed,
char *pattern, /* wild-card pattern, built on fly */
int touches_center, int touches_horiz,
int touches_vert, int touches_below,
int tile_showing, int word_is_flat,
int orientation, int hscore, int vscore)
{
int valid;
int pp = strlen(pattern);
char *s;
/* No more loop. Just place one, and recurse. If I had done this
with the scrabble program to begin with, I wouldn't have had the
stupid bug to do with playing blanks as the same letter as another
letter you hold in the rack... */
/* Ran off end of board with tiles still to place? */
if ((c > WIDTH) && (still_to_place > 0)) return;
if (height[r][c] == 5) {
int i;
/* There is already a tile on the board here. */
pattern[pp++] = board[r][c]; pattern[pp] = '\0';
slot_internal(orig_r, orig_c,
r, c+1, still_to_place, placed, pattern,
touches_center, touches_horiz,
touches_vert, touches_below,
TRUE, FALSE, orientation, hscore+height[r][c], vscore);
/* add the horizontal component of the score */
pattern[--pp] = '\0'; /* undo recursion */
return;
} else if (height[r][c] > 0) {
int i;
/* There is already a tile on the board here, but we're going to skip it */
pattern[pp++] = board[r][c]; pattern[pp] = '\0';
slot_internal(orig_r, orig_c,
r, c+1, still_to_place, placed, pattern,
touches_center, touches_horiz,
touches_vert, touches_below,
TRUE, (height[r][c] > 1 ? FALSE : word_is_flat),
orientation, hscore+height[r][c], vscore);
pattern[--pp] = '\0'; /* undo recursion */
/* Now try again with a tile on top of this letter or empty square */
word_is_flat = FALSE;
hscore += (height[r][c]+1);
if (vertical_score[r][c] != 0) vscore += (vertical_score[r][c] + 1);
} else {
/* single tile being placed on board, none underneath */
hscore += 1;
if (vertical_score[r][c] != 0) vscore += (vertical_score[r][c] + 1);
}
/* square is either empty or has < 5 tiles on it */
/* If center squares are empty this must be the first move */
if ((board[WIDTH/2][HEIGHT/2] == 0) && (board[(WIDTH/2)+1][(HEIGHT/2)] == 0)
&& (board[WIDTH/2][(HEIGHT/2)+1] == 0) && (board[(WIDTH/2)+1][(HEIGHT/2)+1] == 0)
&& ((WIDTH/2 <= r) && (r <= (WIDTH/2)+1))
&& ((WIDTH/2 <= c) && (c <= (WIDTH/2)+1))
) {
touches_center = (touches_center || TRUE);
}
if (board[r][c-1] != 0 || board[r][c+1] != 0) touches_horiz = (touches_horiz || TRUE);
if (board[r-1][c] != 0 || board[r+1][c] != 0) touches_vert = (touches_vert || TRUE);
if (board[r][c] != 0) touches_below = (touches_below || TRUE);
if (crosschecks[r][c] == NULL) {
crosschecks[r][c] = strdup(tiles);
}
/* If no valid crosscheck at all, then reject this slot */
if (*crosschecks[r][c] == '!') return;
assert(strcmp(crosschecks[r][c], "?") != 0);
if ((board[r][c] != 0) && ((s = strchr(crosschecks[r][c], board[r][c])) != NULL)) {
/* Don't allow tile to be placed on top of same letter */
*s++ = '\0'; sprintf(pattern+pp, "[%s%s]", crosschecks[r][c], s); *--s = board[r][c];
if (strcmp(pattern+pp, "[]") == 0) return;
} else {
sprintf(pattern+pp, "[%s]", crosschecks[r][c]);
}
pp = strlen(pattern);
placed += 1; still_to_place -= 1;
if (still_to_place != 0) {
slot_internal(orig_r, orig_c,
r, c+1, still_to_place, placed, pattern,
touches_center, touches_horiz,
touches_vert, touches_below,
tile_showing, word_is_flat,
orientation, hscore, vscore);
pattern[pp] = '\0';
return;
}
/* after placing all tiles, are there still some letters abutting
to the right? If so, add them to the string to be matched */
{int p = c+1; while (board[r][p] != 0) {
hscore += height[r][p];
if (height[r][p] > 1) word_is_flat = FALSE;
touches_horiz = TRUE; tile_showing = TRUE;
pattern[pp++] = board[r][p++];
}}
pattern[pp] = '\0';
valid = (touches_horiz ||
(touches_vert && (placed > 1)) ||
(touches_center && (placed > 1))); /* Eliminate any plays totally on top of another word */
if (touches_below) {
/* at least one new tile is stacked on an existing tile */
/* and there are no tiles in the new word which *don't* have a tile
placed on top of them */
if (!tile_showing) valid = FALSE;
/* NOTE: We have a problem here:
??F??
R
E
DAVID
If we play a word over ??F??, according to the rules if you cover
a word completely, it's not a valid play. Well, 'F' is not a
word, and this is not what the rule is meant to block, but it's
hard for the program to see that.
For instance,
??F?S
R T
E E
DAVID
E
if we play 5 tiles over ??F?S, this too is probably allowed, BUT:
??FJ?
RE
EM
DAVID
playing over this pattern "??FJ?" (let's assume FJ is a valid word)
should NOT be allowed. So the test must be that there are two abutting
tiles being covered up somewhere within the placement. Not impossible
to define, but tricky coding that I haven't done yet.
*/
}
/* In upwords we ban words which are formed by appending just an S */
if (touches_horiz && (placed == 1)) {
/* TO DO: because we haven't yet done final word generation, we can't
just add a check for a final -s and discard the word if present;
what we have to do is look at a word where we may be adding the
final -s, and remove that option.
eg if our pattern is "word[sy]" then we convert it to "word[y]",
but if our pattern is "word[s]" then when we convert it to "word[]"
we *can* remove it from our options.
*/
}
/* At this point we COULD not bother to walk the dawg if we can already
tell that the maximum score possible is less than some existing try */
if (valid) upwords_match(dawg, pattern, tiles,
(orientation == HORIZONTAL ? orig_c : orig_r)-1+'A',
(orientation == HORIZONTAL ? orig_r : orig_c), orientation,
word_is_flat, hscore, vscore + (placed == 7 ? 20 : 0));
/* vscore is not the ideal way to pass in the bingo bonus */
}
void slot(int r, int c, int still_to_place, int orientation) /* wrapper */
{
int touches_center = FALSE;
int touches_horiz = FALSE;
int touches_vert = FALSE;
int touches_below = FALSE;
int tile_showing = FALSE;
int word_is_flat = TRUE;
char pattern[(WIDTH * (256+2)) + 1];
int placed=0;
pattern[0] = '\0';
/* Covered with an earlier hook */
if (board[r][c-1] != 0) return;
return(slot_internal(r, c,
r, c, still_to_place, placed, pattern,
touches_center, touches_horiz,
touches_vert, touches_below,
tile_showing, word_is_flat,
orientation, 0, 0));
}
int main(int argc, char **argv)
{
int orientation = 0;
int row = 0, col = 0;
int length = 0;
char *dict = NULL, *boardfile = NULL;
if (argc != 3) {
if (argc == 2) {
dict = "twl98-q"; /* Tweaked for "Qu" -> "q" */
} else {
fprintf(stderr, "syntax: %s board.dat dict?\n", argv[0]);
exit(1);
}
} else dict = argv[2]; /* Default word list is TWL98 */
boardfile = argv[1];
if (!dawg_init(dict, &dawg, &nedges)) {
fprintf(stderr, "%s: cannot open wordlist '%s'\n", argv[0], dict);
exit(2);
}
for (row = 0; row < (WIDTH+2); row++) { /* Clear the arrays */
for (col = 0; col < (WIDTH+2); col++) {
board[row][col] = height[row][col] = 0;
crosschecks[row][col] = NULL;
}
}
read_board(boardfile);
for (orientation = HORIZONTAL; orientation <= VERTICAL; orientation++) {
for (row = 1; row < (HEIGHT+1); row++) {
for (col = 0; col < (WIDTH+2); col++) {
vertical_score[row][col] = 0;
if (crosschecks[row][col] != NULL) free(crosschecks[row][col]);
crosschecks[row][col] = NULL;
}
for (col = 1; col < (WIDTH+1); col++) {
if (crosschecks[row][col] != NULL) free(crosschecks[row][col]);
crosschecks[row][col] = create_crosscheck_wildcard(row, col);
if (crosschecks[row][col] == NULL) {
crosschecks[row][col] = strdup(tiles); /* was strdump("?") */
} else {
char *s = convert_wildcard_to_permitted_set(dawg, crosschecks[row][col]);
free(crosschecks[row][col]);
crosschecks[row][col] = strdup((s == NULL) ? "!" : s);
}
}
for (col = 1; col < (WIDTH+1); col++) {
for (length = 1; length <= tiles_held; length++) {
if (debug) fprintf(stdout, "Testing %c%d %s: %d\n",
(orientation == HORIZONTAL ? col : row)-1+'A',
(orientation == HORIZONTAL ? row : col),
(orientation == HORIZONTAL ? "across" : "down"),
length);
slot(row, col, length, orientation);
}
}
} /* Try every row on the board */
/* flip the board around the x=y diagonal */
assert(WIDTH == HEIGHT);
for (row = 1; row < (WIDTH+1); row++) {
for (col = 1; col < (WIDTH+1); col++) {
int i;
if (row > col) { /* avoid doing twice (which would be a no-op) */
swap(board[row][col], board[col][row], i);
swap(height[row][col], height[col][row], i);
}
}
}
} /* end of horiz/vert placement loop */
{int i; FILE *sample;
sample = fopen(boardfile, "w"); if (sample == NULL) exit(1);
/* If want to make best play on board and save it, do it here */
for (row = 1; row < HEIGHT+1; row++) {
for (col = 1; col < WIDTH+1; col++) {
if (height[row][col] <= 1) fputc(' ', sample); else fputc('0'+height[row][col], sample);
if (height[row][col] > 0) fputc(toupper(board[row][col]), sample); else fputc('.', sample);
}
fputc('\n', sample);
}
for (i = 0; i < strlen(tiles); i++) fputc(toupper(tiles[i]), sample);
for (i = strlen(tiles); i < 7; i++) fputc('?', sample);
fprintf(sample, " %d %d\n", score, tiles_left_in_bag);
if (*remaining_tiles != '\0') fprintf(sample, "tiles: %s\n", remaining_tiles);
fclose(sample);
}
exit(0);
}