"Rack 'em up!" says Jane. She's beaten you at pool again, so you're stuck with the chore of racking the balls for the next game. There are fifteen balls at your disposal, numbered 1 through 15. Those numbered 1 through 7 are called "solids", while 9 through 15 are "stripes". Number 8, the "eight-ball", is neither stripe nor solid.
You are to arrange the balls into five rows such that the first row contains one ball; the second, two balls; and so on. The overall effect is that of an equilateral triangle pointing upward. For the purpose of this problem, we number the positions in the triangle from 0 to 14, starting in the first row and proceeding from left to right, top to bottom. The following piece of ASCII art shows the position numbers.
0
1 2
3 4 5
6 7 8 9
10 11 12 13 14
In a correct rack, the eight-ball occupies position 4, while positions 10 and 14 may not be occupied by two stripes or two solids. Furthermore, you are at a pool hall whose rules dictate that stripes and solids alternate along the upper left side of the triangle (positions 10, 6, 3, 1, 0); along the fourth row (positions 6, 7, 8, 9); and along the first four positions in the bottom row (positions 10, 11, 12, 13). Finally, positions 5 and 9 must be occupied by two stripes or two solids. In effect, only two patterns of stripes and solids are possible. These patterns are shown below, using X to represent stripes, O for solids, and the numeral 8 for the eight-ball.
X O
O O X X
X 8 X O 8 O
O X O X X O X O
X O X O O O X O X X
The balls are, at first, arranged randomly in the triangle. Etiquette demands that you change the configuration only by swapping the positions of two balls at a time. Any two balls, not merely an adjacent pair, may be swapped. Given a int[] describing the initial configuration of the triangle, so that the element at index 0 is the number of the ball at position 0 and so forth, what is the smallest number of swaps required to achieve a correct rack?
|