[src/trunk]: src/games/wump Ensure that the random hop delta does make the ca...

[jsm <jsm%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/e02fddd408d0
branches:  trunk
changeset: 514377:e02fddd408d0
user:      jsm <jsm%NetBSD.org@localhost>
date:      Fri Aug 31 07:16:22 2001 +0000

description:
Ensure that the random hop delta does make the cave connected.  Based
on bug report and patch from <afghan%afghanhound.org.uk@localhost>.

diffstat:

 games/wump/wump.c |  27 +++++++++++++++++++++++----
 1 files changed, 23 insertions(+), 4 deletions(-)

diffs (62 lines):

diff -r d12da35c67e2 -r e02fddd408d0 games/wump/wump.c
--- a/games/wump/wump.c Fri Aug 31 07:15:44 2001 +0000
+++ b/games/wump/wump.c Fri Aug 31 07:16:22 2001 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: wump.c,v 1.13 2000/05/08 07:56:06 mycroft Exp $        */
+/*     $NetBSD: wump.c,v 1.14 2001/08/31 07:16:22 jsm Exp $    */
 
 /*
  * Copyright (c) 1989, 1993
@@ -47,7 +47,7 @@
 #if 0
 static char sccsid[] = "@(#)wump.c     8.1 (Berkeley) 5/31/93";
 #else
-__RCSID("$NetBSD: wump.c,v 1.13 2000/05/08 07:56:06 mycroft Exp $");
+__RCSID("$NetBSD: wump.c,v 1.14 2001/08/31 07:16:22 jsm Exp $");
 #endif
 #endif /* not lint */
 
@@ -120,6 +120,7 @@
 void   cave_init __P((void));
 void   clear_things_in_cave __P((void));
 void   display_room_stats __P((void));
+int    gcd __P((int, int));
 int    getans __P((const char *));
 void   initialize_things_in_cave __P((void));
 void   instructions __P((void));
@@ -520,6 +521,18 @@
        return(0);
 }
 
+int
+gcd(a, b)
+       int a, b;
+{
+       int r;
+
+       r = a % b;
+       if (r == 0)
+               return (b);
+       return (gcd(b, r));
+}
+
 void
 cave_init()
 {
@@ -542,8 +555,14 @@
                for (j = 0; j < link_num ; ++j)
                        cave[i].tunnel[j] = -1;
 
-       /* choose a random 'hop' delta for our guaranteed link */
-       while (!(delta = random() % room_num));
+       /*
+        * Choose a random 'hop' delta for our guaranteed link.
+        * To keep the cave connected, we need the greatest common divisor
+        * of (delta + 1) and room_num to be 1.
+        */
+       do {
+               delta = (random() % (room_num - 1)) + 1;
+       } while (gcd(room_num, delta + 1) != 1);
 
        for (i = 1; i <= room_num; ++i) {
                link = ((i + delta) % room_num) + 1;    /* connection */