You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
135 lines
3.7 KiB
135 lines
3.7 KiB
#include <stdio.h> |
|
#include <stdlib.h> |
|
#include <string.h> |
|
#include <stdint.h> |
|
#include "boilerplate.h" |
|
|
|
#if PRINT_INTERMEDIATES |
|
extern uint32_t rawWC; |
|
#endif |
|
|
|
int main(int argc, char * argv[]) { |
|
#if TIME_SECTIONS |
|
clock_t prog_start = clock(); |
|
#endif |
|
|
|
FILE * f; |
|
|
|
#if ASSUME_SAFE |
|
if (argc != 2) { |
|
fprintf(stderr, "usage: %s file\n", argv[0]); |
|
return 2; |
|
} |
|
f = fopen(argv[1], "r"); |
|
if (f == NULL) { |
|
fprintf(stderr, "%s: %s: no such file or directory\n", argv[0], argv[1]); |
|
return 2; |
|
} |
|
#else |
|
f = fopen(argv[1], "r"); |
|
#endif |
|
|
|
START_TIME("making array") |
|
uint32_t fiveUniqWC; |
|
signature* sigs = makeArray(f, &fiveUniqWC); |
|
END_TIME |
|
fclose(f); |
|
|
|
#if PRINT_INTERMEDIATES |
|
fprintf(stderr, "INTERMEDIATE: read %u words\n", rawWC); |
|
fprintf(stderr, "INTERMEDIATE: kept %u words with 5 unique letters\n", i); |
|
#endif |
|
|
|
START_TIME("sorting") |
|
qsort(sigs, fiveUniqWC, sizeof(signature), compare); |
|
END_TIME |
|
|
|
START_TIME("removing duplicates") |
|
uint32_t cookedWC = rmdups(sigs, fiveUniqWC); |
|
|
|
#if PRINT_INTERMEDIATES |
|
fprintf(stderr, "INTERMEDIATE: ended with %u totally unique words\n", cookedWC); |
|
#endif |
|
findWords(sigs, cookedWC); |
|
|
|
#if TIME_SECTIONS |
|
clock_t prog_end = clock(); |
|
fprintf(stderr, "%s took %fs total\n", argv[0], ((double)(prog_end - prog_start)) / CLOCKS_PER_SEC); |
|
#endif |
|
|
|
#if FREE |
|
free(sigs); |
|
#endif |
|
|
|
return 0; |
|
} |
|
|
|
void findWords(signature* restrict sigs, const uint32_t len) { |
|
START_TIME("finding starts") |
|
// for each index, locate the first index of |
|
// a word that shares no letters with it, and |
|
// store the distance between the two. |
|
uint32_t endindex = 0; |
|
uint32_t* starts = calloc(len, sizeof(uint32_t)); |
|
for (uint32_t i = 0; endindex < len && i < len; endindex++) { |
|
uint32_t sig = sigs[endindex].sign; |
|
for (i = endindex+1; i < len; i++) { |
|
if ((sig & sigs[i].sign) == 0) { |
|
starts[endindex] = i; |
|
break; |
|
} |
|
} |
|
} |
|
starts[endindex-1] = endindex-1; |
|
END_TIME |
|
|
|
#define START(var) (starts[var]-1) |
|
START_TIME("finding words") |
|
// the big loop. |
|
for (uint32_t i1 = 0; i1 < len; i1++) { |
|
uint32_t a = sigs[i1].sign; |
|
|
|
for (uint32_t i2 = START(i1); i2 < endindex; i2++) { |
|
do { i2++; } while (a & sigs[i2].sign); |
|
uint32_t ab = a | sigs[i2].sign; |
|
PRINT2 |
|
|
|
for (uint32_t i3 = START(i2); i3 < endindex; i3++) { |
|
do { i3++; } while (ab & sigs[i3].sign); |
|
uint32_t abc = ab | sigs[i3].sign; |
|
PRINT3 |
|
|
|
for (uint32_t i4 = START(i3); i4 < endindex; i4++) { |
|
if (abc & sigs[i4].sign) { continue; } |
|
uint32_t abcd = abc | sigs[i4].sign; |
|
PRINT4 |
|
|
|
uint32_t i5start = START(i4); |
|
for (uint32_t i5 = MAX(endindex, i5start); i5 < len; i5++) { |
|
if (abcd & sigs[i5].sign) { continue; } |
|
#if FANCYPRINT |
|
printsigs(sigs, 5, i1, i2, i3, i4, i5); |
|
#else |
|
printf("%s, %s, %s, %s, %s\n", sigs[i1].word, sigs[i2].word, sigs[i3].word, sigs[i4].word, sigs[i5].word); |
|
#endif |
|
|
|
#if FIND_ONE |
|
goto loopend; |
|
#endif |
|
|
|
} |
|
} |
|
} |
|
} |
|
} |
|
#undef START |
|
|
|
#if FIND_ONE |
|
loopend: |
|
#endif |
|
END_TIME |
|
#if FREE |
|
free(starts); |
|
#endif |
|
return; |
|
} |