(**
 * Zig-zag Cipher
 * Problem 2, AIC 2004 (Senior)
 * Pascal 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.
 *
 *)

program ZigZag;

const
    MAXMESSAGE = 10000;
    MAXROWS    = 100;

var
    { decrypt[i] = ciphertext index for plaintext[i]. }
    decryptMap : array[1..MAXMESSAGE] of longint;
    dummyText  : array[1..MAXROWS, 1..MAXMESSAGE] of longint;
    rowLen     : array[1..MAXROWS] of longint;
    rows       : longint;
    ciphertext : string;
    textLength : longint;

    { Input and output files. }
    inFile     : text;
    outFile    : text;

    { currRow keeps track of the current row we are on (starting from 0) }
    currRow    : longint;

    { currDir keeps track of the direction the text is currently heading
      (-1 for upwards, -1 for downwards). }
    currDir    : longint;

    i          : longint;
    dummyIndex : longint;
    inputLine  : string;

begin
    { Open the I/O files. }
    assign(inFile, 'zigin.txt');
    reset(inFile);

    assign(outFile, 'zigout.txt');
    rewrite(outFile);

    readln(inFile, rows);

    for i := 1 to rows do
        rowLen[i] := 0;

    { Read in the first line of text. }
    readln(inFile, inputLine);
    ciphertext := '';
    { If the current line of text is a "#", then we have the entire input. }
    while inputLine <> '#' do begin
        { We have a string which is not just a #
          Append it to the existing string. }
        cipherText := cipherText + inputLine;

        { Read in the next line. }
        readln(inFile, inputLine);
    end;
    close(inFile);
    textLength := length(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 := 1; { Starting at row 0. }
    currDir := 1; { Heading down to begin with. }
    for i := 1 to textLength do begin
        { Mark this position in the dummy array. }
        inc(rowLen[currRow]);
        dummyText[currRow][rowLen[currRow]] := i;

        { Move to the next row for the next character. }
        inc(currRow, currDir);

        { If we are at the top or the bottom, change direction. }
        if currRow = rows then
            currDir := -1
        else if currRow = 1 then
            currDir := 1;
    end;

    { Construct the decryptMap array from the dummyText. }
    dummyIndex := 1;
    for currRow := 1 to rows do begin
        for i := 1 to rowLen[currRow] do begin
            decryptMap[dummyText[currRow][i]] := dummyIndex;
            inc(dummyIndex);
        end;
    end;

    { We now know the order to print out the letters from the plain text. }
    for dummyIndex := 1 to textLength do
        write(outFile, ciphertext[decryptMap[dummyIndex]]);
    writeln(outFile);
    close(outFile);
end.