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