Fictitious VM pages must remain structurally stable after free.
[dragonfly.git] / games / arithmetic / arithmetic.c
1 /*
2  * Copyright (c) 1989, 1993
3  *      The Regents of the University of California.  All rights reserved.
4  *
5  * This code is derived from software contributed to Berkeley by
6  * Eamonn McManus of Trinity College Dublin.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
15  *    documentation and/or other materials provided with the distribution.
16  * 3. All advertising materials mentioning features or use of this software
17  *    must display the following acknowledgement:
18  *      This product includes software developed by the University of
19  *      California, Berkeley and its contributors.
20  * 4. Neither the name of the University nor the names of its contributors
21  *    may be used to endorse or promote products derived from this software
22  *    without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34  * SUCH DAMAGE.
35  *
36  * @(#) Copyright (c) 1989, 1993 The Regents of the University of California.  All rights reserved.
37  * @(#)arithmetic.c     8.1 (Berkeley) 5/31/93
38  * $FreeBSD: src/games/arithmetic/arithmetic.c,v 1.10 1999/12/12 06:40:28 billf Exp $
39  * $DragonFly: src/games/arithmetic/arithmetic.c,v 1.4 2005/04/24 15:31:30 liamfoy Exp $
40  */
41
42 /*
43  * By Eamonn McManus, Trinity College Dublin <emcmanus@cs.tcd.ie>.
44  *
45  * The operation of this program mimics that of the standard Unix game
46  * `arithmetic'.  I've made it as close as I could manage without examining
47  * the source code.  The principal differences are:
48  *
49  * The method of biasing towards numbers that had wrong answers in the past
50  * is different; original `arithmetic' seems to retain the bias forever,
51  * whereas this program lets the bias gradually decay as it is used.
52  *
53  * Original `arithmetic' delays for some period (3 seconds?) after printing
54  * the score.  I saw no reason for this delay, so I scrapped it.
55  *
56  * There is no longer a limitation on the maximum range that can be supplied
57  * to the program.  The original program required it to be less than 100.
58  * Anomalous results may occur with this program if ranges big enough to
59  * allow overflow are given.
60  *
61  * I have obviously not attempted to duplicate bugs in the original.  It
62  * would go into an infinite loop if invoked as `arithmetic / 0'.  It also
63  * did not recognise an EOF in its input, and would continue trying to read
64  * after it.  It did not check that the input was a valid number, treating any
65  * garbage as 0.  Finally, it did not flush stdout after printing its prompt,
66  * so in the unlikely event that stdout was not a terminal, it would not work
67  * properly.
68  */
69
70 #include <sys/types.h>
71 #include <sys/signal.h>
72 #include <ctype.h>
73 #include <stdio.h>
74 #include <string.h>
75 #include <stdlib.h>
76 #include <time.h>
77 #include <unistd.h>
78
79 const char keylist[] = "+-x/";
80 const char defaultkeys[] = "+-";
81 const char *keys = defaultkeys;
82 int nkeys = sizeof(defaultkeys) - 1;
83 int rangemax = 10;
84 int nright, nwrong;
85 time_t qtime;
86 #define NQUESTS 20
87
88 static void usage (void);
89 int getrandom (int, int, int);
90 void intr (int);
91 int opnum (int);
92 void penalise (int, int, int);
93 int problem (void);
94 void showstats (void);
95
96 /*
97  * Select keys from +-x/ to be asked addition, subtraction, multiplication,
98  * and division problems.  More than one key may be given.  The default is
99  * +-.  Specify a range to confine the operands to 0 - range.  Default upper
100  * bound is 10.  After every NQUESTS questions, statistics on the performance
101  * so far are printed.
102  */
103 int
104 main(int argc, char **argv)
105 {
106         int ch, cnt;
107
108         /* Revoke setgid privileges */
109         setgid(getgid());
110
111         while ((ch = getopt(argc, argv, "r:o:")) != -1)
112                 switch(ch) {
113                 case 'o': {
114                         const char *p;
115
116                         for (p = keys = optarg; *p; ++p)
117                                 if (!index(keylist, *p)) {
118                                         (void)fprintf(stderr,
119                                             "arithmetic: unknown key.\n");
120                                         exit(1);
121                                 }
122                         nkeys = p - optarg;
123                         break;
124                 }
125                 case 'r':
126                         if ((rangemax = atoi(optarg)) <= 0) {
127                                 (void)fprintf(stderr,
128                                     "arithmetic: invalid range.\n");
129                                 exit(1);
130                         }
131                         break;
132                 case '?':
133                 default:
134                         usage();
135                 }
136         if (argc -= optind)
137                 usage();
138
139         /* Seed the random-number generator. */
140         srandomdev();
141
142         (void)signal(SIGINT, intr);
143
144         /* Now ask the questions. */
145         for (;;) {
146                 for (cnt = NQUESTS; cnt--;)
147                         if (problem() == EOF)
148                                 exit(0);
149                 showstats();
150         }
151         /* NOTREACHED */
152 }
153
154 /* Handle interrupt character.  Print score and exit. */
155 void
156 intr(__unused int sig)
157 {
158         showstats();
159         exit(0);
160 }
161
162 /* Print score.  Original `arithmetic' had a delay after printing it. */
163 void
164 showstats(void)
165 {
166         if (nright + nwrong > 0) {
167                 (void)printf("\n\nRights %d; Wrongs %d; Score %d%%",
168                     nright, nwrong, (int)(100L * nright / (nright + nwrong)));
169                 if (nright > 0)
170         (void)printf("\nTotal time %ld seconds; %.1f seconds per problem\n\n",
171                             (long)qtime, (float)qtime / nright);
172         }
173         (void)printf("\n");
174 }
175
176 /*
177  * Pick a problem and ask it.  Keeps asking the same problem until supplied
178  * with the correct answer, or until EOF or interrupt is typed.  Problems are
179  * selected such that the right operand and either the left operand (for +, x)
180  * or the correct result (for -, /) are in the range 0 to rangemax.  Each wrong
181  * answer causes the numbers in the problem to be penalised, so that they are
182  * more likely to appear in subsequent problems.
183  */
184 int
185 problem(void)
186 {
187         char *p;
188         time_t start, finish;
189         int left, op, right, result;
190         char line[80];
191
192         left = 0;
193         right = 0;
194         result = 0;
195         op = keys[random() % nkeys];
196         if (op != '/')
197                 right = getrandom(rangemax + 1, op, 1);
198 retry:
199         /* Get the operands. */
200         switch (op) {
201         case '+':
202                 left = getrandom(rangemax + 1, op, 0);
203                 result = left + right;
204                 break;
205         case '-':
206                 result = getrandom(rangemax + 1, op, 0);
207                 left = right + result;
208                 break;
209         case 'x':
210                 left = getrandom(rangemax + 1, op, 0);
211                 result = left * right;
212                 break;
213         case '/':
214                 right = getrandom(rangemax, op, 1) + 1;
215                 result = getrandom(rangemax + 1, op, 0);
216                 left = right * result + random() % right;
217                 break;
218         }
219
220         /*
221          * A very big maxrange could cause negative values to pop
222          * up, owing to overflow.
223          */
224         if (result < 0 || left < 0)
225                 goto retry;
226
227         (void)printf("%d %c %d =   ", left, op, right);
228         (void)fflush(stdout);
229         (void)time(&start);
230
231         /*
232          * Keep looping until the correct answer is given, or until EOF or
233          * interrupt is typed.
234          */
235         for (;;) {
236                 if (!fgets(line, sizeof(line), stdin)) {
237                         (void)printf("\n");
238                         return(EOF);
239                 }
240                 for (p = line; *p && isspace(*p); ++p);
241                 if (!isdigit(*p)) {
242                         (void)printf("Please type a number.\n");
243                         continue;
244                 }
245                 if (atoi(p) == result) {
246                         (void)printf("Right!\n");
247                         ++nright;
248                         break;
249                 }
250                 /* Wrong answer; penalise and ask again. */
251                 (void)printf("What?\n");
252                 ++nwrong;
253                 penalise(right, op, 1);
254                 if (op == 'x' || op == '+')
255                         penalise(left, op, 0);
256                 else
257                         penalise(result, op, 0);
258         }
259
260         /*
261          * Accumulate the time taken.  Obviously rounding errors happen here;
262          * however they should cancel out, because some of the time you are
263          * charged for a partially elapsed second at the start, and some of
264          * the time you are not charged for a partially elapsed second at the
265          * end.
266          */
267         (void)time(&finish);
268         qtime += finish - start;
269         return(0);
270 }
271
272 /*
273  * Here is the code for accumulating penalties against the numbers for which
274  * a wrong answer was given.  The right operand and either the left operand
275  * (for +, x) or the result (for -, /) are stored in a list for the particular
276  * operation, and each becomes more likely to appear again in that operation.
277  * Initially, each number is charged a penalty of WRONGPENALTY, giving it that
278  * many extra chances of appearing.  Each time it is selected because of this,
279  * its penalty is decreased by one; it is removed when it reaches 0.
280  *
281  * The penalty[] array gives the sum of all penalties in the list for
282  * each operation and each operand.  The penlist[] array has the lists of
283  * penalties themselves.
284  */
285
286 int penalty[sizeof(keylist) - 1][2];
287 struct penalty {
288         int value, penalty;     /* Penalised value and its penalty. */
289         struct penalty *next;
290 } *penlist[sizeof(keylist) - 1][2];
291
292 #define WRONGPENALTY    5       /* Perhaps this should depend on maxrange. */
293
294 /*
295  * Add a penalty for the number `value' to the list for operation `op',
296  * operand number `operand' (0 or 1).  If we run out of memory, we just
297  * forget about the penalty (how likely is this, anyway?).
298  */
299 void
300 penalise(int value, int op, int operand)
301 {
302         struct penalty *p;
303
304         op = opnum(op);
305         if ((p = (struct penalty *)malloc((u_int)sizeof(*p))) == NULL)
306                 return;
307         p->next = penlist[op][operand];
308         penlist[op][operand] = p;
309         penalty[op][operand] += p->penalty = WRONGPENALTY;
310         p->value = value;
311 }
312
313 /*
314  * Select a random value from 0 to maxval - 1 for operand `operand' (0 or 1)
315  * of operation `op'.  The random number we generate is either used directly
316  * as a value, or represents a position in the penalty list.  If the latter,
317  * we find the corresponding value and return that, decreasing its penalty.
318  */
319 int
320 getrandom(int maxval, int op, int operand)
321 {
322         int value;
323         struct penalty **pp, *p;
324
325         op = opnum(op);
326         value = random() % (maxval + penalty[op][operand]);
327
328         /*
329          * 0 to maxval - 1 is a number to be used directly; bigger values
330          * are positions to be located in the penalty list.
331          */
332         if (value < maxval)
333                 return(value);
334         value -= maxval;
335
336         /*
337          * Find the penalty at position `value'; decrement its penalty and
338          * delete it if it reaches 0; return the corresponding value.
339          */
340         for (pp = &penlist[op][operand]; (p = *pp) != NULL; pp = &p->next) {
341                 if (p->penalty > value) {
342                         value = p->value;
343                         penalty[op][operand]--;
344                         if (--(p->penalty) <= 0) {
345                                 p = p->next;
346                                 (void)free((char *)*pp);
347                                 *pp = p;
348                         }
349                         return(value);
350                 }
351                 value -= p->penalty;
352         }
353         /*
354          * We can only get here if the value from the penalty[] array doesn't
355          * correspond to the actual sum of penalties in the list.  Provide an
356          * obscure message.
357          */
358         (void)fprintf(stderr, "arithmetic: bug: inconsistent penalties\n");
359         exit(1);
360         /* NOTREACHED */
361 }
362
363 /* Return an index for the character op, which is one of [+-x/]. */
364 int
365 opnum(int op)
366 {
367         char *p;
368
369         if (op == 0 || (p = index(keylist, op)) == NULL) {
370                 (void)fprintf(stderr,
371                     "arithmetic: bug: op %c not in keylist %s\n", op, keylist);
372                 exit(1);
373         }
374         return(p - keylist);
375 }
376
377 /* Print usage message and quit. */
378 static void
379 usage(void)
380 {
381         (void)fprintf(stderr, "usage: arithmetic [-o +-x/] [-r range]\n");
382         exit(1);
383 }