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.
Programming Praxis 
In Haskell:
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..]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)))
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)))))
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 ksHi,
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
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.”
[…] up we have zipSort, which I also used in the Rail-Fence Cipher […]
Common Lisp solution at http://paste.lisp.org/display/83135.
https://github.com/ftt/programming-praxis/blob/master/20090331-rail-fence-cipher/rail-fence-cipher.py