8
\$\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>

Improve this question
\$\endgroup\$
11
  • 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\$ Commented May 12, 2016 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\$ Commented May 12, 2016 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\$ Commented May 12, 2016 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\$ Commented May 13, 2016 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\$ Commented May 13, 2016 at 17:03

10 Answers 10

Reset to default
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
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ The way u, e, M, and & work is so impressive here \$\endgroup\$ Commented May 14, 2016 at 4:06
  • \$\begingroup\$ @David indeed! :-) \$\endgroup\$ Commented May 14, 2016 at 8:58
  • 1
    \$\begingroup\$ haha, "kune" - thats the currency we use in Croatia \$\endgroup\$ Commented Jan 10, 2017 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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Save 1 byte by abstracting len() to a 1-letter function \$\endgroup\$ Commented May 12, 2016 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\$ Commented May 12, 2016 at 20:10
  • \$\begingroup\$ ah, I forgot about the comma. Sorry \$\endgroup\$ Commented May 12, 2016 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...

Improve this answer
\$\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>

Improve this answer
\$\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))
Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Well, this wins for most calls to zip in one answer. \$\endgroup\$ Commented May 12, 2016 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.)

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Hello, and welcome to PPCG! Great first post! \$\endgroup\$ Commented May 13, 2016 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
Improve this answer
\$\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)*''}
Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You take in t and k as aeguments, then yiu use test and key \$\endgroup\$ Commented May 13, 2016 at 8:50
  • \$\begingroup\$ Yes, that is how my example works. \$\endgroup\$ Commented May 13, 2016 at 13:27
  • 2
    \$\begingroup\$ In the main code, you still reference test and key \$\endgroup\$ Commented May 13, 2016 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
Improve this answer
\$\endgroup\$