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.

About these ads

Pages: 1 2

9 Responses to “Rail-Fence Cipher”

  1. FalconNL said

    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..]
    
  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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 635 other followers

%d bloggers like this: