Chapter 3 Daily 05 Problem Set

1. How many numbers are between two given binary numbers, including the start and end number?

    bcount :: [Int] -> [Int] -> Int
    bcount [1,1,0,0,1] [0,1,0,1,1] == 8
   

2. (ensureLen :: Int -> [Int] -> [Int]). The call ensureLen 6 xs append zeros to xs if necessary to ensure it has a length of at least 6.

    ensureLen 4 [1] == [1,0,0,0]
    ensureLen 3 [1,0,1,0,1] == [1,0,1,0,1]
   

3. (and' :: Int -> Int -> Int). Helper function. Give 1 if both inputs are 1, otherwise 0.

4. (bitwiseAnd) Given two binary integers a and b (represented as lists of 0 and 1), produce the binary number given by lining up the ones places and then “and”-ing the digits of a and b together.

    bitwiseAnd :: [Int] -> [Int] -> [Int]

    check_bitwise = [
        bitwiseAnd [0,1,0,1,0,1,0,1]
                   [0,0,0,0,1,1,1,1] ==
                   [0,0,0,0,0,1,0,1],
        bitwiseAnd     [1,1,1]
                       [1,0,1,1,0,1] ==
                       [1,0,1] -- or [1,0,1,0,0,0]
        ]

5. (bitwise) There is nothing special about the operator “and” in the previous example. Given any operation on two binary numbers, call it (op :: Int -> Int -> Int), create a number by performing the operation bitwise as in the previous exercise. The shorter number should be padded with zeros to be the same length as the long number.

   The type signature for op in the big bitwise signature is (Int->Int->Int). Example:

    xor' :: Int -> Int -> Int
    xor' a b = if a == b then 0 else 1
   
    bitwise xor' [0,1,0,1] [0,1,1,0] = [0,0,1,1]
   

6. txtToBin :: String -> [[Int]]. Translate a string into a list of binary numbers using the location each character is found in the (abbreviated) list below. If a character is not found, produce the empty list to represent it.

    [space]A-Za-z0-9
   

   Which means the following (but please think of a better way to produce this list than typing or copy and paste):

    " ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
   

   Example: txtToBin ['A','Y'] means change the numbers [1,25] to binary, so the result would be [[1],[1,0,0,1,1]].

7. binToMsg :: [[Int]] -> [Int]. Make sure each binary number is 6 digits, and then concatenate all of the binary numbers into one long list of integers.

8. msgDecode :: [Int] -> String. Now decode the big binary number, changing it back into text.

Encryption and Decryption Problems

(encrypt :: String -> String -> String). The encrypt function takes in a key string and a message string. The encryption lines up the letters in the key and the message, changes the characters into binary numbers, joins the binary numbers with “exclusive or” (see the next paragraph), and then changes the resulting number back into a string. The string will be nonsense.

The function “exclusive or” (called xor) is mentioned in the problem above. Exclusive or takes in two numbers and gives 1 if the numbers are different and 0 if the numbers are the same.

Simple Example

A simple example will illustrate the process.

    encrypt "M" "S" == "d"

The key is “M” and the secret is “S”. The letter “M” is letter 13 in the alphabet, so 1101 in binary, represented by the list [1,0,1,1]. The letter “S” is letter 19 in the alphabet, which is 10011 in binary, so the list [1,1,0,0,1]. Matching up the binary digits and exclusive or-ing gives [0,1,1,1,1], which is 11110 binary, or 30 decimal. In the alphabet string above, letter 30 is lowercase “d”, so that is the encrypted version.

Complete example

A more complex example illustrates the complete process.

    encrypt "Key" "Secrets"

The key is repeated and lined up with the secret message, then the values of the binary numbers are combined with xor.

    "KeyKeyK"
    "Secrets"
    "X tm cl"

Note: this function is likely to require helper functions!

Problem Statements

9. Write encrypt :: String -> String -> String as described above.

10. decrypt :: String -> String -> String. Given an encrypted message and a key, reverse the encryption process. This is kind of tricky without experimentation; try just re-encrypting the message and see if you can figure out a pattern.

Appendix

Load lyrics for a song from a file for a cool thing to encrypt in problem 8. See the file loading example showing how to read a bunch of lyrics from a file.