Problem 4 -- Loyola College Programming Contest

Problem 4: Crossword Puzzle

Loyola College > Department of Computer Science > Dr. James Glenn > HS Programming Contest > Problems > Problem 4: Crossword Puzzle

Introduction

A crossword puzzle is a rectangular grid of empty squares and filled blocks. Each empty square at the leftmost edge of a horizontal run of more than one empty square is given a number, as is each empty square at the top of a vertical run. Only one number is given to an empty square that meets both criteria. The numbers are assigned starting from 1 in the leftmost numbered square in the top row and then proceeding from left to right in the top row with consecutive numbers assigned to the other numbered squares in the top row. The second row is then numbered from left to right starting with the next available number, and so forth.

A crossword puzzle then has clues to what words fit in each horizontal ("across") space and each vertical ("down") space. Although the clues are not given as input to the problem, we will refer to the combination of number and direction of each answer as a clue.

Answers
Across	Down
1 - EVA 4 - TILL 6 - PPO 7 - SO	1 - ET 2 - VIP 3 - ALPS 5 - LOO

Problem

Complete the isValid method in the Crossword class, which determines if the given set of answers is valid. The answers are valid if and only if they give a complete answer for each clue and the across answers and the down answers fit together (an across answer can't put one character in a square if a down answer would put a different character in that square).

Only the locations of the empty squares in the puzzle are given, not the numbers. The Crossword class has the following methods for you to determine the locations of the empty squares:

int getWidth(), to return the number of columns in the puzzle,
int getHeight(), to return the number of rows in the puzzle, and
boolean isEmpty(int row, int col), to determine if the a square in the puzzle is empty or blocked off, where the location of the square in question is given by a row index (0 at the top) and a column index (0 at the left); note that this method only considers the shape of the puzzle and not the answers that are being validated.

For example, if p is the puzzle shown above, then p.getWidth() and p.getHeight() both return 4, p.isEmpty(0, 0) returns true, and p.isEmpty(3, 1) returns false.

The answers to check are given as an instance of the Answers class which is passed to isValid. The Answers class has the following methods:

String getAcrossAnswer(int num), to return the proposed answer for the given across clue; and
String getDownAnswer(int num), to return the proposed answer for the given down clue.

These methods will throw an exception if the argument is invalid (that is, if the corresponding clue does not exist). For example, if a is the answers shown above then a.getAcrossAnswer(5) will throw an exception.

The isValid method should return true if the answers are valid and false otherwise.

Assumptions

You may assume that the puzzle is non-empty and is connected.
You may assume that an answer is given for each empty horizontal and vertical run and that each answer is nonempty.
You may assume that the answers do not include any for nonexistent clues.
You may assume that there are no completely filled rows or columns in the puzzle.
You may assume that the answers are all upper case.