Skip to content

Rail Fence Cipher

Encode a message by writing it in a zig-zag across a number of rails and reading the rails off in turn, and decode it back.

Adapted from Exercism’s problem specification (MIT). Listed under Encoding & Ciphers.

// FILE: rail_fence_cipher.nomi
//# The rail fence cipher: the message is written in a zig-zag across the
//# rails, then read off one rail after another.

/// `message` read off the rails, top rail first.
pub fn encode(message: String, rails: Int) -> String
    message
    |> Iter.zip(zigzag(rails))
    |> Iter.sort_by(.second)
    |> Iter.map(.first)
    |> String.join()
end

/// The message whose encoding on `rails` rails is `ciphertext`.
pub fn decode(ciphertext: String, rails: Int) -> String
    positions =
        0..String.length(ciphertext)
        |> Iter.zip(zigzag(rails))
        |> Iter.sort_by(.second)
        |> Iter.map(.first)

    positions
    |> Iter.zip(ciphertext)
    |> Iter.sort_by(.first)
    |> Iter.map(.second)
    |> String.join()
end

/// The rail each position of the message is written on, without end: down
/// from the top rail to the bottom, then back up.
fn zigzag(rails: Int) -> Iter<Int>
    up = Iter.reverse(1..rails - 1)

    0..rails
    |> Iter.concat(up)
    |> Iter.cycle()
end

// FILE: rail_fence_cipher_test.nomi
import rail_fence_cipher

test "encode"
    [
        ("encode with two rails", "XOXOXOXOXOXOXOXOXO", 2, "XXXXXXXXXOOOOOOOOO"),
        ("encode with three rails", "WEAREDISCOVEREDFLEEATONCE", 3, "WECRLTEERDSOEEFEAOCAIVDEN"),
        ("encode with ending in the middle", "EXERCISES", 4, "ESXIEECSR"),
    ]
    |> subtests (description, message, rails, expected), description
        assert rail_fence_cipher.encode(message, rails) == expected
    end
end

test "decode"
    [
        ("decode with three rails", "TEITELHDVLSNHDTISEIIEA", 3, "THEDEVILISINTHEDETAILS"),
        ("decode with five rails",  "EIEXMSMESAORIWSCE",      5, "EXERCISMISAWESOME"),
        (
            "decode with six rails",
            "133714114238148966225439541018335470986172518171757571896261",
            6,
            "112358132134558914423337761098715972584418167651094617711286",
        ),
    ]
    |> subtests (description, ciphertext, rails, expected), description
        assert rail_fence_cipher.decode(ciphertext, rails) == expected
    end
end

// Not a canonical case: one rail leaves the message as it is.
test "one rail"
    assert rail_fence_cipher.encode("WEARE", 1) == "WEARE"
    assert rail_fence_cipher.decode("WEARE", 1) == "WEARE"
end
  • No fence is built. zigzag(rails) is the endless sequence of rails the letters fall on, 0, 1, 2, 1, 0, 1, ...: the range down, the range back up from Iter.reverse, and Iter.cycle. Iter.zip with the message stops it at the message’s end.
  • encode pairs each letter with its rail and sorts by rail. Iter.sort_by is stable, so letters on one rail keep their order, which is the reading the cipher asks for.
  • decode runs the same sort on the positions 0..n instead of the letters. That answers which position of the message each letter of the ciphertext came from; pairing the positions with the ciphertext and sorting by position puts the letters back. Both directions share the one zig-zag, so neither has a rail-length calculation of its own.
  • The tuples are read with the .first and .second accessors (style §10), each a line or two below where Iter.zip builds them.
  • The encode and decode cases are one subtests table each. One rail, which leaves the message as it is, is a test of its own, marked as not canonical.