# 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 . .
``````

``````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
``````

## 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(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;
}
}``````