061.c

/****************************************************************************
Problem 61
16 January 2004

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are 
all figurate (polygonal) numbers and are generated by the following formulae:

Triangle     P3,n = n(n+1)/2    1, 3,  6, 10, 15, ... 
Square       P4,n = n^2         1, 4,  9, 16, 25, ... 
Pentagonal   P5,n = n(3n-1)/2   1, 5, 12, 22, 35, ... 
Hexagonal    P6,n = n(2n-1)     1, 6, 15, 28, 45, ... 
Heptagonal   P7,n = n(5n-3)/2   1, 7, 18, 34, 55, ... 
Octagonal    P8,n = n(3n-2)     1, 8, 21, 40, 65, ... 

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three 
interesting properties.

1.The set is cyclic, in that the last two digits of each number is the first 
two digits of the next number (including the last number with the first).
2.Each polygonal type: triangle (P3,127=8128), square (P4,91=8281), and 
pentagonal (P5,44=2882), is represented by a different number in the set.
3.This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which 
each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and 
octagonal, is represented by a different number in the set.

*******
Outputs is:
8128, 2882, 8256, 5625, 2512, 1281

whose sum is 28684
******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#define SIX			6	//size of the array with cyclic numbers
#define SHOWSETS	1   //show triangular, square, etc sets at the start
#define DEBUG		1	//show debug output in function main()
#define INFUNCDEBUG	0	//show debug output in checking functions - not recommendes, lots of output
#define VERBOSE		0   //verbose output during run

//Creates 6 sets with triangular, square, pentagonal, hexagonal,
//heptagonal and octagonal numbers, return a pointer to the sets.
//Note that altough num_sets, num_elem and max_idx are passed as
//arguments, they can't be changed at will. Need to take care with
//its values.
int* create_sets(int num_sets, int num_elem, int max_idx) {
   
   int offset   =0;
   //allocate memory for the sets
   //more straightforward way would be like this:
   //use: sets[set][element]
   //int** sets = (int**) malloc(num_sets * sizeof(int*));
   //for (int i=0; i<num_sets; i++) sets[i] = (int*) malloc(num_elem * sizeof(int));
   //
   //but, alternatively, this way result in contiguos memory, better for the cache
   //use: int offset = set*num_elem+element;
   //then: sets[offset]
   int *sets = (int *) malloc (num_sets * num_elem * sizeof(int)); 
   
   //check memory
   if (sets == NULL)
      return NULL;
   
   //create sets
   int idx; int val;
   for(int set=0; set<SIX; set++) {
		idx=0;
		for(int i=0; i<max_idx; i++) {
			int n   = i+1;
			switch (set) {	case 0: val = n*(n+1)/2; 	break;	//triangular
							case 1: val = n*n;			break;	//square
							case 2: val = n*(3*n-1)/2;	break;	//pentagonal
							case 3: val = n*(2*n-1);	break;	//hexagonal
							case 4: val = n*(5*n-3)/2;	break;	//heptagonal
							case 5: val = n*(3*n-2); 	break;}	//octagonal
			if ((val > 999) & (val <= 9999)) {
				offset = set*num_elem+idx;
				sets[offset] = val;
				idx++;
			}
		}
	}
   return sets;
}

int check_types(int* nums,int *sets, int num_elem) {
    
	int ndx[]  ={0,1,2,3,4,5}; //indexes of nums to be checked
	int flag;
	int offset=0;
	//each number has to be in at least one set, and
	//each set has to have at least one number in it.
	//
	//first, check whether each set has at least 1 number:
	for (int set=0; set<SIX; set++) {
		flag=0;
		for(int i=0; i<num_elem; i++) {
			offset = set*num_elem+i;
			for(int n=0; n<SIX; n++) { 
				if(nums[n] == sets[offset]) {
					flag=1;
					break;
				}
			}
			if (flag==1) break;
		}
		if (flag==0) return 0;
	}
	//and then, check whether all numbers are in at least 1 set:
	for(int n=0; n<SIX; n++) { 
		flag=0;
		for (int set=0; set<SIX; set++) {
			for(int i=0; i<num_elem; i++) {
				offset = set*num_elem+i;
				if(nums[n] == sets[offset]) {
					flag=1;
					break;
				}
			}
			if (flag==1) break;
		}
		if (flag==0) return 0;
	}
	return 1; 
}
	
int check_cyclic(int* nums) {
	int l1[] = {0,0,0,0,0,0};
	int l2[] = {0,0,0,0,0,0};
	for(int i=0; i<SIX; i++) {
		l1[i] = nums[i]/100;
		l2[i] = nums[i]-100*(nums[i]/100);
		//DEBUG - print nums, l1 and l2
		if (INFUNCDEBUG) printf("%d\t%d\t%d\n",nums[i], l1[i], l2[i]);
	}
	//check if l1 == l2
	//first a quick check just to exclude most cases
	if (l1[0]+l1[1]+l1[2]+l1[3]+l1[4]+l1[5] != l2[0]+l2[1]+l2[2]+l2[3]+l2[4]+l2[5])
		return 0;
	//then a more robust check
	//not allowing inner circles
	int idx[]={0,1,2,3,4,5};
	int flag; int n=0;
	for(int i=0; i<SIX-1; i++) {
		flag=0;
		for(int j=1; j<SIX; j++) {
			if(idx[j] != -1 ) {
				if(l2[n]==l1[idx[j]]) {
					flag = 1;
					idx[j] = -1;
					n=j;
					break;
				}
			}
		}
		if (flag==0) return 0;
	}
	//need to check last one
	if (l2[n]==l1[0]) return 1;
	return 0;
}

int main () {

	//set up and create sets
	int num_sets = SIX;
	int max_idx  = 141;
	int sz       = 100;
	int *sets = create_sets(num_sets, sz, max_idx);
	//check if sets are created ok
	if (sets==NULL) {
	  printf("Erro ao alocar memoria.\n");
	  return -1;
	}
	//print the sets:
	if (SHOWSETS) {
		printf("Sets created:\n");
		printf("Triang\tSquare\tPenta\tHexa\tHepta\tOcta\n");
		for(int i=0; i<sz; i++) 
			printf("%d\t%d\t%d\t%d\t%d\t%d\n", sets[0*sz+i],sets[1*sz+i],sets[2*sz+i],sets[3*sz+i],sets[4*sz+i],sets[5*sz+i]);
	}

	//allocate array for the numbers
	int nums[] = {8128, 2882, 8256, 5625, 2512, 1281}; 
	
	/*DEBUG - check functions check_types() and check_cyclic() */
	if (DEBUG) {
		printf("\nNumbers to be checked are:\n");
		for(int i=0; i<SIX; i++)
			printf("%d\t", nums[i]); printf("\n");
		int chk = check_types(nums, sets, sz);
		if (chk==1) { printf("True - each set has a different number associated to it\n"); }
		else        { printf("False - some sets have no number associated\n"); }
		printf("\nChecking split of numbers:\n");
		chk= check_cyclic(nums);
		if (chk==1) { printf("True - set is cyclic\n"); }
		else        { printf("False - set is not cyclic\n"); }
	}
	
	//ok, there you go... start the big loop 
	int offset; float prog; int intertotp=sz*sz/100; char progstr[]={"|/-\\"};
	for(int i0=0; i0<sz; i0++) {
		offset = 0*sz+i0;
		if (sets[offset]) {
			nums[0]=sets[offset];
			for(int i1=0; i1<sz; i1++) {
				offset = 1*sz+i1;
				if (sets[offset]) {
					nums[1]=sets[offset];
					for(int i2=0; i2<sz; i2++) {
						offset = 2*sz+i2;
						if (sets[offset]) {
							nums[2]=sets[offset];
							for(int i3=0; i3<sz; i3++) {
								offset = 3*sz+i3;
								if (sets[offset]) {
									nums[3]=sets[offset];
									for(int i4=0; i4<sz; i4++) {
										offset = 4*sz+i4;
										if (sets[offset]) {
											nums[4]=sets[offset];
											for(int i5=0; i5<sz; i5++) {
												offset = 5*sz+i5;
												if (sets[offset]) {
													nums[5]=sets[offset];
													//do the big checks
													if(check_cyclic(nums)) {
														if (VERBOSE) printf("Numbers are ciclic. Checking sets...\n");
														if (check_types(nums, sets, sz)) {
															if (VERBOSE) printf("True! Found one! They are:\n");
															for(int i=0; i<SIX; i++) printf("%4.4d   ",nums[i]); printf("\n");
														} else {
															if (VERBOSE) printf("False.\n");
														}
													} 
												}
											}
										}
									}
								}
							}
						}
					}
				}
				//give some progress
				prog = (float)(i1+1+i0*sz) / intertotp;
				printf("%.2f%% done %c \r", prog, progstr[i1%4]); fflush(stdout);
			}
		}
	}// */
   
	//clear up memory
	free(sets);
	return 0;
}