4
\$\begingroup\$

Let's say that we are programming a game that lets you play Scrabble®.

  • We have a board with tiles placed on it, and empty cells are either normal or have multiplier properties (double or triple the points for a word or for a single letter).
  • Each tile has a value and blank tiles have no value.

Thee goal here is to write a method that, given a new_word structure, will:

  • verify that this word can be placed onto the grid at the specified position (the originating rack has the missing letters, it is not out of board range, blank tiles will not be adjacent on the board)
  • return the number of points granted to the player.
  • letter multipliers have priority over word multipliers
  • all new words on the grid are counted (both horizontal and vertical)

Below are sample structures provided as an example.

// SCRABBLE® STRUCTURES

// a single Scrabble® tile.
struct tile
{
    // blank tiles are recognized by their value of 0.
    // The value of 'letter' is a space (L' ') until they
    // are positioned on the board. From that stage the
    // value of 'letter' contains what they represent.
    wchar_t      letter;
    unsigned int points;
};

// the bag with undrawed tiles
struct tile_bag
{
    // English version: 100 at start of game
    unsigned int  remaining_tiles;
    tile         *tiles;
};

// the content of a player rack
struct player_rack
{
    unsigned int     tile_count;
    tile            *tiles;
};

// a multiplier square
struct multiplier_cell
{
    enum
    {
        letter_scope,
        word_scope,
    } multiplier_scope;

    unsigned int multiplication_factor;
};

// a cell on the Scrabble® board
struct cell
{
    enum
    {
        normal,     // empty cell with no multiplier
        multiplier, // empty special cell, see multiplier_detail
        tile,       // cell with a tile on it, see tile_detail
    } cell_type;

    union
    {
        multiplier_cell multiplier_detail;
        tile            tile_detail;
    };
};

// a scrabble board;
struct board
{
    unsigned int width;  // usually 15
    unsigned int height; // usually 15
    cell **cells;
};


// a new word, placed on the grid
struct new_word
{
    // zero-terminated string representing the actual word.
    const wchar_t *zWord;

    // the same string, but with spaces for blanks that come
    // from the rack
    const wchar_t *zWord_with_blanks;

    // the rack the word originates from
    player_rack   *original_rack;

    // the cell position where the word begins
    unsigned int   verticalStart;
    unsigned int   horizontalStart;

    // the direction
    enum { vertical, horizontal, } direction;
};

// SCRABBLE® NUMERIC CONSTANTS

// how many tiles are allowed on the rack of a single player
// this is also the number of tiles that grant a bonus when
// placed onto the board at the same time.
// usually 7
extern const int max_allowed_tiles_on_a_rack;

// how many extra points are granted when scrabbling
// usually 50
extern const int scrabble_extra_points;

// GLOBAL VARIABLES

extern board        theBoard;
extern tile_bag     theBag;
extern int          theNumberOfPlayers;
extern player_rack *theRacks;
\$\endgroup\$

closed as off-topic by Geobits, Justin, ProgramFOX, ace_HongKongIndependence, Mhmd Apr 19 '14 at 11:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Geobits, Justin, ProgramFOX, ace_HongKongIndependence, Mhmd
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ The spec needs fixing. At present all the tiles start out as blanks. \$\endgroup\$ – Peter Taylor Feb 19 '11 at 12:00
  • \$\begingroup\$ @Peter Taylor: Those are structures, which are not initialized here. Assume they have been initialized in another part of the code. \$\endgroup\$ – Benoit Feb 19 '11 at 12:10
  • \$\begingroup\$ I was referring to "The value of 'letter' is a space (L' ') until they are positioned on the board." \$\endgroup\$ – Peter Taylor Feb 19 '11 at 12:29
  • \$\begingroup\$ @Peter Taylor: Oh, maybe the comment is not clear, but it is about the blank tiles. Once on the board we need to know what letter they represent if we want to check the words in a dictionary. \$\endgroup\$ – Benoit Feb 19 '11 at 13:04
2
\$\begingroup\$

Haskell:

pointsFromWord :: [[Tile]] -> [Char] -> Word -> Maybe Int
pointsFromWord board rack (word, (x, y), Vertical) = 
  pointsFromWord (transpose board) rack (Word word (y,x) Horizontal)
pointsFromWord board rack w@(word, (x, y), Horizontal) = 
  if (validWord board w)
    then Just (wordScore board w)
    else Nothing

validWord :: [[Tile]] -> [Char] -> Word -> Bool
validWord board rack w@(word, (x, y), _) = x >= 0 && y >= 0 &&
  y < length board && (a + length word) < length (board!!y) &&
  foldl (\acc (c,t)->acc && characterFits t c) True (zip word wordLocation)
    where wordLocation = take (length word) (drop x (board!!y))
          characterFits (PlacedTile letter) c = letter == c
          characterFits _ c = contains rack c

wordScore :: [[Tile]] -> Word -> Int
wordScore board (word, (x, y), _) = (letterScore * multiplier) + scrabbleBonus
  where
    letterScore = foldl (\acc (c,t)->acc + value t c) 0 (zip word wordLocation)
    wordLocation = take (length word) (drop x (board!!y))
    value (LetterMultiplier mult) c = tileValue c * mult
    value (PlacedTile letter value) c = value
    value _ c = tileValue c

    multiplier = foldl (\acc t->acc * wordMultValue t) 1 wordLocation
    wordMultValue (WordMultiplier mult) = mult
    wordMultValue _ = 1

    scrabbleBonus = if length (filter fromRack wordLocation) == 7
                      then 50
                      else 0
    fromRack PlacedTile = False
    fromRack _ = True

A little longer than I'd like (especially the ton of where clauses on wordScore), but seems readable enough (at least to me).

I took a few liberties with the data structures themselves - transliterating the C structures into Haskell doesn't really work.

The board structure is a list of lists of tiles - a list of tiles forms a row, and a list of rows form a board.

Words contain, in order:

  • A [Char] containing the exact tiles used (including blanks where a blank will be used instead of a letter). I assume this is prescreened for the no-two-blanks-next-to-each-other condition, though I suppose I could validate that as well.
  • An (Int, Int) tuple specifying the location of the word
  • An Orientation type constructed with either Vertical or Horizontal, specifying the orientation of the word.

Additionally, the player's current rack of tiles is passed separately from the word being tested, because that makes more sense.

I also assume a tileValue function which takes a character (including space) and returns the standard value of a tile depicting that character.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.