/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include <stdio.h>
#include <time.h>
int grid[12],used[12];
int inner_group[60][6];
int inner_primes[6]={2,3,5,7,11,13};
int outer_primes[12]={17,19,23,29,31,37,41,43,47,53,59,61};
int min_solution[18];
int min_sum=99999;
long count=0;
void get_inner_groups(int pos);
void search(int pos);
void evaluate_grid();
int main()
{
clock_t start_t, end_t;
int minutes, seconds;
for(int i=0;i<6;i++)grid[i]=used[i]=0;
count=0;
get_inner_groups(1);
count=0;
start_t = clock();
// full search: (run-time approx. 25 minutes, will time-out in this environment)
// search(0);
// partial search: (run-time 2 to 2.5 minutes)
grid[0]=0; // use value in range [0 to 11], minumum solution has grid[0]=11
used[grid[0]]=1;
search(1);
end_t = clock();
seconds=(end_t - start_t) / CLOCKS_PER_SEC;
minutes=seconds/60;
seconds%=60;
printf("Arrangements checked: %ld\n",count);
printf("Elapsed time: %d minutes, %d seconds\n",minutes,seconds);
printf("Minimum sum: %d\n",min_sum);
// the first 6 numbers in the solution are the inner primes in order
// (clockwise or counter-clockwise from any starting point)
// the other 12 numbers are the outer primes in order,
// starting from the same point and moving in the same direction
for(int i=0;i<18;i++)printf("%d ",min_solution[i]);
return 0;
}
void get_inner_groups(int pos)
{
for(grid[pos]=1;grid[pos]<6;grid[pos]++){
if(used[grid[pos]]==0){
used[grid[pos]]=1;
if(pos==5){
if(grid[1]<grid[pos]){
for(int i=0;i<6;i++)inner_group[count][i]=grid[i];
count++;
}
}else{
get_inner_groups(pos+1);
}
used[grid[pos]]=0;
}
}
grid[pos]=0;
}
void search(int pos)
{
for(grid[pos]=0;grid[pos]<12;grid[pos]++){
if(used[grid[pos]]==0){
used[grid[pos]]=1;
if(pos==11)evaluate_grid();
else search(pos+1);
used[grid[pos]]=0;
}
}
}
void evaluate_grid()
{
int i,n0,n1,n2,n3,sum;
int group;
for(group=0;group<60;group++){
count++;
sum=30030;
for(i=0;i<6;i++){
n0=inner_primes[inner_group[group][i]];
n1=outer_primes[grid[2*i]];
n2=outer_primes[grid[2*i+1]];
n3=outer_primes[grid[i==0?11:2*i-1]];
sum+=n1*n2+n0*n1*n3;
}
if(sum<min_sum){
min_sum=sum;
for(i=0;i<6;i++)min_solution[i]=inner_primes[inner_group[group][i]];
for(i=0;i<12;i++)min_solution[i+6]=outer_primes[grid[i]];
}
}
}
