CIS194 HW 1

hw1.hs

-- Problem set: http://www.seas.upenn.edu/~cis194/hw/01-intro.pdf

-- I wonder how I'd define this without toDigitsRev...
toDigits :: Integer -> [Integer]
toDigits x = reverse $ toDigitsRev x

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

-- This is the slow way that looks similar to a loop in an imperative language
-- I should have just toggled a bool instead of using an integer, but oh well.
doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ doubleEveryOtherHelper 0 $ reverse xs

doubleEveryOtherHelper :: Integer -> [Integer] -> [Integer]
doubleEveryOtherHelper _ [] = []
doubleEveryOtherHelper i (x:xs) | i `mod` 2 == 0 =
  x : (doubleEveryOtherHelper (i + 1) xs)
doubleEveryOtherHelper i (x:xs) | i `mod` 2 == 1 =
  2 * x : (doubleEveryOtherHelper (i + 1) xs)

-- This method is also slow, but it's easier to read
doubleEveryOther' :: [Integer] -> [Integer]
doubleEveryOther' xs =
  reverse [a * b | (a, b) <- zip (reverse xs) $ cycle [1, 2]]

-- This method is efficient
doubleEveryOther'' :: [Integer] -> [Integer]
doubleEveryOther'' xs = fst $ foldr (\x (acc, bool) ->
                                    ((if bool then 2 * x else x) : acc,
                                     not bool)) ([], False) xs

-- Doing it with recursion for practice
sumDigits :: [Integer] -> Integer
sumDigits []     = 0
sumDigits (x:xs) = sum (toDigits x) + sumDigits xs

-- Using an accumulator is more idiomatic
sumDigits' :: [Integer] -> Integer
sumDigits' xs = foldl (\acc x -> acc + (sum $ toDigits x)) 0 xs

validate :: Integer -> Bool
validate x = let sum = sumDigits' $ doubleEveryOther'' $ toDigits x
             in sum `mod` 10 == 0

-- Note: The extra parenthesis in the function make it *slightly* more efficient
type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
hanoi 1 a b _ = [(a, b)]
hanoi n a b c = (hanoi (n - 1) a c b) ++
                ((hanoi 1 a b c) ++ (hanoi (n - 1) c b a))

-- Frame-Stewart algorithm for any number of pegs
hanoi' :: Integer -> [Peg]-> [Move]
hanoi' 0 _           = []
hanoi' 1 (a : b : _) = [(a, b)]
hanoi' n (a : b : c : rest) = hanoi' k (a : c : b : rest) ++
                              hanoi' (n - k) (a : b : rest) ++
                              hanoi' k (c : b : a : rest)
  where k
          | null rest = n - 1
          | otherwise = n `div` 2