/**
 * Zig-zag Cipher
 * Problem 2, AIC 2004 (Senior)
 * C Sample Solution
 */

/**
 * This solution deciphers the message by:
 *  - first determining the length of the original message, textLength;
 *  - encrypting the integers 0 .. textLength-1 according to the scheme in the
 *    question.
 *  - reading the numbers left-to-right, top-to-bottom from the step above to
 *    generate a table that links index in the encrypted text to an index in
 *    the plain text.
 *  - use this table to decrypt the message.
 *
 * For example, to decrypt COPATGAHRRY in 3 rows, we consider the 11 integers
 * 0, 1, 2, ... 11. Encrypting this into a 2-D array, dummyText, makes the
 * array look like:
 *
 *   0 5 6 11
 *   1 4 7 10
 *   2 3 8 9
 *
 * We can then generate a table, decryptMap, that matches the position in the
 * encrypted text to their index in the original text:
 *
 *            i  0    1    2    3    4    5    6    7    8    9   10   11
 * decryptMap[i] 0    5    6   11    1    4    7   10    2    3    8    9
 *
 * We can then read the original message by printing out the characters in the
 * order given by the table.
 *
 */

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

#define MAXMESSAGE 10000
#define MAXROWS 100
#define MAXLINELENGTH 70

/* decrypt[i] = ciphertext index for plaintext[i]. */
int decryptMap[MAXMESSAGE];

int dummyText[MAXROWS][MAXMESSAGE];
int rowLen[MAXROWS];

int rows;
char ciphertext[MAXMESSAGE+1];
int textLength;

int main() {
    FILE *in;
    FILE *out;
    int currRow; /* Keep track of the current row we are on (starting from 0) */
    int currDir; /* Keep track of the direction the text is currently heading */
                 /* (-1 for upwards, +1 for downwards).                       */
    int pos;
    int i;

    /*
     * Allocate some space on the stack for the line we read in.
     * We add for 2 newline characters, and 1 for null terminator
     */
    char text[MAXLINELENGTH+3];

    /* Open the I/O files. */
    in = fopen("zigin.txt", "r");
    out = fopen("zigout.txt", "w");

    /* Read the number of rows the deciphered text will fill. */
    fscanf(in, "%d", &rows);

    /* Clear the rowLen array - assume all rows are empty. */
    for (i = 0; i < rows; i++)
        rowLen[i] = 0;

    /* Read in the first line of text. */
    fscanf(in, "%s", text);
    /* If the current line of text is a "#", then we have the entire input. */
    while (strcmp(text, "#") != 0) {
        /*
         * We have a string which is not just a #
         * Append it to the existing string.
         */
        strcat(ciphertext, text);

        /* Read in the next line. */
        fscanf(in, "%s", text);
    }
    fclose(in);
    textLength = strlen(ciphertext);

    /*
     * We know the length of the encrypted text and the number of rows that it
     * fills.
     *
     * Fill in the dummyText array with the encrypted version of the integers
     * 0 .. textLength-1.
     */
    currRow = 0; /* Starting at row 0. */
    currDir = 1; /* Heading down to begin with. */
    for (i = 0; i < textLength; i++) {
        /* Mark this position in the dummy array. */
        dummyText[currRow][rowLen[currRow]] = i;
        rowLen[currRow]++;

        /* Move to the next row for the next character. */
        currRow += currDir;

        /* If we are at the top or the bottom, change direction. */
        if (currRow == rows - 1)
            currDir = -1;
        else if (currRow == 0)
            currDir = 1;
    }

    /* Construct the decryptMap array from the dummyText. */
    for (currRow = 0, pos = 0; currRow < rows; currRow++) {
        for (i = 0; i < rowLen[currRow]; i++) {
            decryptMap[dummyText[currRow][i]] = pos;
            pos++;
        }
    }

    /* We now know the order to print out the letters from the plain text. */
    for (pos = 0; pos < textLength; pos++)
        fputc(ciphertext[decryptMap[pos]], out);
    fprintf(out, "\n");
    fclose(out);

    return 0;
}