TopCoder problem "TupleLine" used in TCCC '03 NE/SE Regional (Division I Level Three)

Problem Statement

     An "n-dimensional grid of size k" contains k^n cells. Each cell can be represented as an n-tuple of values from the set {0,1,...,k-1}. For example a 2-dimensional grid of size 3 is just a 3 x 3 square, with cells (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) and (2,2). A 3-dimensional grid of size 5 is a cube containing 125 cells. Cell (0,2,2) is the cell in row 0, column 2, layer 2.

Higher dimensions get a little harder to describe geometrically, but not algebraically! Every cell in an n-dimensional grid can be uniquely represented by an n-tuple specifying the "row" "column" "layer" "plane" "hyper-row" etc. (English fails us at about the same point as geometry fails us). We can define a straight line in an n-dimensional grid algebraically. It is a set of distinct cells that can be placed in a sequence such that the difference between each pair of adjacent cells is the same throughout the sequence. Of course, the difference between two n-tuples is an n-tuple. A maximal line in an n-dimensional grid of size k is a line containing k cells.

In a 3-dimensional grid of size 4, one example of a maximal straight line is (3,0,1),(2,1,1),(1,2,1),(0,3,1) which is a straight line of length 4. The difference between each pair of adjacent cells in the sequence is (-1,1,0).

You want to create a maximal line in your n-dimensional grid by adding to a collection of cells that have already been chosen. Create a class TupleLine that contains the method quickLine that takes an int size and a String[] chosen as inputs and returns the smallest number of additional cells that you could choose to form a maximal line in the grid.

Each String in chosen is a sequence of digits indicating a particular cell. For example, "410" would indicate the cell at row 4, column 1, layer 0 in a 3-dimensional grid whose size is at least 5 (since it has a row 4). The dimension of the grid is always the same as the length of each String in chosen.



Parameters:int, String[]
Method signature:int quickLine(int size, String[] chosen)
(be sure your method is public)


-size is between 3 and 9 inclusive
-chosen contains between 1 and 50 elements inclusive
-each character in each element of chosen is a digit whose value is less than size
-each element in chosen contains the same number of characters, n. n is the dimension of the grid and is between 2 and 9 inclusive


Returns: 2
    X - X -         X X X X
    - - - -         - - - -
    - X - -         - X - -
    - - - -         - - - -
The left-hand picture shows the original situation. The right-hand picture shows the only way of completing a maximal line by adding two X's.
Returns: 3
    X - - -
    - - - -
    - X - -
    - - X -
There are lots of ways to form a maximal line with 3 more cells. Note that the cell "32" appears twice in chosen but, of course, this does not help us to form a maximal line.
Returns: 0
These first three cells already form a maximal line in this 4-dimensional grid.
Returns: 7

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Math, Search