%Towers of Hanoi illustrated and computed by TeX. The problem is solved in
%TeX and for every move the situation is drawn. The idea and visualization were
%by Martin Hofmann, Berteun Damman programmed the actual recursion.
%
% Authors: Martin Hofmann and Berteun Damman

% This is needed for a hyperref/beamer interaction bug
\RequirePackage{atbegshi}
\documentclass{beamer}



\usepackage{scalefnt}

\hypersetup{pdfpagemode=FullScreen}
\usetheme{Warsaw}

\usepackage{tikz}
\usetikzlibrary{shadows,patterns,shapes}

% The logic for Hanoi, we record the discs at every pole
% as a comma separated list ending with a '.'; i.e. the
% starting list for 4 discs would be 1,2,3,4,.
\newcount\ndiscs
\def\initpoles#1{
    \def\disclist{}
    \foreach \n in {1,...,#1} {
        \xdef\disclist{\disclist\n,}
    }
    \expandafter\xdef\csname pole 1\endcsname{\disclist.}
    \expandafter\gdef\csname pole 2\endcsname{.}
    \expandafter\gdef\csname pole 3\endcsname{.}
}

% Delimited macro; #1 is everything up to the first ',' and
% #2 everything after it.
\def\head#1,#2.{#1}
\def\tail#1,#2.{#2}

% This macro updates the disc lists, its arguments are the name
% names of the macro's corresponding to the poles, for example
% 'pole 1' and 'pole 3'.
\def\movedisc#1#2{
    \edef\lista{\csname #1\endcsname}
    \edef\listb{\csname #2\endcsname}
    \expandafter\xdef\csname #2\endcsname{\expandafter\head\lista,\listb}
    \expandafter\xdef\csname #1\endcsname{\expandafter\tail\lista.}
}

% Updates the lists and then draws a new frame.
\def\move#1#2{
    \movedisc{pole #1}{pole #2}
    \gdef\fmsg{\node[anchor=north] at (3.8,-.5) {Moved disc from pole #1 to pole #2.};}
    \drawpoles
}

% This macro boils down to a well-known recursive solution, as given
% here for example: http://en.wikipedia.org/wiki/Towers_of_Hanoi#Recursive_solution
%
% #1 Pole to move from
% #2 Pole to move to
% #3 Pole to use as scratch
% #4 Number of disks
\def\rhanoi#1#2#3#4{
    \ifnum#4>1
        {\advance#4 by -1 \rhanoi#1#3#2#4}
        \move{#1}{#3}
        {\advance#4 by -1 \rhanoi#2#1#3#4}
    \else
        \move{#1}{#3}
    \fi
}

% Below is the TikZ code to draw the towers:
\tikzset{
    disc/.style={shade, shading=radial, rounded rectangle,minimum height=.5cm,
        inner color=#1!20, outer color=#1!60!gray},
    disc 1/.style={disc=yellow, minimum width=15mm},
    disc 2/.style={disc=orange, minimum width=20mm},
    disc 3/.style={disc=red, minimum width=25mm},
    disc 4/.style={disc=green, minimum width=30mm},
    disc 5/.style={disc=blue, minimum width=35mm},
    disc 6/.style={disc=purple, minimum width=40mm},
}

% Define some colors, I don't like plain green and brown.
\definecolor{darkgreen}{rgb}{0.2,0.55,0}
\definecolor{darkbrown}{rgb}{0.375,0.25,0.125}

\newcommand{\pole}{
  \fill[darkbrown] (-1.6cm, 0) rectangle (1.6cm,0.25cm)
    (-1.25mm,2.5mm) rectangle (1.25mm,4.25cm);
}

% Because the list starts with the topmost disc, we
% use two recursive macro's to invert the drawing process.
\newcount\curlevel

% This macro checks whether the list is empty, if not,
% it calls \rdrawdiscs which removes one element and
% calls this one again.
\def\drawdiscs#1.{
    % If #1 is empty, this expands to \if.. which is true, otherwise
    % we're safe to assume there's at least one element.
    \expandafter\if#1..\else
        \rdrawdiscs#1.
        \advance\curlevel by 1\relax
    \fi
}

\def\rdrawdiscs#1,#2.{
    \drawdiscs#2.
    {\edef\n{\the\curlevel}
        % Draw the actual disk.
        \node[disc #1,yshift={\n*5mm}] {#1};
    }
}

\def\discs#1{
    \curlevel=1
    \expandafter\drawdiscs#1
}

% Draws the whole situation based on the lists.
\def\drawpoles{
    \begin{frame}{\ftitle}
    \begin{tikzpicture}
        \foreach \n/\x in {1/0cm,2/3.8cm,3/7.6cm} {
            \begin{scope}[xshift=\x]
                \pole
                \expandafter\discs\csname pole \n\endcsname
            \end{scope}
        }
        % Macro that either contains something like OK or
        % the last move.
        \fmsg
        % We use this to prevent the picture from jumping between
        % frames.
        \useasboundingbox (-1.6cm,-1.2cm) rectangle (9.2cm,4.25cm);
    \end{tikzpicture}
    \end{frame}
}

% Main macro, inits the lists for the current number, sets a title
% for the frame and starts the recursion.
\def\hanoi#1{
    \ndiscs=#1
    \initpoles{#1}
    \ifnum\ndiscs=1
        \xdef\ftitle{Tower of Hanoi -- \the\ndiscs\ Disc}
    \else
        \xdef\ftitle{Tower of Hanoi -- \the\ndiscs\ Discs}
    \fi
    \gdef\fmsg{}
    % Starting frame.
    \drawpoles
    % Recursion draws a new frame for every step.
    \rhanoi{1}{2}{3}{\ndiscs}
    % Final frame.
    \gdef\fmsg{\node[] at (3.8,2.5) {\Huge\scalefont{2}\color{darkgreen}OK};}
    \drawpoles
}

\begin{document}
    \hanoi{1}
    \hanoi{2}
    \hanoi{3}
    \hanoi{4}

    % For 5 discs we don't show everything (although it could be done).
    \ndiscs=5
    \initpoles{5}
    \def\ftitle{Tower of Hanoi -- \the\ndiscs\ Disc}
    \def\fmsg{\node[cloud, draw, fill=gray!20, aspect=2] at (3.8,2.5) {\Huge\scalefont{2}?};}
    \drawpoles
\end{document}