#include <errno.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int lineWidth = 0;
static FILE* file = NULL;

static char** words = NULL;
static int wordAmount = 0;
static int wordCapacity = 0;

static int randA = 0;
static int randB = 0;

static const char* afterWord = "";
static int afterWordLength = 0;
static const char* afterLine = "";
static int afterLineLength = 0;

static void addWord(char* word) {
    if(wordAmount >= wordCapacity) {
        wordCapacity = wordCapacity * 2 + 1;
        words = (char**)realloc(words, (size_t)wordCapacity * sizeof(char*));
    }
    words[wordAmount++] = word;
}

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]);
        }
        free(words);
    }
}

static int getScore(void) {
    int score = 0;
    int length = 0;
    for(int i = 0; i < wordAmount; i++) {
        int l = (int)strlen(words[i]) + afterWordLength;
        if(length + l <= lineWidth - afterLineLength) {
            length += l;
        } else {
            score += lineWidth - length;
            length = l;
        }
    }
    return score;
}

static void print(void) {
    for(int i = 0; i < lineWidth; i++) {
        putchar('0' + (i % 10));
    }
    putchar('\n');
    int length = 0;
    for(int i = 0; i < wordAmount; i++) {
        int l = (int)strlen(words[i]) + afterWordLength;
        if(length + l <= lineWidth - afterLineLength) {
            printf("%s%s", words[i], afterWord);
            length += l;
        } else {
            length = l;
            printf("%s\n%s%s", afterLine, words[i], afterWord);
        }
    }
}

static void generateRandom(void) {
    randA = rand() % wordAmount;
    randB = rand() % wordAmount;
}

static void swap(void) {
    char* tmp = words[randA];
    words[randA] = words[randB];
    words[randB] = 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();
            int score = getScore();
            if(score < minScore) {
                minScore = score;
            } else {
                swap();
            }
        }
        if(minScore < globalMin) {
            globalMin = minScore;
            print();
            printf("\nscore: %d\n", minScore);
        }
        for(int i = 0; i < 50; i++) {
            generateRandom();
            swap();
        }
    }
}

int main(int argAmount, const char* const* args) {
    if(argAmount <= 0) {
        puts("... <width> <file> <after> <line>");
        return 0;
    } else if(argAmount < 5) {
        printf("%s <width> <file> <after> <line>\n", args[0]);
        return 0;
    }
    lineWidth = atoi(args[1]);
    if(lineWidth <= 0) {
        printf("%s is an invalid line width\n", args[1]);
        return 0;
    }
    file = fopen(args[2], "rb");
    if(file == NULL) {
        printf("%s is an invalid file: %s\n", args[2], strerror(errno));
        return 0;
    }
    afterWord = args[3];
    afterWordLength = (int)strlen(args[3]);
    afterLine = args[4];
    afterLineLength = (int)strlen(args[4]);
    parseFile();
    optimize();
    clean();
    if(fclose(file)) {
        printf("close error: %s\n", strerror(errno));
    }
    return 0;
}