test/hanoi.c

   1 /****************************************************************************
   2  * Copyright (c) 1998-2010,2012 Free Software Foundation, Inc.              *
   3  *                                                                          *
   4  * Permission is hereby granted, free of charge, to any person obtaining a  *
   5  * copy of this software and associated documentation files (the            *
   6  * "Software"), to deal in the Software without restriction, including      *
   7  * without limitation the rights to use, copy, modify, merge, publish,      *
   8  * distribute, distribute with modifications, sublicense, and/or sell       *
   9  * copies of the Software, and to permit persons to whom the Software is    *
  10  * furnished to do so, subject to the following conditions:                 *
  11  *                                                                          *
  12  * The above copyright notice and this permission notice shall be included  *
  13  * in all copies or substantial portions of the Software.                   *
  14  *                                                                          *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
  16  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
  18  * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
  19  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
  20  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
  21  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
  22  *                                                                          *
  23  * Except as contained in this notice, the name(s) of the above copyright   *
  24  * holders shall not be used in advertising or otherwise to promote the     *
  25  * sale, use or other dealings in this Software without prior written       *
  26  * authorization.                                                           *
  27  ****************************************************************************/
  28 /*
  29  *      Name: Towers of Hanoi.
  30  *
  31  *      Desc:
  32  *              This is a playable copy of towers of hanoi.
  33  *              Its sole purpose is to demonstrate my Amiga Curses package.
  34  *              This program should compile on any system that has Curses.
  35  *              'hanoi'         will give a manual game with 7 playing pieces.
  36  *              'hanoi n'       will give a manual game with n playing pieces.
  37  *              'hanoi n a' will give an auto solved game with n playing pieces.
  38  *
  39  *      Author: Simon J Raybould        (sie@fulcrum.bt.co.uk).
  40  *      (This version has been slightly modified by the ncurses maintainers.)
  41  *
  42  *      Date: 05.Nov.90
  43  *
  44  * $Id: hanoi.c,v 1.34 2012/12/08 16:41:56 tom Exp $
  45  */
  46
  47 #include <test.priv.h>
  48 #include <math.h>
  49
  50 #define NPEGS                   3       /* This is not configurable !! */
  51 #define MINTILES                3
  52 #define MAXTILES                9
  53 #define DEFAULTTILES            7
  54 #define TOPLINE                 6
  55 #define BASELINE                16
  56 #define STATUSLINE              (LINES-3)
  57 #define LEFTPEG                 19
  58 #define MIDPEG                  39
  59 #define RIGHTPEG                59
  60
  61 #define LENTOIND(x)             (((int)(x)-1)/2)
  62 #define OTHER(a,b)              (3-((a)+(b)))
  63
  64 struct Peg {
  65     size_t Length[MAXTILES];
  66     int Count;
  67 };
  68
  69 static struct Peg Pegs[NPEGS];
  70 static int PegPos[] =
  71 {
  72     LEFTPEG,
  73     MIDPEG,
  74     RIGHTPEG
  75 };
  76 static short TileColour[] =
  77 {
  78     COLOR_GREEN,                /* Length 3 */
  79     COLOR_MAGENTA,              /* Length 5 */
  80     COLOR_RED,                  /* Length 7 */
  81     COLOR_BLUE,                 /* Length 9 */
  82     COLOR_CYAN,                 /* Length 11 */
  83     COLOR_YELLOW,               /* Length 13 */
  84     COLOR_GREEN,                /* Length 15 */
  85     COLOR_MAGENTA,              /* Length 17 */
  86     COLOR_RED,                  /* Length 19 */
  87 };
  88 static int NTiles = 0;
  89 static int NMoves = 0;
  90 static bool AutoFlag = FALSE;
  91
  92 static void InitTiles(void);
  93 static void DisplayTiles(void);
  94 static void MakeMove(int From, int To);
  95 static void AutoMove(int From, int To, int Num);
  96 static void Usage(void);
  97 static int Solved(int NumTiles);
  98 static int GetMove(int *From, int *To);
  99 static int InvalidMove(int From, int To);
 100
 101 int
 102 main(int argc, char **argv)
 103 {
 104     int FromCol, ToCol;
 105
 106     setlocale(LC_ALL, "");
 107
 108     switch (argc) {
 109     case 1:
 110         NTiles = DEFAULTTILES;
 111         break;
 112     case 2:
 113         NTiles = atoi(argv[1]);
 114         if (NTiles > MAXTILES || NTiles < MINTILES) {
 115             fprintf(stderr, "Range %d to %d\n", MINTILES, MAXTILES);
 116             ExitProgram(EXIT_FAILURE);
 117         }
 118         break;
 119     case 3:
 120         if (strcmp(argv[2], "a")) {
 121             Usage();
 122             ExitProgram(EXIT_FAILURE);
 123         }
 124         NTiles = atoi(argv[1]);
 125         if (NTiles > MAXTILES || NTiles < MINTILES) {
 126             fprintf(stderr, "Range %d to %d\n", MINTILES, MAXTILES);
 127             ExitProgram(EXIT_FAILURE);
 128         }
 129         AutoFlag = TRUE;
 130         break;
 131     default:
 132         Usage();
 133         ExitProgram(EXIT_FAILURE);
 134     }
 135     initscr();
 136     if (has_colors()) {
 137         int i;
 138         short bg = COLOR_BLACK;
 139         start_color();
 140 #if HAVE_USE_DEFAULT_COLORS
 141         if (use_default_colors() == OK)
 142             bg = -1;
 143 #endif
 144         for (i = 0; i < 9; i++)
 145             init_pair((short) (i + 1), bg, TileColour[i]);
 146     }
 147     cbreak();
 148     if (LINES < 24) {
 149         endwin();
 150         fprintf(stderr, "Min screen length 24 lines\n");
 151         ExitProgram(EXIT_FAILURE);
 152     }
 153     if (AutoFlag) {
 154         curs_set(0);
 155         leaveok(stdscr, TRUE);  /* Attempt to remove cursor */
 156     }
 157     InitTiles();
 158     DisplayTiles();
 159     if (AutoFlag) {
 160         do {
 161             noecho();
 162             AutoMove(0, 2, NTiles);
 163         } while (!Solved(NTiles));
 164         sleep(2);
 165     } else {
 166         echo();
 167         for (;;) {
 168             if (GetMove(&FromCol, &ToCol))
 169                 break;
 170             if (InvalidMove(FromCol, ToCol)) {
 171                 MvAddStr(STATUSLINE, 0, "Invalid Move !!");
 172                 refresh();
 173                 beep();
 174                 continue;
 175             }
 176             MakeMove(FromCol, ToCol);
 177             if (Solved(NTiles)) {
 178                 MvPrintw(STATUSLINE, 0,
 179                          "Well Done !! You did it in %d moves", NMoves);
 180                 refresh();
 181                 sleep(5);
 182                 break;
 183             }
 184         }
 185     }
 186     endwin();
 187     ExitProgram(EXIT_SUCCESS);
 188 }
 189
 190 static int
 191 InvalidMove(int From, int To)
 192 {
 193     if (From >= NPEGS)
 194         return TRUE;
 195     if (From < 0)
 196         return TRUE;
 197     if (To >= NPEGS)
 198         return TRUE;
 199     if (To < 0)
 200         return TRUE;
 201     if (From == To)
 202         return TRUE;
 203     if (!Pegs[From].Count)
 204         return TRUE;
 205     if (Pegs[To].Count &&
 206         Pegs[From].Length[Pegs[From].Count - 1] >
 207         Pegs[To].Length[Pegs[To].Count - 1])
 208         return TRUE;
 209     return FALSE;
 210 }
 211
 212 static void
 213 InitTiles(void)
 214 {
 215     int Size, SlotNo;
 216
 217     for (Size = NTiles * 2 + 1, SlotNo = 0; Size >= 3; Size -= 2)
 218         Pegs[0].Length[SlotNo++] = (size_t) Size;
 219
 220     Pegs[0].Count = NTiles;
 221     Pegs[1].Count = 0;
 222     Pegs[2].Count = 0;
 223 }
 224
 225 static void
 226 DisplayTiles(void)
 227 {
 228     int Line, peg, SlotNo;
 229     char TileBuf[BUFSIZ];
 230
 231     erase();
 232     MvAddStr(1, 24, "T O W E R S   O F   H A N O I");
 233     MvAddStr(3, 34, "SJR 1990");
 234     MvPrintw(19, 5, "Moves : %d of %.0f", NMoves, pow(2.0, NTiles) - 1);
 235     (void) attrset(A_REVERSE);
 236     MvAddStr(BASELINE, 8,
 237              "                                                               ");
 238
 239     for (Line = TOPLINE; Line < BASELINE; Line++) {
 240         MvAddCh(Line, LEFTPEG, ' ');
 241         MvAddCh(Line, MIDPEG, ' ');
 242         MvAddCh(Line, RIGHTPEG, ' ');
 243     }
 244     MvAddCh(BASELINE, LEFTPEG, '1');
 245     MvAddCh(BASELINE, MIDPEG, '2');
 246     MvAddCh(BASELINE, RIGHTPEG, '3');
 247     (void) attrset(A_NORMAL);
 248
 249     /* Draw tiles */
 250     for (peg = 0; peg < NPEGS; peg++) {
 251         for (SlotNo = 0; SlotNo < Pegs[peg].Count; SlotNo++) {
 252             size_t len = Pegs[peg].Length[SlotNo];
 253             if (len < sizeof(TileBuf) - 1 && len < (size_t) PegPos[peg]) {
 254                 memset(TileBuf, ' ', len);
 255                 TileBuf[len] = '\0';
 256                 if (has_colors())
 257                     (void) attrset((attr_t) COLOR_PAIR(LENTOIND(len)));
 258                 else
 259                     (void) attrset(A_REVERSE);
 260                 MvAddStr(BASELINE - (SlotNo + 1),
 261                          (PegPos[peg] - (int) len / 2),
 262                          TileBuf);
 263             }
 264         }
 265     }
 266     (void) attrset(A_NORMAL);
 267     refresh();
 268 }
 269
 270 static int
 271 GetMove(int *From, int *To)
 272 {
 273     MvAddStr(STATUSLINE, 0, "Next move ('q' to quit) from ");
 274     clrtoeol();
 275     refresh();
 276     if ((*From = getch()) == 'q')
 277         return TRUE;
 278     *From -= ('0' + 1);
 279     addstr(" to ");
 280     clrtoeol();
 281     refresh();
 282
 283     if ((*To = getch()) == 'q')
 284         return TRUE;
 285     *To -= ('0' + 1);
 286     refresh();
 287     if (!AutoFlag)
 288         napms(500);
 289
 290     move(STATUSLINE, 0);
 291     clrtoeol();
 292     refresh();
 293     return FALSE;
 294 }
 295
 296 static void
 297 MakeMove(int From, int To)
 298 {
 299     Pegs[From].Count--;
 300     Pegs[To].Length[Pegs[To].Count] = Pegs[From].Length[Pegs[From].Count];
 301     Pegs[To].Count++;
 302     NMoves++;
 303     DisplayTiles();
 304 }
 305
 306 static void
 307 AutoMove(int From, int To, int Num)
 308 {
 309     if (Num == 1) {
 310         MakeMove(From, To);
 311         napms(500);
 312     } else {
 313         AutoMove(From, OTHER(From, To), Num - 1);
 314         MakeMove(From, To);
 315         napms(500);
 316         AutoMove(OTHER(From, To), To, Num - 1);
 317     }
 318 }
 319
 320 static int
 321 Solved(int NumTiles)
 322 {
 323     int i;
 324
 325     for (i = 1; i < NPEGS; i++)
 326         if (Pegs[i].Count == NumTiles)
 327             return TRUE;
 328     return FALSE;
 329 }
 330
 331 static void
 332 Usage(void)
 333 {
 334     fprintf(stderr, "Usage: hanoi [<No Of Tiles>] [a]\n");
 335     fprintf(stderr,
 336             "The 'a' option causes the tower to be solved automatically\n");
 337 }