C++

Forum

 
I can't see the missing thing in the algorithm

istemihan (45)
In code below, each unit works fine, tested well(checkArrs, flipX and flipY). To summarize, question is like this:

You have red, blue and green unit cubes. You will create a 2x2x2 cube by using 8 of these unit cubes. What is the maximum number of different cubes you can create?

Note: If a cube can be obtained by rotating another one, these two cubes are not considered to be different.

If the problem was asked for only red and blue unit cubes, the answer would be 23.


So I represent a cube with std::array each subCube is an element of tempArr<int , 8> as like: 1 for red, 2 for blue and 3 for green. I form cubes, flip them and check them if they are same, and if not same, I add them into a vector: possVec.

So these are assumptions:

1- If you flip a cube in same rotation(x or y) four times, you get the same cube.

2- If you rotate a cube for 4 times in X and 4 times in Y direction and do not see the same, thos cubes are not same.

But! When I code this algorith exactly as it is, I get failure! The very interesting thing is this:

If I set for loop as (int loopY = 0; loopY < 6; loopY++) I get the result as 60,
for (int loopY = 0; loopY < 4; loopY++) I get 31. How crazy is that?!

Can you see where do I do wrong? Thanks.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
 
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <array>

std::vector<std::array< int, 8 > > possVec;
std::vector<std::array< int, 8 > > usedPossVec;
std::array<int, 8> tempArr;
std::array<int, 8> test;
int counter=0;
int check, checkSum;

int checkArrs(std::array<int, 8>& arr1, std::array<int, 8>& arr2)
{
	//
	//int check = 0;
	for (int i = 0; i < 8; i++)
	{
		//
		if (arr1[i] != arr2[i])
		{
			// return 0 if not equal
			return 0;
		}
	}
	return 1;
}

void flipX(std::array<int, 8>& arrX)
{
	//
	int * tempArrX = new int[8];
	for (int i = 0; i < 8; i++)
	{
		//
		tempArrX[i] = arrX[i];
	}

	arrX[0] = tempArrX[4];
	arrX[1] = tempArrX[6];
	arrX[2] = tempArrX[0];
	arrX[3] = tempArrX[1];
	arrX[5] = tempArrX[2];
	arrX[7] = tempArrX[3];
	arrX[4] = tempArrX[5];
	arrX[6] = tempArrX[7];

	delete[] tempArrX;
}

void flipY(std::array<int, 8>& arrY)
{
	//
	int * tempArrY = new int[8];
	for (int i = 0; i < 8; i++)
	{
		//
		tempArrY[i] = arrY[i];
	}

	arrY[0] = tempArrY[1];
	arrY[4] = tempArrY[6];
	arrY[1] = tempArrY[3];
	arrY[6] = tempArrY[7];
	arrY[3] = tempArrY[2];
	arrY[7] = tempArrY[5];
	arrY[2] = tempArrY[0];
	arrY[5] = tempArrY[4];

	delete[] tempArrY;
}

void tempFillPoss(int x, int y)
{
	//
	if ( x < y)
	{
		//
		for (int i = 1; i <= 2; i++)
		{
			//
			tempArr[x] = i;
			tempFillPoss(x + 1, y);
		}
	}
	else
	{
		//
		if (possVec.empty())
		{
			//
			possVec.push_back(tempArr);
		}
		else
		{
			//
			check = 0;
			for (int j = 0; j < possVec.size(); j++)
			{
				//
				checkSum = 0;
				for (int loopX = 0; loopX < 4; loopX++)
				{
					//
					flipX(tempArr);
					for (int loopY = 0; loopY < 6; loopY++)
					{
						//
						flipY(tempArr);
						if (checkArrs(tempArr, possVec[j]) == 1)
						{
							//
							checkSum += 1;
						}
					}
				}
				if (checkSum != 0)
				{
					//
					check += 1;
				}
			}
			if (check == 0)
			{
				//
				possVec.push_back(tempArr);
				for (int k = 0; k < tempArr.size(); k++)
				{
					//
					std::cout << tempArr[k];
				}
				std::cout << std::endl;
			}
		}
	}
}

void fillPoss()
{
	//
	tempFillPoss(0, 8);
}


int main()
{
	fillPoss();
	//doWork();
	std::cout << "the count is: " << possVec.size() << std::endl;
	system("pause");
    return 0;
}
Last edited on
doug4 (1538)
I think you also need to check for rotations around the z axis. The z transform would be 4 = 6 = 1 = 0 and 5 = 7 = 3 = 2.

By the way, your indexing is really weird. You really need to come up with a consistent ordering of your cubes. The relative positions of 4 - 7 should align with the relative positions of 0 - 3. That will make it easier to figure out where things move to on a flip. However, if you consider 0 - 3 as a 2 x 2 array, it looks like this:

0 1
2 3

But your 4 - 7 looks like this:

4 6
5 7

You will save yourself some headaches if you put 4 - 7 in the same relative order as 0 - 3. Then you will find a pattern in your 2 sets of transfomations. Your flips will then be:

X: 0 -> 4 -> 6 -> 2 and 1 -> 5 -> 7 -> 3 (second is 1 more than first)
Y: 0 -> 1 -> 3 -> 2 and 4 -> 5 -> 7 -> 6 (second is 4 more than first)
Z: 0 -> 1 -> 5 -> 4 and 2 -> 3 -> 7 -> 6 (second is 2 more that first)
istemihan (45)
Thank you very Much!!! How did I miss that! I get the correct answer :)
Topic archived. No new replies allowed.