7
\$\begingroup\$

Columnar Transposition Cipher

While I have plenty of programs I have written for more advanced ciphers, I just realised I don't actually have one for one of the simplest: Columnar Transposition. The cipher, in case you don't know, works as follows:

  1. First, you take the key, and write it as numbers. The numbers are made by replacing the letter which comes first in the alphabet with 1, the letter that comes next 2 and so on, ignoring duplicates (the key GOAT would become 2314). These numbers are the headers of the columns.

    2314
    ----
    
  2. Next, you write your message under the columns.

    2314
    ----
    Hell
    o Wo
    rld!
    
  3. Finally, rearrange the columns into the numerical order in which they would fall, and read the ciphertext across.

    1234
    ----
    lHel
    Wo o
    drl!
    
  4. Which will result in your encoded text: lHelWo odrl!

Rules

  • Each submission should be either a full program or function. If it is a function, it must be runnable by only needing to add the function call to the bottom of the program. Anything else (e.g. headers in C), must be included.
  • There must be a free interpreter/compiler available for your language.
  • If it is possible, provide a link to a site where your program can be tested.
  • Your program must not write anything to STDERR.
  • Your program should take input as an argument or from STDIN (or the closest alternative in your language).
  • Standard loopholes are forbidden.

Requirements

  • Case must be preserved.
  • Your cipher should be 'irregular', that is, if there are any spaces left after you have written out your message, it is treated as if it were a normal space character.
  • Only encryption is required, decryption may come in a later challenge.
  • Input should be taken from STDIN with the key on the first line, and the plaintext on the second. If you are taking input as an argument, please specify how this is done for your language.
  • The key can be in any case.
  • Duplicates in the key should be ignored - that is, ABCDB would become ABCD. Duplicates also apply in any case.
  • Trailing whitespace is included.

Test Cases

CBABD, Duplicates are ignored. ==> puDlacit sea eriongr.de
bDaEc, Key can be in multicase! ==> yKce  aenbn mi tucliea s!

Full example, with 'surplus space' rule.

ADCB
----
"Goo
d Mo
rnin
g!" 
he c
alle
d.  

ABCD
----
"ooG
dom 
rnin
g "!
hc e
aell
d  .

Message: "ooGdom rning "!hc eaelld  .

Scoring

is how we score this challenge!

Submissions

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 79810; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 53406; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
    languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang > b.lang) return 1;
    if (a.lang < b.lang) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<div id="language-list">
  <h2>Winners by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
  • 4
    \$\begingroup\$ The multicase key test case looks wrong; there are 5 different letters in the key so the u in 16th position can't end up in 14th position, since that's now a different block of 5. \$\endgroup\$ – Neil May 12 '16 at 20:25
  • 2
    \$\begingroup\$ What do you mean by "surplus space at the end of your columns is not padded."? Can you give a worked example of a case where it's relevant? \$\endgroup\$ – Peter Taylor May 12 '16 at 22:06
  • 4
    \$\begingroup\$ Is case in the key ignored? If so, is that before or after ignoring duplicates? Also, please state all rules explicitly, don't make us infer them from the test cases \$\endgroup\$ – Luis Mendo May 12 '16 at 22:19
  • 1
    \$\begingroup\$ I still don't get your 2nd test case: the 13th letter (i from in) should be in 11th place in the result: it is put into first place of it's chunk because it lines up with a from the key. \$\endgroup\$ – nimi May 13 '16 at 14:26
  • 1
    \$\begingroup\$ @GeorgeGibson Also, in the second case I get yKce aenbn mi tuclieas!. It may be my mistake, but in any it should be explained how the output is obtained in that case \$\endgroup\$ – Luis Mendo May 13 '16 at 17:03

10 Answers 10

2
\$\begingroup\$

MATL, 12 bytes

kune2M&SY)1e

Try it online!

Explanation

The code works using rows instead of columns. This is totally equivalent and fits better with MATL's column-major indexing.

k     % Take first input (key) implicitly. Convert to lowercase
u     % Keep unique chars, stably
n     % Number of unique chars
e     % Take second input (message) implicitly. Reshape into char matrix
      % with the above number of rows, padding with zeros if needed
2M    % Push string with unique chars of key again
&S    % Sort and push the indices of the sorting
Y)    % Use as row indices into char matrix
1e    % Reshape into a row. Zeros are displayed as spaces
\$\endgroup\$
  • 1
    \$\begingroup\$ The way u, e, M, and & work is so impressive here \$\endgroup\$ – David May 14 '16 at 4:06
  • \$\begingroup\$ @David indeed! :-) \$\endgroup\$ – Luis Mendo May 14 '16 at 8:58
  • 1
    \$\begingroup\$ @Georgegibson Thanks for accepting, but you may want to wait for a few days so as not to discourage other people from posting new answers \$\endgroup\$ – Luis Mendo May 14 '16 at 9:00
  • \$\begingroup\$ @LuisMendo OK, will accept in a while. \$\endgroup\$ – George Gibson May 14 '16 at 15:54
  • 1
    \$\begingroup\$ haha, "kune" - thats the currency we use in Croatia \$\endgroup\$ – FlipTack Jan 10 '17 at 18:52
2
\$\begingroup\$

Python 3, 188 bytes.

There's gotta be a saner way to do this.

from itertools import*
def f(a,b):a,c,s=a.upper(),''.join,sorted;return c(map(c,zip_longest(*[v for k,v in s([(v,b[i::len({*a})])for i,v in enumerate(s({*a},key=a.find))])],fillvalue='')))

Test cases:

assert f('goat', 'Hello World!') == 'lHelWo odrl!'
assert f('GOAT', 'Hello World!') == 'lHelWo odrl!'
assert f('GOAATAT', 'Hello World!') == 'lHelWo odrl!'
assert f('CBABD', 'Duplicates are ignored.') == 'puDlacit sea eriongr.de'

Well that was a fun journey back to square one.

\$\endgroup\$
  • \$\begingroup\$ Save 1 byte by abstracting len() to a 1-letter function \$\endgroup\$ – Blue May 12 '16 at 20:09
  • \$\begingroup\$ @Blue That doesn't save me any bytes. lambda a,b,l=len:''.join(map(''.join,zip(*[v for k,v in sorted([(ord(v),[l for l in b[i::l(a)]])for i,v in enumerate(a.upper()+' '*(l(b)%l(a)))])]))) is also 149. \$\endgroup\$ – Morgan Thrapp May 12 '16 at 20:10
  • \$\begingroup\$ ah, I forgot about the comma. Sorry \$\endgroup\$ – Blue May 12 '16 at 20:11
1
\$\begingroup\$

JavaScript (ES6), 170 bytes

(k,s)=>[...s].map((c,i)=>(i%l||(r+=t.join``,t=[]),t[[...k].sort().search(k[i%l])]=c),k=[...k=k.toLowerCase()].filter((c,i)=>i==k.search(c)),l=k.length,r=t=[])&&r+t.join``

Preprocessing the key is a waste of 56 bytes...

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

Javascript, 155 159 149 151

(w,s)=>(a='',z=new Set,w=[...[...w].map(z.add,z)[0]].sort(),eval(`s.match(/.{1,${z.size}}/g)`).map(l=>[...l].map((c,i)=>a+=l[[...z].indexOf(w[i])]||'')),a)
  • Saved 4 bytes thanks @Bergi.

Here it goes, ungolfed and explained:

function ColumnarTranspositionCipher(word, sentence) {
    var answer = "";
    
    // the own methods of Set does it shorter than a raw Object
    var z = new Set;
    
    // As Set only allows unique keys, we get the processed key by adding
    [...word].forEach(function(letter) {
        z.add(letter);
    });

    // word now has the sorted key
    word = [...z].sort(),

    // divide sentence by the processed key's length
    sentence = sentence.match(RegExp(".{1," + z.size + "}", "g"));

    sentence.forEach(function(row) {
        [...row].forEach(function(letter, newIndex) {

            // get the old index - relative to the previous sorted/unsorted keys
            var oldIndex = [...z].indexOf(word[newIndex]);

            // and add to the answer
            answer += row[oldIndex] || "";
        });
    });

    return answer;
}

r= code=> output.innerHTML += '\n>  ' + code + '\n<- "' + eval(code) + '"\n';
r("ColumnarTranspositionCipher('GOAT', 'Hello World!')");
r("ColumnarTranspositionCipher('CBABD', 'Duplicates are ignored.')");
r("ColumnarTranspositionCipher('aBeCd', 'Key can be in multicase!')");
<pre id=output></pre>

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

Python 3.5, 139

def f(a,b):a,s,j=a.lower(),sorted,''.join;a=s({*a},key=a.find);l=len(a);return j(map(j,[*zip(*s(zip(*zip(*[iter(a+[*b+' '*l])]*l))))][1:]))

Slightly more readable version:

def f(a, b):
    a = a.lower()
    # Remove duplicates
    a = sorted({*a}, key=a.find)
    l = len(a)
    # Add the key
    z = zip(*[iter(a + [*b, *[''] * l])]*l)
    # Sort tuples lexicographically, remove the key
    z = [*zip(*sorted(zip(*z)))][1:]
    return ''.join(map(''.join, z))
\$\endgroup\$
  • 2
    \$\begingroup\$ Well, this wins for most calls to zip in one answer. \$\endgroup\$ – Morgan Thrapp May 12 '16 at 21:04
1
\$\begingroup\$

J, 53 bytes

(3 :',/|:((/:tolower~.>0{y){|:((-#~.>0{y),\(>1{y)))')

Usage example: (3 :',/|:((/:tolower~.>0{y){|:((-#~.>0{y),\(>1{y)))') ('ADCB';'"Good Morning!" he called.') ==> "ooGdoM rning "!hc eaelld .

I basically did exactly what the cipher does, no shortcuts. I had to transpose the matrix to deal with ranking the columns then transpose it back.

Try it Online! (make sure to type "j-bot: " without quotes then paste the code.)

\$\endgroup\$
  • \$\begingroup\$ Hello, and welcome to PPCG! Great first post! \$\endgroup\$ – NoOneIsHere May 13 '16 at 19:05
1
\$\begingroup\$

Haskell, 98 84 83 bytes

import Data.List
h c=map snd.sort.zip((<$>nub((`mod`32).fromEnum<$>c)).(,)=<<[1..])

Usage example: h "CBAbD" "Duplicates are ignored." -> "puDlacit sea eriongr.de".

How it works:

       nub((`mod`32).fromEnum<$>c)  -- turn key to lowercase and remove duplicates
    (<$>      ).(,)=<<[1..]         -- make pairs of (number , char from key)
                                    -- for every character in the key and every
                                    -- number starting with 1. This builds and
                                    -- infinite list, e.g. for the key "cba":
                                    -- (1,c),(1,b),(1,a),(2,c),(2,b),(2,a),(3,c)...
              zip(          )       -- zip this list with input String, e.g. for
                                    -- the string "mnopq" with the key from above:
                                    -- ((1,c),m),((1,b),n),((1,a),o),((2,c),p),((2,b),q)
                                    -- zip stops at the end of the shorter list
         sort                       -- sort lexicographically
 map snd                            -- extract characters of the string
\$\endgroup\$
0
\$\begingroup\$

Ruby, 133 bytes

Zip, sort, zip again, combine.

->k,s{k=k.upcase.chars.uniq
c,*r=k.zip(*s.scan(/.{1,#{k.size}}/).map(&:chars)).sort
c.zip(*r.map{|e|e ?e:' '})[1..-1].map(&:join)*''}
\$\endgroup\$
0
\$\begingroup\$

R, 182 177

Here is the golfed version:

function(t,k){k=unique(unlist(strsplit(tolower(k),"")));t=unlist(strsplit(t,""));l=length(t);c=length(k);r=ceiling(l/c);t=c(t,rep("",c*r-l));cat(matrix(t,r,c)[order(rank(k)),])}

And ungolfed version, which shows how the function takes the data.

# test data
key = "aBeCd"
test = "ABCDEabcdeABCDEabcdeABC!"

# t is the test phrase, k is the key
cipher=function(t,k){
    k=unique(unlist(strsplit(tolower(key),"")))
    t=unlist(strsplit(test,""))
    l=length(t)
    c=length(k)
    r=ceiling(l/c)
    t=c(t,rep("",c*r-l))
    cat(matrix(t,r,c)[order(rank(k)),])
}

# Show that it works
cipher(test,key)
## A B D E C a b d e c A B D E C a b d e c A B !  C

The test cases provided by the OP seem incorrect. I intentionally chose a test case here that makes it more clear what is happening to the letters, and this seems correct.

\$\endgroup\$
  • 1
    \$\begingroup\$ You take in t and k as aeguments, then yiu use test and key \$\endgroup\$ – Bálint May 13 '16 at 8:50
  • \$\begingroup\$ Yes, that is how my example works. \$\endgroup\$ – Slow loris May 13 '16 at 13:27
  • 2
    \$\begingroup\$ In the main code, you still reference test and key \$\endgroup\$ – Bálint May 13 '16 at 13:37
0
\$\begingroup\$

Q, 52 Bytes

f:{n:#u::?_x;,/+(+(0N;n)#(n*-_-(#y)%n)#y,n#" ")@<u}

NOTE.- defined as function named f to facilitate tests. As an anonymous function we delete chars f: (50 Bytes)

Test

Interpreter (evaluation but unrestricted) downloadable by not fee at kc.com (windows/linux/mac versions)

f["CBABD"]"Duplicates are ignored."     /"puDlacit sea eriongr.de"
f["bDaEc"]"Key can be in multicase!"    /"yKce  aenbn mi tucliea s!"

Explanation

n:#u:?_x u is unique chars in lowercase key, and n its length

(n*-_-(#y)%n)#y,n#" " appends blanks to accomplish 'space surplus' rule.

% is division -_- implements ceil as negate floor negate, so (n*-_-(#y)%n) is the length required by space surplus. y,n#" " append n blank spaces to end of text, and then take length of that extended text

(0N;n)#.. takes items of sequence .. to fill a matrix of n columns by row

+(..) flip that matrix (traspose) to work by rows

@<u selects row indexes by ascending index order of u

,/(..) concatenates the resulting matrix to obtain a text
\$\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.