home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 13 / 13.iso / p / p024 / 12.img / ADS2.LIB / TOWER.C < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-17  |  11.9 KB  |  482 lines
  1. /* Next available MSG number is  20 */
  2.  
  3. /*
  4.       TOWER.C
  5.       ¬⌐┼v (C) 1988-1992  Autodesk ñ╜Ñq
  6.  
  7.       Ñ╗│n┼ΘºK╢O¿╤▒z╢iªµÑ⌠ª≤Ñ╬│~╗▌¿D¬║½■¿⌐íB¡╫º∩ñ╬╡oªµ, ª²¼O░╚╜╨┐φ┤`ñU¡z
  8.       ¡∞½h :
  9.  
  10.       1)  ñWªC¬║¬⌐┼v│qºi░╚╗▌ÑX▓{ªb¿Cñ@Ñ≈½■¿⌐∙╪íC
  11.       2)  ¼█├÷¬║╗í⌐·ñσÑ≤ñ]Ñ▓╢╖⌐·╕ⁿ¬⌐┼v│qºiñ╬Ñ╗╢╡│\Ñi│qºiíC
  12.  
  13.       Ñ╗│n┼Θ╢╚┤ú¿╤º@¼░└│Ñ╬ñW¬║░╤ª╥, ª╙Ñ╝┴n⌐·⌐╬┴⌠ºtÑ⌠ª≤½O├╥; ╣∩⌐≤Ñ⌠ª≤»S«φ
  14.       Ñ╬│~ñº╛A║┘⌐╩, ÑHñ╬░╙╖~╛P░Γ⌐╥┴⌠ºtÑX¿π¬║½O├╥, ªbª╣ñ@╖ºñ⌐ÑHº_╗{íC
  15.  
  16.  
  17.  
  18.         Tower of Hanoi in C
  19.  
  20.         Implemented by John Lynch   December 1988
  21.  
  22.         This is basically a translation of tower.lsp written by
  23.         Kelvin R. Throop.
  24.  
  25.        This file implements the Tower of Hanoi problem.  It is as
  26.        specified in the rules:
  27.  
  28.           1.  Only one disc may be moved at a time.
  29.           2.  No disc may be placed on top of a smaller one.
  30.  
  31.        The only incompatibility with the original is that the universe
  32.        will not come to an end when this function completes (however, if
  33.        you run it with the specified number of discs, 64, the protons may
  34.        decay before it's done).
  35.  
  36.        One defines the tower with the command TOWER, which asks for the
  37.        number of discs.  Scaling is automatic, as is clearing away of any
  38.        previous execution.  Once the tower is defined, the solution may
  39.        be accomplished with the command SOLVE.
  40.  
  41.        The solution function, TRANSFER, is as given in Winston and Horn,
  42.        "LISP", second edition, pp. 112-114.
  43.  
  44.  
  45. */
  46.  
  47. #include  <stdio.h>
  48. #include  <string.h>
  49. #include  "adslib.h"
  50.  
  51.  
  52. /* Local functions */
  53. static int loadfuncs _((void));
  54. static int dofun _((void));
  55. static int tower2 _((void));
  56. static int solve2 _((void));
  57. #ifdef __ZTC__
  58. static int movedisc _((int from, int to));
  59. static int transfer _((int from, int to, int spare, int n));
  60. #else
  61. static int movedisc _((short from, short to));
  62. static int transfer _((short from, short to, short spare, short n));
  63. #endif
  64.  
  65.  
  66. /* For convenience, make the global variables the same as in the LISP
  67.    version */
  68.  
  69. int nrings = 0,                       /* Number of rings */
  70.     before = 0,                       /* Whether or not we have run before */
  71.     armed = 0;                        /* Set if we are ready to solve */
  72.  
  73. ads_real bthick = 1.0,                /* Base thickness */
  74.          rthick = 1.0,                /* Ring thickness */
  75.          smring = 1.5,                /* Smallest ring */
  76.          ringinc = 1.0,               /* Ring size increment */
  77.          postdia = 1.0,               /* Post diameter */
  78.          airspace = 0.1,              /* Airspace */
  79.          rspace = 1.1,                /* Total ring space */
  80.          postposx[3],
  81.          postposy;
  82.  
  83.  
  84. /* Some of the common strings used to call AutoCAD's Command processor */
  85.  
  86. char layer[] = /*MSG0*/"_.layer",
  87.      vpoint[] = /*MSG0*/"_.vpoint",
  88.      erase[] = /*MSG0*/"_.erase",
  89.      new[] = /*MSG0*/"_new",
  90.      set[] = /*MSG0*/"_set",
  91.      base[] = /*MSG6*/"base",
  92.      basetc[] = /*MSG7*/"base,1,2,3,4,5,6",
  93.      color[] = /*MSG0*/"_color",
  94.      elev[] = /*MSG0*/"_.elev",
  95.      solid[] = /*MSG0*/"_.solid",
  96.      zoom[] = /*MSG0*/"_.zoom",
  97.      circle[] = /*MSG0*/"_.circle",
  98.      origin[] = "0,0,0",
  99.      oneoneone[] = "1,1,1",
  100.      d[] = /*MSG0*/"_d",
  101.      l[] = /*MSG0*/"_l",
  102.      e[] = /*MSG0*/"_e",
  103.      nullstring[] = "";
  104.  
  105.  
  106. /* The postlist structure is used to hold the disks */
  107. struct disk {
  108.      struct disk *next;
  109.      short layer;
  110.      ads_real r;
  111. };
  112.  
  113. struct postlist {
  114.      struct disk *top;
  115.      short count;
  116. };
  117.  
  118. struct disk *disks;
  119. struct postlist postl[3];
  120.  
  121.  
  122. /* MAIN -- the main routine */
  123. void
  124. main(argc,argv)
  125.   int argc; char *argv[];
  126. {
  127.     int stat;
  128.     short scode = RSRSLT;
  129.  
  130.     ads_init(argc, argv);
  131.  
  132.     for ( ;; ) {
  133.  
  134.         if ((stat = ads_link(scode)) < 0) {
  135.             printf(/*MSG16*/"TOWER: Ñ╤ ads_link() ╢╟ª^¬║ñú¿╬¬¼║A = %d\n", stat);
  136.             fflush(stdout);
  137.             exit(1);
  138.         }
  139.  
  140.         scode = RSRSLT;               /* default return code */
  141.  
  142.         /* process the AutoLisp request */
  143.         switch (stat) {
  144.  
  145.         case RQXLOAD:                 /* register our function names */
  146.             scode = loadfuncs() ? -RSRSLT : -RSERR;
  147.             break;
  148.  
  149.         case RQXUNLD:                 /* unload our functions */
  150.             break;
  151.  
  152.         case RQSUBR:                  /* execute registered function */
  153.             dofun();
  154.             break;
  155.  
  156.         default:
  157.             break;
  158.         }
  159.     }
  160. }
  161.  
  162.  
  163.  
  164. /* LOADFUNCS  --  Register (or define) external functions with AutoLISP */
  165. static int
  166. loadfuncs()
  167. {
  168.     if (!ads_defun(/*MSG0*/"C:TOWER2", 0))        /* tower2 command has id 0 */
  169.         return 0;
  170.     if (!ads_defun(/*MSG0*/"C:SOLVE2", 1))        /* solve2 command has id 1 */
  171.         return 0;
  172.  
  173.     ads_printf(/*MSG17*/"\
  174. ╣BÑ╬ tower2 ¿╙ªµíu▒╥⌐lív, ª╙ÑH solve2 ¿╙╕╤¿Míu╢≡ (tower)ív¬║░▌├D\n");
  175.  
  176.     return 1;
  177. }
  178.  
  179. /* Execute registered functions here */
  180. static int
  181. dofun()
  182. {
  183.     int id;
  184.  
  185.     /* Get the function id */
  186.     if ((id = ads_getfuncode()) < 0)
  187.         return 0;
  188.  
  189.     /* No arguments are passed as a part of C:XXX functions */
  190.  
  191.  
  192.     switch (id) {                     /* Which function is being called */
  193.     case 0:
  194.         if (!tower2())
  195.             return 0;
  196.         break;
  197.  
  198.     case 1:
  199.         if (!solve2())
  200.             return 0;
  201.         break;
  202.     }
  203.     return 1;
  204. }
  205.  
  206. /* Handle setup of tower */
  207.  
  208. static int
  209. tower2()
  210. {
  211.     ads_real lring;                   /* largest ring diameter */
  212.     int a, i;
  213.     ads_real bwidth, blength;         /* width and length of base */
  214.     ads_real x, y, z, r;
  215.     struct resbuf genrb;
  216.     ads_point pt1, pt2, pt3, pt4;
  217.  
  218.     bthick = rthick = ringinc = postdia = 1.0;
  219.     smring = 1.5;
  220.     airspace = 0.1;
  221.     rspace = 1.1;
  222.  
  223.  
  224.     ads_getint(/*MSG18*/"┐ΘñJíu└⌠ (ring)ív╝╞╢q: ", &nrings);
  225.  
  226.     lring = smring + (nrings * ringinc);
  227.  
  228.     /* reset from possible previous run */
  229.  
  230.     postl[0].top   = postl[1].top   = postl[2].top = NULL;
  231.     postl[0].count = postl[1].count = postl[2].count = 0;
  232.  
  233.  
  234.     disks = (struct disk *) malloc ((nrings + 1) * (sizeof (struct disk)));
  235.  
  236.     rspace = rthick + airspace;       /* Actual ring spacing */
  237.  
  238.     /* set up the appropriate environment variables */
  239.     genrb.restype = RTSHORT;
  240.     genrb.resval.rint = 0;
  241.     ads_setvar(/*MSG0*/"blipmode", &genrb);
  242.     ads_setvar(/*MSG0*/"cmdecho", &genrb);
  243.     ads_setvar(/*MSG0*/"fillmode", &genrb);
  244.  
  245.  
  246.     if (before) {
  247.  
  248.         ads_command(RTSTR, vpoint, RTSTR, origin, NULL);
  249.  
  250.         a = 1;
  251.  
  252.         while (a <= before) {
  253.  
  254.             ads_command(RTSTR, erase, RTSTR, l, RTSTR, nullstring, NULL);
  255.  
  256.             a++;
  257.  
  258.         }
  259.  
  260.         ads_command(RTSTR, layer, RTSTR, set, RTSTR, base, RTSTR,
  261.                     nullstring, NULL);
  262.  
  263.     } else {
  264.  
  265.         /* Note:  this leave the command function "open" (non-terminated) */
  266.         if (!ads_tblsearch (/*MSG0*/"layer", base, 1))
  267.             ads_command(RTSTR, layer, RTSTR, new, RTSTR, basetc, RTSTR, color,
  268.                         RTSHORT, 7, RTSTR, base, NULL);
  269.  
  270.  
  271.         a = 0;
  272.  
  273.         while (++a <= 6) {
  274.  
  275.             ads_command(RTSTR, color, RTSHORT, a, RTSHORT, a, NULL);
  276.         }
  277.  
  278.         /* Set the current layer (command still "open") */
  279.  
  280.  
  281.         ads_command(RTSTR, set, RTSTR, base, RTSTR, nullstring, NULL);
  282.  
  283.     }
  284.  
  285.     /* Draw the base */
  286.  
  287.     /* Command: "elev" 0.0 bthick */
  288.  
  289.     ads_command(RTSTR, elev, RTREAL, 0.0, RTREAL, bthick, NULL);
  290.  
  291.  
  292.     bwidth = lring + 2 * postdia;
  293.     blength = 3 * (postdia + lring) + postdia;
  294.  
  295.     ads_command(RTSTR, vpoint, RTSTR, origin, NULL);
  296.  
  297.     pt1[X] = pt1[Y] = 0.0;
  298.     pt2[Y] = pt4[Y] = bwidth;
  299.     pt3[X] = pt4[X] = blength;
  300.     pt2[X] = pt3[Y] = 0.0;
  301.  
  302.     ads_command(RTSTR, solid, RTPOINT, pt1, RTPOINT, pt2, RTPOINT, pt3,
  303.                 RTPOINT, pt4, NULL);
  304.  
  305.  
  306.     /* We must use ads_command(0) for ads_command(NULL) to be compatible */
  307.     ads_command(0);
  308.  
  309.     ads_command(RTSTR, zoom, RTSTR, e, NULL);
  310.  
  311.     /* Draw the posts */
  312.  
  313.     /* Set the elevation through the command function */
  314.     ads_command(RTSTR, elev, RTREAL, bthick, RTREAL,
  315.                 (nrings + 1) * rspace, NULL);
  316.  
  317.     x = postdia + lring;
  318.     y = lring / 2 + postdia;
  319.  
  320.     postposx[0] = y;
  321.     postposx[1] = y + x;
  322.     postposx[2] = y + x + x;
  323.  
  324.     postposy = postdia + lring / 2;
  325.  
  326.     pt1[Y] = postposy;
  327.  
  328.     for (i = 0; i < 3; i++) {
  329.         pt1[X] = postposx[i];
  330.         ads_command(RTSTR, circle, RTPOINT, pt1, RTSTR, d, RTREAL,
  331.                     postdia, NULL);
  332.     }
  333.  
  334.     bthick += airspace;               /* Offset position of lowest ring */
  335.  
  336.     ads_command(RTSTR, vpoint, RTSTR, oneoneone, NULL);
  337.  
  338.  
  339.     /* Draw the rings, placing them on post 1 initially */
  340.  
  341.     pt1[X] = y;
  342.     pt1[Y] = postposy;
  343.  
  344.     a = 6;
  345.     z = bthick;
  346.     r = lring / 2;
  347.     for (i = 1; i <= nrings; i++) {
  348.  
  349.         /* Command: "layer" "set" (l%6 + 1) ""  */
  350.         ads_command(RTSTR, layer, RTSTR, set, RTSHORT, a%6 + 1,
  351.                     RTSTR, nullstring, NULL);
  352.  
  353.         /* Command:  "elev" z rthick  */
  354.  
  355.         ads_command(RTSTR, elev, RTREAL, z, RTREAL, rthick, NULL);
  356.  
  357.         /* Command: "circle" (m postposy) r  */
  358.  
  359.         pt1[Z] = z;
  360.         ads_command(RTSTR, circle, RTPOINT, pt1, RTREAL, r, NULL);
  361.  
  362.  
  363.         /* Hang it on the postlist */
  364.         disks[i].layer = a%6 + 1;
  365.         disks[i].r = r;
  366.         disks[i].next = postl[0].top;
  367.  
  368.  
  369.         postl[0].top = &disks[i];
  370.         postl[0].count++;
  371.  
  372.         r -= ringinc / 2;
  373.         z += rspace;
  374.         a++;
  375.  
  376.  
  377.     }
  378.  
  379.     before = nrings + 4;
  380.  
  381.     genrb.restype = RTSHORT;
  382.     genrb.resval.rint = 0;
  383.     ads_setvar(/*MSG0*/"cmdecho", &genrb);
  384.  
  385.     armed = TRUE;
  386.     ads_retvoid();
  387.  
  388.     return TRUE;
  389.  
  390. }
  391.  
  392. /* Solve the tower problem. */
  393.  
  394. static int
  395. solve2()
  396. {
  397.     if (!armed) {
  398.         ads_printf(/*MSG19*/"╕╤├Dñº½eÑ▓╢╖Ѳ░⌡ªµíutower2ív\n");
  399.         return TRUE;
  400.     } else
  401.         armed = FALSE;
  402.  
  403.     transfer(1, 2, 3, nrings);
  404.     ads_redraw(NULL, 0);
  405.     ads_retvoid();
  406.     return  TRUE;
  407. }
  408.  
  409. static int
  410. movedisc(from, to)
  411.   short from, to;
  412. {
  413.     struct disk *lfrom, *lto;
  414.     ads_point pt;
  415.  
  416.     /* Get the current heads of the to and from lists */
  417.     lfrom = postl[from - 1].top;
  418.     lto = postl[to - 1].top;
  419.  
  420.     /* Remove this disk from the head of the from list */
  421.     postl[from - 1].top = lfrom->next;
  422.     postl[from - 1].count--;
  423.  
  424.     /* Command: "layer" "set" lfrom->layer "" */
  425.  
  426.     ads_command(RTSTR, layer, RTSTR, set, RTSHORT, lfrom->layer,
  427.                 RTSTR, nullstring, NULL);
  428.  
  429.     /* Command: "elev" b rthick */
  430.  
  431.     ads_command(RTSTR, elev, RTREAL, bthick + rspace * postl[from - 1].count,
  432.                 RTREAL, rthick, NULL);
  433.  
  434.  
  435.     /* Command: "erase" postposx[from - 1], postposy+lfrom->r ""  */
  436.  
  437.     pt[X] = postposx[from - 1];
  438.     pt[Y] = postposy + lfrom->r;
  439.     pt[Z] = bthick + rspace * postl[from-1].count;
  440.  
  441.     ads_command(RTSTR, erase, RTPOINT, pt, RTSTR, nullstring, NULL);
  442.  
  443.     /* Command: "elev" (bthick + postl[to-1]->count*rspace  rthick */
  444.  
  445.     ads_command(RTSTR, elev, RTREAL, bthick + postl[to-1].count * rspace,
  446.                 RTREAL, rthick, NULL);
  447.  
  448.  
  449.     /* Command: "circle" postpostx[to - 1],postposy lfrom->r */
  450.  
  451.     pt[X] = postposx[to - 1];
  452.     pt[Y] = postposy;
  453.     pt[Z] = bthick + postl[to-1].count * rspace;
  454.  
  455.     ads_command(RTSTR, circle, RTPOINT, pt, RTREAL, lfrom->r, NULL);
  456.  
  457.  
  458.     /* Place the disk on the top of the to list */
  459.     lfrom->next = lto;
  460.     postl[to - 1].top = lfrom;
  461.     postl[to - 1].count++;
  462.  
  463.     return TRUE;
  464. }
  465.  
  466.  
  467. static int
  468. transfer(from, to, spare, n)
  469.   short from, to, spare, n;
  470. {
  471.     if (n == 0)
  472.         return TRUE;
  473.     else if (n == 1)
  474.         movedisc(from, to);
  475.     else {
  476.         transfer(from, spare, to, n - 1);
  477.         movedisc(from, to);
  478.         transfer(spare, to, from, n - 1);
  479.     }
  480.     return TRUE;
  481. }
  482.