TopcoderArchiveVisit Topcoder
Archive
Algorithm problem

Rings

Problem statement, definition, constraints, and public examples.

Problem Statement

PROBLEM STATEMENT

Given a String[] board, you are to create an N by N matrix of integers where
the first String of board corresponds to the first row of the matrix, the
second String of board corresponds to the second row of the matrix, etc.  The
following matrix shows the position of elements that make up the rings of the
matrix N = 7 and N = 6:

N is 7               N is 6
4444444              333333
4333334              322223
4322234              321123
4321234              321123
4322234              322223
4333334              333333
4444444

The points given to a game are as follows:  
The square matrix is created from the board input.  Each element in this matrix
is a two-digit integer.  If an integer from the matrix is found in moves, the
element is considered "selected".  The matrix contains many rings, as seen from
the two matrices above (matrix N = 7 contains 4 rings, all elements labeled 1
through 4 describe which ring an element is associated with).  If all elements
located on a ring are selected (found in moves), one scores points
corresponding to that ring.  The innermost ring (ring 1) is worth one point if
all elements of ring 1 are selected (in the case where N=7 above, the element
in the center is represented by 1).  The second ring is worth two points if all
elements located at position two (an element from ring 2, found by the 2's in
the above matrixes) are all selected. If all elements of ring 3 are selected,
then three more points are added to this round's score, and so on.  If there is
at least one element in a ring that is not selected, then the ring is worth no
points.  The total score for a round is the sum of all points scored by a
completely selected ring (for the N=7 case, 1, 2, 3 or 4 points, with a maximum
round score of 1+2+3+4 = 10).

00 01 02 03  
04 05 06 07  
08 09 10 11
12 13 14 15

The initial board would therefore look like above:
Ring 1 is worth one point if all elements of the ring, 5, 6, 9, and 10 are
elements of moves.  Ring 2 is worth two points if all elements of the ring, 0,
1, 2, 3, 4, 7, 8, 11, 12, 13, 14, and 15 are elements of moves.  The first
round is created just the original matrix passed in.  Assume the game = {"00 01
02 03","04 05 06 07","08 09 10 11","12 13 14 15"}

12 13 14 15  
00 01 02 03
04 05 06 07
08 09 10 11

After the first round, the board changes by shifting the rows as such in the
above example:
For the second round, the matrix is shifted down by 1 row.  Row 1 shifts down
to row 2, row 2 to row 3, and so on. The last row will wrap around and become
the first row.  Ring 1 is worth one point if all elements of the ring, 1, 2, 5,
and 6 are elements of moves.  Ring 2 is worth two points if all elements of the
ring, 12, 13, 14, 15, 0, 3, 4, 7, 8, 9, 10 and 11, are elements of moves.

15 12 13 14
03 00 01 02
07 04 05 06
11 08 09 10

After the second round, the board changes by shifting the columns as such in
the above example:
The last matrix will be changed by taking the second round's matrix and
changing the columns, such that the matrix is shifted right by 1 column.
Column 1 shifts right to column 2, column 2 to column 3, and so on.  The last
column will wrap around and become the first column. Ring 1 is worth one point
if all elements of the ring, 2, 3, 6, and 7 are elements of moves.  Ring 2 is
worth two points if all elements of the ring, 13, 14, 15, 12, 1, 0, 5, 4, 9,
10, 11 and 8, are elements of moves.
  
Create a class Rings that contains the method score, which takes in a String[]
board and an int[] moves which "selects" the elements of the matrix.  The score
method returns the sum of the points scored in all three rounds of a game.

Class: Rings
Method: score
Parameters: String[], int[]
Returns: int
Method signature (be sure your method is public):  int score(String[] board,
int[] moves);


TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- board contains between 2 and 10 elements, inclusive.
- elements of board will be formatted as follows: "DD DD ..." where D is a
digit 0 - 9, and each two digit number is separated by one space, with no
leading or trailing spaces.
- each String in board will contain N two digit numbers formatted "DD DD ..."
where D is a digit 0 - 9, and each two digit number is separated by one space,
with no leading or trailing spaces
- game should represent an N by N matrix, therefore, elements of game will
contain N two digit numbers where N is equal to the number of elements in game.
For example, if games contains 5 elements, each element of game will contain 5
two digit numbers.
- moves contains between 0 and 50 elements, inclusive.
- elements of moves will be an integer between 0 and 99, inclusive.

NOTES: 
- The representation of the integer 0 is given by "00", 1 is given my "01", and
so forth.
- The ring in the center will be one element if N is odd, and 4 elements if N
is even.
- Numbers are not unique, there can be multiple instances of them in a matrix.
- The score method returns the sum from all three rounds of a game.
	
EXAMPLES
1) board = {"00 01","02 03"}, moves = {0,1,2,3}  Method returns 3.
The first round has only one ring which, with all elements on it selected.  The
second round and third round have the same.
2) board = {"00 01 02","03 04 05","06 07 08"}, moves = {1}  Method returns 1.
The first round does not contain a selected ring.  For the second round, the
middle element of the 3x3 matrix is 1, which is selected, and therefore has the
first ring, worth 1 point.  The last round does not contain a selected ring.
3) board = {"00 01 02 03","04 05 06 07","08 09 10 11","12 13 14 15"}, moves =
{1,2,5,6}  Method returns 1.
After the rows shift, the second round has the inner 1 point ring.
4) board = {"00 01 02 03","04 05 06 07","08 09 10 11","12 13 14 15"}, moves =
{0,1,2,3,4,7,8,11,12,13,14,15}  Method returns 2.
The first round has ring 2 completely selected and is worth 2 points.
5) board = {"01 01 01 01","01 02 02 01","01 02 02 01","01 01 01 00"}, moves =
{0,1}  Method returns 2.
The first round has ring 2 completely selected and is worth 2 points.
6) board = {"00 01 02 03 16","04 05 06 07 17","08 09 10 11 18","12 13 14 15
19","20 21 22 23 24"}, moves = {0,1,2,3,16,4,17,8,18,12,19,20,21,22,23,24,5}
Method returns 4.
The first round has ring 3 completely selected and is worth 3 points.  The
second round has no rings, and the third round has the inner ring worth one
point because the element 5 is the only element of the ring and is selected.

Definition

Class:
Rings
Method:
score
Parameters:
String[], int[]
Returns:
int
Method signature:
int score(String[] param0, int[] param1)
(be sure your method is public)

Constraints

    Examples

      No public sample cases were explicitly marked for this problem in the original data.

      Back to all problems