|
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.
|