123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265 |
- #include <errno.h>
- #include <stdbool.h>
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- static int lineWidth = 0;
- static FILE* file = NULL;
- typedef struct {
- char* data;
- int length;
- } Word;
- static Word* words = NULL;
- static int wordAmount = 0;
- static int wordCapacity = 0;
- static int randA = 0;
- static int randB = 0;
- static const char* beforeWord = "";
- static int beforeWordLength = 0;
- static const char* afterWord = "";
- static int afterWordLength = 0;
- static const char* afterLine = "";
- static int afterLineLength = 0;
- typedef struct {
- int a;
- int b;
- } Swap;
- static Swap swaps[50];
- static int swapIndex = 0;
- static void addSwap(int a, int b) {
- if(swapIndex >= (int)(sizeof(swaps) / sizeof(swaps[0]))) {
- return;
- }
- swaps[swapIndex].a = a;
- swaps[swapIndex++].b = b;
- }
- static void addWord(char* word) {
- if(wordAmount >= wordCapacity) {
- wordCapacity = wordCapacity * 2 + 1;
- words = (Word*)realloc(words, (size_t)wordCapacity * sizeof(Word));
- }
- int index = wordAmount++;
- words[index].data = word;
- words[index].length =
- beforeWordLength + (int)strlen(word) + afterWordLength;
- }
- static int compareWords(const void* a, const void* b) {
- const Word* ra = (const Word*)a;
- const Word* rb = (const Word*)b;
- return ra->length == rb->length ? 0 : ra->length < rb->length ? 1 : -1;
- }
- static void parseFile(void) {
- while(true) {
- int c = fgetc(file);
- while(c == ' ' || c == '\n') {
- c = fgetc(file);
- }
- if(c == EOF) {
- break;
- }
- int capacity = 8;
- int index = 0;
- char* word = (char*)malloc((size_t)capacity * sizeof(char));
- while(c != ' ' && c != EOF && c != '\n') {
- if(index >= capacity) {
- capacity *= 2;
- word = (char*)realloc(word, (size_t)capacity);
- }
- word[index++] = (char)c;
- c = fgetc(file);
- }
- if(index >= capacity) {
- capacity *= 2;
- word = (char*)realloc(word, (size_t)capacity);
- }
- word[index++] = '\0';
- addWord(word);
- }
- }
- static void clean(void) {
- if(words != NULL) {
- for(int i = 0; i < wordAmount; i++) {
- free(words[i].data);
- }
- free(words);
- }
- }
- static int getScore(void) {
- int score = 0;
- int length = 0;
- for(int i = 0; i < wordAmount; i++) {
- int l = words[i].length;
- if(length + l <= lineWidth - afterLineLength) {
- length += l;
- } else {
- score += lineWidth - length;
- length = l;
- }
- }
- return score;
- }
- static void print(void) {
- for(int i = 1; i <= lineWidth; i++) {
- putchar('0' + (i % 10));
- }
- putchar('\n');
- int length = 0;
- for(int i = 0; i < wordAmount; i++) {
- int l = (int)words[i].length;
- if(length + l <= lineWidth - afterLineLength) {
- printf("%s%s%s", beforeWord, words[i].data, afterWord);
- length += l;
- } else {
- length = l;
- printf("%s\n%s%s%s", afterLine, beforeWord, words[i].data,
- afterWord);
- }
- }
- putchar('\n');
- }
- static void generateRandom(void) {
- randA = rand() % wordAmount;
- randB = rand() % wordAmount;
- }
- static void swap(int indexA, int indexB) {
- Word tmp = words[indexA];
- words[indexA] = words[indexB];
- words[indexB] = tmp;
- }
- static void optimize(void) {
- int globalMin = getScore();
- for(int k = 0; k < 5000; k++) {
- int minScore = getScore();
- for(int i = 0; i < 100000; i++) {
- generateRandom();
- swap(randA, randB);
- int score = getScore();
- if(score < minScore) {
- minScore = score;
- } else {
- swap(randA, randB);
- }
- }
- if(minScore < globalMin) {
- globalMin = minScore;
- print();
- printf("\nscore: %d\n", minScore);
- }
- for(int i = 0; i < 50; i++) {
- generateRandom();
- swap(randA, randB);
- }
- }
- }
- static int findIndexOfLargestMatch(int sum, int start, int end) {
- for(int i = start; i < end; i++) {
- if(sum + words[i].length <= lineWidth - afterLineLength) {
- return i;
- }
- }
- return -1;
- }
- static void sort(int start, int end) {
- if(start >= end) {
- return;
- }
- qsort(words + start, (size_t)(end - start), sizeof(words[0]), compareWords);
- }
- static int analyseRecursion(int sum, int start, int globalIndex, int end) {
- if(start >= end) {
- return -1;
- } else if(sum == lineWidth - afterLineLength) {
- return 0;
- }
- int index = findIndexOfLargestMatch(sum, start, end);
- if(index < 0) {
- return -1;
- }
- int r = analyseRecursion(sum + words[index].length, index + 1,
- globalIndex + 1, end);
- if(r < 0) {
- // no match with this index, try starting from next
- return analyseRecursion(sum, start + 1, globalIndex, end);
- }
- addSwap(index, globalIndex);
- return r + 1;
- }
- static void analyse(void) {
- int i = 0;
- int end = wordAmount;
- while(i < end) {
- sort(i, end);
- int r = analyseRecursion(0, i, i, end);
- if(r > 0) {
- i += r;
- while(--swapIndex >= 0) {
- swap(swaps[swapIndex].a, swaps[swapIndex].b);
- }
- swapIndex = 0;
- } else {
- end--;
- swap(i, end);
- }
- }
- print();
- }
- int main(int argAmount, const char* const* args) {
- if(argAmount <= 0) {
- puts("... <mode> <width> <file> <before> <after> <line>");
- return 0;
- } else if(argAmount < 7) {
- printf("%s <mode> <width> <file> <before> <after> <line>\n", args[0]);
- return 0;
- }
- lineWidth = atoi(args[2]);
- if(lineWidth <= 0) {
- printf("%s is an invalid line width\n", args[2]);
- return 0;
- }
- file = fopen(args[3], "rb");
- if(file == NULL) {
- printf("%s is an invalid file: %s\n", args[3], strerror(errno));
- return 0;
- }
- beforeWord = args[4];
- beforeWordLength = (int)strlen(args[4]);
- afterWord = args[5];
- afterWordLength = (int)strlen(args[5]);
- afterLine = args[6];
- afterLineLength = (int)strlen(args[6]);
- parseFile();
- if(strcmp(args[1], "random") == 0) {
- optimize();
- } else if(strcmp(args[1], "think") == 0) {
- analyse();
- }
- clean();
- if(fclose(file)) {
- printf("close error: %s\n", strerror(errno));
- }
- return 0;
- }
|