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.
Execute the tests with:
$ elixir rail_fence_cipher_test.exs
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.
Wikipedia https://en.wikipedia.org/wiki/Transposition_cipher#Rail_Fence_cipher
It's possible to submit an incomplete solution so you can see how others have completed the exercise.
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
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.
Level up your programming skills with 3,122 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors. Exercism is 100% free forever.
Sign up Learn More
Community comments
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 . . . .