Avatar of glennj

glennj's solution

to Rail Fence Cipher in the Java Track

Published at Jan 09 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.

Running the tests

You can run all the tests for an exercise by entering

$ gradle test

in your terminal.

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.

RailFenceCipherTest.java

import org.junit.Assert;
import org.junit.Ignore;
import org.junit.Test;

public class RailFenceCipherTest {

    private RailFenceCipher railFenceCipher;

    @Test
    public void encodeWithTwoRails() {
        railFenceCipher = new RailFenceCipher(2);
        Assert.assertEquals("XXXXXXXXXOOOOOOOOO",
            railFenceCipher.getEncryptedData("XOXOXOXOXOXOXOXOXO"));
    }

    @Ignore("Remove to run test")
    @Test
    public void encodeWithThreeRails() {
        railFenceCipher = new RailFenceCipher(3);
        Assert.assertEquals("WECRLTEERDSOEEFEAOCAIVDEN",
            railFenceCipher.getEncryptedData("WEAREDISCOVEREDFLEEATONCE"));
    }

    @Ignore("Remove to run test")
    @Test
    public void encodeWithEndingInTheMiddle() {
        railFenceCipher = new RailFenceCipher(4);
        Assert.assertEquals("ESXIEECSR",
            railFenceCipher.getEncryptedData("EXERCISES"));
    }

    @Ignore("Remove to run test")
    @Test
    public void decodeWithThreeRails() {
        railFenceCipher = new RailFenceCipher(3);
        Assert.assertEquals("THEDEVILISINTHEDETAILS",
            railFenceCipher.getDecryptedData("TEITELHDVLSNHDTISEIIEA"));
    }

    @Ignore("Remove to run test")
    @Test
    public void decodeWithFiveRails() {
        railFenceCipher = new RailFenceCipher(5);
        Assert.assertEquals("EXERCISMISAWESOME",
            railFenceCipher.getDecryptedData("EIEXMSMESAORIWSCE"));
    }

    @Ignore("Remove to run test")
    @Test
    public void decodeWithSixRails() {
        railFenceCipher = new RailFenceCipher(6);
        Assert.assertEquals("112358132134558914423337761098715972584418167651094617711286",
            railFenceCipher.getDecryptedData("133714114238148966225439541018335470986172518171757571896261"));
    }
}
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class RailFenceCipher {

    /** A RailWalker knows how to walk the rails, reversing direction
     *  when it hits one of the the outer rails.
     */
    private static class RailWalker {
        private int rail = -1;
        private int inc = 1;
        private int numRails;
        RailWalker(int rails) { numRails = rails; }
        int next() {
            if ((rail == 0 && inc < 0) || (rail == numRails - 1 && inc > 0))
                inc *= -1;
            rail += inc;
            return rail;
        }
    }

    private int numRails;

    RailFenceCipher(int rails) {
        numRails = rails;
    }

    /** Place each character of the plaintext on the "next" rail,
     *  then concatenate the rail text.
     */
    String getEncryptedData(String plaintext) {
        if (numRails == 1 || numRails > plaintext.length())
            return plaintext;

        List<StringBuilder> rails = IntStream
                .range(0, numRails)
                .mapToObj(i -> new StringBuilder())
                .collect(Collectors.toList());

        RailWalker rw = new RailWalker(numRails);
        plaintext.chars().forEach(c -> rails.get(rw.next()).append((char) c));

        return rails.stream()
                .map(StringBuilder::toString)
                .collect(Collectors.joining());
    }

    /** Split the ciphertext into what would appear on the rails,
     *  then iteratively select the next character from each rail
     *  and join the characters to form the plain text.
     */
    String getDecryptedData(String ciphertext) {
        if (numRails == 1 || numRails > ciphertext.length())
            return ciphertext;

        List<StringBuilder> rails = partition(ciphertext);
        RailWalker rw = new RailWalker(numRails);

        return IntStream
                .rangeClosed(1, ciphertext.length())
                .mapToObj(i -> {
                    StringBuilder rail = rails.get(rw.next());
                    char c = rail.charAt(0);
                    rail.deleteCharAt(0);
                    return c;
                })
                .reduce(new StringBuilder(), StringBuilder::append, StringBuilder::append)
                .toString();
    }

    /** Split the ciphertext into rails.
     */
    private List<StringBuilder> partition(String ciphertext) {
        AtomicInteger i = new AtomicInteger(0);
        return partitionLengths(ciphertext)
                .stream()
                .map(len -> ciphertext.substring(i.get(), i.addAndGet(len)))
                .map(StringBuilder::new)
                .collect(Collectors.toList());
    }

    /** Determine how many characters should be present on each rail.
     */
    private List<Integer> partitionLengths(String ciphertext) {
        // each journey down and up the rails consumes 2 * (numRails - 1) characters
        int cycleLength = 2 * (numRails - 1);
        int baseRailLength = ciphertext.length() / cycleLength;
        int leftovers = ciphertext.length() % cycleLength;

        // the inner rails consume twice as much as the top & bottom rails
        List<Integer> lengths = IntStream
                .rangeClosed(1, numRails)
                .map(i -> baseRailLength * ((i == 1 || i == numRails) ? 1 : 2))
                .boxed()
                .collect(Collectors.toList());

        // handle the leftovers: add 1 to each rail starting from the top
        RailWalker rw = new RailWalker(numRails);
        IntStream.rangeClosed(1, leftovers)
                .forEach(i -> {
                    int railIdx = rw.next();
                    lengths.set(railIdx, 1 + lengths.get(railIdx));
                });

        return lengths;
    }
}

Community comments

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

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?