Square Code
One classic method for composing secret messages is called a square code. First, the input is normalized: the spaces and punctuation are removed from the English text, and the message is downcased. Then, the normalized characters are broken into rows. These rows can be regarded as forming a rectangle. For example, the sentence
If man was meant to stay on the ground, god would have given us roots.
is normalized to:
ifmanwasmeanttostayonthegroundgodwouldhavegivenusroots
The normalized string is 54 characters long, so it is written into a rectangle with 7 rows and 8 columns.
ifmanwas
meanttos
tayonthe
groundgo
dwouldha
vegivenu
sroots
Note that the last row is padded with spaces at the end to make it 8 characters long.
The coded message is obtained by reading down the columns going left to right. For example, the message above is coded as:
imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau
Given the length of the normalized text, the number of columns in the rectangle is computed by , i.e., is the smallest natural number greater than or equal to .
Racket
In Racket, implement a function (encode str)
that accepts a string and returns the encoded string as described above. Your file is to be called square-code.rkt
and must provide the function encode
. Hence, the head of your file should start with
#lang racket
(provide encode)
; your code here
Hint
To make the string downcased, you may use the function (string-downcase str)
. To remove spaces and punctuation, you may use the predicate (char-alphabetic? ch)
. To get the least integer above a real number , use the function (exact-ceiling x)
.
Examples
The following shows the behaviour of the encode
function.
> (encode "If man was meant to stay on the ground, god would have given us roots.")
"imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau "
> (encode "Have a nice day!")
"hae and via ecy"
Solution
#lang racket
(provide encode)
(define (normalize str)
(filter char-alphabetic? (string->list (string-downcase str))))
(define (get-num-cols n)
(exact-ceiling (sqrt n)))
(define (make-rows lst n)
(let ([len (length lst)])
(cond
([null? lst] '())
([< len n] (list (append lst (make-list (- n len) #\space))))
(else (cons (take lst n) (make-rows (drop lst n) n))))))
(define (transpose lst)
(apply map list lst))
(define (encode str)
(let* ([lst (normalize str)]
[n (get-num-cols (length lst))]
[rows (transpose (make-rows lst n))])
(string-join (map list->string rows))))
Haskell
In Haskell, implement a function encode :: String -> String
that accepts a string and returns the encoded string as described above. Your task is to be called SquareCode.hs
and must export the encode
function. Hence, the head of your file should read
module SquareCode ( encode ) where
import Data.Char
-- your code goes here
Hint
To make the string downcased, you may use the function toLower :: Char -> Char
. To remove spaces and punctuation, you may use the predicate isAlpha :: Char -> Bool
. Both functions are located at the module Data.Char
. To get the least integer above a real number, use the function ceiling :: Integral b => a -> b
.
Examples
The following shows the behaviour of the encode
function.
> encode "If man was meant to stay on the ground, god would have given us roots."
"imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau "
> encode "haveaniceday"
"hae and via ecy"
Solution
module Task4 ( encode ) where
import Data.Char
import Data.List
normalize :: String -> String
normalize s = [toLower c | c <- s, isAlpha c]
getNumCols :: Int -> Int
getNumCols n = ceiling $ sqrt $ fromIntegral n
makeRows :: String -> Int -> [String]
makeRows s n | s == "" = []
| len < n = [s ++ replicate (n-len) ' ']
| otherwise = take n s:makeRows (drop n s) n
where len = length s
encode :: String -> String
encode s = unwords rows'
where ns = normalize s
n = getNumCols $ length ns
rows = makeRows ns n
rows' = transpose rows