March 31, 2009 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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..]By FalconNL on March 31, 2009 at 3:06 PM
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)))
By matthias on April 1, 2009 at 2:31 PM
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)))))
By matthias on April 1, 2009 at 3:37 PM
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 ksBy FalconNL on April 2, 2009 at 9:40 AM
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
By Luis Sergio Oliveira on May 17, 2009 at 5:03 PM
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.”
By programmingpraxis on May 22, 2009 at 4:50 AM
[…] up we have zipSort, which I also used in the Rail-Fence Cipher […]
By Programming Praxis – Double Transposition Cipher « Bonsai Code on May 30, 2009 at 3:49 PM
Common Lisp solution at http://paste.lisp.org/display/83135.
By Jan Van lent on July 6, 2009 at 11:08 PM
https://github.com/ftt/programming-praxis/blob/master/20090331-rail-fence-cipher/rail-fence-cipher.py
By ftt on February 27, 2014 at 10:46 PM