2
\$\begingroup\$

Below, I have created a rudimentary script to decipher a columnar transposition. I am wondering if there is a more efficient way to determine the number of the rows in a column? Also, is there a way to build the resulting string without creating a matrix in the interim?

Overview

Quick refresher for columnar transpositions.

Method 1

Given a key of 3,

the text 'Attack at dawn' is transposed into three columns...

1   2   3
A   t   t
a   c   k
a   t   D
a   w   n

...joining each column; left->right, top->bottom; will result in the following text:

Aaaa tctw tkDn

Method 2

Given a key 'table',

the text 'Attack at dawn' is transposed into five columns (length of the key)...

t   a   b   l   e
A   t   t   a   c
k   a   t   D   a
w   n

...joining the columns, as described above, result in the following text:

tAkw atan btt laD eca

Code

Is there a better way to determine how many rows will be present for each column?

function decrypt(ciphertext, key) {
    var chars   = normalizeText(ciphertext);
    var len     = chars.length;
    var isStr   = typeof key === 'string';
    var cols    = isStr ? key.length : key;
    var rows    = Math.ceil(len / cols);
    var mod     = divMod(len, cols)[1];
    var matrix  = Matrix(rows, cols, '');
    var counter = 0;
    for (var col = 0; col < cols; col++) {
        var remainder = mod !== 0 && col >= mod ? 1 : 0;
        for (var row = 0; row < rows - remainder; row++) {
            matrix[row][col] = chars[counter++];
        }
    }
    return (function(plaintext, startIndex) {
        return plaintext.substr(startIndex);
    }(matrix.reduce(function(result, row) {
        return result + row.join('');
    }, ''), isStr ? cols : 0));
}

Demo

[ [ 'Aaaa tctw tkDn'       , 3       ],
  [ 'tAkw atan btt laD eca', 'table' ]
].forEach(function(cipher) {
    println(decrypt(cipher[0], cipher[1]));
});

function decrypt(ciphertext, key) {
    var chars   = normalizeText(ciphertext);
    var len     = chars.length;
    var isStr   = typeof key === 'string';
    var cols    = isStr ? key.length : key;
    var rows    = Math.ceil(len / cols);
    var mod     = divMod(len, cols)[1];
    var matrix  = Matrix(rows, cols, '');
    var counter = 0;
    for (var col = 0; col < cols; col++) {
        var remainder = mod !== 0 && col >= mod ? 1 : 0;
        for (var row = 0; row < rows - remainder; row++) {
            matrix[row][col] = chars[counter++];
        }
    }
    return (function(plaintext, startIndex) {
        return plaintext.substr(startIndex);
    }(matrix.reduce(function(result, row) {
        return result + row.join('');
    }, ''), isStr ? cols : 0));
}
function divMod(y, x) {
    return [~~(y / x), y % x];
}
function normalizeText(ciphertext) {
    return ciphertext.replace(/ +/g, "").split('');
}
function Matrix(rows, cols, defaultVal) {
    defaultVal = defaultVal !== undefined ? defaultVal : 0;
    var arr = [];
    for (var i = 0; i < rows; i++) {
        arr.push([]);
        arr[i].push(new Array(cols));
        for (var j = 0; j < cols; j++) {
            arr[i][j] = defaultVal;
        }
    }
    return arr;
}
function print(str, targetEl) {
    return (function (el) {
        return el.html(el.html() + (str || ''));
    }(targetEl || $('#out')));
}
function println(str, targetEl) {
    print((str || '') + '<br />', targetEl)
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="out"></div>

\$\endgroup\$
1
\$\begingroup\$

Allow me to provide a bit of a different approach. I know it does not exactly answer your questions, but I believe it makes them somewhat obsolete.

This is how I would do the decrypt:

function decrypt(sentence) {
    var result = '';
    var pos = 0;

    var words = sentence.split(' ');
    words = words.map(function(word) {
       return word.split(''); 
    });

    while(true) {
       char = words[pos].shift();
        if (! char) {
            break;
        }
        result += char;

        pos = pos > words.length -2 ? 0 : pos + 1;
    }

    return result;
}

For a working example: http://jsfiddle.net/35jyyv8g/1/

Note that I left the key out, since it is not really necessary with the spaces in the input.

\$\endgroup\$
0
\$\begingroup\$

For me, all it takes are two for loops, the first one with i going from 0 to cols (stricly inferior), with increments of 1, and the second loop (inside the first one) with j going from i to len (stricly inferior) with increments of rows . And the characters you want will be at the position j of the initial message. Of course, a better naming for i and j would be a good thing.

\$\endgroup\$
0
\$\begingroup\$

Interesting question,

first off, your encryption approach has some serious problems: To know the encryption key length, you just need ciphertext.split(' ').length

Worse, the cipher-text even has the key in clear text:

tAkw atan btt laD eca

This means @Pevara's approach is correct, and far more elegant. (It does also output the key for strings encrypted with the second method.)

My personal approach uses a bit of ES6 and is a bit more functional:

function simpleDecrypt2(cipher) {
    let out = '',
        parts = cipher.split(' ').map(function(part) { return part.split(''); });

    while( parts[0].length ){
       out += parts.reduce( (out,part)=>out+(part.shift()||''), '' );  
    }
    return out;
}

As for your first question, you could have calculated the row count by

ciphertext.split(' ')[0].length

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.