chris@umcp-cs.UUCP (07/08/83)
Well, now that you've all been thinking "what do we do with this
wonderful window software" (either that or "why is he sending out this
junk") I have a sample program. It's a variation on that old favorite,
Towers of Hanoi. This one has a twist! It does any number of pegs
from 2 to 40 (though you'll never fit 40 on a screen) with up to 40
discs. It shows off almost no capabilities, using neither inverse
video nor fancy updates (well, it does do character ins/del on some
terminals); it's not at all useful; but it's fun.
It's interesting to watch it do 10 discs on 3 pegs, compared to 10
discs on 4 pegs (use "hanoi -qq 10 3" and "hanoi -qq 10 4"), to see
just how the complexity of the problem changes.
By the way, we haven't been able to prove that the algorithm used
generates the mininal number of moves. Can anyone either prove it or
come up with a better algorithm?
Anyway, here's hanoi.c.
- Chris
: Run this shell script with "sh" not "csh"
PATH=:/bin:/usr/bin:/usr/ucb
export PATH
all=FALSE
if [ $1x = -ax ]; then
all=TRUE
fi
/bin/echo 'Extracting hanoi.c'
sed 's/^X//' <<'//go.sysin dd *' >hanoi.c
X#ifndef lint
Xstatic char sccsid[] = "@(#)hanoi.c U of Maryland ACT 24-Apr-1983";
X#endif
X
X#include <stdio.h>
X#include <local/window.h>
X
X#define MAXDISCS 40
X#define MAXPEGS 40
X#define MAXWINS 10
X
X/* Upper left corner of given peg */
X#define WIN(p) wins[(p)/perrow]
X#define TR(p) 0
X /* (((p)/perrow) * discs2) */
X#define TC(p) (((p)%perrow) * widest)
X
XWin *wins[MAXWINS];
Xint discs, pegs, rows, perrow, widest,
X towerdepth[MAXPEGS], qflag, discs2, K[MAXDISCS][MAXPEGS];
X
Xmain (argc, argv)
Xregister argc;
Xregister char **argv;
X{
X register i, j;
X char *prog = *argv;
X int nr, nc;
X char usepegs[MAXPEGS];
X
X while (argc > 1 && argv[1][0] == '-') {
X argc--;
X ++*++argv;
X while (**argv) switch (*(*argv)++) {
X case 'q':
X qflag++;
X break;
X default:
X fprintf (stderr, "%s: option '%c' not recognized.\n",
X prog, argv[0][-1]);
Xusage:
X fprintf (stderr, "Usage: %s [-q] [ndisks [npegs]]",
X prog);
X exit (1);
X }
X }
X if (argc == 1)
X discs = 8, pegs = 4;
X else if (argc == 2)
X discs = atoi (argv[1]), pegs = 4;
X else if (argc == 3)
X discs = atoi (argv[1]), pegs = atoi (argv[2]);
X else
X goto usage;
X if (discs < 2)
X discs = 2;
X if (pegs < 3)
X pegs = 3;
X if (Winit (0, 0)) {
X fprintf (stderr, "%s: can't run windows, forget it\n", prog);
X exit (1);
X }
X Wscreensize (&nr, &nc);
X if (discs > MAXDISCS)
X discs = MAXDISCS;
X if ((discs2 = discs + 2) > nr) {
X discs = nr - 2;
X discs2 = nr;
X }
X if (pegs > MAXPEGS)
X pegs = MAXPEGS;
X widest = (discs + 1) * 2;
X rows = nr / discs2; /* How many rows will fit? */
X perrow = nc / widest; /* How many discs will fit per row? */
X if (perrow == 0) {
Xtoobig:
X Wcleanup ();
X fprintf (stderr, "%s: try smaller values\n", prog);
X exit (1);
X }
X if (perrow * rows < pegs) {
X pegs = perrow * rows;
X if (pegs < 3)
X goto toobig;
X }
X rows = (pegs + perrow - 1) / perrow;
X
X nc = widest * (rows == 1 ? pegs : perrow);
X nr -= rows * discs2;
X if (nr)
X nr--;
X for (i = 0; i < rows; i++) {
X wins[i] = Wopen (0, 0, nr + i * discs2, nc, discs2, 0, 0);
X if (wins[i] == 0) {
X Wcleanup ();
X fprintf (stderr, "%s: window open failed\n", prog);
X exit (1);
X }
X Wwrap (wins[i], 0);
X Woncursor (wins[i], 0);
X }
X
X for (i = 0; i < pegs; i++) {
X register Win *w = WIN(i);
X
X WAcursor (w, TR(i) + discs + 1, TC(i));
X for (j = widest/2 - 1; --j >= 0; )
X Wputc ('-', w);
X Wputc ('+', w);
X for (j = widest/2 - 1; --j >= 0; )
X Wputc ('-', w);
X }
X for (i = 1; i <= discs; i++)
X for (j = 0; j < pegs; j++)
X Draw (i, i, j, 0, j == 0);
X i = pegs - 1;
X for (j = 1; j < i; j++)
X usepegs[j] = 1;
X usepegs[0] = 0;
X usepegs[i] = 0;
X towerdepth[0] = discs;
X Wrefresh (0);
X SeedKArray (discs, pegs - 2);
X MoveTower (discs, 0, pegs - 1, usepegs, 0);
X Wexit (0);
X}
X
XSeedKArray (n, p)
Xregister n, p;
X{
X register i, l;
X
X for (l = 0; ! (l && K[l-1][p] > n); l++)
X for (i = 0; i <= p; i++)
X K[l][i] = i==0 || l==0 ? 1 : K[l-1][i]+K[l][i-1];
X}
X
XMoveTower (n, from, to, others, base)
Xregister n, from, to;
Xregister char *others;
Xint base;
X{
X char lothers[MAXPEGS];
X int nums[MAXPEGS], len = 0, b = base;
X register i;
X
X for (i = 0; i < pegs; i++)
X if (lothers[i] = others[i])
X len++;
X spread (n, len, nums, others);
X lothers[to] = 1;
X for (i = 0; i < pegs; i++) {
X if (nums[i]) {
X lothers[i] = 0;
X MoveTower (nums[i], from, i, lothers, b);
X b += nums[i];
X }
X }
X MoveADisc (n + base, from, to);
X for (i = 0; i < pegs; i++)
X lothers[i] = 0;
X lothers[from] = 1;
X for (i = pegs; --i >= 0; ) {
X if (nums[i]) {
X b -= nums[i];
X MoveTower (nums[i], i, to, lothers, b);
X lothers[i] = 1;
X }
X }
X}
X
Xspread (n, p, nums, others)
Xregister n, p, *nums;
Xregister char *others;
X{
X register i, l, extra, tmp;
X
X for (l = 0; K[l][p] <= n; l++)
X ;
X l--;
X extra = l >= 0 ? n - K[l][p] : (l = 0);
X for (i = 0; i < pegs; i++) {
X if (!others[i]) {
X nums[i] = 0;
X continue;
X }
X nums[i] = l ? K[l-1][p] : 0;
X if (extra) {
X tmp = K[l][p] - nums[i];
X if (tmp > extra)
X tmp = extra;
X extra -= tmp;
X nums[i] += tmp;
X }
X p--;
X }
X}
X
XDraw (disc, yoffset, peg, xoffset, c)
Xregister disc, peg, c;
Xint yoffset, xoffset;
X{
X register i;
X register Win *w = WIN(peg);
X
X c = c ? 'x' : ' ';
X WAcursor (w, TR(peg)+yoffset, TC(peg)+xoffset + widest/2 - disc - 1);
X for (i = disc; --i >= 0; )
X Wputc (c, w);
X Wputc (yoffset ? '|' : c, w);
X for (i = disc; --i >= 0; )
X Wputc (c, w);
X}
X
XMoveADisc (n, from, to)
Xregister n, from, to;
X{
X register i, j, k;
X
X /* Should it just 'blip' to where it goes? */
X if (qflag > 1) {
X Draw (n, discs - --towerdepth[from], from, 0, 0);
X Draw (n, discs - towerdepth[to]++, to, 0, 1);
X Wrefresh (0);
X return;
X }
X
X /* Draw the disc moving up the peg */
X for (i = discs - --towerdepth[from]; --i >= 0; ) {
X Draw (n, i+1, from, 0, 0);
X Draw (n, i, from, 0, 1);
X Wrefresh (0);
X }
X if (!qflag && WIN(from) == WIN(to)) {
X /* Now move the disc along the top */
X
X k = to - from;
X j = k < 0 ? -1 : 1;
X k *= widest;
X for (i = j; i != k; i += j) {
X Draw (n, 0, from, i - j, 0);
X Draw (n, 0, from, i, 1);
X Wrefresh (0);
X }
X Draw (n, 0, to, -j, 0);
X Draw (n, 0, to, 0, 1);
X Wrefresh (0);
X }
X else {
X /* Just 'blip' it from one tower to the other */
X
X Draw (n, 0, from, 0, 0);
X Draw (n, 0, to, 0, 1);
X Wrefresh (0);
X }
X
X /* And now move it down the 'to' peg */
X
X j = discs - towerdepth[to]++;
X for (i = 0; i < j; i++) {
X Draw (n, i, to, 0, 0);
X Draw (n, i+1, to, 0, 1);
X Wrefresh (0);
X }
X}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 hanoi.c
/bin/echo -n ' '; /bin/ls -ld hanoi.c
fi
--
UUCP: {seismo,allegra,brl-bmd}!umcp-cs!chris
CSNet: chris@umcp-cs
ARPA: chris.umcp-cs@UDel-Relay