test/hanoi.c

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