main.c

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

int isFinal(int element, int finals[], size_t finalsCount) {
    for (int i = 0; i < finalsCount; ++i) {
        if (element == finals[i]) {
            return 1;
        }
    }

    return 0;
}

// breath-first search

typedef struct {
    char status;
    int ancestor;
    int letter;
} nodeMeta;

struct Node {
    int data;
    struct Node *next;
};

// Two glboal variables to store address of front and rear nodes.
struct Node *front = NULL;
struct Node *rear = NULL;

// To Enqueue an integer
void Enqueue(int x) {
    struct Node *temp = (struct Node *) malloc(sizeof(struct Node));
    temp->data = x;
    temp->next = NULL;
    if (front == NULL && rear == NULL) {
        front = rear = temp;
        return;
    }
    rear->next = temp;
    rear = temp;
}

// To Dequeue an integer.
void Dequeue() {
    struct Node *temp = front;
    if (front == NULL) {
        printf("Queue is Empty :(\n");
        return;
    }
    if (front == rear) {
        front = rear = NULL;
    } else {
        front = front->next;
    }
    free(temp);
}

int Front() {
    if (front == NULL) {
        printf("Queue is empty :(\n");
        return -1;
    }
    return front->data;
}

void Print() {
    struct Node *temp = front;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}


int getIndexOfAlphabet(char element, char alphabet[], size_t alphabetSize) {
    int innerIndex;
    for (innerIndex = 0; innerIndex < alphabetSize; ++innerIndex) {
        if (alphabet[innerIndex] == element) {
            break;
        }
    }

    return innerIndex;
}

// dynamic list
typedef struct {
    int *array;
    size_t used;
    size_t size;
} Array;

Array initArray(Array *a, size_t initialSize) {
    a->array = (int *) malloc(initialSize * sizeof(int));
    a->used = 0;
    a->size = initialSize;

    return *a;
}

void insertArray(Array *a, int element) {
    // a->used is the number of used entries, because a->array[a->used++] updates a->used only *after* the array has been accessed.
    // Therefore a->used can go up to a->size
    if (a->used == a->size) {
        a->size *= 2;
        a->array = (int *) realloc(a->array, a->size * sizeof(int));
    }
    a->array[a->used++] = element;
}

void freeArray(Array *a) {
    free(a->array);
    a->array = NULL;
    a->used = a->size = 0;
}

struct transition {
    int start;
    char character;
    int end;
};

int main() {
    // distinguist test (0) and production (1) data
    int useProd = 0;


    // load data

    char alphabet[11];
    size_t alphabetCount = 0;
    int N1 = 0, M1 = 0, N2 = 0, M2 = 0;
    int finals1[10], finals2[10];
    int finalCount1 = 0, finalCount2 = 0;

    FILE *f;
    if (!useProd) f = fopen("/home/tom/prg/c/4_bud_words/dataset/pub05.in", "r");


    int countAlphabet = 0;
    (useProd) ? fgets(alphabet, sizeof(alphabet), stdin) : fgets(alphabet, sizeof(alphabet), f);
    alphabetCount = strlen(alphabet);

    // automata 1st
    (useProd) ? scanf("%i %i", &N1, &M1) : fscanf(f, "%i %i", &N1, &M1);

    struct transition trans1[M1];
    for (int i = 0; i < M1; ++i) {
        (useProd) ? scanf("%i %c %i", &trans1[i].start, &trans1[i].character, &trans1[i].end) :
        fscanf(f, "%i %c %i", &trans1[i].start, &trans1[i].character, &trans1[i].end);
    }

    char tempFinals[100];
    int c;
    int tempCount = 0;
    // get line and parse it
    if (useProd) {
        c = fgetc(stdin); // get last newlane
        // load ...
        do {
            c = fgetc(stdin);
            tempFinals[tempCount] = (char) c;
            tempCount++;
        } while (c != '\n');
        // ... and parse

        char *p = tempFinals;
        tempCount = 0;
        while (p < tempFinals + sizeof(tempFinals)) {
            char *end;
            long int value = strtol(p, &end, 10);
            if (value == 0L && end == p)  //docs also suggest checking errno value
                break;

            // printf("%ld\n", value);
            finals1[tempCount] = (int) value;
            p = end;
            tempCount++;
        }
        finalCount1 = tempCount;
    } else {
        c = fgetc(f); // get last newlane
        // load ...
        do {
            c = fgetc(f);
            tempFinals[tempCount] = (char) c;
            tempCount++;
        } while (c != '\n');
        // ... and parse

        char *p = tempFinals;
        tempCount = 0;
        while (p < tempFinals + sizeof(tempFinals)) {
            char *end;
            long int value = strtol(p, &end, 10);
            if (value == 0L && end == p)  //docs also suggest checking errno value
                break;

            // printf("%ld\n", value);
            finals1[tempCount] = (int) value;
            p = end;
            tempCount++;
        }
        finalCount1 = tempCount;
    }

    // automata 2nd
    (useProd) ? scanf("%i %i", &N2, &M2) : fscanf(f, "%i %i", &N2, &M2);

    struct transition trans2[M2];
    for (int i = 0; i < M2; ++i) {
        (useProd) ? scanf("%i %c %i", &trans2[i].start, &trans2[i].character, &trans2[i].end) :
        fscanf(f, "%i %c %i", &trans2[i].start, &trans2[i].character, &trans2[i].end);
    }

    char tempFinals2[100];
    tempCount = 0;
    // get line and parse it
    if (useProd) {
        c = fgetc(stdin); // get last newlane
        // load ...
        do {
            c = fgetc(stdin);
            tempFinals2[tempCount] = (char) c;
            tempCount++;
        } while (c != '\n');
        // ... and parse

        char *p = tempFinals2;
        tempCount = 0;
        while (p < tempFinals2 + sizeof(tempFinals2)) {
            char *end;
            long int value = strtol(p, &end, 10);
            if (value == 0L && end == p)  //docs also suggest checking errno value
                break;

            // printf("%ld\n", value);
            finals2[tempCount] = (int) value;
            p = end;
            tempCount++;
        }
        finalCount2 = tempCount;
    } else {
        c = fgetc(f); // get last newlane
        // load ...
        do {
            c = fgetc(f);
            tempFinals2[tempCount] = (char) c;
            tempCount++;
        } while (c != '\n');
        // ... and parse

        char *p = tempFinals2;
        tempCount = 0;
        while (p < tempFinals2 + sizeof(tempFinals2)) {
            char *end;
            long int value = strtol(p, &end, 10);
            if (value == 0L && end == p)  //docs also suggest checking errno value
                break;

            // printf("%ld\n", value);
            finals2[tempCount] = (int) value;
            p = end;
            tempCount++;
        }
        finalCount2 = tempCount;
    }


    // chrunch data into two NFA tables
    // automata 1st
    Array nfa1[alphabetCount][N1];
    for (int i = 0; i < alphabetCount; ++i) {
        for (int j = 0; j < N1; ++j) {
            Array a;
            nfa1[i][j] = initArray(&a, 1);
        }
    }

    int characterIndex;
    for (int i = 0; i < M1; ++i) {
        characterIndex = getIndexOfAlphabet(trans1[i].character, alphabet, alphabetCount);
        insertArray(&nfa1[characterIndex][trans1[i].start], trans1[i].end);
    }

    // automata 2nd
    Array nfa2[alphabetCount][N2];
    for (int i = 0; i < alphabetCount; ++i) {
        for (int j = 0; j < N2; ++j) {
            Array a;
            nfa2[i][j] = initArray(&a, 1);
        }
    }

    for (int i = 0; i < M2; ++i) {
        characterIndex = getIndexOfAlphabet(trans2[i].character, alphabet, alphabetCount);
        insertArray(&nfa2[characterIndex][trans2[i].start], trans2[i].end);
    }

/*
    // test output
    for (int k = 0; k < alphabetCount; ++k) {
        for (int l = 0; l < N2; ++l) {
            printf("Tabulka okno %i;%i, použito %zi", k, l, nfa2[k][l].used);
            if (nfa2[k][l].used > 0) {
                printf(" -> první element: %i", nfa2[k][l].array[0]);
            }
            printf("\n");
        }

    }
*/


    // multiple automatas

    Array NFA[alphabetCount][N1][N2];
    for (int i = 0; i < alphabetCount; ++i) {
        for (int j = 0; j < N1; ++j) {
            for (int k = 0; k < N2; ++k) {
                Array a;
                NFA[i][j][k] = initArray(&a, 1);
            }
        }
    }
    Array NFAfinals;
    initArray(&NFAfinals, 1);

    int A1end, A2end, indexOfEnd1D, indexOfElement1D;
    // each node in A1
    for (int nodeA1 = 0; nodeA1 < N1; ++nodeA1) {
        // each letter
        for (int letter = 0; letter < alphabetCount; ++letter) {
            // each trasition in A1 (if any)
            for (int transA1 = 0; transA1 < nfa1[letter][nodeA1].used; ++transA1) {
                // each node in A2
                for (int nodeA2 = 0; nodeA2 < N2; ++nodeA2) {
                    // each transition in A2 (if any)
                    for (int transA2 = 0; transA2 < nfa2[letter][nodeA2].used; ++transA2) {
                        // create transition from start to end
                        A1end = nfa1[letter][nodeA1].array[transA1];
                        A2end = nfa2[letter][nodeA2].array[transA2];
                        indexOfEnd1D = (A1end * N2) + A2end;
                        insertArray(&NFA[letter][nodeA1][nodeA2], indexOfEnd1D);

                        // check for final destinations
                        for (int fin1temp = 0; fin1temp < finalCount1; ++fin1temp) {
                            if (finals1[fin1temp] == nodeA1) {
                                for (int fin2temp = 0; fin2temp < finalCount2; ++fin2temp) {
                                    if (finals2[fin2temp] == nodeA2) {
                                        // match
                                        indexOfElement1D = (nodeA1 * N2) + nodeA2;
                                        insertArray(&NFAfinals, indexOfElement1D);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // test output
    // int position1D;
    for (int k = 0; k < alphabetCount; ++k) {
        for (int l = 0; l < N1; ++l) {
            for (int m = 0; m < N2; ++m) {
                // position1D = (l * N2) + m;
                //printf("BIG tabulka okno %i;%i;%i, 1D: %i, použito %zi", k, l, m, position1D, NFA[k][l][m].used);
                if (NFA[k][l][m].used > 0) {
                    //printf(" -> elementy: ");
                    for (int i = 0; i < NFA[k][l][m].used; ++i) {
                        //printf(" %i", NFA[k][l][m].array[i]);
                    }
                }
                //printf("\n");
            }
        }

    }
    //printf("Finals in 1D:");
    for (int n = 0; n < NFAfinals.used; ++n) {
        //printf(" %i", NFAfinals.array[n]);
    }
    //printf("\n\n");

    // breath-first search (shortest path == shortest word)

    // statuses - o == open, c == closed, f == fresh
    nodeMeta nodeStatus[N1][N2];
    for (int i = 0; i < N1; ++i) {
        for (int j = 0; j < N2; ++j) {
            nodeStatus[i][j].status = 'f';
            nodeStatus[i][j].ancestor = -1;
            nodeStatus[i][j].letter = 'z';
        }
    }

    // push first nodes
    for (int alphTemp = 0; alphTemp < alphabetCount; ++alphTemp) {
        for (int countTemp = 0; countTemp < NFA[alphTemp][0][0].used; ++countTemp) {
            Enqueue(0);
        }
    }

    int element, x, y, nextX, nextY, nextElement;
    int countFinalWord = 0;
    char finalWord[100]; //possible extend?
    while (front != NULL) {
        element = Front();
        Dequeue();
        //printf("Getting element %i from queue.\n", element);

        if (isFinal(element, NFAfinals.array, NFAfinals.used)) {
            // done!
            do {
                x = element / N2;
                y = element % N2;

                finalWord[countFinalWord] = alphabet[nodeStatus[x][y].letter];
                countFinalWord++;

                element = nodeStatus[x][y].ancestor;
            } while (element != 0);

            break; //not nessessary
        } else {
            // continuing...

            // deconstruct element into indexes
            x = element / N2;
            y = element % N2;

            if (nodeStatus[x][y].status != 'c') {
                for (int alphTemp = 0; alphTemp < alphabetCount; ++alphTemp) {
                    for (int countTemp = 0; countTemp < NFA[alphTemp][x][y].used; ++countTemp) {
                        nextElement = NFA[alphTemp][x][y].array[countTemp];
                        nextX = nextElement / N2;
                        nextY = nextElement % N2;

                        if (nodeStatus[nextX][nextY].status == 'f') {
                            nodeStatus[nextX][nextY].ancestor = element;
                            nodeStatus[nextX][nextY].letter = alphTemp;
                            nodeStatus[nextX][nextY].status = 'o';

                            Enqueue(nextElement);
                            //printf("Enqueuing element %i into queue.\n", nextElement);
                        }
                    }
                }

                nodeStatus[x][y].status = 'c';
            }
        }
    } //end while


    for (int i = 0; i < countFinalWord; i++) {
        printf("%c", finalWord[countFinalWord - i - 1]);
    }

    return 0;
}