Problem Statement
You recently designed the Cube Stacking Game. This is a single-player puzzle. All you need to play the game is a collection of cubes, as described below.
You have n cubes. The cubes are numbered from 0 to n-1. Each face of each cube has a single color. There are n+1 colors. One of the colors is white and has number 0. The remaining colors have numbers 1 to n.
Each cube has exactly two white faces, and these are always two opposite faces. Let's number the remaining faces on each cube 1, 2, 3, 4 in adjacent order. (That is, face 1 is adjacent to 2, 2 to 3, 3 to 4, and 4 to 1.) For each cube, you are given the colors of these four faces: on cube i these faces have colors c1[i], c2[i], c3[i] and c4[i], in order. Remember that these faces are never white.
You want to build a single stack of cubes with cube 0 on the bottom, cube 1 on top of cube 0, and so on. (I.e., you have to use the cubes in the given order, starting with 0, and you are not allowed to skip any cube.)
The cubes have to be aligned to form a single stack with four vertical sides. You may rotate the cubes arbitrarily but you must place them onto the stack in such a way that the top and bottom face of each cube will be white. On each of the four sides of the stack each color can only appear at most once. Calculate and return the maximum height of a valid stack that can be built out of the given cubes.
Definition
- Class:
- CubeStackingGame
- Method:
- MaximumValue
- Parameters:
- int, int[], int[], int[], int[]
- Returns:
- int
- Method signature:
- int MaximumValue(int n, int[] c1, int[] c2, int[] c3, int[] c4)
- (be sure your method is public)
Constraints
- n will be between 2 and 8, inclusive.
- Each of c1, c2, c3, c4 will contain exactly n elements.
- Each element of c1 will be between 1 and n, inclusive.
- Each element of c2 will be between 1 and n, inclusive.
- Each element of c3 will be between 1 and n, inclusive.
- Each element of c4 will be between 1 and n, inclusive.
Examples
2
{1,1}
{2,1}
{1,2}
{2,2}
Returns: 1
You can place cube 0 arbitrarily but won't be able to place cube 1 on top of it. Regarless of how you rotate cube 1, there will always be a side of the stack where both cubes have color 1. Thus, the tallest valid stack consists of just a single cube.
2
{1,2}
{1,2}
{1,2}
{1,2}
Returns: 2
Here you can place cube 1 onto cube 0 in any way you like, the result will always look the same: a stack of height 2 where on each side you can see a square of color 1 and a square of color 2.
2
{1,1}
{1,2}
{1,2}
{1,2}
Returns: 1
2
{1,1}
{2,2}
{1,1}
{2,2}
Returns: 2
2
{1,1}
{1,2}
{2,2}
{2,1}
Returns: 2
Theoretically one could use cubes 0, 2, and 3 to form a stack of height 3. However, such a stack is not valid because we are not allowed to skip cubes. And as there is no valid way of placing cube 1 onto cube 0, the tallest valid stack only has height 1.
4
{1,1,3,4}
{1,2,3,4}
{1,3,3,4}
{1,4,3,4}
Returns: 1
We can stack up three cubes (cube 1, 3, and 4) with no duplicate colors on the sides, but we cannot skip cube 2.
4
{1,1,1,1}
{2,2,2,4}
{3,3,3,3}
{4,4,4,2}
Returns: 4
Here we can build a valid stack that will contain all four cubes. Note that in order to do so we need to flip cube 3 "upside down".
3
{1,1,3}
{2,2,3}
{1,1,1}
{1,3,2}
Returns: 1
3
{1,3,1}
{3,3,3}
{3,3,3}
{2,3,1}
Returns: 1
3
{1,1,3}
{1,2,3}
{3,3,1}
{3,1,1}
Returns: 2
3
{1,2,2}
{2,2,2}
{2,3,1}
{3,2,3}
Returns: 1
3
{2,3,3}
{2,3,1}
{2,2,1}
{3,1,3}
Returns: 2
3
{2,3,1}
{2,2,3}
{2,2,1}
{2,2,2}
Returns: 1
3
{1,1,3}
{2,1,2}
{1,1,3}
{1,3,3}
Returns: 1
3
{2,2,1}
{1,2,1}
{1,2,1}
{2,3,1}
Returns: 1
3
{2,1,3}
{3,1,1}
{2,3,2}
{3,3,3}
Returns: 1
3
{2,2,2}
{2,1,1}
{3,1,3}
{3,1,2}
Returns: 2
4
{2,1,3,4}
{4,4,2,3}
{3,1,1,1}
{4,3,1,2}
Returns: 2
4
{3,2,3,3}
{4,1,4,2}
{4,3,2,3}
{3,4,3,2}
Returns: 2
4
{4,1,4,2}
{3,1,2,2}
{1,3,4,3}
{3,2,2,2}
Returns: 3
4
{3,1,1,3}
{4,1,1,1}
{2,1,1,4}
{3,1,4,4}
Returns: 2
4
{2,1,1,1}
{4,2,1,2}
{1,2,4,2}
{4,3,1,3}
Returns: 2
4
{2,2,3,3}
{4,4,4,1}
{2,3,2,1}
{4,2,4,1}
Returns: 1
4
{1,2,4,3}
{3,1,3,1}
{2,3,2,1}
{4,4,1,3}
Returns: 2
4
{2,2,1,3}
{3,2,4,2}
{3,1,1,3}
{4,3,2,2}
Returns: 3
4
{2,4,1,4}
{2,4,2,4}
{2,3,1,1}
{3,1,2,4}
Returns: 2
4
{4,3,2,4}
{3,3,3,4}
{2,3,3,3}
{3,1,2,3}
Returns: 1
5
{5,2,3,4,5}
{4,2,3,4,2}
{2,1,1,5,2}
{1,1,4,2,1}
Returns: 3
5
{4,1,1,4,1}
{1,2,2,4,1}
{2,1,2,2,4}
{1,5,2,2,2}
Returns: 2
5
{4,4,2,4,2}
{4,3,1,5,1}
{3,3,5,4,3}
{1,5,4,3,4}
Returns: 3
5
{5,3,3,4,5}
{3,5,2,4,3}
{2,1,3,3,4}
{2,4,2,1,4}
Returns: 2
5
{1,2,1,4,4}
{5,3,5,1,4}
{5,1,5,4,2}
{1,2,3,5,2}
Returns: 3
5
{1,4,2,3,2}
{3,5,2,4,4}
{1,5,5,4,3}
{2,3,5,3,5}
Returns: 4
5
{3,1,2,3,3}
{3,4,2,5,3}
{5,1,4,3,4}
{1,1,1,1,5}
Returns: 2
5
{5,2,4,1,1}
{5,3,1,2,5}
{3,2,4,1,5}
{3,4,1,1,3}
Returns: 3
5
{5,2,2,4,3}
{5,5,2,3,3}
{2,4,3,2,1}
{3,2,5,1,5}
Returns: 2
5
{3,2,2,3,5}
{2,2,1,2,2}
{3,2,2,1,1}
{3,2,3,2,3}
Returns: 1
6
{3,6,4,4,5,5}
{2,1,1,2,6,6}
{2,6,2,1,4,2}
{1,2,6,2,4,3}
Returns: 3
6
{5,3,5,6,6,4}
{4,2,1,2,3,3}
{5,6,2,6,2,6}
{4,5,3,4,4,6}
Returns: 4
6
{2,6,1,4,1,6}
{3,3,4,6,2,5}
{2,2,4,4,3,2}
{3,5,3,6,5,1}
Returns: 3
6
{1,6,6,4,1,4}
{1,5,4,3,6,4}
{3,6,3,6,3,3}
{4,6,2,4,1,6}
Returns: 3
6
{1,4,6,3,2,6}
{1,3,2,6,3,3}
{5,6,4,3,3,4}
{3,6,3,5,6,2}
Returns: 3
6
{6,6,3,2,1,3}
{6,4,2,4,5,4}
{2,5,6,2,5,1}
{4,1,3,4,4,1}
Returns: 4
6
{5,5,4,5,1,5}
{2,2,5,5,4,6}
{4,3,6,1,5,3}
{6,2,2,2,1,2}
Returns: 3
6
{4,1,3,6,6,3}
{1,6,6,6,3,4}
{3,4,5,3,5,2}
{6,3,6,3,5,5}
Returns: 3
6
{5,1,4,6,5,3}
{6,6,2,5,5,3}
{4,1,2,6,3,3}
{1,3,5,2,1,6}
Returns: 4
6
{6,3,4,3,5,2}
{1,3,3,5,6,3}
{5,2,3,5,3,3}
{2,5,1,1,3,1}
Returns: 3
7
{6,4,2,4,2,4,3}
{3,5,6,2,2,5,1}
{3,1,1,6,5,4,2}
{3,6,7,3,1,6,4}
Returns: 5
7
{5,2,6,2,5,1,3}
{2,6,7,1,4,6,3}
{7,1,1,2,4,6,4}
{4,2,6,1,3,2,1}
Returns: 3
7
{4,2,3,7,3,5,6}
{1,6,5,4,5,2,4}
{1,4,5,6,1,5,4}
{2,1,5,7,3,7,3}
Returns: 5
7
{6,3,2,1,2,5,1}
{4,4,6,1,2,4,5}
{7,1,7,5,4,5,7}
{6,1,2,6,6,1,1}
Returns: 4
7
{5,3,7,4,2,4,2}
{7,2,1,7,3,7,4}
{6,4,5,2,6,1,7}
{6,2,5,7,3,2,1}
Returns: 5
7
{1,7,6,5,6,2,4}
{1,6,4,1,2,1,1}
{7,6,2,3,5,1,5}
{2,6,2,4,3,3,4}
Returns: 4
7
{5,1,4,7,3,7,3}
{5,5,6,4,5,5,5}
{5,3,6,5,7,7,1}
{1,1,1,4,4,5,5}
Returns: 3
7
{4,3,1,5,5,1,2}
{7,2,4,6,2,3,1}
{7,5,2,2,5,4,3}
{3,6,4,5,3,2,3}
Returns: 4
7
{6,2,4,5,3,1,5}
{2,3,2,1,4,2,3}
{7,1,3,1,2,6,1}
{6,3,1,7,4,4,7}
Returns: 5
7
{3,6,6,5,3,3,5}
{2,1,1,6,6,6,2}
{1,1,4,5,5,1,1}
{5,1,1,6,7,7,7}
Returns: 2
8
{3,6,3,1,3,4,6,3}
{5,3,7,7,7,6,3,5}
{6,3,8,8,2,2,1,3}
{3,7,2,6,6,8,5,8}
Returns: 2
8
{5,2,6,4,5,5,8,8}
{8,3,2,8,7,8,1,4}
{3,2,8,7,1,7,2,6}
{6,7,8,6,2,1,2,3}
Returns: 5
8
{7,6,3,2,8,3,3,7}
{3,6,7,6,2,8,2,8}
{6,2,1,8,2,3,1,7}
{1,4,6,8,4,8,1,6}
Returns: 3
8
{4,4,2,8,3,8,3,5}
{1,1,7,4,5,1,6,4}
{4,2,1,6,8,7,8,3}
{5,4,3,3,7,8,4,5}
Returns: 1
8
{5,6,5,1,6,2,3,1}
{1,2,4,6,7,3,7,2}
{8,3,6,4,6,7,8,4}
{3,6,8,2,4,7,7,1}
Returns: 4
8
{2,2,4,6,3,6,7,8}
{4,6,1,2,5,6,1,8}
{4,1,3,6,4,5,5,5}
{8,1,7,2,1,3,4,5}
Returns: 5
8
{7,4,1,7,2,1,3,3}
{1,5,1,6,1,8,7,4}
{3,1,7,7,6,8,1,6}
{5,3,3,7,7,5,6,7}
Returns: 3
8
{5,7,8,4,6,2,8,2}
{7,6,5,5,8,6,4,3}
{5,8,6,2,4,2,8,1}
{5,2,4,4,1,2,6,8}
Returns: 3
8
{7,7,6,6,2,1,3,3}
{6,3,8,7,8,3,2,7}
{5,5,2,3,5,3,5,7}
{2,1,3,3,8,2,1,3}
Returns: 5
8
{5,5,8,4,4,5,3,1}
{3,4,7,5,5,2,6,3}
{7,1,5,5,8,6,4,3}
{1,5,1,1,7,1,1,6}
Returns: 3
2
{1, 1 }
{2, 2 }
{1, 1 }
{2, 2 }
Returns: 2
4
{1, 1, 1, 1 }
{2, 2, 2, 4 }
{3, 3, 3, 3 }
{4, 4, 4, 2 }
Returns: 4
4
{1, 1, 1, 1 }
{4, 2, 2, 2 }
{3, 3, 3, 3 }
{2, 4, 4, 4 }
Returns: 4
6
{1, 3, 2, 1, 1, 1 }
{2, 4, 4, 1, 1, 1 }
{1, 3, 2, 1, 1, 1 }
{2, 4, 4, 1, 1, 1 }
Returns: 3