Avatar of EricRicketts

EricRicketts's solution

to Rail Fence Cipher in the Ruby Track

Published at Oct 19 2019 · 0 comments
Instructions
Test suite
Solution

Implement encoding and decoding for the rail fence cipher.

The Rail Fence cipher is a form of transposition cipher that gets its name from the way in which it's encoded. It was already used by the ancient Greeks.

In the Rail Fence cipher, the message is written downwards on successive "rails" of an imaginary fence, then moving up when we get to the bottom (like a zig-zag). Finally the message is then read off in rows.

For example, using three "rails" and the message "WE ARE DISCOVERED FLEE AT ONCE", the cipherer writes out:

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .

Then reads off:

WECRLTEERDSOEEFEAOCAIVDEN

To decrypt a message you take the zig-zag shape and fill the ciphertext along the rows.

? . . . ? . . . ? . . . ? . . . ? . . . ? . . . ?
. ? . ? . ? . ? . ? . ? . ? . ? . ? . ? . ? . ? .
. . ? . . . ? . . . ? . . . ? . . . ? . . . ? . .

The first row has seven spots that can be filled with "WECRLTE".

W . . . E . . . C . . . R . . . L . . . T . . . E
. ? . ? . ? . ? . ? . ? . ? . ? . ? . ? . ? . ? .
. . ? . . . ? . . . ? . . . ? . . . ? . . . ? . .

Now the 2nd row takes "ERDSOEEFEAOC".

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . ? . . . ? . . . ? . . . ? . . . ? . . . ? . .

Leaving "AIVDEN" for the last row.

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .

If you now read along the zig-zag shape you can read the original message.


For installation and learning resources, refer to the Ruby resources page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

gem install minitest

If you would like color output, you can require 'minitest/pride' in the test file, or note the alternative instruction, below, for running the test file.

Run the tests from the exercise directory using the following command:

ruby rail_fence_cipher_test.rb

To include color from the command line:

ruby -r minitest/pride rail_fence_cipher_test.rb

Source

Wikipedia https://en.wikipedia.org/wiki/Transposition_cipher#Rail_Fence_cipher

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

rail_fence_cipher_test.rb

require 'minitest/autorun'
require_relative 'rail_fence_cipher'

class RailFenceCipherTest < Minitest::Test
  def test_encode_with_empty_string
    assert_equal '', RailFenceCipher.encode('', 4)
  end

  def test_encode_with_one_rail
    skip
    assert_equal 'One rail, only one rail',
                 RailFenceCipher.encode('One rail, only one rail', 1)
  end

  def test_encode_with_two_rails
    skip
    assert_equal 'XXXXXXXXXOOOOOOOOO',
                 RailFenceCipher.encode('XOXOXOXOXOXOXOXOXO', 2)
  end

  def test_encode_with_three_rails
    skip
    assert_equal 'WECRLTEERDSOEEFEAOCAIVDEN',
                 RailFenceCipher.encode('WEAREDISCOVEREDFLEEATONCE', 3)
  end

  def test_encode_with_ending_in_the_middle
    skip
    assert_equal 'ESXIEECSR', RailFenceCipher.encode('EXERCISES', 4)
  end

  def test_encode_with_less_letters_than_rails
    skip
    assert_equal 'More rails than letters',
                 RailFenceCipher.encode('More rails than letters', 24)
  end

  def test_decode_with_empty_string
    skip
    assert_equal '', RailFenceCipher.decode('', 4)
  end

  def test_decode_with_one_rail
    skip
    assert_equal 'ABCDEFGHIJKLMNOP',
                 RailFenceCipher.decode('ABCDEFGHIJKLMNOP', 1)
  end

  def test_decode_with_two_rails
    skip
    assert_equal 'XOXOXOXOXOXOXOXOXO',
                 RailFenceCipher.decode('XXXXXXXXXOOOOOOOOO', 2)
  end

  def test_decode_with_three_rails
    skip
    assert_equal 'THEDEVILISINTHEDETAILS',
                 RailFenceCipher.decode('TEITELHDVLSNHDTISEIIEA', 3)
  end
end
class RailFenceCipher

  def self.decode(str, num_rails)
    arr = Array.new(num_rails) { Array.new }
    char_ary = str.chars

    idx_array = gen_index_array(num_rails, char_ary)

    grouped_indices = idx_array.group_by(&:itself).values.flatten
    indices_and_chars = grouped_indices.zip(char_ary)

    indices_and_chars.each { |idx, char| arr[idx].push(char) }
    idx_array.inject('') { |str, idx| str << arr[idx].shift }
  end

  def self.encode(str, num_rails)
    arr = Array.new(num_rails) { Array.new }

    indices_and_chars = gen_index_array(num_rails, str.chars).zip(str.chars)

    indices_and_chars.each { |idx, char| arr[idx].push(char) }
    arr.flatten.join
  end

  class << self
    private

    # method generates a pattern and expands the pattern to match the number
    # of characters in the provided string.  Example, a fence with three rails
    # would have the pattern [0, 1, 2, 1] and would be repeated to match the
    # size of the provided string.
    def gen_index_array(num_rails, chars)
      idx_pattern = ((0..num_rails-1).to_a + (-(num_rails-2)...0).map(&:-@))

      num_chars = chars.length
      pattern_length = idx_pattern.length

      idx_pattern * (num_chars / pattern_length) + \
        idx_pattern.slice(0, num_chars % pattern_length)
    end
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.

EricRicketts's Reflection

It took a while for me to figure out a somewhat concise algorithm to solve this problem. To begin with, if a fence had three rails, then each rail had a series of letters according to some pattern. My decision was to use an array of arrays to solve this problem with each subarray holding the appropriate letters on the corresponding fence.

For the encode, I had to figure out how to get each letter into the correct subarray. Once I did this then all I needed to do was to flatten and join the subarrays to get the encoded word.

I noted that if each fence represented a subarray then a pattern emerged of which subarray got which letter. So if a fence had three rails (subarrays) then the pattern would be 0 1 2 1 0 1 2 1 0 1 2 1 0 ... where the numbers 0, 1, and 2 would represent the index for each subarray.

Once I figured out how to generate this pattern, which could easily adjust to a different number of fences, all I had to do was to repeat this pattern enough to match the size of the string to encode. It then became a simple process of populating the array of arrays using the array of characters and the encoding pattern of indices.

On the decode side, most of the algorithm was the same as the encoding but with one important difference, I had to figure how how big each subarray had to be. Generating the pattern and repeating it to match the size of the string, like I did with the encode, gave me all of the information I needed. Once I had the properly sized array of indices, I grouped them to get the size of each subarray. Now the subarrays and chars could easily be matched up by a #zip operation.