%
%                  Towers of Hanoi by TeX
%
% Copyright (C) 2004 NIIBE Yutaka  <gniibe@fsij.org>
%
% $Id: towers-of-hanoi.tex,v 1.1 2004/02/03 01:03:18 gniibe Exp $
%
% This program 'Towers of Hanoi by TeX' is free software; you can
% redistribute it and/or modify it under the terms of the GNU General
% Public License as published by the Free Software Foundation; either
% version 2 or (at your option) any later version.
%
% This program is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.

%
% This file is intended to be processed by (plain) TeX, such that:
%
%       $ tex \\def\\NUMDISKS{10} \\input towers-of-hanoi.tex
%
% where the definition of NUMDISKS specifies the number of disks.
%
% If you invoke TeX without the definition, TeX will ask you the number.
%

\catcode`\$=11\catcode`\@=11
\def\title{{\sl Towers of Hanoi by \TeX}}
\def\revision{{\rm $Revision: 1.1 $}}
\def\author{{\tt gniibe@fsij.org}}
%                ^^^^^^^^^^^^^^^------- Your name here, please.

\newbox\headlinebox
\setbox\headlinebox=\hbox{\title}
\setbox\headlinebox=\hbox to \wd\headlinebox{%
  \raise 3pt\hbox to 0pt{\copy\headlinebox\hss}\hrulefill}
\headline={\hfill\copy\headlinebox}
\footline=\expandafter{\the\footline%
                       \hbox to0pt{\hss\author\hskip 10pt\revision}}

% \tracingmacros=1  % To debug, please enable this line.
\parskip=30pt minus 28pt

% Constants what you may customize
\newdimen\WD  \WD=0.24em  % Unit width of disk
\newdimen\HT  \HT=0.30em  % Unit height of disk

\newskip\towerglue      \towerglue=10pt
\newdimen\polethickness \polethickness=0.2pt
\newdimen\diskthickness \diskthickness=0.5pt

\newdimen\NoteSize      \NoteSize=2em
\newdimen\NoteRaise     \NoteRaise=1pt
\newdimen\NoteDepth     \NoteDepth=1pt

\newcount\MAXCOL        \MAXCOL=2  % Number of columns -1

%
\newdimen\TowersOfHanoiWidth
\newdimen\halfbasewidth
\newdimen\halfarrowwidth
\newdimen\fullarrowwidth

% Variables
\newcount\BASE		%  Size of base (= number of disks + 1)

\newcount\poleAheight   %  Height of the part of poleA with no disks
\newcount\poleBheight   %  Height of the part of poleB with no disks
\newcount\poleCheight   %  Height of the part of poleC with no disks

\newcount\hanoiStep     %  Step
\newcount\col           %  Current column

\def\Inst{}             %  Instruction display explaining how-to-move

\def\disksA{\base}      %  Disks of pole A
\def\disksB{\base}      %  Disks of pole B
\def\disksC{\base}      %  Disks of pole C

\newcount\lastmoveddisk \lastmoveddisk=0

%%%%%% Primitive Drawing routines thePole and theDisk
% Draw routine: thePole(Hight), assuming vmode
\def\thePole#1{%
  \hbox to \BASE\WD{\hfill%
    \vbox{\kern-0.5\polethickness%
      \hrule height\polethickness%
      \kern-0.5\polethickness%
      \hbox{\kern-0.5\polethickness%
        \vrule width\polethickness height#1\HT%
        \kern-0.5\polethickness%
        \hbox to 0.25\WD{}%
        \kern-0.5\polethickness%
        \vrule width\polethickness height#1\HT%
        \kern-0.5\polethickness%
      }}\hfill}\hrule height 0pt}

% Draw routine: theDisk(Width), assuming vmode
\def\theDisk#1{%
 \ifnum#1=\lastmoveddisk%
   \hbox to \BASE\WD{\hfill\vbox{\hrule width#1\WD height\HT}\hfill}%
 \else%
   \hbox to \BASE\WD{\hfill%
     \vbox{\hrule height\diskthickness\kern-\diskthickness%
       \hbox to #1\WD{%
         \vrule height\HT width\diskthickness%
         \kern-\diskthickness\hfill\kern-\diskthickness%
         \vrule height\HT width\diskthickness%
       }%
     }\hfill}%
 \fi\hrule height 0pt}
%%%%%%

%%%%%% Data structure manipulation
\newtoks\CONS\CONS={\cons}
\newtoks\CDR
\def\diskpush#1#2{%
  \global\expandafter\advance\csname pole#2height\endcsname by-1%
  \CDR=\expandafter\expandafter\expandafter{\csname disks#2\endcsname}%
  \expandafter\xdef\csname disks#2\endcsname{\the\CONS{#1}{\the\CDR}}}

\def\diskmove#1#2{{% Temporarily re-define CONS
  \def\cons##1##2{\expandafter\gdef\csname disks#1\endcsname{##2}%
    \global\expandafter\advance\csname pole#1height\endcsname by1%
    \diskpush{##1}{#2}}%
  \csname disks#1\endcsname}}

% Rendering of the data structure
\def\base{\hrule height\diskthickness\kern0pt}
\def\cons#1#2{\theDisk{#1}#2}

%%%%%%
\def\SP{\hskip\towerglue}  % Space between towers

% Main Drawing routines

%%
%%          [         Inst              ]
%%
%%               ||         ||     ||
%%             <---->       ||     ||
%%            <------>      ||     ||
%% [ Note ]  <-------->     ||     ||
%% --------------------------------------
%%
\def\TowersOfHanoi{\hbox{\vbox{\hbox{\Towers}\hrule height\polethickness}}}
\def\Towers{\Note\SP%
            \vbox{\hbox{\Inst}%
                  \hbox{\Tower{A}\SP\Tower{B}\SP\Tower{C}\SP\hbox{}}}}
\def\Tower#1{\vbox{\Pole{#1}\Disks{#1}}}
\def\Pole#1{\expandafter\thePole\csname pole#1height\endcsname}
\def\Disks#1{\let\disks=\expandafter\csname disks#1\endcsname \disks}
\def\Note{\hbox to \NoteSize{\hfill\raise\NoteRaise\hbox{\the\hanoiStep}%
                             \hbox{\vrule depth \NoteDepth width 0pt}}
          \global\advance\hanoiStep by 1}

%%%%%
% Local auto variable: n: number of disks to move (or the Nth disk)
\newcount\n

%%
\def\GenerateDisks#1{{\n=#1% Number of disks
  \loop\ifnum\n>0\expandafter\diskpush\expandafter{\the\n}{A}%
       \advance\n by-1\repeat}}

\def\InitTowersOfHanoi#1{%
  \BASE=#1 \advance\BASE by 1
  \poleAheight=#1 \advance\poleAheight by 2
  \poleBheight=\poleAheight
  \poleCheight=\poleAheight

  \TowersOfHanoiWidth=\towerglue\advance\TowersOfHanoiWidth by \BASE\WD
  \multiply\TowersOfHanoiWidth by 3
  \advance\TowersOfHanoiWidth by \NoteSize
  \advance\TowersOfHanoiWidth by \towerglue
  \halfbasewidth=\BASE\WD \divide\halfbasewidth by 2
  \halfarrowwidth=\towerglue \advance\halfarrowwidth by \BASE\WD
  \fullarrowwidth=\halfarrowwidth \multiply\fullarrowwidth by 2

  \hanoiStep=0 \col=0
  \GenerateDisks{#1}}

\def\FiniTowersOfHanoi{%
  \loop\ifnum\col<\MAXCOL\global\advance\col by1%
  \hfill\hskip\TowersOfHanoiWidth\repeat%
  \hfill\hbox{}\par}

%%%%%%%%%%
%
\def\instructionAB{\hbox to\halfarrowwidth{\rightarrowfill}}  % --->
\def\instructionBC{\SP\hskip \BASE\WD%
                   \hbox to\halfarrowwidth{\rightarrowfill}}  %     --->
\def\instructionAC{\hbox to\fullarrowwidth{\rightarrowfill}}  % ------->
\def\instructionBA{\hbox to\halfarrowwidth{\leftarrowfill}}   % <---
\def\instructionCB{\SP\hskip \BASE\WD%
                   \hbox to\halfarrowwidth{\leftarrowfill}}   %     <---
\def\instructionCA{\hbox to\fullarrowwidth{\leftarrowfill}}   % <-------

%% Main moving routine

% Base: moveonedisk(disk, pole-from,pole-to)
%%
% Move a disk.
% Set the last moved disk and instruction how to move.
% Then, Draw.
%%
\def\moveonedisk#1#2#3{\diskmove{#2}{#3}%
  \lastmoveddisk=#1%
  \def\Inst{\hskip\halfbasewidth\csname instruction#2#3\endcsname\hfill}%
  \ifnum\col=\MAXCOL\global\col=0\hfill\hbox{}\par\noindent\hfill%
  \else\global\advance\col by1\hfill\fi%
  \TowersOfHanoi}

% Induction step: move(# of disks, pole-from, pole-to, pole-temp)
\def\move#1#2#3#4{%
  {\n=#1\advance\n by-1\relax%
   \ifnum#1>1\expandafter\move\expandafter{\the\n}{#2}{#4}{#3}\fi%
   \moveonedisk{#1}{#2}{#3}%   Move the Nth disk
   \ifnum#1>1\expandafter\move\expandafter{\the\n}{#4}{#3}{#2}\fi}}

%%%%%%%%% Here we go...
\expandafter\ifx\csname NUMDISKS\endcsname\relax%
  \message{Please enter number of disks:}%
  \read16 to \NUMDISKS%
\fi

\InitTowersOfHanoi{\NUMDISKS}
\noindent\hfill\TowersOfHanoi%
\move{\NUMDISKS}{A}{B}{C}%
\FiniTowersOfHanoi

\vfill\eject
\bye
%% End: %%
