home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 047.lha / hanoi.c < prev    next >
C/C++ Source or Header  |  1986-11-20  |  15KB  |  443 lines
  1. /* hanoi.c                  21-Feb-1987           From: 2294.comp-sys-amiga
  2. **
  3. ** Towers of Hanoi for the Amiga, by Ali Ozer (ali@Score.Stanford.Edu).
  4. ** Originally written June '86, revised February '87. This program may be
  5. ** freely distributed. Please do not delete the author's name & picture: 8-)
  6. **
  7. ** This program will create a window within the workbench screen and start
  8. ** solving the Towers of Hanoi problem (with 5 disks). The main purpose
  9. ** of this program is to sit in the side and absorb unused cycles --- By
  10. ** default it runs at priority -20... 
  11. ** 
  12. ** This program can be started from the CLI or the Workbench. If started
  13. ** from the CLI, it will accept command line arguments to change the various
  14. ** parameters. (Give "?" as an argument to see what arguments are expected.)
  15. ** If started from the Workbench, the program will open a window and explicitly
  16. ** ask for the parameters. Hit <return> or ctrl-\ to use the default values.
  17. **
  18. ** The idea for this program came from a similar program that runs on some
  19. ** Xerox Lisp machine. (I think it was some Xerox machine, I just saw it
  20. ** run one day as I was watching a friend work on one of them...) 
  21. **
  22. ** Future improvements to this code might include (if anyone wishes to
  23. ** play with this program) making the disks look better and making them
  24. ** move pixel by pixel instead of jumping as they do now. 
  25. **
  26. ** Thanks to Lee Taran (who was a few weeks ahead of me in solving the great
  27. ** mysteries of the Rom Kernel Manual, back in May '86, when we first got the
  28. ** Amiga --- Most of the initialization code is from her), and Tom Rokicki,
  29. ** who convinced us to get an Amiga in the first place and who also posted the
  30. ** code for the OpenInfoWindow routine used near the end of this program...
  31. */
  32.  
  33. #include <exec/types.h>
  34. #include <intuition/intuition.h>
  35. #include <graphics/gfxmacros.h>
  36. #include <stdio.h>
  37.  
  38. /* Default values. Actually there are some more values in the program
  39. ** that should be #define'd here, such as the default speed, default number
  40. ** of disks, etc, but then I would have to have my strings work more
  41. ** dynamically, and, and, and... (excuses excuses)
  42. */
  43. #define MAXDISKS            25
  44. #define WIDTH              180
  45. #define HEIGHT              60
  46. #define WINDOWX    (625-WIDTH)
  47. #define WINDOWY             14
  48. #define TEXTDELAY           6L           /* Time to wait after text */
  49. #define MINWIDTHFORTEXT  (4 + 8 * 7)     /* 8: Font Width, 7: #chars */
  50.  
  51. FILE *fopen(), *input, *output, temp;    /* For fputs/fgets console I/O. */
  52.  
  53. char *fgets();
  54. void  fputs();
  55.  
  56. void *OpenLibrary(), *OpenWindow(), *FindTask(), *IntuitionBase, *GfxBase;
  57.  
  58. BYTE disks[3][MAXDISKS+1];  /* We have 3 towers with upto MAXDISKS disks  */
  59. int  topdisk[3];            /* Free location on each tower (0 = all free) */
  60. int  towerloc[4];           /* Pixel location of each tower (4th = imag.) */
  61.  
  62. /* Tons of globals... */
  63. int dx, dy, height, width, top, moveto, 
  64.     numsteps, numdisks, wbench, writetext;
  65. long movedelay, windowcolor, diskcolor, 
  66.      outlinecolor, beepcolor, textcolor, priority;
  67.  
  68. struct NewWindow WindowInfo =
  69. { WINDOWX, WINDOWY, WIDTH, HEIGHT,         /* Left, Top, Width, Height */
  70.   0, 0,                    /* Detail pen, Block pen (-1 = use screens) */
  71.   CLOSEWINDOW | NEWSIZE | REFRESHWINDOW | SIZEVERIFY,    /* IDCMPflags */
  72.   WINDOWDEPTH | WINDOWSIZING |
  73.   SMART_REFRESH | WINDOWCLOSE | WINDOWDRAG,                   /* Flags */
  74.   NULL, NULL, NULL,              /* FirstGadget, Menu Checkmark, Title */
  75.   NULL, NULL,                                        /* Screen, Bitmap */
  76.   0, 0, 640, 200,                 /* Min Width/Height Max Width/Height */
  77.   WBENCHSCREEN                                                 /* Type */
  78. };
  79.  
  80. /* Structure to hold all the window info maintained by Intuition */
  81. struct Window   *HanoiWindow;
  82. struct RastPort *HanoiRPort;
  83.  
  84. /* A macro to make dealing with undefined argv's easier... */
  85. #define ARGV(n) (argc <= n ? "" : argv[n])
  86.  
  87. main(argc, argv)
  88. int   argc;
  89. char *argv[];
  90. { 
  91.   int i, cnt, GetNum(), GetArg();
  92.   struct Task *thistask;
  93.  
  94.   if (wbench = (argc == 0)) {   /* Ie, started from the workbench */
  95.     if (!OpenInfoWindow()) exit (1);
  96.     fputs ("Enter parameters, <CR> or ^\\ for defaults\n", output);
  97.     numdisks    = GetNum ("Number of disks? [1..25, default 5] ", 1, 25, 5);
  98.     movedelay   = 12-GetNum ("Speed? [1..12, default 4]           ", 1, 12, 4);
  99.     windowcolor = GetNum ("Background Color? [0..3, default 3] ", 0, 3, 3);
  100.     textcolor   = GetNum ("Text Color? [0..3, default 3]       ", 0, 3, 3);
  101.     diskcolor   = GetNum ("Disk Color [0..3, default 2]        ", 0, 3, 2);
  102.     outlinecolor= GetNum ("Outline Color [0..3, default 2]     ", 0, 3, 2);
  103.     priority    = -20L;
  104.     CloseInfoWindow ();
  105.   } else {    /* Started from the CLI */
  106.     numdisks    = GetArg (ARGV(1), 1, 25, 5);
  107.     movedelay   = 12-GetArg (ARGV(2), 1, 12, 4);
  108.     windowcolor = GetArg (ARGV(3), 0, 3, 3);
  109.     textcolor   = GetArg (ARGV(4), 0, 3, 3);
  110.     diskcolor   = GetArg (ARGV(5), 0, 3, 2);
  111.     outlinecolor= GetArg (ARGV(6), 0, 3, 2);
  112.     WindowInfo.LeftEdge = GetArg (ARGV(7), 0, 640 - WIDTH,  WINDOWX);
  113.     WindowInfo.TopEdge  = GetArg (ARGV(8), 0, 200 - HEIGHT, WINDOWY);
  114.     priority    = GetArg (ARGV(9), 0, 8, 0) * 5 - 20;
  115.   };
  116.  
  117.   if (thistask = FindTask (NULL)) SetTaskPri (thistask, (long)priority);
  118.  
  119.   numsteps             = (numdisks * 2) + 4;
  120.   writetext            = (windowcolor != textcolor);
  121.   WindowInfo.DetailPen = windowcolor;
  122.   WindowInfo.BlockPen  = windowcolor;
  123.   WindowInfo.MinWidth  = numsteps * 3;
  124.   WindowInfo.MinHeight = numdisks * 2 + 4 + writetext * 10;
  125.   WindowInfo.Height   += (writetext * 10);
  126.   /* Make sure beepcolor is different than disk or window color */
  127.   if ((beepcolor = ((diskcolor - 1) & 3)) == windowcolor)
  128.      beepcolor = (beepcolor - 1) & 3;
  129.  
  130.   OpenLibraries();  
  131.   SetupEnvironment();  
  132.   ReCalculateParameters();
  133.   InitializeTowers();  
  134.   ClearWindow();
  135.   DrawAllDisks(diskcolor);
  136.  
  137.   for (cnt = 0; cnt < 10; cnt++) {
  138.     CheckForMessages ();  Delay (20L);
  139.   }
  140.   while (1) 
  141.     for (i = 0; i < 3; i++) {
  142.       MoveDisks(i, (i+1)%3, (i+2)%3, numdisks);  
  143.       DrawAllDisks (beepcolor); Delay (6L); DrawAllDisks (diskcolor);
  144.       for (cnt = 0; cnt < numdisks * 3; cnt++) {
  145.         CheckForMessages ();  Delay (20L);
  146.       }
  147.     }
  148. }
  149.  
  150. /* Called after resizing to determine new parameters...
  151. */
  152. ReCalculateParameters()
  153. {
  154.   int xstart, i;
  155.  
  156.   top    = (writetext ? 9 : 0);
  157.   height = HanoiWindow->Height;
  158.   width  = HanoiWindow->Width;
  159.   dx     = width / (3 * numsteps);
  160.   dy     = (height-top) / (numdisks + 2);
  161.   xstart = (width - dx * 3 * numsteps) / 2;
  162.   for (i = 0; i < 4; i++) towerloc[i] = xstart + i * numsteps * dx;
  163.   moveto = top + dy;
  164. }
  165.  
  166. DrawDiskAtLoc (disk, tower, location, diskcolor, outlinecolor)
  167. int  disk, tower, location;
  168. long diskcolor, outlinecolor;
  169. {
  170.   if (disk) {
  171.     SetAPen (HanoiRPort, diskcolor);
  172.     SetOPen (HanoiRPort, outlinecolor);
  173.     RectFill (HanoiRPort, 
  174.               (long)(towerloc[tower] + (numdisks - disk + 1) * dx),
  175.               (long)(height - (location + 1) * dy),
  176.               (long)(towerloc[tower+1] - 1 - (numdisks - disk + 1) * dx),
  177.               (long)(height - (location * dy) - 2)); 
  178.   }
  179. }
  180.             
  181. DrawAllDisks(color)
  182. long color;
  183. {
  184.   int tower, location;
  185.  
  186.   for (tower = 0; tower < 3; tower++) 
  187.     for (location = 0; location < numdisks; location++)
  188.       DrawDiskAtLoc (disks [tower][location], tower,
  189.                      location, color, outlinecolor);
  190. }
  191.   
  192.  
  193. /* InitializeTowers will clear towers 1 and 2 and fill up tower 0. 
  194. ** To start off, we have disk[0][0] = largest disk, disk[0][1] = next
  195. */
  196. InitializeTowers()
  197. {
  198.   int i;
  199.   for (i=0; i<numdisks; i++) {
  200.     disks[0][i] = numdisks-i; 
  201.     disks[1][i] = 0;
  202.     disks[2][i] = 0;
  203.   }
  204.   topdisk[0] = numdisks;
  205.   topdisk[1] = 0;
  206.   topdisk[2] = 0;
  207. }
  208.  
  209. /* Write over *everything* in sight, including the borders and the title...
  210. */
  211. ClearWindow ()
  212. {
  213.   SetOPen  (HanoiRPort, windowcolor);
  214.   SetAPen  (HanoiRPort, windowcolor);
  215.   RectFill (HanoiRPort, 0L, 0L, (long)(width-1), (long)(height-1));
  216. }
  217.  
  218. static char titlestring[8] =  "X->X   ";
  219.  
  220. /* ShowMoveInfo will print out the current move being made. Note that
  221. ** this routine is NOT CALLED at all if the user specifies the text color
  222. ** to be the same as the window color... This routine does slow down the
  223. ** program, but it makes it a more educational tool...
  224. */
  225. ShowMoveInfo (fromtower, totower, ndisks)
  226. int fromtower, totower, ndisks;
  227. {
  228.   if (ndisks > 9) titlestring[5] = '0' + ndisks / 10;
  229.   else titlestring[5] = ' ';
  230.   titlestring[6] = '0' + ndisks % 10;
  231.   titlestring[0] = 'A' + fromtower;
  232.   titlestring[3] = 'A' + totower;
  233.  
  234.   SetAPen (HanoiRPort, textcolor);
  235.   SetDrMd (HanoiRPort, JAM2);
  236.   Move (HanoiRPort, 1L, 8L);
  237.   Text (HanoiRPort, "       ", 7L);
  238.   SetDrMd (HanoiRPort, JAM1);
  239.   Move (HanoiRPort, 1L, 8L);
  240.   Text (HanoiRPort, titlestring, 7L);
  241. }  
  242.       
  243.  
  244. /* This is the recursive Hanoi function! Looks simple, no?
  245. */
  246. MoveDisks (fromtower, totower, sparetower, ndisks)
  247. int fromtower, totower, sparetower, ndisks;
  248. {
  249.   if (writetext && width > MINWIDTHFORTEXT) {
  250.     ShowMoveInfo (fromtower, totower, ndisks);
  251.     Delay (TEXTDELAY * movedelay);
  252.     CheckForMessages ();
  253.   }
  254.  
  255.   if (ndisks == 1)  /* Base case */
  256.     MoveOneDisk (fromtower, totower);
  257.   else {
  258.     MoveDisks   (fromtower, sparetower, totower, ndisks-1);
  259.     MoveOneDisk (fromtower, totower);
  260.     MoveDisks   (sparetower, totower, fromtower, ndisks-1);
  261.   }
  262. }
  263.  
  264. /* This moves (graphically) the top disk from fromtower to totower.
  265. */
  266. MoveOneDisk (fromtower, totower)
  267. int fromtower, totower;
  268. {
  269.   int cnt;
  270.   int disk = disks[fromtower][topdisk[fromtower]-1];
  271.  
  272.   if (writetext && width > MINWIDTHFORTEXT) 
  273.     ShowMoveInfo (fromtower, totower, 1);
  274.  
  275.   for (cnt = topdisk[fromtower]; cnt <= numdisks; cnt++) {
  276.     DrawDiskAtLoc (disk, fromtower, cnt-1, windowcolor, windowcolor);
  277.     DrawDiskAtLoc (disk, fromtower, cnt, diskcolor, outlinecolor);
  278.     Delay (movedelay);
  279.   }
  280.  
  281.   topdisk[fromtower]--;
  282.   disks[fromtower][topdisk[fromtower]] = 0;
  283.   CheckForMessages ();
  284.  
  285.   if (fromtower < totower) 
  286.     for (cnt = fromtower+1; cnt <= totower; cnt++) {
  287.       DrawDiskAtLoc (disk, cnt-1, numdisks, windowcolor, windowcolor);
  288.       DrawDiskAtLoc (disk, cnt, numdisks, diskcolor, outlinecolor);
  289.       Delay (movedelay);
  290.     }
  291.   else 
  292.     for (cnt = fromtower-1; cnt >= totower; cnt--) {
  293.       DrawDiskAtLoc (disk, cnt+1, numdisks, windowcolor, windowcolor);
  294.       DrawDiskAtLoc (disk, cnt, numdisks, diskcolor, outlinecolor);
  295.       Delay (movedelay);
  296.     };
  297.  
  298.   CheckForMessages ();
  299.  
  300.   for (cnt = numdisks-1; cnt >= topdisk[totower]; cnt--) {
  301.     DrawDiskAtLoc (disk, totower, cnt+1, windowcolor, windowcolor);
  302.     DrawDiskAtLoc (disk, totower, cnt, diskcolor, outlinecolor);
  303.     Delay (movedelay);
  304.   }
  305.  
  306.   disks[totower][topdisk[totower]] = disk;
  307.   topdisk[totower]++;
  308.  
  309.   CheckForMessages ();  
  310. }
  311.  
  312. CheckForMessages ()
  313. {
  314.   struct IntuiMessage *message, *GetMsg();
  315.   ULONG  class;  /* What kind of message? */
  316.  
  317.   /* Try to get a message. If there is one, process it. */  
  318.  
  319.   while (message = GetMsg(HanoiWindow->UserPort)) {
  320.     class = message->Class;
  321.     ReplyMsg(message);
  322.     switch (class) {
  323.     case SIZEVERIFY    : Wait (1L << HanoiWindow->UserPort->mp_SigBit);
  324.                  break;
  325.         case NEWSIZE       : ReCalculateParameters();  /* Fall through */
  326.         case REFRESHWINDOW : ClearWindow(); 
  327.                              DrawAllDisks(diskcolor);
  328.                    break;
  329.         case CLOSEWINDOW   : CloseThings(0);  /* CloseThings exits */
  330.         default            : CloseThings(1);  /* CloseThings exits */
  331.     }
  332.   }  
  333. }
  334.  
  335. OpenLibraries ()
  336. {
  337.   if (!(IntuitionBase = OpenLibrary("intuition.library",0L))) 
  338.     Panic("No intuition library\n");
  339.   if (!(GfxBase = OpenLibrary("graphics.library",0L))) 
  340.     Panic("No graphics library\n");
  341. }  
  342.  
  343. /* Initializes the Hanoi window and sets up the HanoiRPort, used often. */
  344. SetupEnvironment()
  345. {
  346.   if (!(HanoiWindow = OpenWindow(&WindowInfo))) Panic ("Can't open window\n");
  347.   HanoiRPort = HanoiWindow->RPort;
  348.   SetBPen (HanoiRPort, windowcolor);
  349. }
  350.  
  351. /* Prints out an error message about what went wrong and exits gracefully */
  352. Panic(errormsg)
  353. char *errormsg;
  354. {
  355.   if (wbench) DisplayBeep (NULL);   /* Simply flash the display... */
  356.   else puts (errormsg);
  357.   CloseThings(1);
  358. }
  359.  
  360. /* Closes the Libraries that have been opened and frees up all memory */ 
  361. CloseThings(error_code)
  362. int error_code;
  363. { 
  364.   if (HanoiWindow)   CloseWindow(HanoiWindow);
  365.   if (GfxBase)       CloseLibrary(GfxBase);
  366.   if (IntuitionBase) CloseLibrary(IntuitionBase);
  367.   exit (error_code);
  368. }
  369.  
  370. int GetNum (prompt, min, max, def)
  371. int min, max, def;
  372. char *prompt;
  373. {
  374.   int   result, cnt;
  375.   char  resp[80];
  376.  
  377.   while (1) {
  378.     fputs (prompt, output); fflush (output);
  379.     fgets (resp, 80, input);
  380.     cnt = 0;
  381.     while (resp[cnt] == ' ') cnt++;
  382.     if (resp[cnt] == '\0' || resp[cnt] == '\n') return (def);
  383.     result = 0;
  384.     while (resp[cnt] != '\0' && resp[cnt] != '\n' &&
  385.            result <= max && result != -1) {
  386.       if (resp[cnt] < '0' || resp[cnt] > '9') result = -1;
  387.       else result = result * 10 + resp[cnt++] - '0';
  388.     };
  389.     if (result >= min && result <= max) return (result);
  390.     if (result == -1) fputs ("Illegal integer, please try again.\n", output);
  391.     else fputs ("Value out of range, please try again.\n", output);
  392.   }
  393. }
  394.  
  395. /* Opens a console window for fputs/fgets compatible I/O. Thanks to Tom
  396. ** Rokicki (from whose posting the last 4 lines of this routine come...).
  397. */
  398. int OpenInfoWindow ()
  399. {
  400.    static char consp[] = "CON:30/30/400/80/Hanoi by Ali Ozer";
  401.    consp[30] = 214; /* Guess what this does? Run the program and see */
  402.  
  403.    if ((output = fopen (consp, "w+")) == NULL) return (0);     
  404.    input = &temp;
  405.    *input = *output;
  406.    return (1);
  407. }
  408.  
  409. CloseInfoWindow ()
  410. {
  411.   fclose (input);
  412.   fclose (output);
  413. }
  414.  
  415. /* Gets a positive integer from argstr. If argstr is empty or "-", return
  416. ** defaultnum. Error if argstr is an invalid number or is not in range.
  417. */
  418. int GetArg (argstr, min, max, def)
  419. int min, max, def;
  420. char *argstr;
  421. {
  422.   int result = 0;
  423.   if (strlen(argstr) == 0 || !strcmp(argstr,"-")) return (def);
  424.   while (*argstr != '\0' && result <= max) {
  425.     if (*argstr < '0' || *argstr > '9') IllegalArgs();
  426.     result = result * 10 + *argstr++ - '0';
  427.   };
  428.   if (result >= min && result <= max) return (result);
  429.   IllegalArgs ();
  430. }
  431.  
  432. /* Prints usage line and causes program to terminate. Considering we only
  433. ** call GetArg once we know we were called from CLI, we can safely do puts.
  434. */
  435. IllegalArgs ()
  436. {
  437.   puts ("\nUsage:\nHanoi NDisks Speed BGColor TxtColor DskColor OutLineColor X Y Priority");
  438.   puts (" NDisks 1..25, Speed 0..12, Colors 0..3 (WorkBench colors)");
  439.   puts (" Priority 0..8 (Corresponding to -20..+20)");
  440.   puts (" All arguments are optional. Use - to get a default value.\n");
  441.   CloseThings (1);
  442. }
  443.