Problem
You have four colored cubes. Each side of each cube is a single color, and there are four colors:
blue (B), red (R), green (G) and yellow (Y)
Describing the six faces as front, back, left, right, top, bottom, the cube colors are:
Cube Front Back Left Right Top Bottom
1 R B G Y B Y
2 R G G Y B B
3 Y B R G Y R
4 Y G B R R R
The objective is to find ways to stack the four cubes as a vertical column so that
each side of the column is showing all four colors.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find ways to stack four cubes
Created Date : 30-July-2013
Last Modified : 26-August-2013
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;
enum COLOR{
B = 0x01,
R = 0x02,
G = 0x04,
Y = 0x08,
};
typedef array<int, 6> CUBE;
enum LABELS{
One = 0,
Two,
Three,
Four,
Five,
Six
};
/*
Cube Front Back Left Right Top Bottom
1 R B G Y B Y
2 R G G Y B B
3 Y B R G Y R
4 Y G B R R R
*/
/**
* Dye cube with colors from front right back left top and bottom
* @param cube cube to dye
* @param colors color of front right back left top and bottom
* @param number of planes
*/
void DyeCube(CUBE& cube, const int* colors, const int len = 6)
{
for(int i = 0; i < 6; ++i){
cube[i] = colors[i];
}
}
/**
* Check whether two cubes are same when rotating on z axis
* @param cube1 first cube to test
* @param cube2 second cube to test
* @return true if same
*/
bool IsSameRotateZAxis(const CUBE& cube1, const CUBE& cube2)
{
bool same;
for(int j = 0; j < 3; j++){
same = (cube1[4] == cube2[4]) && (cube1[5] == cube2[5]);
for(int i = 0; i < 4; ++i){
same = (same && (cube1[i] == cube2[(i + j) % 4]));
}
if(same) return true;
}
return false;
}
/**
* Check whether cubes contains a specified cube
* @param cubes candidate cubes
* @param cube new cube to add
* @return true if contains
*/
bool Contains(const vector<CUBE>& cubes, const CUBE& cube)
{
for(int i = 0; i < cubes.size(); ++i){
if(IsSameRotateZAxis(cubes[i], cube)){
return true;
}
}
return false;
}
/**
* Check two cubes conflicted
* @param cube1 first cube to test
* @param cube2 second cube to test
* @return true if conflict
*/
bool IsConflicted2(const CUBE& cube1, const CUBE& cube2)
{
for(int i = 0; i < 4; ++i){
if(cube1[i] == cube2[i]){
return true;
}
}
return false;
}
/**
* Create top candidate cubes
* @param candidates permutations of cube of different positions
* @param arr colors of cube from one viewpoint
* @param len number of plane
*/
void CreateCandidatesTop(vector<CUBE>& candidates, const int* arr, const int len = 6)
{
// Front Right Back Left Top Bottom
int combs[6][6] =
{
{One, Two, Three, Four, Five, Six},
{One, Four, Three, Two, Six, Five},
{Five, Four, Six, Two, One, Three},
{Five, Two, Six, Four, Three, One},
{One, Five, Three, Six, Four, Two},
{One, Six, Three, Five, Two, Four}
};
for(int i = 0; i < 6; ++i){
CUBE cube;
int colors[6];
for(int j = 0; j < 6; ++j){
colors[j] = arr[combs[i][j]];
}
DyeCube(cube, colors, 6);
if(!Contains(candidates, cube)){
candidates.push_back(cube);
}
}
}
/**
* Create candidates for the second, third and fourth cubes
* @param candidates permutations of cube of different positions
* @param arr colors of cube from one viewpoint
* @param len number of plane
*/
void CreateCandidates(vector<CUBE>& candidates, const int* arr, const int len = 6)
{
// Front Right Back Four Top Bottom
int combs[24][6] =
{
{One, Two, Three, Four, Five, Six},
{Two, Three, Four, One, Five, Six},
{Three, Four, One, Two, Five, Six},
{Four, One, Two, Three, Five, Six},
{One, Four, Three, Two, Six, Five},
{Four, Three, Two, One, Six, Five},
{Three, Two, One, Four, Six, Five},
{Two, One, Four, Three, Six, Five},
{Five, Four, Six, Two, One, Three},
{Four, Six, Two, Five, One, Three},
{Six, Two, Five, Four, One, Three},
{Two, Five, Four, Six, One, Three},
{Five, Two, Six, Four, Three, One},
{Two, Six, Four, Five, Three, One},
{Six, Four, Five, Two, Three, One},
{Four,Five, Two, Six, Three, One},
{One, Five, Three, Six, Four, Two},
{Five, Three, Six, One, Four, Two},
{Three, Six, One, Five, Four, Two},
{Six,One, Five, Three, Four, Two},
{One, Six, Three, Five, Two, Four},
{Six, Three, Five, One, Two, Four},
{Three, Five, One, Six, Two, Four},
{Five, One, Six, Three, Two, Four}
};
for(int i = 0; i < 24; ++i){
CUBE cube;
int colors[6];
for(int j = 0; j < 6; ++j){
colors[j] = arr[combs[i][j]];
}
DyeCube(cube, colors, 6);
candidates.push_back(cube);
}
}
int main(int argc, char* argv[])
{
// Front Right Back Left Top Bottom
int cubes[4][6] =
{
{R, Y, B, G, B, Y},
{R, Y, G, G, B, B},
{Y, G, B, R, Y, R},
{Y, R, G, B, R, R}
};
int count(0);
// Label four cube with 0, 1, 2, 3, so the permutation of four cubes are 24
int indices[] = {0, 1, 2, 3};
do{
vector<CUBE> candidatesTop;
CreateCandidatesTop(candidatesTop, cubes[indices[0]], 6);
for(int i = 0; i < candidatesTop.size(); ++i){
vector<CUBE> candidatesSecond;
CreateCandidates(candidatesSecond, cubes[indices[1]], 6);
for(int j = 0; j < candidatesSecond.size(); ++j){
// If current color of 1st and 2nd cube do not meet requirement, skip this iteration
if(IsConflicted2(candidatesTop[i], candidatesSecond[j])) continue;
vector<CUBE> candidatesThird;
CreateCandidates(candidatesThird, cubes[indices[2]], 6);
for(int k = 0; k < candidatesThird.size(); ++k){
// If current color of 1st, 2nd and 3rd cube do not meet requirement, skip this iteration
if(IsConflicted2(candidatesTop[i], candidatesThird[k])) continue;
if(IsConflicted2(candidatesSecond[j], candidatesThird[k])) continue;
vector<CUBE> candidatesFourth;
CreateCandidates(candidatesFourth, cubes[indices[3]], 6);
for(int m = 0; m < candidatesFourth.size(); ++m){
if(IsConflicted2(candidatesTop[i], candidatesFourth[m])) continue;
if(IsConflicted2(candidatesSecond[j], candidatesFourth[m])) continue;
if(IsConflicted2(candidatesThird[k], candidatesFourth[m])) continue;
// increase by one if no conflict
count ++;
}
}
}
}
}while(next_permutation(indices, indices + 4));
cout << "The total ways to stack four cubes is " << count << endl;
return 0;
}
Output
The total ways to stack four cubes is 48
Press any key to continue . . .