From 5b23f76c7ea20190dc727fc1cbc9537ace72ff7b Mon Sep 17 00:00:00 2001 From: jsm Date: Fri, 31 Aug 2001 07:16:22 +0000 Subject: Ensure that the random hop delta does make the cave connected. Based on bug report and patch from . --- wump/wump.c | 27 +++++++++++++++++++++++---- 1 file changed, 23 insertions(+), 4 deletions(-) (limited to 'wump') diff --git a/wump/wump.c b/wump/wump.c index afd1bee0..4147d14b 100644 --- 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 */ -- cgit v1.2.3-56-ge451