N-finder for Problem Set 2

The N we found in last week's lecture was determined after calculating the 6th possible combination of stamps. Not too much work, but with numbers as ugly as 5 and 11 I figured that manually finding it would be more time consuming than just asking a Pentium 3 to find it for me :-)

Here's a small C program that calculates the first few possible combinations of 5- and 11-cent stamps, and finds the first combination that starts the series of consecutive values. It can be used for any stamp values, provided you adjust the STAMP_1, STAMP_2, and SIZE constants.

#include <stdio.h>
#include <stdlib.h>

#define STAMP_1 5  // STAMP_1 must be smaller than STAMP_2
#define STAMP_2 11

#define SIZE 50

struct DATA {
    int total;  // the total value
    int five;   // the factor of 5-cent stamps
    int eleven; // the factor of 11-cent stamps
};

int order(const void* a, const void* b)
{
    return ((struct DATA*)a)->total - ((struct DATA*)b)->total;
}

int main(int argc, char* argv[])
{
    struct DATA* data = calloc(SIZE * SIZE, sizeof(struct DATA));
    struct DATA* Data = calloc(SIZE * SIZE, sizeof(struct DATA));

    int i, j;
    
    // calculate many different combinations of 5 and 11 cents
    for(i = 0; i < SIZE; i++) {     // for every 5-cent stamp
        for(j = 0; j < SIZE; j++) { // for every 11-cent stamp
            data[i * SIZE + j] = (struct DATA) {
                i * STAMP_1 + j * STAMP_2, i, j
            };
        }
    }
    
    // sort them in ascending order
    qsort(data, SIZE * SIZE, sizeof(struct DATA), order);
    
    // remove duplicate totals
    for(i = 0, j = 0; i < SIZE * SIZE - 1 && j < SIZE * SIZE; j++) {
        do {
            i++;
        } while(i < SIZE * SIZE - 1 && data[i].total == data[i + 1].total);

        Data[j] = data[i];
    }
    
    int entries = j;
    int consecutive = 0;
    
    // search for 5 consecutive total values
    for(i = 0; i < entries - STAMP_1; i++) {
        consecutive = 1;
        
        for(j = i; j < i + STAMP_1 - 1; j++) {
            if(Data[j].total + 1 != Data[j + 1].total) {
                consecutive = 0;
                break;
            }
        }
        
        if(consecutive) {
            consecutive = i;
            break;
        }
    }

    if(consecutive > 0) {
        printf("The first batch of %d consecutive total values occurs at:\n\n",
        STAMP_1);

        printf("%d = %d * (%d) + %d * (%d)  --  unique combination #%d\n\n",
        Data[consecutive].total,
        Data[consecutive].five, STAMP_1,
        Data[consecutive].eleven, STAMP_2,
        consecutive + 1);
        
        for(i = 1; i < STAMP_1; i++) {
            printf("%d = %d * (%d) + %d * (%d)\n",
            Data[consecutive + i].total,
            Data[consecutive + i].five, STAMP_1,
            Data[consecutive + i].eleven, STAMP_2);
        }
        
        printf("\nThen N = %d. ", Data[consecutive].total - 1);
    } else {
        printf("No batch of %d consecutive total values found!\n", STAMP_1);
        printf("Try a total data size larger than %d * %d = %d.\n\n",
        SIZE, SIZE, SIZE * SIZE);
    }
    
    free(data);
    free(Data);
    
    printf("Press RETURN to exit\n");
    getchar();

    return 0;
}

It turns out that N was derived from the 20th possible combination. I noticed a potential pattern in the combinations, and if I'll have the time I'll devise a prettier algorithm to replace the brute-force approach sometime before the course ends.