10
\$\begingroup\$

Write two programs:
- One which reads a string and a key and encodes the string into a rail-fence cipher using that key. - Similarly, write a program for the reverse function: deciphering a rail fence using a key.

For those who don't know what rail fence cipher is, it is basically a method of writing plain text in a way it creates linear pattern in a spiral way. Example - when "FOOBARBAZQUX" rail-fenced using key of 3.

F . . . A . . . Z . . . .
  O . B . R . A . Q . X
    O . . . B . . . U

Reading the above spiral line-by-line, the cipher text becomes "FAZOBRAQXOBU".

Read more at - Rail fence cipher - Wikipedia.

Code in any language is welcome.

Shortest answer in bytes wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ What is the winning criterion ? \$\endgroup\$ – Paul R Jan 25 '13 at 10:37
9
\$\begingroup\$

Python 133 bytes

def cipher(t,r):
 m=r*2-2;o='';j=o.join
 for i in range(r):s=t[i::m];o+=i%~-r and j(map(j,zip(s,list(t[m-i::m])+[''])))or s
 return o

Sample usage:

>>> print cipher('FOOBARBAZQUX', 3)
FAZOBRAQXOBU

>>> print cipher('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 4)
AGMSYBFHLNRTXZCEIKOQUWDJPV

>>> print cipher('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 5)
AIQYBHJPRXZCGKOSWDFLNTVEMU

>>> print cipher('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 6)
AKUBJLTVCIMSWDHNRXEGOQYFPZ

Note: the results from even rail counts are different than for the code you provided, but they seem to be correct. For example, 6 rails:

A         K         U
 B       J L       T V
  C     I   M     S   W
   D   H     N   R     X
    E G       O Q       Y
     F         P         Z

corresponds to AKUBJLTVCIMSWDHNRXEGOQYFPZ, and not AKUTBLVJICMSWXRDNHQYEOGZFP as your code produces.

The basic idea is that each rail can be found directly by taking string slices [i::m], where i is the rail number (0-indexed), and m is (num_rails - 1)*2. The inner rails additionally need to be interwoven with [m-i::m], achieved by zipping and joining the two sets of characters. Because the second of these can potentially be one character shorter, it is padded with a character assumed not to appear anywhere (_), and then that character is stripped off if necessary it is converted to a list, and padded with an empty string.


A slightly more human readable form:

def cipher(text, rails):
  m = (rails - 1) * 2
  out = ''
  for i in range(rails):
    if i % (rails - 1) == 0:
      # outer rail
      out += text[i::m]
    else:
      # inner rail
      char_pairs = zip(text[i::m], list(text[m-i::m]) + [''])
      out += ''.join(map(''.join, char_pairs))
  return out
\$\endgroup\$
  • \$\begingroup\$ A deciphering function is also needed. \$\endgroup\$ – ShuklaSannidhya Jan 17 '14 at 16:47
  • \$\begingroup\$ @ShuklaSannidhya Then why did you accept an incomplete answer? \$\endgroup\$ – Jo King Jul 18 '18 at 6:37
  • 3
    \$\begingroup\$ @JoKing for clarity, the "two programs" requirement was added one year after I posted my solution. \$\endgroup\$ – primo Aug 9 '18 at 9:38
2
\$\begingroup\$

APL 52 41

i←⍞⋄n←⍎⍞⋄(,((⍴i)⍴(⌽⍳n),1↓¯1↓⍳n)⊖(n,⍴i)⍴(n×⍴i)↑i)~' '

If the input text string i and the key number n are preinitialised the solution can be shortened by 9 characters. Running the solution against the examples given by primo gives identical answers:

FOOBARBAZQUX
3
FAZOBRAQXOBU

ABCDEFGHIJKLMNOPQRSTUVWXYZ
4
AGMSYBFHLNRTXZCEIKOQUWDJPV

ABCDEFGHIJKLMNOPQRSTUVWXYZ
5
AIQYBHJPRXZCGKOSWDFLNTVEMU

ABCDEFGHIJKLMNOPQRSTUVWXYZ
6
AKUBJLTVCIMSWDHNRXEGOQYFPZ

On further reflection there appears to be a shorter index based solution:

i[⍋+\1,(y-1)⍴((n←⍎⍞)-1)/1 ¯1×1 ¯1+y←⍴i←⍞]
\$\endgroup\$
  • \$\begingroup\$ A deciphering function is also needed. \$\endgroup\$ – ShuklaSannidhya Jan 17 '14 at 17:08
1
\$\begingroup\$

Python 2, 124 + 179 = 303 bytes

Encode:

lambda t,k:''.join(t[i+j]for r in R(k)for i in R(k-1,len(t)+k,2*k-2)for j in[r-k+1,k+~r][:1+(k-1>r>0)]if i+j<len(t))
R=range

Try it online!

Decode:

lambda t,k:''.join(t[dict((b,a)for a,b in enumerate(i+j for r in R(k)for i in R(k-1,len(t)+k,2*k-2)for j in[r-k+1,k+~r][:1+(k-1>r>0)]if i+j<len(t)))[m]]for m in R(len(t)))
R=range

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You also need a deciphering function \$\endgroup\$ – Jo King Jul 18 '18 at 6:36
  • \$\begingroup\$ @Jo King: I have belatedly added a deciphererer. \$\endgroup\$ – Chas Brown Jul 18 '18 at 7:52
0
\$\begingroup\$

MATL, 70 bytes (total)

f'(.{'iV'})(.{1,'2GqqV'})'5$h'$1'0'$2'0K$hYX2Get2LZ)P2LZ(!tg)i?&S]1Gw)

Try it on MATL Online
Try multiple test cases

Takes a flag as third input, F to encipher the string, T to decipher it (thanks to Kevin Cruijssen for that idea).

This started as a Julia answer until I realized strict typing got in the way too much, especially for decipherment. Here's the Julia code I had for encipherment (backported to v0.6 for TIO):

Julia 0.6, 191 bytes

!M=(M[2:2:end,:]=flipdim(M[2:2:end,:],2);M)
s|n=replace(String((!permutedims(reshape([rpad(replace(s,Regex("(.{$n})(.{1,$(n-2)})"),s"\1ø\2ø"),length(s)*n,'ø')...],n,:),(2,1)))[:]),"ø","")

Try it online!

Explanation:

The rail fence operation

F . . . A . . . Z . . . .
  O . B . R . A . Q . X
    O . . . B . . . U

can be seen as reading r = 3 characters of input, then reading r-2 characters and prefixing and suffixing that with dummy values (nulls), then reading r characters again, etc., creating a new column every time:

F.A.Z.
OBRAQX
O.B.U.

then reversing every second column (since the zag part of zigzag goes up instead of down, which makes a difference when r > 3), then reading this matrix along the rows, and removing the dummy characters.

Decipherment didn't seem to have any obvious patterns like this, but when searching around about this I came across this post, which told me that (a) this was a well known and (possibly?) published algorithm for rail ciphers, and (b) decipherment was a simple reuse of the same method, giving it the indices of the string and getting the indices of those indices after encipherment, and reading the ciphertext at those places.

Since decipherment needs to do things by working on indices, this code does encipherment also by sorting the indices of the string, and then in this case just indexing at those rearranged indices.

              % implicit first input, say 'FOOBARBAZQUX'
f             % indices of input string (i.e. range 1 to length(input)
'(.{'iV'})(.{1,'2GqqV'})'5$h
              % Take implicit second input, say r = 3
              % Create regular expression '(.{$r})(.{1,$(r-2)})'
              % matches r characters, then 1 to r-2 characters
              %  (to allow for < r-2 characters at end of string)
'$1'0'$2'0K$h % Create replacement expression, '$1\0$2\0'
YX            % Do the regex replacement
2Ge           % reshape the result to have r rows (padding 0s if necessary)
t2LZ)         % extract out the even columns of that
P             % flip them upside down
2LZ(          % assign them back into the matrix
!             % transpose
tg)           % index into the non-zero places (i.e. remove dummy 0s)
i?            % read third input, check if it's true or false
&S]           % if it's true, decipherment needed, so get the indices of the 
              %  rearranged indices
1Gw)          % index the input string at those positions
\$\endgroup\$
0
\$\begingroup\$
int r=depth,len=plainText.length();
int c=len/depth;
char mat[][]=new char[r][c];
int k=0;
String cipherText="";
for(int i=0;i< c;i++)
{
 for(int j=0;j< r;j++)
 {
  if(k!=len)
   mat[j][i]=plainText.charAt(k++);
  else
   mat[j][i]='X';
 }
}
for(int i=0;i< r;i++)
{
 for(int j=0;j< c;j++)
 {
  cipherText+=mat[i][j];
 }
}
return cipherText;
}

I want be explain in this code.

\$\endgroup\$
  • \$\begingroup\$ Since this is code-golf, you should make an attempt at shortening your code. Also, you should add the language and byte count to this submission \$\endgroup\$ – Jo King Nov 6 '18 at 6:40
  • \$\begingroup\$ In addition to what Jo King said, you might consider using an online service like TIO so other people can easily test your code out. \$\endgroup\$ – Οurous Nov 6 '18 at 7:04
0
\$\begingroup\$

Java 10, 459 451 445 439 327 bytes

(s,k,M)->{int l=s.length,i=-1,f=0,r=0,c=0;var a=new char[k][l];for(;++i<l;a[r][c++]=M?s[i]:1,r+=f>0?1:-1)f=r<1?M?f^1:1:r>k-2?M?f^1:0:f;for(c=i=0;i<k*l;i++)if(a[i/l][i%l]>0)if(M)System.out.print(a[i/l][i%l]);else a[i/l][i%l]=s[c++];if(!M)for(r=c=i=0;i++<l;f=r<1?1:r>k-2?0:f,r+=f>0?1:-1)if(a[r][c]>1)System.out.print(a[r][c++]);}

-12 bytes thanks to @ceilingcat.
-112 bytes combining the two functions with an additional mode-flag as input.

The function takes a third input M. If this is true it will encipher, and if it is false it will decipher.

Try it online.

Explanation:

(s,k,M)->{              // Method with character-array, integer, and boolean parameters
                        // and no return-type
  int l=s.length,       //  Length of the input char-array
      i=-1,             //  Index-integer, starting at -1
      f=0,              //  Flag-integer, starting at 0
      r=0,c=0;          //  Row and column integers, starting both at 0
  var a=new char[k][l]; //  Create a character-matrix of size `k` by `l`
  for(;++i<l            //  Loop `i` in the range (-1, `l`):
      ;                 //    After every iteration:
       a[r][c++]=       //     Set the matrix-cell at `r,c` to:
         M?s[i++]       //      If we're enciphering: set it to the current character
         :1,            //      If we're deciphering: set it to 1 instead
       r+=f>0?          //     If the flag is 1:
           1            //      Go one row down
          :             //     Else (flag is 0):
           -1)          //      Go one row up
    f=r<1?              //   If we're at the first row:
       M?f^1            //    If we're enciphering: toggle the flag (0→1; 1→0)
       :1               //    If we're deciphering: set the flag to 1
      :r>k-2?           //   Else-if we're at the last row:
       M?f^1            //    If we're enciphering: toggle the flag (0→1; 1→0)
       :0               //    If we're deciphering: set the flag to 0
      :                 //   Else (neither first nor last row):
       f;               //    Leave the flag unchanged regardless of the mode
  for(c=i=0;            //  Reset `c` to 0
            i<k*l;i++)  //  Loop `i` in the range [0, `k*l`):
    if(a[i/l][i%l]>0)   //   If the current matrix-cell is filled with a character:
      if(M)             //    If we're enciphering:
        System.out.print(a[i/l][i%l]);}
                        //     Print this character
      else              //    Else (we're deciphering):
        a[r][i]=s[c++]; //     Fill this cell with the current character
  if(!M)                //  If we're deciphering:
    for(r=c=i=0;        //   Reset `r` and `c` both to 0
        i++<l           //   Loop `i` in the range [0, `l`)
        ;               //     After every iteration:
         f=r<1?         //      If we are at the first row:
            1           //       Set the flag to 1
           :r>k-2?      //      Else-if we are at the last row:
            0           //       Set the flag to 0
           :            //      Else:
            f,          //       Leave the flag the same
         r+=f>0?        //      If the flag is now 1:
             1          //       Go one row up
            :           //      Else (flag is 0):
             -1)        //       Go one row down
      if(a[r][c]>1)     //    If the current matrix-cell is filled with a character:
        System.out.print(a[r][c++]);}
                        //     Print this character
\$\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.