TopCoder problem "Cubism" used in SRM 172 (Division II Level Three)



Problem Statement

    

64 cubes are packed into a four-by-four-by-four lattice. (No, not the kind used to make salad. Forget lettuce! Think of a three-dimensional grid.) Each cube is either black or white.

The lattice configuration is described by a String[] containing four elements of 16 characters each. Imagine the lattice resting on a table with one face oriented north. If we cut the lattice into four slices parallel to the tabletop, then the first String describes the topmost slice, the second describes the second slice from the top, and so on. Each String lists the contents of a slice row by row from north to south, and from west to east within each row. Every character has one of two values: "B" stands for a black cube, "W" for a white one.

We say that a line consists of four cubes, all the same color, arranged sequentially in any orthogonal or diagonal direction. A line may be such that consecutive cubes touch each other with their faces, or such that they touch with their edges, or such that they touch with their corners. All four cubes must be aligned in the same direction. Two lines are distinct if they are not formed of the same four cubes.

Given a lattice configuration and a color, count the number of distinct lines formed by cubes of that color.

 

Definition

    
Class:Cubism
Method:lines
Parameters:String[], String
Returns:int
Method signature:int lines(String[] lattice, String color)
(be sure your method is public)
    
 

Constraints

-lattice contains exactly four elements
-each element of lattice is exactly 16 characters long
-each character is either 'B' or 'W'
-color is either "black" or "white"
 

Examples

0)
    
{"BBBBBWWWBWWWBWWW",
 "BWWWWWWWWWWWWWWW",
 "BWWWWWWWWWWWWWWW",
 "BWWWWWWWWWWWWWWW"}
"black"
Returns: 3
Black lines lie along three edges of the lattice and meet at a corner.
1)
    
{"BWWWWWWWWWWWWWWW",
 "WWWWWBWWWWWWWWWW",
 "WWWWWWWWWWBWWWWW",
 "WWWWWWWWWWWWWWWB"}
"black"
Returns: 1
A black line stretches diagonally between two corners, its endpoints as far apart as any two cubes of the lattice can be.
2)
    
{"WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW"}
"black"
Returns: 0
There are no black lines here.
3)
    
{"WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW"}
"white"
Returns: 76
This is the greatest number of lines possible in a lattice.
4)
    
{"WWWWWWWWWBWWWWWW",
 "WWWBWWWWWWWWWWWW",
 "WWWWWWWWWWWWBWWW",
 "WWWBWWWWWWWWWWWW"}
"white"
Returns: 58
5)
    
{"BWBWBWBWBWBWBWBW","BWBWBWBWBWBWBWBW",
 "BWBWBWBWBWBWBWBW","BWBWBWBWBWBWBWBW"}
"white"
Returns: 20

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1815

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4665&pm=1815

Writer:

Eeyore

Testers:

lbackstrom , brett1479

Problem categories:

Brute Force, Search