Saturday, August 8, 2015

CrossWord

Problem:

TopCoder Problem Statement - CrossWord
Single Round Match 174 Round 1 - Division II, Level One

Overview:

Determine how many slots of a given length appear horizontally in a given crossword puzzle.

Java Source:
     1 public class CrossWord {
     2
     3     public int countWords(String[] board, int size) {
     4
     5         int total = 0;
     6
     7         /*
     8         * Sum up the number of horizontal slots in each
     9         * of the rows in the board.
    10         */
    11         for (String s : board) {
    12             total += countHorizontalSlots(s, size);
    13         }
    14
    15         return total;
    16     }
    17
    18     /*
    19     * Count the number of horizontal slots in a
    20     * single row of the board.
    21     */
    22     private static int countHorizontalSlots(String s, int size) {
    23
    24         // Number of horizontal slots found.
    25         int num = 0;
    26
    27         // Number of continuous spaces found.
    28         int spaces = 0;
    29
    30         // Loop through each character in the given string.
    31         for (int i = 0; i < s.length(); i++) {
    32
    33             /*
    34             * An 'X' marks the end of a slot.  So when an
    35             * 'X' is encountered, if the number of spaces
    36             * matches the size we're looking for, then
    37             * increase the count.
    38             * Set spaces to 0 whenever an 'X' is found.
    39             */
    40             if (s.charAt(i) == 'X') {
    41                 if (spaces == size) {
    42                     num++;
    43                 }
    44                 spaces = 0;
    45
    46             } else {
    47
    48                 /*
    49                 * If it's not an 'X', then increment the number
    50                 * of open spaces found.
    51                 */
    52                 spaces++;
    53             }
    54
    55         }
    56
    57         /*
    58         * This condition is met when the slot leads up to the
    59         * right edge of the board.
    60         */
    61         if (spaces == size) {
    62             num++;
    63         }
    64
    65         return num;
    66     }
    67 }
Notes:

The first step is to divide the crossword up into individual rows. For each row, we'll add up the number of slots, and then return the sum.

The count the slots in an single row we'll step through each character of the given string looking for 'X's since the 'X' character terminates a slot. If any character other than an 'X' is encountered, we simply increase the number of spaces seen. When an 'X' appears, we check to see if the number of spaces matches what we're looking for. If so, increment the count for this line.

Be careful to include the case where the slot ends at the end of the string. The last check - "if (spaces == size)" takes care of this.

No comments:

Post a Comment