homework-01

Homework 1

This homework contains the following files:

• Assignment
• CreditCard.hs (file to submit)
• Hanoi.hs (file to submit)

Exercise 1

The function toDigits :: Integer -> [Integer] converts a positive integer to a list of digits. If the integer is less or equal than 0, it should return the empty list. We can use guards to check whether the integer is positive or not. If the integer n is positive, we can easily access its last digit using n `mod` 10. To maintain the digits in order, we must concatenate that digit to the right of toDigits (n `div` 10). This recursive call returns the list of digits of the number without its last digit. Note that we will eventually hit the case n <= 0 as an integer has a finite amount of digits.

toDigits:: Integer -> [Integer]
toDigits n
  | n <= 0    = []
  | otherwise = toDigits (n `div` 10) ++ [n `mod` 10]

The function toDigitsRev :: Integer -> [Integer] does exactly the same as toDigits except that the digits are reversed. A trivial solution would be to call the toDigits function and then reverse its result. However, implementing toDigitsRev from scratch is also easy. The only difference with the previous function is that instead of concatenating the last digit to the right, we use the cons : operator to prepend the element:

toDigitsRev :: Integer -> [Integer]
toDigitsRev n
  | n <= 0    = []
  | otherwise = n `mod` 10 : toDigitsRev (n `div` 10)

Exercise 2

The function doubleEveryOther :: [Integer] -> [Integer] doubles every other number beginning from the right. For example, doubleEveryOther [8,7,6,5] must double the second-to-last and fourth-to-last numbers and return [16,7,12,5].

My first implementation was the following:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther []                          = []
doubleEveryOther (x:[])                      = [x]
doubleEveryOther (x:y:zs) | even (length zs) = 2*x : y : doubleEveryOther zs
doubleEveryOther (x:y:zs)                    = x : 2*y : doubleEveryOther zs

This implementation is pretty verbose as it matches four patterns. Since I am taking the first two elements of the list, depending on whether the length of the list is even or not I might end with zero or one element. Moreover, I also have to check the length of the list in the recursive cases.

I realised there is a much cleaner solution. The complexity of this function is that we must begin from the right, and in Haskell we usually traverse lists from left to right. Thus, what if we reverse the list? If we reverse the list, we just have to double every other number beginning from the left. Then we can use the zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] function which takes a function and two lists and applies that function to each pair generated by zipping [a] and [b]. The list [a] will be the original list reversed, while [b] will be cycle [1,2]. That way, every second element will be doubled, provided that we use (*) as function in zipWith.

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ zipWith (*) (cycle [1,2]) (reverse xs)

An better version where we directly return a function:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther = reverse . zipWith (*) (cycle [1,2]) . reverse

Exercise 3

The function sumDigits :: [Integer] -> Integer returns the sum of all digits of each number of the list. For that, we must apply the function toDigits to each number of the list:

sumDigits :: [Integer] -> Integer
sumDigits []     = 0
sumDigits (x:xs) = sum (toDigits x) + sumDigits xs

A cleaner solution, without using explicit recursion and using concat :: [[a]] -> [a] is:

sumDigits :: [Integer] -> Integer
sumDigits = sum . concat . map toDigits

Note that here the approach varies a bit since we do not sum the digits after the call to toDigits, instead we flatten the list of digits and we sum them all at the end.

Exercise 4

The function validate :: Integer -> Bool returns whether or not a credit card number is valid. Here we just had to reuse the functions that were implemented in previous exercises:

validate :: Integer -> Bool
validate x = (sumDigits . doubleEveryOther . toDigits $ x) `mod` 10 == 0

Exercise 5

The Tower of Hanoi is a mathematical puzzle that is usually metioned when introducing recursion. The function hanoi :: Integer -> Peg -> Peg -> Peg -> [Move] takes an integer and three pegs and returns the list of moves needed to move the stack of discs from the first peg to the second using one auxiliary peg.

The problem can be solved as follows:

• move n−1 discs from src to aux using dst as temporary storage
• move the top disc from src to dst
• move n−1 discs from aux to dst using src as temporary storage

hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi 0 _ _ _ = []
hanoi n src dst aux =
  moveFromSrcToAux ++ moveFromSrcToDst ++ moveFromAuxToDst
  where
    moveFromSrcToAux = hanoi (n-1) src aux dst
    moveFromSrcToDst = [(src, dst)]
    moveFromAuxToDst = hanoi (n-1) aux dst src

Exercise 6

The final exercise was pretty challenging as it introduced a variant of the previous puzzle. Here, instead of three towers, we have four, that is, we have two auxiliary pegs instead of one. A trivial implementation is to simply ignore one of the two auxiliary pegs and then the solution is exactly the same as the previous one. However, using two auxiliary pegs allows us to go much faster! For example, moving 15 discs with 3 pegs takes 32767 moves while it only takes 129 moves with 4 pegs.

It turns out that this problem is not trivial at all, I had to research a bit to come up with the solution. After reading some papers about that, I ended up implementing the Frame-Stewart algorithm, which ensures that the number of steps is optimum for 4 pegs:

• for some k (1 <= k < n), move k discs from src to aux1
• move the remaining n-k discs from src to dst without using aux1
• move k discs from aux1 to dst

Note that for this solution we use the hanoi function that we implemented in the previous exercise.

hanoi4 :: Integer -> Peg -> Peg -> Peg -> Peg -> [Move]
hanoi4 0 _ _ _ _ = []
hanoi4 n src dst aux1 aux2 =
  moveFromSrcToAux1 ++ moveFromSrcToDst ++ moveFromAux1ToDst
  where
    moveFromSrcToAux1 = hanoi4 k src aux1 aux2 dst
    moveFromSrcToDst  = hanoi (n-k) src dst aux2
    moveFromAux1ToDst = hanoi4 k aux1 dst aux2 src
    n' = fromIntegral n :: Double
    k  = n - round (sqrt (2*n' + 1)) + 1