## Rail-Fence Cipher

### March 31, 2009

The rail-fence cipher is a transposition cipher that rearranges the characters of a clear-text to form the cipher-text. The clear-text is arranged in up-and-down waves like the tops of the pickets on a rail fence; the cipher key is the height of the fence. For instance, the encipherment of “PROGRAMMING PRAXIS” with a key of 4 is shown below, using an underscore to make the space character visible:

```P R O G R A M M I N G _ P R A X I S P           M           P            = P M P   R       A   M       _   R       S  = R A M _ R S     O   R       I   G       A   I    = O R I G A I       G           N           X      = G N X```

The cipher-text is read at the right of the pickets: “PMPRAM RSORIGAIGNX”.

Your task is to write functions that encipher and decipher texts using the rail-fence method. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

### 9 Responses to “Rail-Fence Cipher”

1. FalconNL said

```import Data.List

main = do print \$ rail 4 "PROGRAMMING PRAXIS"
print . derail 4 \$ rail 4 "PROGRAMMING PRAXIS"

rail :: Int -> String -> String
rail n s = map (s !!) \$ waves n s

derail :: Int -> String -> String
derail n s = map snd . sort \$ zip (waves n s) s

waves :: Int -> String -> [Int]
waves n = map snd . sort . zip (cycle \$ [1..n] ++ [n-1,n-2..2]) . zipWith const [0..]
```
2. matthias said

FalconNL, your design turns the solution into
“Fortran”, using indexes into lists (of chars)
where a generative-recursion design (for freshmen)
exposes the waves as they come about.

Then again, you demonstrate how temporary
laziness in ‘waves’ is a useful tool. Let me show
you how temporary, invisible assignments accomplish the exact same purpose.

;; [Listof X] Nat -> [Listof X]
;; 1 5 9
;; 1 2 3 4 5 6 7 8 9 10 11 ==> 2 4 6 8 10 ==> 1 5 9 2 4 6 8 10 3 7 11
;; 3 7 11

(check-expect (fence ‘(1 2 3 4 5 6) 3) ‘(1 5 2 4 6 3))
(check-expect (fence ‘(1 2 3 4 5 6 7 8 9 10 11) 3) ‘(1 5 9 2 4 6 8 10 3 7 11))

(define (fence s n)
(define is (shared ((x (append (range 1 n) (range (- n 1) 2) x))) x))
(define wv (for/list ((c s)) (begin0 (list c (car is)) (set! is (cdr is)))))
(map first (sort2 wv)))

3. matthias said

Oops, fence is a two-liner in PLT Scheme, too:

(define (fence s n)
(define is (shared ((x (append (range 1 n) (range (- n 1) 2) x))) x))
(map first (sort2 (for/list ((c s) (i (in-list is))) (list c i)))))

4. FalconNL said

Updated version that I believe should run in O(n log n) for both rail and derail (rail was O(n^2) in the previous version):

```import Data.List
import GHC.Exts

main = do print \$ rail 4 "PROGRAMMING PRAXIS"
print . derail 4 \$ rail 4 "PROGRAMMING PRAXIS"

rail :: Int -> [a] -> [a]
rail n = zipSort (cycle \$ [1..n] ++ [n-1,n-2..2])

derail :: Ord a => Int -> [a] -> [a]
derail n s = zipSort (rail n \$ zipWith const [0..] s) s

zipSort :: Ord a => [a] -> [b] -> [b]
zipSort ks = map snd . sortWith fst . zip ks
```
5. Hi,

my solution in Common Lisp, including some tests is here: http://lisp.pastebin.com/f27e23d44.

Notice that I haven’t followed the algorithm proposed in your solution which is indeed very interesting…

Thanks for the problem,

Luis

6. programmingpraxis said

Posted on behalf of Matthias Felleisen:

“I have finally found some time to write up my version of the story which only starts with the post here as a way to explain the idea in a first-semester FP course — with design principles.

In contrast to the Haskell solution, mine is linear. If a linear purely FP solution exists, I’d like to know.”

7. […] up we have zipSort, which I also used in the Rail-Fence Cipher […]

8. Jan Van lent said

Common Lisp solution at http://paste.lisp.org/display/83135.