Rail-Fence Cipher

March 31, 2009

The obvious solution uses arithmetic to extract characters at the various positions of the text in the desired order. But the details are tricky and hard to get right. Matthias Felleisen, a Professor in the Computer Science department at Northeastern University in Boston and one of the authors of The Little Schemer proposes instead the following solution:

(define X '_) ; a unique tag for padding the data structure

Waves splits a text into pieces of length equal to the key; alternate pieces are reversed and have their first and last characters padded. For instance, (waves (string->list "PROGRAMMING PRAXIS") 4) evaluates to ((#\P #\R #\O #\G) (_ #\A #\R _) (#\M #\M #\I #\N) (_ #\space #\G _) (#\P #\R #\A #\X) (_ #\S #\I _)).

(define (waves str h)
  (define (down str)
    (if (>= h (length str))
        (list (fill h str))
        (cons (take h str) (up (drop h str)))))
  (define (up str)
    (if (>= (- h 2) (length str))
        (list (pad (fill (- h 2) str)))
        (cons (pad (take (- h 2) str)) (down (drop (- h 2) str)))))
  (define (pad str) (append (list X) (reverse str) (list X)))
  (define (fill h str) (append str (make-list (- h (length str)) X)))
  (down str))

Fence uses waves to produce a list of the positions from which the transposed characters will be taken. For instance, (fence (range (string-length "PROGRAMMING PRAXIS")) 4) produces the list (0 6 12 1 5 7 11 13 17 2 4 8 10 14 16 3 9 15).

Fence uses waves to perform the transposition:

(define (fence lox h)
  (define a (apply append (transpose (waves lox h))))
  (filter (lambda (e) (not (eq? X e))) a))

Encipherment is done by calling fence:

(define (encipher str h)
  (list->string (fence (string->list str) h)))

Decipherment is somewhat more difficult. Fence builds a list of the positions of the transposed characters; for our running example, e will be (0 6 12 1 5 7 11 13 17 2 4 8 10 14 16 3 9 15). Those positions are melded with the cipher-text in x, the position/character pairs are sorted into order in y, and the characters extracted in z:

(define (decipher str h)
  (define e (fence (range (string-length str)) h))
  (define x (map list e (string->list str)))
  (define y (sort (lambda (i j) (<= (car i) (car j))) x))
  (define z (map cadr y))
  (list->string z))

Felleisen's program is simple and clear, a fine example of beautiful code by a master of the craft. Running the rail-fence cipher looks like this:

> (encipher "PROGRAMMING PRAXIS" 4)
"PMPRAM RSORIGAIGNX"
> (decipher "PMPRAM RSORIGAIGNX" 4)
"PROGRAMMING PRAXIS"

We can test the functions using assert; remember that, with the assert macro, no news is good news:

(do ((i 2 (+ i 1))) ((< 18 i))
  (assert (decipher (encipher "PROGRAMMING PRAXIS" i) i)
          "PROGRAMMING PRAXIS"))

We use take, drop, range, filter, make-list, sort and assert from the Standard Prelude. We also use the utility function (transpose m), which transposes the rows and columns of a list of lists:

(define (transpose m)
  (if (null? (car m)) '()
    (cons (map car m) (transpose (map cdr m)))))

You can run this program at http://programmingpraxis.codepad.org/9abH1QKb.

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 611 other followers