Scruffle is a single player word game, played on a rectangular board. The goal of the game is to score as many point as possible by placing words on the board. The board contains obstacles in some of the cells; no word may be placed to overlap with one of these obstacles. The player is given a list of available words; each word may be placed on the board only once. A word may be placed horizontally or vertically and must read from left to right or top to bottom. A word may be placed such that it overlaps with an already placed word, in which case the overlapping letters of the words must be the same. A word may not go off the edge of the board. When placing a word, at least one of its letters must not overlap with any previously placed word.
Each letter is worth a specific amount of points.
- The letters A, E, I, L, N, O, R, S, T and U is worth 1 point.
- The letters D and G are worth 2 points.
- The letters B, C, M and P are worth 3 points.
- The letters F, H, V, W and Y are worth 4 points.
- The letter K is worth 5 points.
- The letters J and X are worth 8 points.
- The letters Q and Z are worth 10 points.
Each cell of the board can contain one of the following:
- # : The cell contains an obstacle, no word may overlap with this cell.
- 0-9 : Letter multiplier. The score of the letter that is placed on this cell will be multiplied by the given number. Ex. If the cell contains a 5 and the player places a letter B on the cell, the score for that placement will be 5 * 3 = 15.
- D : Double word multiplier. The score of the word placed over this cell will be multiplied by 2. The score of the letter placed on this cell will be just the letter points (Letter multiplier of 1.). If a word overlaps with more than one word multiplier, the word score will be cumulative. Ex. If the score of a word before applying the word multiplier is 12 and the word overlaps with 2 D?s, then the total score for the placement will be 12 * 2 * 2 = 48.
- T : Triple word multiplier. The score of the word placed over this cell will be multiplied by 3. This multiplier works cumulatively with the double word multiplier.
The score for each word placement will be calculated independently from previously placed words. All letter and word multipliers that form part of the placement will be used in the calculation. Pseudo code for calculating the score of a word placement:
letterScore = 0
wordMultiplier = 1
for each letter in the word
cell = cell where this letter will be placed
if cell contains a D
letterScore = letterScore + worth of letter
wordMultiplier = wordMultiplier * 2
else if cell contains a T
letterScore = letterScore + worth of letter
wordMultiplier = wordMultiplier * 3
letterScore = letterScore + worth of letter * letter multiplier of cell
score for placement = letterScore * wordMultiplier
You will play the game by writing a single method play. The play method will take a String that contains the definition of the board and a String that contains a list of all the available words. The method will be called only once. You must return a String that contains all your word placements. Each element contains a single placement. Words will be placed on the board in the same order as in your return. The format of a placement is the direction of the placement followed by the 0-based index of the word that must be placed, followed by the (x, y) 0-based position where the first letter of the word must be placed. The direction character must be a H for horizontal placement or a V for vertical placement. Ex. ?H 10 5 3? indicates the horizontal placement of the word at index 10, and the placement starts at position (5, 3) of the board.
Your score for a test case will be the sum of all the scores for each placement. You will receive a score of 0 when you perform an invalid placement or when the method runs out of time. Your final score will be found by taking the sum over test cases of (your score)/(highest score).
Test case generation
All random values are computed uniformly and ranges are stated inclusively. The horizontal dimension X of the board will be chosen between 10 and 100. The vertical dimension Y of the board will be chosen between 10 and 100.
A fraction 0 <= B <= 0.2 of the cells are blocked with obstacles, a fraction 0 <= D <= 0.05 of the cells are doubles ('D'), and a fraction 0 <= T <= 0.02 of the cells are triples ('T'). All these cells are selected randomly, with a new random selection being made if a selected cell was already previously marked. The remaining cells are filled with numbers '0'-'9'.
The number of words W will be chosen between 10 and 10000. Words will then be randomly selected from the English dictionary. The same word may appear more than once in the list given to your method. See the notes section for a link to the words of our dictionary.