It all started during a "fourInARow" game... A friend of mine asked: "If you drop in all 42 stones, what will the number of "four in a row"s be with the optimal configuration?"
I thought it should be something like this: (0 is player1's coins , 1 is player2's coins)
1111110
1111100
1111000
1110000
1100000
1000000
Which should be 12row+12col+12diagDownLeft=36
.
After that I tried to write a program to bruteforce test all possible combinations... After my calculations the sum of all possible ways should be (42!)/((21!)*(21!))≈5,4*10^11
I first tried the code on an android phone... But after implementing a progress bar I estimated a runtime of 9 years.
The situation on desktop wasn't much better ≈300days
with 1.000.000FieldsTested/sec
.
I'm also interested how the situation evolves for larger fields than 7(width)*6(height)
...
Details on how to count the "sum of four in a rows": If you have 7 clips of equal color in one row then this counts as 4*" fourInARow" (same is true for diagonal or rows)
I took a look on other possibilities to count the "fourInARow"s more efficiently, but most solutions are more optimized to find only one winning condition like this one:
Does anyone have a recommendation how to optimize the performance of the code or is everything lost because I need a performance speedup of at least x300.
Should I try to use parallel processing and opencl? Or is the code too inefficient?
I tried to avoid functions and so on as much as possible and sorry for bad coding style, thats because I come from the "assembler/hardware" area where you don't have to bother about names :).
My code so far:
#include <stdio.h>
int main()
{
char height = 6; //height of the field
char width = 7; //width of the field
short length = height * width; // number of places in the field
short temp1;
short temp2;
short temp3;
short temp4;
short scoreold = 0;
short scorenew = 0;
long int b = 0;
long int a=0;
//check if field has even number of places, if not abort
if ((length % 2) != 0)
{
printf("Error Code 1: Uneven number of fields");
return 1;
}
char field[length];
//generate initial field (111 ... 111000 ... 000)
for (short a = 0; a < (length / 2); a++)
{
field[a] = 1;
}
for (short a = (length / 2); a < length; a++)
{
field[a] = 0;
}
//iterate through every possible combination
while ((b++) < (538257874440)) // (42!)/((21!)*(21!))
{
a++;
temp1 = 0;
//generate the next testing setup for the field
while (field[temp1] == 0)
{
temp1++; //temp1 is number of 0 from the low end
};
if (temp1 == 0) //if there are no zeros from low end move first one one space to the higher end: eg. 000....000111...000 => 000...010111...111
{
while (field[temp1] == 1)
{
temp1++;
}
field[temp1--] = 1;
field[temp1] = 0;
}
else
{
temp2 = temp1;
while (field[temp2] == 1)
{
temp2++;
}
field[temp2] = 1;
temp2 = temp2 - (++temp1);
while ((temp1--) != 0)
{
field[((temp1) + temp2)] = 0;
}
while ((temp2--) != 0)
{
field[temp2] = 1;
}
}
// end field generation
// test for rows (temp1 used as iterator through all fields)
for (temp1 = 0; temp1 < (width * height); temp1++)
{
if (temp1 % width == 0) //beginning of new row reset counters
{
temp2 = 0; //used as counter for player1
temp3 = 0; //used as counter for player2
}
if (field[temp1] == 0) //coin of player 2
{
temp2 = 0;
temp3++;
}
else //coin of player 1
{
temp2++;
temp3 = 0;
}
if((temp2 > 3) | (temp3 > 3)) //four in a row detecred increase score
{
scorenew++;
// test1++;
}
}
// test for colums
for (temp1 = 0; temp1 < (width * height); temp1++)
{
if (temp1 % height == 0) //reset counter for new column
{
temp2 = 0;
temp3 = 0;
}
if (field[((temp1 * width) % (width * height)) + (temp1 / (height))] == 0)
{
temp2 = 0;
temp3++;
}
else
{
temp2++;
temp3 = 0;
}
if ((temp2 > 3)|(temp3 > 3))
{
scorenew++;
// test2++;
}
}
// test down right
for (temp1 = 0; temp1 < ((width + height) - 1); temp1++)
{
temp2 = 0;
temp3 = 0;
if (temp1 < width)
{
temp4 = temp1;
}
else
{
temp4 = (((temp1 - width) + 1) * width);
}
while (temp4 < (width * height))
{
if (field[temp4] == 0)
{
temp2 = 0;
temp3++;
}
else
{
temp2++;
temp3 = 0;
}
if ((temp2 > 3)|(temp3 > 3))
{
scorenew++;
// test3++;
}
if ((temp4 + 1) % width == 0)
{ // right border reached
break;
}
temp4 += (width + 1);
}
}
// test down left
for (temp1 = 0; temp1 < ((width + height) - 1); temp1++)
{
temp2 = 0;
temp3 = 0;
if (temp1 < width)
{
temp4 = temp1;
}
else
{
temp4 = (((temp1 - width) + 1) * width) + (width - 1);
}
while (temp4 < (width * height))
{
if (field[temp4] == 0)
{
temp2 = 0;
temp3++;
}
else
{
temp2++;
temp3 = 0;
}
if ((temp2 > 3)|(temp3 > 3))
{
scorenew++;
// test4++;
}
if (temp4 % width == 0)
{ // left border reached
break;
}
temp4 += (width - 1);
}
}
if (scorenew > scoreold)
{
scoreold = scorenew;
for (temp1 = 0; temp1 < 42;)
{
printf("%d ", field[temp1++]);
if ((temp1) % width == 0)
{
printf("\n");
}
}
printf("score: %d" , scoreold);
/* printf("T1:%d\n", test1); printf("T2:%d\n", test2);
printf("T3:%d\n", test3); printf("T4:%d\n", test4); */
printf("\n\n");
}
if(a==538257){
printf("%f\n",((float)b)/538257874440);
a=0;
}
scorenew = 0;
/* test1 = 0; test2 = 0; test3 = 0; test4 = 0; */
}
printf("Finished!---------------------\n");
}