Ensure that the random hop delta does make the cave connected. Based

on bug report and patch from <afghan@afghanhound.org.uk>.

diff --git a/wump/wump.c b/wump/wump.c
index afd1bee0038c4fb00c4ce6f3182df525901f4b05..4147d14be92bfb13e03c07f45eca7b40d9e5f4d3 100644 (file)
--- a/wump/wump.c
+++ b/wump/wump.c
@@ -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 @@ __COPYRIGHT("@(#) Copyright (c) 1989, 1993\n\
 #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 @@ int bats_nearby __P((void));
 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 @@ The arrow is weakly shot and can go no further!\n");
        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 @@ cave_init()
                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 */