#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;
}