Avatar of davearonson

davearonson's solution

to Rail Fence Cipher in the Elixir Track

Published at Jul 13 2018 · 1 comment
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

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.

Running tests

Execute the tests with:

$ elixir rail_fence_cipher_test.exs

Pending tests

In the test suites, all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by commenting out the relevant @tag :pending with a # symbol.

For example:

# @tag :pending
test "shouting" do
  assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end

Or, you can enable all the tests by commenting out the ExUnit.configure line in the test suite.

# ExUnit.configure exclude: :pending, trace: true

For more detailed information about the Elixir track, please see the help page.

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.exs

if !System.get_env("EXERCISM_TEST_EXAMPLES") do
  Code.load_file("rail_fence_cipher.exs", __DIR__)
end

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)

defmodule RailFenceCipherTest do
  use ExUnit.Case

  # @tag :pending
  test "encode with ending at the first rail" do
    assert RailFenceCipher.encode("XOXOXOXOXOXOXOXOXO", 2) == "XXXXXXXXXOOOOOOOOO"
  end

  @tag :pending
  test "encode with ending in the middle" do
    msg = "WEAREDISCOVEREDFLEEATONCE"
    assert RailFenceCipher.encode(msg, 3) == "WECRLTEERDSOEEFEAOCAIVDEN"
  end

  @tag :pending
  test "encode empty string" do
    assert RailFenceCipher.encode("", 4) == ""
  end

  @tag :pending
  test "encode a more diverse text" do
    msg = "The quick brown fox jumps over the lazy dog."
    cipher = "Tioxs aghucrwo p rtlzo.eqkbnfjmoeh yd   uve "
    assert RailFenceCipher.encode(msg, 4) == cipher
  end

  @tag :pending
  test "encode with one rail" do
    msg = "One rail, only one rail"
    assert RailFenceCipher.encode(msg, 1) == msg
  end

  @tag :pending
  test "encode letters of less than rails" do
    msg = "More rails than letters"
    assert RailFenceCipher.encode(msg, 24) == msg
  end

  @tag :pending
  test "decode full zigzag cipher" do
    cipher = "TEITELHDVLSNHDTIEIIEA"
    assert RailFenceCipher.decode(cipher, 3) == "THEDEVILISINTHEDETAIL"
  end

  @tag :pending
  test "decode with ending in the middle" do
    cipher = "EIEXMSMESAORIWSCE"
    assert RailFenceCipher.decode(cipher, 5) == "EXERCISMISAWESOME"
  end

  @tag :pending
  test "decode empty string" do
    assert RailFenceCipher.decode("", 4) == ""
  end

  @tag :pending
  test "decode with one rail" do
    assert RailFenceCipher.decode("ABCDEFGHIJKLMNOP", 1) == "ABCDEFGHIJKLMNOP"
  end

  @tag :pending
  test "decode letters of less than rails" do
    assert RailFenceCipher.decode("More rails than letters", 24) == "More rails than letters"
  end

  @tag :pending
  test "decode a more diverse text" do
    msg = "The quick brown fox jumps over the lazy dog."
    cipher = RailFenceCipher.encode(msg, 4)
    assert RailFenceCipher.decode(cipher, 4) == msg
  end
end
defmodule RailFenceCipher do
  @doc """
  Encode a given plaintext to the corresponding rail fence ciphertext
  """
  @spec encode(String.t, pos_integer) :: String.t
  def encode(str, rails) do
    make_cycle(rails)
    |> Enum.zip(String.graphemes(str))
    |> encode_rails(%{})
    |> Enum.join
  end

  defp make_cycle(rails) do
    count_up_and_down(rails) |> Stream.cycle
  end

  defp count_up_and_down(n) when n < 3, do: (1..n)
  defp count_up_and_down(n), do: Enum.concat(1..n, (n-1)..2)

  defp encode_rails([{rail,char}|more], acc) do
    encode_rails(more, Map.put(acc, rail, [char|Map.get(acc, rail, [])]))
  end

  defp encode_rails([], acc) do
    acc
    |> Map.keys
    |> Enum.sort
    |> Enum.map(&(acc[&1] |> Enum.reverse |> Enum.join))
  end


  @accumulator_key "result"

  @doc """
  Decode a given rail fence ciphertext to the corresponding plaintext
  """
  @spec decode(String.t, pos_integer) :: String.t
  def decode(str, 1    ), do: str
  def decode(str, rails)  do
    rail_map = split_rails(str, rails) |> Map.put(@accumulator_key, [])
    make_cycle(rails)
    |> Enum.take(String.length(str))
    |> Enum.reduce(rail_map, &get_char_from_rail/2)
    |> Map.get(@accumulator_key)
    |> Enum.join
    |> String.reverse
  end

  defp split_rails(str, num_rails) do
    cycle_size = num_rails * 2 - 2
    str_len = String.length(str)
    info = %{ cycle_size: cycle_size,
              num_cycles: div(str_len, cycle_size),
              left_over: rem(str_len, cycle_size)}
    do_split_rails(String.graphemes(str), info, 1, %{})
  end

  defp do_split_rails([], _, _, acc), do: acc

  defp do_split_rails(chars, info, rail_num, acc)  do
    rail_len = calc_rail_length(rail_num, info)
    do_split_rails(chars |> Enum.drop(rail_len), info, rail_num + 1, 
                   Map.put(acc, rail_num, chars |> Enum.take(rail_len)))
  end

  defp calc_rail_length(rail_num, info) do
    length_from_full_cycles(rail_num, info[:num_cycles]) +
    length_from_leftovers(rail_num, info[:left_over], info[:cycle_size])
  end

  defp length_from_full_cycles(1, num_cycles), do: num_cycles
  # last rail (if there are more than one)
  # will TRY to take double portion, but only single is left
  defp length_from_full_cycles(_, num_cycles), do: num_cycles * 2

  defp length_from_leftovers(rail_num, left_over, _)
    when left_over < rail_num, do: 0

  defp length_from_leftovers(rail_num, left_over, cycle_size)
    when left_over < cycle_size - rail_num, do: 1

  defp length_from_leftovers(_, _, _), do: 2

  # bit of a kluge, keeping the accumulator in the same map as the data,
  # but we only get to pass *one* accumulator and i haven't yet
  # figured out a better way to consume the chars in order,
  # than keeping the "rails" in a map and removing them as we go.
  defp get_char_from_rail(rail_num, rail_map) do
    [char|rest] = rail_map[rail_num]
    %{ rail_map | @accumulator_key => [char|rail_map[@accumulator_key]] }
    |> Map.put(rail_num, rest)
  end

end

Community comments

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

got around to making it more elixirish, with fewer ifs, less imperative-ness, etc. still not too happy with the kluge of keeping the cleartext string being built, in the rail map, but . . . .

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?