% -*- mode: LaTeX; compile-command: "mk" -*- \documentclass{tufte-handout} %include lhs2TeX.fmt \usepackage[stable]{footmisc} % for putting footnotes in section headings \usepackage{../../hshw} \title{\thecourse\ problem set 1} \date{} \begin{document} \maketitle When solving the homework, strive to create not just code that works, but code that is stylish and concise. See the style guide on the website for some general guidelines. Try to write small functions which perform just a single task, and then combine those smaller pieces to create more complex functions. Don't repeat yourself: write one function for each logical task, and reuse functions as necessary. Be sure to write functions with exactly the specified name and type signature for each exercise (to help in testing your code). You may create additional helper functions with whatever names and type signatures you wish. \section{Validating Credit Card Numbers\footnote{Adapted from the first practicum assigned in the University of Utrecht functional programming course taught by Doaitse Swierstra, 2008-2009.}} Most credit card providers rely on a checksum formula, the \emph{Luhn algorithm} (\url{http://en.wikipedia.org/wiki/Luhn_algorithm}), as a straightforward line of defense against simple typos. (It does not protect against \emph{fraud}.) \begin{center} \includegraphics[width=3in]{images/credit-card.png} \end{center} In this section, you will implement the validation algorithm for credit cards. It follows these steps: \begin{itemize} \item Double the value of every second digit beginning from the right. That is, the last digit is unchanged; the second-to-last digit is doubled; the third-to-last digit is unchanged; and so on. For example, |[1,3,8,6]| becomes |[2,3,16,6]|. \item Add the digits of the doubled values and the undoubled digits from the original number. For example, |[2,3,16,6]| becomes |2+3+1+6+6 = 18|. \item Calculate the remainder when the sum is divided by 10. For the above example, the remainder would be |8|. \end{itemize} If the result equals 0, then the number is valid. \exercise We need to first find the digits of a number. Define the functions \begin{code} toDigits :: Integer -> [Integer] toDigitsRev :: Integer -> [Integer] \end{code} |toDigits| should convert positive |Integer|s to a list of digits. (For |0| or negative inputs, |toDigits| should return the empty list.) |toDigitsRev| should do the same, but with the digits reversed. \begin{example} |toDigits 1234 == [1,2,3,4]| \end{example} \begin{example} |toDigitsRev 1234 == [4,3,2,1]| \end{example} \begin{example} |toDigits 0 == []| \end{example} \begin{example} |toDigits (-17) == []| \end{example} \exercise Once we have the digits in the proper order, we need to double every other one. Define a function \begin{code} doubleEveryOther :: [Integer] -> [Integer] \end{code} Remember that |doubleEveryOther| should double every other number \emph{beginning from the right}, that is, the second-to-last, fourth-to-last, \dots numbers are doubled. \begin{example} |doubleEveryOther [8,7,6,5] == [16,7,12,5]| \end{example} \begin{example} |doubleEveryOther [1,2,3] == [1,4,3]| \end{example} \exercise The output of |doubleEveryOther| has a mix of one-digit and two-digit numbers. Define the function \begin{code} sumDigits :: [Integer] -> Integer \end{code} to calculate the sum of all digits. \begin{example} |sumDigits [16,7,12,5] = 1 + 6 + 7 + 1 + 2 + 5 = 22| \end{example} \exercise Define the function \begin{code} validate :: Integer -> Bool \end{code} that indicates whether an |Integer| could be a valid credit card number. This will use all functions defined in the previous exercises. \begin{example} |validate 79927398713 = True| \end{example} \begin{example} |validate 79927398714 = False| \end{example} \section{The Towers of Hanoi\footnote{Adapted from an assignment given in UPenn CIS 552, taught by Benjamin Pierce}} \begin{center} \includegraphics[width=5in]{images/Tower_of_Hanoi.jpeg} \end{center} \exercise The \term{Towers of Hanoi} is a classic puzzle with a solution that can be described recursively. Disks of different sizes are stacked on three pegs; the goal is to get from a starting configuration with all disks stacked on the first peg to an ending configuration with all disks stacked on the last peg, as shown in \pref{fig:hanoi}. \begin{marginfigure}[-8em] \begin{center} \begin{diagram}[width=150] import Hanoi dia = renderHanoi [[0..4], [], []] # pad 1.1 \end{diagram} \vspace{1em} {\LARGE $\Downarrow$} \vspace{0.5em} \begin{diagram}[width=150] import Hanoi dia = renderHanoi [[], [], [0..4]] # pad 1.1 \end{diagram} \end{center} \caption{The Towers of Hanoi} \label{fig:hanoi} \end{marginfigure} The only rules are \begin{itemize} \item you may only move one disk at a time, and \item a larger disk may never be stacked on top of a smaller one. \end{itemize} For example, as the first move all you can do is move the topmost, smallest disk onto a different peg, since only one disk may be moved at a time. \begin{marginfigure}[-5em] \begin{center} \begin{diagram}[width=150] import Hanoi dia = renderHanoi [[1..4], [0], []] # pad 1.1 \end{diagram} \end{center} \caption{A valid first move.} \end{marginfigure} From this point, it is \emph{illegal} to move to the configuration shown in \pref{fig:illegal}, because you are not allowed to put the green disk on top of the smaller blue one. \begin{marginfigure}[-3em] \begin{center} \begin{diagram}[width=150] import Hanoi dia = renderHanoi [[2..4], [1,0], []] # pad 1.1 \end{diagram} \end{center} \caption{An illegal configuration.} \label{fig:illegal} \end{marginfigure} For this exercise, define a function |hanoi| with the following type: \begin{code} type Peg = String type Move = (Peg, Peg) hanoi :: Integer -> Peg -> Peg -> Peg -> [Move] \end{code} Given the number of discs and names for the three pegs, |hanoi| should return a list of moves to be performed to move the stack of discs from the first peg to the last. Note that a |type| declaration, like |type Peg = String| above, makes a \emph{type synonym}. In this case |Peg| is declared as a synonym for |String|, and the two names |Peg| and |String| can now be used interchangeably. Giving more descriptive names to types in this way can be used to give shorter names to complicated types, or (as here) simply to help with documentation. \begin{example} |hanoi 2 "a" "b" "c" == [("a","b"), ("a","c"), ("b","c")]| \end{example} \exercise What if there are four pegs instead of three? That is, the goal is still to move a stack of discs from the first peg to the last peg, without ever placing a larger disc on top of a smaller one, but now there are two extra pegs that can be used as temporary'' storage instead of only one. Write a function similar to |hanoi| which solves this problem in as few moves as possible. It should be possible to do it in far fewer moves than with three pegs. For example, with three pegs it takes $2^{15} - 1 = 32767$ moves to transfer $15$ discs. With four pegs it can be done in $129$ moves.\marginnote{See Exercise 1.17 in Graham, Knuth, and Patashnik, \emph{Concrete Mathematics}, second ed., Addison-Wesley, 1994.} If you are stuck, feel free to search for more information on the Internet; be sure to cite any sources you use. \exercise \pref{fig:chords} shows several circles, cut by chords into one, two, four, and six regions, respectively. \begin{figure*} \centering \begin{diagram}[width=400] import Chords d0 = c d1 = c <> ch 0.5 (1/7) d2 = c <> ch 0.5 (-1/9) <> ch 0.3 (1/20) d3 = c <> ch 0 (1/4 + 1/41) <> ch 0.7 (1/2 + 1/19) <> ch 0.1 (1/7) dia = hcat' (with & sep .~ 0.5) [d0, d1, d2, d3] # centerX # frame 0.5 \end{diagram} \caption{Circles cut by zero, one, two, and three chords.} \label{fig:chords} \end{figure*} The pictures with zero, one, and two chords show the maximum possible number of regions (one, two, and four, respectively) which can be created with that many chords. However, using three chords it is possible to create more regions than shown. In general, what is the maximum number of regions that can be created using $n$ chords? Write a paragraph explaining your answer, along with a Haskell function $|maxRegions :: Integer -> Integer|$ which computes this number. (Your explanation can be included above the code as a comment.) \end{document} \end{document}