diff options
author | Franklin Wei <franklin@rockbox.org> | 2024-08-18 21:14:07 -0400 |
---|---|---|
committer | Franklin Wei <franklin@rockbox.org> | 2024-08-25 19:30:01 -0400 |
commit | eca00638aeab59cf03287b9f298c86a6de1b5a9a (patch) | |
tree | 32f14d7c1a05f86b2ba7e91be647233570203599 /apps/plugins/puzzles/src/unfinished/numgame.c | |
parent | 3dd69ce23e3089ac78c512f02e59406d05302fa4 (diff) | |
download | rockbox-eca00638aeab59cf03287b9f298c86a6de1b5a9a.tar.gz rockbox-eca00638aeab59cf03287b9f298c86a6de1b5a9a.zip |
puzzles: add Slide and Sokoban.
This enables two of the "unfinished" puzzles. Slide requires a new "sticky
mouse mode" to enable dragging. The help system is disabled for these
puzzles, since they lack manual chapters.
Group is currently unplayable due to lack of request_keys() support, which
will need to be added upstream. Separate fails to draw anything.
Change-Id: I7bcff3679ac5b10b0f39c5eaa19a36b4b1fe8d53
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/numgame.c')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/numgame.c | 1294 |
1 files changed, 1294 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/unfinished/numgame.c b/apps/plugins/puzzles/src/unfinished/numgame.c new file mode 100644 index 0000000000..cf919922e7 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/numgame.c | |||
@@ -0,0 +1,1294 @@ | |||
1 | /* | ||
2 | * This program implements a breadth-first search which | ||
3 | * exhaustively solves the Countdown numbers game, and related | ||
4 | * games with slightly different rule sets such as `Flippo'. | ||
5 | * | ||
6 | * Currently it is simply a standalone command-line utility to | ||
7 | * which you provide a set of numbers and it tells you everything | ||
8 | * it can make together with how many different ways it can be | ||
9 | * made. I would like ultimately to turn it into the generator for | ||
10 | * a Puzzles puzzle, but I haven't even started on writing a | ||
11 | * Puzzles user interface yet. | ||
12 | */ | ||
13 | |||
14 | /* | ||
15 | * TODO: | ||
16 | * | ||
17 | * - start thinking about difficulty ratings | ||
18 | * + anything involving associative operations will be flagged | ||
19 | * as many-paths because of the associative options (e.g. | ||
20 | * 2*3*4 can be (2*3)*4 or 2*(3*4), or indeed (2*4)*3). This | ||
21 | * is probably a _good_ thing, since those are unusually | ||
22 | * easy. | ||
23 | * + tree-structured calculations ((a*b)/(c+d)) have multiple | ||
24 | * paths because the independent branches of the tree can be | ||
25 | * evaluated in either order, whereas straight-line | ||
26 | * calculations with no branches will be considered easier. | ||
27 | * Can we do anything about this? It's certainly not clear to | ||
28 | * me that tree-structure calculations are _easier_, although | ||
29 | * I'm also not convinced they're harder. | ||
30 | * + I think for a realistic difficulty assessment we must also | ||
31 | * consider the `obviousness' of the arithmetic operations in | ||
32 | * some heuristic sense, and also (in Countdown) how many | ||
33 | * numbers ended up being used. | ||
34 | * - actually try some generations | ||
35 | * - at this point we're probably ready to start on the Puzzles | ||
36 | * integration. | ||
37 | */ | ||
38 | |||
39 | #include <stdio.h> | ||
40 | #include <string.h> | ||
41 | #include <limits.h> | ||
42 | #include <assert.h> | ||
43 | #ifdef NO_TGMATH_H | ||
44 | # include <math.h> | ||
45 | #else | ||
46 | # include <tgmath.h> | ||
47 | #endif | ||
48 | |||
49 | #include "puzzles.h" | ||
50 | #include "tree234.h" | ||
51 | |||
52 | /* | ||
53 | * To search for numbers we can make, we employ a breadth-first | ||
54 | * search across the space of sets of input numbers. That is, for | ||
55 | * example, we start with the set (3,6,25,50,75,100); we apply | ||
56 | * moves which involve combining two numbers (e.g. adding the 50 | ||
57 | * and the 75 takes us to the set (3,6,25,100,125); and then we see | ||
58 | * if we ever end up with a set containing (say) 952. | ||
59 | * | ||
60 | * If the rules are changed so that all the numbers must be used, | ||
61 | * this is easy to adjust to: we simply see if we end up with a set | ||
62 | * containing _only_ (say) 952. | ||
63 | * | ||
64 | * Obviously, we can vary the rules about permitted arithmetic | ||
65 | * operations simply by altering the set of valid moves in the bfs. | ||
66 | * However, there's one common rule in this sort of puzzle which | ||
67 | * takes a little more thought, and that's _concatenation_. For | ||
68 | * example, if you are given (say) four 4s and required to make 10, | ||
69 | * you are permitted to combine two of the 4s into a 44 to begin | ||
70 | * with, making (44-4)/4 = 10. However, you are generally not | ||
71 | * allowed to concatenate two numbers that _weren't_ both in the | ||
72 | * original input set (you couldn't multiply two 4s to get 16 and | ||
73 | * then concatenate a 4 on to it to make 164), so concatenation is | ||
74 | * not an operation which is valid in all situations. | ||
75 | * | ||
76 | * We could enforce this restriction by storing a flag alongside | ||
77 | * each number indicating whether or not it's an original number; | ||
78 | * the rules being that concatenation of two numbers is only valid | ||
79 | * if they both have the original flag, and that its output _also_ | ||
80 | * has the original flag (so that you can concatenate three 4s into | ||
81 | * a 444), but that applying any other arithmetic operation clears | ||
82 | * the original flag on the output. However, we can get marginally | ||
83 | * simpler than that by observing that since concatenation has to | ||
84 | * happen to a number before any other operation, we can simply | ||
85 | * place all the concatenations at the start of the search. In | ||
86 | * other words, we have a global flag on an entire number _set_ | ||
87 | * which indicates whether we are still permitted to perform | ||
88 | * concatenations; if so, we can concatenate any of the numbers in | ||
89 | * that set. Performing any other operation clears the flag. | ||
90 | */ | ||
91 | |||
92 | #define SETFLAG_CONCAT 1 /* we can do concatenation */ | ||
93 | |||
94 | struct sets; | ||
95 | |||
96 | struct ancestor { | ||
97 | struct set *prev; /* index of ancestor set in set list */ | ||
98 | unsigned char pa, pb, po, pr; /* operation that got here from prev */ | ||
99 | }; | ||
100 | |||
101 | struct set { | ||
102 | int *numbers; /* rationals stored as n,d pairs */ | ||
103 | short nnumbers; /* # of rationals, so half # of ints */ | ||
104 | short flags; /* SETFLAG_CONCAT only, at present */ | ||
105 | int npaths; /* number of ways to reach this set */ | ||
106 | struct ancestor a; /* primary ancestor */ | ||
107 | struct ancestor *as; /* further ancestors, if we care */ | ||
108 | int nas, assize; | ||
109 | }; | ||
110 | |||
111 | struct output { | ||
112 | int number; | ||
113 | struct set *set; | ||
114 | int index; /* which number in the set is it? */ | ||
115 | int npaths; /* number of ways to reach this */ | ||
116 | }; | ||
117 | |||
118 | #define SETLISTLEN 1024 | ||
119 | #define NUMBERLISTLEN 32768 | ||
120 | #define OUTPUTLISTLEN 1024 | ||
121 | struct operation; | ||
122 | struct sets { | ||
123 | struct set **setlists; | ||
124 | int nsets, nsetlists, setlistsize; | ||
125 | tree234 *settree; | ||
126 | int **numberlists; | ||
127 | int nnumbers, nnumberlists, numberlistsize; | ||
128 | struct output **outputlists; | ||
129 | int noutputs, noutputlists, outputlistsize; | ||
130 | tree234 *outputtree; | ||
131 | const struct operation *const *ops; | ||
132 | }; | ||
133 | |||
134 | #define OPFLAG_NEEDS_CONCAT 1 | ||
135 | #define OPFLAG_KEEPS_CONCAT 2 | ||
136 | #define OPFLAG_UNARY 4 | ||
137 | #define OPFLAG_UNARYPREFIX 8 | ||
138 | #define OPFLAG_FN 16 | ||
139 | |||
140 | struct operation { | ||
141 | /* | ||
142 | * Most operations should be shown in the output working, but | ||
143 | * concatenation should not; we just take the result of the | ||
144 | * concatenation and assume that it's obvious how it was | ||
145 | * derived. | ||
146 | */ | ||
147 | int display; | ||
148 | |||
149 | /* | ||
150 | * Text display of the operator, in expressions and for | ||
151 | * debugging respectively. | ||
152 | */ | ||
153 | const char *text, *dbgtext; | ||
154 | |||
155 | /* | ||
156 | * Flags dictating when the operator can be applied. | ||
157 | */ | ||
158 | int flags; | ||
159 | |||
160 | /* | ||
161 | * Priority of the operator (for avoiding unnecessary | ||
162 | * parentheses when formatting it into a string). | ||
163 | */ | ||
164 | int priority; | ||
165 | |||
166 | /* | ||
167 | * Associativity of the operator. Bit 0 means we need parens | ||
168 | * when the left operand of one of these operators is another | ||
169 | * instance of it, e.g. (2^3)^4. Bit 1 means we need parens | ||
170 | * when the right operand is another instance of the same | ||
171 | * operator, e.g. 2-(3-4). Thus: | ||
172 | * | ||
173 | * - this field is 0 for a fully associative operator, since | ||
174 | * we never need parens. | ||
175 | * - it's 1 for a right-associative operator. | ||
176 | * - it's 2 for a left-associative operator. | ||
177 | * - it's 3 for a _non_-associative operator (which always | ||
178 | * uses parens just to be sure). | ||
179 | */ | ||
180 | int assoc; | ||
181 | |||
182 | /* | ||
183 | * Whether the operator is commutative. Saves time in the | ||
184 | * search if we don't have to try it both ways round. | ||
185 | */ | ||
186 | int commutes; | ||
187 | |||
188 | /* | ||
189 | * Function which implements the operator. Returns true on | ||
190 | * success, false on failure. Takes two rationals and writes | ||
191 | * out a third. | ||
192 | */ | ||
193 | int (*perform)(int *a, int *b, int *output); | ||
194 | }; | ||
195 | |||
196 | struct rules { | ||
197 | const struct operation *const *ops; | ||
198 | int use_all; | ||
199 | }; | ||
200 | |||
201 | #define MUL(r, a, b) do { \ | ||
202 | (r) = (a) * (b); \ | ||
203 | if ((b) && (a) && (r) / (b) != (a)) return false; \ | ||
204 | } while (0) | ||
205 | |||
206 | #define ADD(r, a, b) do { \ | ||
207 | (r) = (a) + (b); \ | ||
208 | if ((a) > 0 && (b) > 0 && (r) < 0) return false; \ | ||
209 | if ((a) < 0 && (b) < 0 && (r) > 0) return false; \ | ||
210 | } while (0) | ||
211 | |||
212 | #define OUT(output, n, d) do { \ | ||
213 | int g = gcd((n),(d)); \ | ||
214 | if (g < 0) g = -g; \ | ||
215 | if ((d) < 0) g = -g; \ | ||
216 | if (g == -1 && (n) < -INT_MAX) return false; \ | ||
217 | if (g == -1 && (d) < -INT_MAX) return false; \ | ||
218 | (output)[0] = (n)/g; \ | ||
219 | (output)[1] = (d)/g; \ | ||
220 | assert((output)[1] > 0); \ | ||
221 | } while (0) | ||
222 | |||
223 | static int gcd(int x, int y) | ||
224 | { | ||
225 | while (x != 0 && y != 0) { | ||
226 | int t = x; | ||
227 | x = y; | ||
228 | y = t % y; | ||
229 | } | ||
230 | |||
231 | return abs(x + y); /* i.e. whichever one isn't zero */ | ||
232 | } | ||
233 | |||
234 | static int perform_add(int *a, int *b, int *output) | ||
235 | { | ||
236 | int at, bt, tn, bn; | ||
237 | /* | ||
238 | * a0/a1 + b0/b1 = (a0*b1 + b0*a1) / (a1*b1) | ||
239 | */ | ||
240 | MUL(at, a[0], b[1]); | ||
241 | MUL(bt, b[0], a[1]); | ||
242 | ADD(tn, at, bt); | ||
243 | MUL(bn, a[1], b[1]); | ||
244 | OUT(output, tn, bn); | ||
245 | return true; | ||
246 | } | ||
247 | |||
248 | static int perform_sub(int *a, int *b, int *output) | ||
249 | { | ||
250 | int at, bt, tn, bn; | ||
251 | /* | ||
252 | * a0/a1 - b0/b1 = (a0*b1 - b0*a1) / (a1*b1) | ||
253 | */ | ||
254 | MUL(at, a[0], b[1]); | ||
255 | MUL(bt, b[0], a[1]); | ||
256 | ADD(tn, at, -bt); | ||
257 | MUL(bn, a[1], b[1]); | ||
258 | OUT(output, tn, bn); | ||
259 | return true; | ||
260 | } | ||
261 | |||
262 | static int perform_mul(int *a, int *b, int *output) | ||
263 | { | ||
264 | int tn, bn; | ||
265 | /* | ||
266 | * a0/a1 * b0/b1 = (a0*b0) / (a1*b1) | ||
267 | */ | ||
268 | MUL(tn, a[0], b[0]); | ||
269 | MUL(bn, a[1], b[1]); | ||
270 | OUT(output, tn, bn); | ||
271 | return true; | ||
272 | } | ||
273 | |||
274 | static int perform_div(int *a, int *b, int *output) | ||
275 | { | ||
276 | int tn, bn; | ||
277 | |||
278 | /* | ||
279 | * Division by zero is outlawed. | ||
280 | */ | ||
281 | if (b[0] == 0) | ||
282 | return false; | ||
283 | |||
284 | /* | ||
285 | * a0/a1 / b0/b1 = (a0*b1) / (a1*b0) | ||
286 | */ | ||
287 | MUL(tn, a[0], b[1]); | ||
288 | MUL(bn, a[1], b[0]); | ||
289 | OUT(output, tn, bn); | ||
290 | return true; | ||
291 | } | ||
292 | |||
293 | static int perform_exact_div(int *a, int *b, int *output) | ||
294 | { | ||
295 | int tn, bn; | ||
296 | |||
297 | /* | ||
298 | * Division by zero is outlawed. | ||
299 | */ | ||
300 | if (b[0] == 0) | ||
301 | return false; | ||
302 | |||
303 | /* | ||
304 | * a0/a1 / b0/b1 = (a0*b1) / (a1*b0) | ||
305 | */ | ||
306 | MUL(tn, a[0], b[1]); | ||
307 | MUL(bn, a[1], b[0]); | ||
308 | OUT(output, tn, bn); | ||
309 | |||
310 | /* | ||
311 | * Exact division means we require the result to be an integer. | ||
312 | */ | ||
313 | return (output[1] == 1); | ||
314 | } | ||
315 | |||
316 | static int max_p10(int n, int *p10_r) | ||
317 | { | ||
318 | /* | ||
319 | * Find the smallest power of ten strictly greater than n. | ||
320 | * | ||
321 | * Special case: we must return at least 10, even if n is | ||
322 | * zero. (This is because this function is used for finding | ||
323 | * the power of ten by which to multiply a number being | ||
324 | * concatenated to the front of n, and concatenating 1 to 0 | ||
325 | * should yield 10 and not 1.) | ||
326 | */ | ||
327 | int p10 = 10; | ||
328 | while (p10 <= (INT_MAX/10) && p10 <= n) | ||
329 | p10 *= 10; | ||
330 | if (p10 > INT_MAX/10) | ||
331 | return false; /* integer overflow */ | ||
332 | *p10_r = p10; | ||
333 | return true; | ||
334 | } | ||
335 | |||
336 | static int perform_concat(int *a, int *b, int *output) | ||
337 | { | ||
338 | int t1, t2, p10; | ||
339 | |||
340 | /* | ||
341 | * We can't concatenate anything which isn't a non-negative | ||
342 | * integer. | ||
343 | */ | ||
344 | if (a[1] != 1 || b[1] != 1 || a[0] < 0 || b[0] < 0) | ||
345 | return false; | ||
346 | |||
347 | /* | ||
348 | * For concatenation, we can safely assume leading zeroes | ||
349 | * aren't an issue. It isn't clear whether they `should' be | ||
350 | * allowed, but it turns out not to matter: concatenating a | ||
351 | * leading zero on to a number in order to harmlessly get rid | ||
352 | * of the zero is never necessary because unwanted zeroes can | ||
353 | * be disposed of by adding them to something instead. So we | ||
354 | * disallow them always. | ||
355 | * | ||
356 | * The only other possibility is that you might want to | ||
357 | * concatenate a leading zero on to something and then | ||
358 | * concatenate another non-zero digit on to _that_ (to make, | ||
359 | * for example, 106); but that's also unnecessary, because you | ||
360 | * can make 106 just as easily by concatenating the 0 on to the | ||
361 | * _end_ of the 1 first. | ||
362 | */ | ||
363 | if (a[0] == 0) | ||
364 | return false; | ||
365 | |||
366 | if (!max_p10(b[0], &p10)) return false; | ||
367 | |||
368 | MUL(t1, p10, a[0]); | ||
369 | ADD(t2, t1, b[0]); | ||
370 | OUT(output, t2, 1); | ||
371 | return true; | ||
372 | } | ||
373 | |||
374 | #define IPOW(ret, x, y) do { \ | ||
375 | int ipow_limit = (y); \ | ||
376 | if ((x) == 1 || (x) == 0) ipow_limit = 1; \ | ||
377 | else if ((x) == -1) ipow_limit &= 1; \ | ||
378 | (ret) = 1; \ | ||
379 | while (ipow_limit-- > 0) { \ | ||
380 | int tmp; \ | ||
381 | MUL(tmp, ret, x); \ | ||
382 | ret = tmp; \ | ||
383 | } \ | ||
384 | } while (0) | ||
385 | |||
386 | static int perform_exp(int *a, int *b, int *output) | ||
387 | { | ||
388 | int an, ad, xn, xd; | ||
389 | |||
390 | /* | ||
391 | * Exponentiation is permitted if the result is rational. This | ||
392 | * means that: | ||
393 | * | ||
394 | * - first we see whether we can take the (denominator-of-b)th | ||
395 | * root of a and get a rational; if not, we give up. | ||
396 | * | ||
397 | * - then we do take that root of a | ||
398 | * | ||
399 | * - then we multiply by itself (numerator-of-b) times. | ||
400 | */ | ||
401 | if (b[1] > 1) { | ||
402 | an = (int)(0.5 + pow(a[0], 1.0/b[1])); | ||
403 | ad = (int)(0.5 + pow(a[1], 1.0/b[1])); | ||
404 | IPOW(xn, an, b[1]); | ||
405 | IPOW(xd, ad, b[1]); | ||
406 | if (xn != a[0] || xd != a[1]) | ||
407 | return false; | ||
408 | } else { | ||
409 | an = a[0]; | ||
410 | ad = a[1]; | ||
411 | } | ||
412 | if (b[0] >= 0) { | ||
413 | IPOW(xn, an, b[0]); | ||
414 | IPOW(xd, ad, b[0]); | ||
415 | } else { | ||
416 | IPOW(xd, an, -b[0]); | ||
417 | IPOW(xn, ad, -b[0]); | ||
418 | } | ||
419 | if (xd == 0) | ||
420 | return false; | ||
421 | |||
422 | OUT(output, xn, xd); | ||
423 | return true; | ||
424 | } | ||
425 | |||
426 | static int perform_factorial(int *a, int *b, int *output) | ||
427 | { | ||
428 | int ret, t, i; | ||
429 | |||
430 | /* | ||
431 | * Factorials of non-negative integers are permitted. | ||
432 | */ | ||
433 | if (a[1] != 1 || a[0] < 0) | ||
434 | return false; | ||
435 | |||
436 | /* | ||
437 | * However, a special case: we don't take a factorial of | ||
438 | * anything which would thereby remain the same. | ||
439 | */ | ||
440 | if (a[0] == 1 || a[0] == 2) | ||
441 | return false; | ||
442 | |||
443 | ret = 1; | ||
444 | for (i = 1; i <= a[0]; i++) { | ||
445 | MUL(t, ret, i); | ||
446 | ret = t; | ||
447 | } | ||
448 | |||
449 | OUT(output, ret, 1); | ||
450 | return true; | ||
451 | } | ||
452 | |||
453 | static int perform_decimal(int *a, int *b, int *output) | ||
454 | { | ||
455 | int p10; | ||
456 | |||
457 | /* | ||
458 | * Add a decimal digit to the front of a number; | ||
459 | * fail if it's not an integer. | ||
460 | * So, 1 --> 0.1, 15 --> 0.15, | ||
461 | * or, rather, 1 --> 1/10, 15 --> 15/100, | ||
462 | * x --> x / (smallest power of 10 > than x) | ||
463 | * | ||
464 | */ | ||
465 | if (a[1] != 1) return false; | ||
466 | |||
467 | if (!max_p10(a[0], &p10)) return false; | ||
468 | |||
469 | OUT(output, a[0], p10); | ||
470 | return true; | ||
471 | } | ||
472 | |||
473 | static int perform_recur(int *a, int *b, int *output) | ||
474 | { | ||
475 | int p10, tn, bn; | ||
476 | |||
477 | /* | ||
478 | * This converts a number like .4 to .44444..., or .45 to .45454... | ||
479 | * The input number must be -1 < a < 1. | ||
480 | * | ||
481 | * Calculate the smallest power of 10 that divides the denominator exactly, | ||
482 | * returning if no such power of 10 exists. Then multiply the numerator | ||
483 | * up accordingly, and the new denominator becomes that power of 10 - 1. | ||
484 | */ | ||
485 | if (abs(a[0]) >= abs(a[1])) return false; /* -1 < a < 1 */ | ||
486 | |||
487 | p10 = 10; | ||
488 | while (p10 <= (INT_MAX/10)) { | ||
489 | if ((a[1] <= p10) && (p10 % a[1]) == 0) goto found; | ||
490 | p10 *= 10; | ||
491 | } | ||
492 | return false; | ||
493 | found: | ||
494 | tn = a[0] * (p10 / a[1]); | ||
495 | bn = p10 - 1; | ||
496 | |||
497 | OUT(output, tn, bn); | ||
498 | return true; | ||
499 | } | ||
500 | |||
501 | static int perform_root(int *a, int *b, int *output) | ||
502 | { | ||
503 | /* | ||
504 | * A root B is: 1 iff a == 0 | ||
505 | * B ^ (1/A) otherwise | ||
506 | */ | ||
507 | int ainv[2], res; | ||
508 | |||
509 | if (a[0] == 0) { | ||
510 | OUT(output, 1, 1); | ||
511 | return true; | ||
512 | } | ||
513 | |||
514 | OUT(ainv, a[1], a[0]); | ||
515 | res = perform_exp(b, ainv, output); | ||
516 | return res; | ||
517 | } | ||
518 | |||
519 | static int perform_perc(int *a, int *b, int *output) | ||
520 | { | ||
521 | if (a[0] == 0) return false; /* 0% = 0, uninteresting. */ | ||
522 | if (a[1] > (INT_MAX/100)) return false; | ||
523 | |||
524 | OUT(output, a[0], a[1]*100); | ||
525 | return true; | ||
526 | } | ||
527 | |||
528 | static int perform_gamma(int *a, int *b, int *output) | ||
529 | { | ||
530 | int asub1[2]; | ||
531 | |||
532 | /* | ||
533 | * gamma(a) = (a-1)! | ||
534 | * | ||
535 | * special case not caught by perform_fact: gamma(1) is 1 so | ||
536 | * don't bother. | ||
537 | */ | ||
538 | if (a[0] == 1 && a[1] == 1) return false; | ||
539 | |||
540 | OUT(asub1, a[0]-a[1], a[1]); | ||
541 | return perform_factorial(asub1, b, output); | ||
542 | } | ||
543 | |||
544 | static int perform_sqrt(int *a, int *b, int *output) | ||
545 | { | ||
546 | int half[2] = { 1, 2 }; | ||
547 | |||
548 | /* | ||
549 | * sqrt(0) == 0, sqrt(1) == 1: don't perform unary noops. | ||
550 | */ | ||
551 | if (a[0] == 0 || (a[0] == 1 && a[1] == 1)) return false; | ||
552 | |||
553 | return perform_exp(a, half, output); | ||
554 | } | ||
555 | |||
556 | static const struct operation op_add = { | ||
557 | true, "+", "+", 0, 10, 0, true, perform_add | ||
558 | }; | ||
559 | static const struct operation op_sub = { | ||
560 | true, "-", "-", 0, 10, 2, false, perform_sub | ||
561 | }; | ||
562 | static const struct operation op_mul = { | ||
563 | true, "*", "*", 0, 20, 0, true, perform_mul | ||
564 | }; | ||
565 | static const struct operation op_div = { | ||
566 | true, "/", "/", 0, 20, 2, false, perform_div | ||
567 | }; | ||
568 | static const struct operation op_xdiv = { | ||
569 | true, "/", "/", 0, 20, 2, false, perform_exact_div | ||
570 | }; | ||
571 | static const struct operation op_concat = { | ||
572 | false, "", "concat", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT, | ||
573 | 1000, 0, false, perform_concat | ||
574 | }; | ||
575 | static const struct operation op_exp = { | ||
576 | true, "^", "^", 0, 30, 1, false, perform_exp | ||
577 | }; | ||
578 | static const struct operation op_factorial = { | ||
579 | true, "!", "!", OPFLAG_UNARY, 40, 0, false, perform_factorial | ||
580 | }; | ||
581 | static const struct operation op_decimal = { | ||
582 | true, ".", ".", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT, 50, 0, false, perform_decimal | ||
583 | }; | ||
584 | static const struct operation op_recur = { | ||
585 | true, "...", "recur", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 2, false, perform_recur | ||
586 | }; | ||
587 | static const struct operation op_root = { | ||
588 | true, "v~", "root", 0, 30, 1, false, perform_root | ||
589 | }; | ||
590 | static const struct operation op_perc = { | ||
591 | true, "%", "%", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 1, false, perform_perc | ||
592 | }; | ||
593 | static const struct operation op_gamma = { | ||
594 | true, "gamma", "gamma", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_FN, 1, 3, false, perform_gamma | ||
595 | }; | ||
596 | static const struct operation op_sqrt = { | ||
597 | true, "v~", "sqrt", OPFLAG_UNARY | OPFLAG_UNARYPREFIX, 30, 1, false, perform_sqrt | ||
598 | }; | ||
599 | |||
600 | /* | ||
601 | * In Countdown, divisions resulting in fractions are disallowed. | ||
602 | * http://www.askoxford.com/wordgames/countdown/rules/ | ||
603 | */ | ||
604 | static const struct operation *const ops_countdown[] = { | ||
605 | &op_add, &op_mul, &op_sub, &op_xdiv, NULL | ||
606 | }; | ||
607 | static const struct rules rules_countdown = { | ||
608 | ops_countdown, false | ||
609 | }; | ||
610 | |||
611 | /* | ||
612 | * A slightly different rule set which handles the reasonably well | ||
613 | * known puzzle of making 24 using two 3s and two 8s. For this we | ||
614 | * need rational rather than integer division. | ||
615 | */ | ||
616 | static const struct operation *const ops_3388[] = { | ||
617 | &op_add, &op_mul, &op_sub, &op_div, NULL | ||
618 | }; | ||
619 | static const struct rules rules_3388 = { | ||
620 | ops_3388, true | ||
621 | }; | ||
622 | |||
623 | /* | ||
624 | * A still more permissive rule set usable for the four-4s problem | ||
625 | * and similar things. Permits concatenation. | ||
626 | */ | ||
627 | static const struct operation *const ops_four4s[] = { | ||
628 | &op_add, &op_mul, &op_sub, &op_div, &op_concat, NULL | ||
629 | }; | ||
630 | static const struct rules rules_four4s = { | ||
631 | ops_four4s, true | ||
632 | }; | ||
633 | |||
634 | /* | ||
635 | * The most permissive ruleset I can think of. Permits | ||
636 | * exponentiation, and also silly unary operators like factorials. | ||
637 | */ | ||
638 | static const struct operation *const ops_anythinggoes[] = { | ||
639 | &op_add, &op_mul, &op_sub, &op_div, &op_concat, &op_exp, &op_factorial, | ||
640 | &op_decimal, &op_recur, &op_root, &op_perc, &op_gamma, &op_sqrt, NULL | ||
641 | }; | ||
642 | static const struct rules rules_anythinggoes = { | ||
643 | ops_anythinggoes, true | ||
644 | }; | ||
645 | |||
646 | #define ratcmp(a,op,b) ( (long long)(a)[0] * (b)[1] op \ | ||
647 | (long long)(b)[0] * (a)[1] ) | ||
648 | |||
649 | static int addtoset(struct set *set, int newnumber[2]) | ||
650 | { | ||
651 | int i, j; | ||
652 | |||
653 | /* Find where we want to insert the new number */ | ||
654 | for (i = 0; i < set->nnumbers && | ||
655 | ratcmp(set->numbers+2*i, <, newnumber); i++); | ||
656 | |||
657 | /* Move everything else up */ | ||
658 | for (j = set->nnumbers; j > i; j--) { | ||
659 | set->numbers[2*j] = set->numbers[2*j-2]; | ||
660 | set->numbers[2*j+1] = set->numbers[2*j-1]; | ||
661 | } | ||
662 | |||
663 | /* Insert the new number */ | ||
664 | set->numbers[2*i] = newnumber[0]; | ||
665 | set->numbers[2*i+1] = newnumber[1]; | ||
666 | |||
667 | set->nnumbers++; | ||
668 | |||
669 | return i; | ||
670 | } | ||
671 | |||
672 | #define ensure(array, size, newlen, type) do { \ | ||
673 | if ((newlen) > (size)) { \ | ||
674 | (size) = (newlen) + 512; \ | ||
675 | (array) = sresize((array), (size), type); \ | ||
676 | } \ | ||
677 | } while (0) | ||
678 | |||
679 | static int setcmp(void *av, void *bv) | ||
680 | { | ||
681 | struct set *a = (struct set *)av; | ||
682 | struct set *b = (struct set *)bv; | ||
683 | int i; | ||
684 | |||
685 | if (a->nnumbers < b->nnumbers) | ||
686 | return -1; | ||
687 | else if (a->nnumbers > b->nnumbers) | ||
688 | return +1; | ||
689 | |||
690 | if (a->flags < b->flags) | ||
691 | return -1; | ||
692 | else if (a->flags > b->flags) | ||
693 | return +1; | ||
694 | |||
695 | for (i = 0; i < a->nnumbers; i++) { | ||
696 | if (ratcmp(a->numbers+2*i, <, b->numbers+2*i)) | ||
697 | return -1; | ||
698 | else if (ratcmp(a->numbers+2*i, >, b->numbers+2*i)) | ||
699 | return +1; | ||
700 | } | ||
701 | |||
702 | return 0; | ||
703 | } | ||
704 | |||
705 | static int outputcmp(void *av, void *bv) | ||
706 | { | ||
707 | struct output *a = (struct output *)av; | ||
708 | struct output *b = (struct output *)bv; | ||
709 | |||
710 | if (a->number < b->number) | ||
711 | return -1; | ||
712 | else if (a->number > b->number) | ||
713 | return +1; | ||
714 | |||
715 | return 0; | ||
716 | } | ||
717 | |||
718 | static int outputfindcmp(void *av, void *bv) | ||
719 | { | ||
720 | int *a = (int *)av; | ||
721 | struct output *b = (struct output *)bv; | ||
722 | |||
723 | if (*a < b->number) | ||
724 | return -1; | ||
725 | else if (*a > b->number) | ||
726 | return +1; | ||
727 | |||
728 | return 0; | ||
729 | } | ||
730 | |||
731 | static void addset(struct sets *s, struct set *set, int multiple, | ||
732 | struct set *prev, int pa, int po, int pb, int pr) | ||
733 | { | ||
734 | struct set *s2; | ||
735 | int npaths = (prev ? prev->npaths : 1); | ||
736 | |||
737 | assert(set == s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN); | ||
738 | s2 = add234(s->settree, set); | ||
739 | if (s2 == set) { | ||
740 | /* | ||
741 | * New set added to the tree. | ||
742 | */ | ||
743 | set->a.prev = prev; | ||
744 | set->a.pa = pa; | ||
745 | set->a.po = po; | ||
746 | set->a.pb = pb; | ||
747 | set->a.pr = pr; | ||
748 | set->npaths = npaths; | ||
749 | s->nsets++; | ||
750 | s->nnumbers += 2 * set->nnumbers; | ||
751 | set->as = NULL; | ||
752 | set->nas = set->assize = 0; | ||
753 | } else { | ||
754 | /* | ||
755 | * Rediscovered an existing set. Update its npaths. | ||
756 | */ | ||
757 | s2->npaths += npaths; | ||
758 | /* | ||
759 | * And optionally enter it as an additional ancestor. | ||
760 | */ | ||
761 | if (multiple) { | ||
762 | if (s2->nas >= s2->assize) { | ||
763 | s2->assize = s2->nas * 3 / 2 + 4; | ||
764 | s2->as = sresize(s2->as, s2->assize, struct ancestor); | ||
765 | } | ||
766 | s2->as[s2->nas].prev = prev; | ||
767 | s2->as[s2->nas].pa = pa; | ||
768 | s2->as[s2->nas].po = po; | ||
769 | s2->as[s2->nas].pb = pb; | ||
770 | s2->as[s2->nas].pr = pr; | ||
771 | s2->nas++; | ||
772 | } | ||
773 | } | ||
774 | } | ||
775 | |||
776 | static struct set *newset(struct sets *s, int nnumbers, int flags) | ||
777 | { | ||
778 | struct set *sn; | ||
779 | |||
780 | ensure(s->setlists, s->setlistsize, s->nsets/SETLISTLEN+1, struct set *); | ||
781 | while (s->nsetlists <= s->nsets / SETLISTLEN) | ||
782 | s->setlists[s->nsetlists++] = snewn(SETLISTLEN, struct set); | ||
783 | sn = s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN; | ||
784 | |||
785 | if (s->nnumbers + nnumbers * 2 > s->nnumberlists * NUMBERLISTLEN) | ||
786 | s->nnumbers = s->nnumberlists * NUMBERLISTLEN; | ||
787 | ensure(s->numberlists, s->numberlistsize, | ||
788 | s->nnumbers/NUMBERLISTLEN+1, int *); | ||
789 | while (s->nnumberlists <= s->nnumbers / NUMBERLISTLEN) | ||
790 | s->numberlists[s->nnumberlists++] = snewn(NUMBERLISTLEN, int); | ||
791 | sn->numbers = s->numberlists[s->nnumbers / NUMBERLISTLEN] + | ||
792 | s->nnumbers % NUMBERLISTLEN; | ||
793 | |||
794 | /* | ||
795 | * Start the set off empty. | ||
796 | */ | ||
797 | sn->nnumbers = 0; | ||
798 | |||
799 | sn->flags = flags; | ||
800 | |||
801 | return sn; | ||
802 | } | ||
803 | |||
804 | static int addoutput(struct sets *s, struct set *ss, int index, int *n) | ||
805 | { | ||
806 | struct output *o, *o2; | ||
807 | |||
808 | /* | ||
809 | * Target numbers are always integers. | ||
810 | */ | ||
811 | if (ss->numbers[2*index+1] != 1) | ||
812 | return false; | ||
813 | |||
814 | ensure(s->outputlists, s->outputlistsize, s->noutputs/OUTPUTLISTLEN+1, | ||
815 | struct output *); | ||
816 | while (s->noutputlists <= s->noutputs / OUTPUTLISTLEN) | ||
817 | s->outputlists[s->noutputlists++] = snewn(OUTPUTLISTLEN, | ||
818 | struct output); | ||
819 | o = s->outputlists[s->noutputs / OUTPUTLISTLEN] + | ||
820 | s->noutputs % OUTPUTLISTLEN; | ||
821 | |||
822 | o->number = ss->numbers[2*index]; | ||
823 | o->set = ss; | ||
824 | o->index = index; | ||
825 | o->npaths = ss->npaths; | ||
826 | o2 = add234(s->outputtree, o); | ||
827 | if (o2 != o) { | ||
828 | o2->npaths += o->npaths; | ||
829 | } else { | ||
830 | s->noutputs++; | ||
831 | } | ||
832 | *n = o->number; | ||
833 | return true; | ||
834 | } | ||
835 | |||
836 | static struct sets *do_search(int ninputs, int *inputs, | ||
837 | const struct rules *rules, int *target, | ||
838 | int debug, int multiple) | ||
839 | { | ||
840 | struct sets *s; | ||
841 | struct set *sn; | ||
842 | int qpos, i; | ||
843 | const struct operation *const *ops = rules->ops; | ||
844 | |||
845 | s = snew(struct sets); | ||
846 | s->setlists = NULL; | ||
847 | s->nsets = s->nsetlists = s->setlistsize = 0; | ||
848 | s->numberlists = NULL; | ||
849 | s->nnumbers = s->nnumberlists = s->numberlistsize = 0; | ||
850 | s->outputlists = NULL; | ||
851 | s->noutputs = s->noutputlists = s->outputlistsize = 0; | ||
852 | s->settree = newtree234(setcmp); | ||
853 | s->outputtree = newtree234(outputcmp); | ||
854 | s->ops = ops; | ||
855 | |||
856 | /* | ||
857 | * Start with the input set. | ||
858 | */ | ||
859 | sn = newset(s, ninputs, SETFLAG_CONCAT); | ||
860 | for (i = 0; i < ninputs; i++) { | ||
861 | int newnumber[2]; | ||
862 | newnumber[0] = inputs[i]; | ||
863 | newnumber[1] = 1; | ||
864 | addtoset(sn, newnumber); | ||
865 | } | ||
866 | addset(s, sn, multiple, NULL, 0, 0, 0, 0); | ||
867 | |||
868 | /* | ||
869 | * Now perform the breadth-first search: keep looping over sets | ||
870 | * until we run out of steam. | ||
871 | */ | ||
872 | qpos = 0; | ||
873 | while (qpos < s->nsets) { | ||
874 | struct set *ss = s->setlists[qpos / SETLISTLEN] + qpos % SETLISTLEN; | ||
875 | struct set *sn; | ||
876 | int i, j, k, m; | ||
877 | |||
878 | if (debug) { | ||
879 | int i; | ||
880 | printf("processing set:"); | ||
881 | for (i = 0; i < ss->nnumbers; i++) { | ||
882 | printf(" %d", ss->numbers[2*i]); | ||
883 | if (ss->numbers[2*i+1] != 1) | ||
884 | printf("/%d", ss->numbers[2*i+1]); | ||
885 | } | ||
886 | printf("\n"); | ||
887 | } | ||
888 | |||
889 | /* | ||
890 | * Record all the valid output numbers in this state. We | ||
891 | * can always do this if there's only one number in the | ||
892 | * state; otherwise, we can only do it if we aren't | ||
893 | * required to use all the numbers in coming to our answer. | ||
894 | */ | ||
895 | if (ss->nnumbers == 1 || !rules->use_all) { | ||
896 | for (i = 0; i < ss->nnumbers; i++) { | ||
897 | int n; | ||
898 | |||
899 | if (addoutput(s, ss, i, &n) && target && n == *target) | ||
900 | return s; | ||
901 | } | ||
902 | } | ||
903 | |||
904 | /* | ||
905 | * Try every possible operation from this state. | ||
906 | */ | ||
907 | for (k = 0; ops[k] && ops[k]->perform; k++) { | ||
908 | if ((ops[k]->flags & OPFLAG_NEEDS_CONCAT) && | ||
909 | !(ss->flags & SETFLAG_CONCAT)) | ||
910 | continue; /* can't use this operation here */ | ||
911 | for (i = 0; i < ss->nnumbers; i++) { | ||
912 | int jlimit = (ops[k]->flags & OPFLAG_UNARY ? 1 : ss->nnumbers); | ||
913 | for (j = 0; j < jlimit; j++) { | ||
914 | int n[2], newnn = ss->nnumbers; | ||
915 | int pa, po, pb, pr; | ||
916 | |||
917 | if (!(ops[k]->flags & OPFLAG_UNARY)) { | ||
918 | if (i == j) | ||
919 | continue; /* can't combine a number with itself */ | ||
920 | if (i > j && ops[k]->commutes) | ||
921 | continue; /* no need to do this both ways round */ | ||
922 | newnn--; | ||
923 | } | ||
924 | if (!ops[k]->perform(ss->numbers+2*i, ss->numbers+2*j, n)) | ||
925 | continue; /* operation failed */ | ||
926 | |||
927 | sn = newset(s, newnn, ss->flags); | ||
928 | |||
929 | if (!(ops[k]->flags & OPFLAG_KEEPS_CONCAT)) | ||
930 | sn->flags &= ~SETFLAG_CONCAT; | ||
931 | |||
932 | for (m = 0; m < ss->nnumbers; m++) { | ||
933 | if (m == i || (!(ops[k]->flags & OPFLAG_UNARY) && | ||
934 | m == j)) | ||
935 | continue; | ||
936 | sn->numbers[2*sn->nnumbers] = ss->numbers[2*m]; | ||
937 | sn->numbers[2*sn->nnumbers + 1] = ss->numbers[2*m + 1]; | ||
938 | sn->nnumbers++; | ||
939 | } | ||
940 | pa = i; | ||
941 | if (ops[k]->flags & OPFLAG_UNARY) | ||
942 | pb = sn->nnumbers+10; | ||
943 | else | ||
944 | pb = j; | ||
945 | po = k; | ||
946 | pr = addtoset(sn, n); | ||
947 | addset(s, sn, multiple, ss, pa, po, pb, pr); | ||
948 | if (debug) { | ||
949 | int i; | ||
950 | if (ops[k]->flags & OPFLAG_UNARYPREFIX) | ||
951 | printf(" %s %d ->", ops[po]->dbgtext, pa); | ||
952 | else if (ops[k]->flags & OPFLAG_UNARY) | ||
953 | printf(" %d %s ->", pa, ops[po]->dbgtext); | ||
954 | else | ||
955 | printf(" %d %s %d ->", pa, ops[po]->dbgtext, pb); | ||
956 | for (i = 0; i < sn->nnumbers; i++) { | ||
957 | printf(" %d", sn->numbers[2*i]); | ||
958 | if (sn->numbers[2*i+1] != 1) | ||
959 | printf("/%d", sn->numbers[2*i+1]); | ||
960 | } | ||
961 | printf("\n"); | ||
962 | } | ||
963 | } | ||
964 | } | ||
965 | } | ||
966 | |||
967 | qpos++; | ||
968 | } | ||
969 | |||
970 | return s; | ||
971 | } | ||
972 | |||
973 | static void free_sets(struct sets *s) | ||
974 | { | ||
975 | int i; | ||
976 | |||
977 | freetree234(s->settree); | ||
978 | freetree234(s->outputtree); | ||
979 | for (i = 0; i < s->nsetlists; i++) | ||
980 | sfree(s->setlists[i]); | ||
981 | sfree(s->setlists); | ||
982 | for (i = 0; i < s->nnumberlists; i++) | ||
983 | sfree(s->numberlists[i]); | ||
984 | sfree(s->numberlists); | ||
985 | for (i = 0; i < s->noutputlists; i++) | ||
986 | sfree(s->outputlists[i]); | ||
987 | sfree(s->outputlists); | ||
988 | sfree(s); | ||
989 | } | ||
990 | |||
991 | /* | ||
992 | * Print a text formula for producing a given output. | ||
993 | */ | ||
994 | static void print_recurse(struct sets *s, struct set *ss, int pathindex, | ||
995 | int index, int priority, int assoc, int child); | ||
996 | static void print_recurse_inner(struct sets *s, struct set *ss, | ||
997 | struct ancestor *a, int pathindex, int index, | ||
998 | int priority, int assoc, int child) | ||
999 | { | ||
1000 | if (a->prev && index != a->pr) { | ||
1001 | int pi; | ||
1002 | |||
1003 | /* | ||
1004 | * This number was passed straight down from this set's | ||
1005 | * predecessor. Find its index in the previous set and | ||
1006 | * recurse to there. | ||
1007 | */ | ||
1008 | pi = index; | ||
1009 | assert(pi != a->pr); | ||
1010 | if (pi > a->pr) | ||
1011 | pi--; | ||
1012 | if (pi >= min(a->pa, a->pb)) { | ||
1013 | pi++; | ||
1014 | if (pi >= max(a->pa, a->pb)) | ||
1015 | pi++; | ||
1016 | } | ||
1017 | print_recurse(s, a->prev, pathindex, pi, priority, assoc, child); | ||
1018 | } else if (a->prev && index == a->pr && | ||
1019 | s->ops[a->po]->display) { | ||
1020 | /* | ||
1021 | * This number was created by a displayed operator in the | ||
1022 | * transition from this set to its predecessor. Hence we | ||
1023 | * write an open paren, then recurse into the first | ||
1024 | * operand, then write the operator, then the second | ||
1025 | * operand, and finally close the paren. | ||
1026 | */ | ||
1027 | const char *op; | ||
1028 | int parens, thispri, thisassoc; | ||
1029 | |||
1030 | /* | ||
1031 | * Determine whether we need parentheses. | ||
1032 | */ | ||
1033 | thispri = s->ops[a->po]->priority; | ||
1034 | thisassoc = s->ops[a->po]->assoc; | ||
1035 | parens = (thispri < priority || | ||
1036 | (thispri == priority && (assoc & child))); | ||
1037 | |||
1038 | if (parens) | ||
1039 | putchar('('); | ||
1040 | |||
1041 | if (s->ops[a->po]->flags & OPFLAG_UNARYPREFIX) | ||
1042 | for (op = s->ops[a->po]->text; *op; op++) | ||
1043 | putchar(*op); | ||
1044 | |||
1045 | if (s->ops[a->po]->flags & OPFLAG_FN) | ||
1046 | putchar('('); | ||
1047 | |||
1048 | print_recurse(s, a->prev, pathindex, a->pa, thispri, thisassoc, 1); | ||
1049 | |||
1050 | if (s->ops[a->po]->flags & OPFLAG_FN) | ||
1051 | putchar(')'); | ||
1052 | |||
1053 | if (!(s->ops[a->po]->flags & OPFLAG_UNARYPREFIX)) | ||
1054 | for (op = s->ops[a->po]->text; *op; op++) | ||
1055 | putchar(*op); | ||
1056 | |||
1057 | if (!(s->ops[a->po]->flags & OPFLAG_UNARY)) | ||
1058 | print_recurse(s, a->prev, pathindex, a->pb, thispri, thisassoc, 2); | ||
1059 | |||
1060 | if (parens) | ||
1061 | putchar(')'); | ||
1062 | } else { | ||
1063 | /* | ||
1064 | * This number is either an original, or something formed | ||
1065 | * by a non-displayed operator (concatenation). Either way, | ||
1066 | * we display it as is. | ||
1067 | */ | ||
1068 | printf("%d", ss->numbers[2*index]); | ||
1069 | if (ss->numbers[2*index+1] != 1) | ||
1070 | printf("/%d", ss->numbers[2*index+1]); | ||
1071 | } | ||
1072 | } | ||
1073 | static void print_recurse(struct sets *s, struct set *ss, int pathindex, | ||
1074 | int index, int priority, int assoc, int child) | ||
1075 | { | ||
1076 | if (!ss->a.prev || pathindex < ss->a.prev->npaths) { | ||
1077 | print_recurse_inner(s, ss, &ss->a, pathindex, | ||
1078 | index, priority, assoc, child); | ||
1079 | } else { | ||
1080 | int i; | ||
1081 | pathindex -= ss->a.prev->npaths; | ||
1082 | for (i = 0; i < ss->nas; i++) { | ||
1083 | if (pathindex < ss->as[i].prev->npaths) { | ||
1084 | print_recurse_inner(s, ss, &ss->as[i], pathindex, | ||
1085 | index, priority, assoc, child); | ||
1086 | break; | ||
1087 | } | ||
1088 | pathindex -= ss->as[i].prev->npaths; | ||
1089 | } | ||
1090 | } | ||
1091 | } | ||
1092 | static void print(int pathindex, struct sets *s, struct output *o) | ||
1093 | { | ||
1094 | print_recurse(s, o->set, pathindex, o->index, 0, 0, 0); | ||
1095 | } | ||
1096 | |||
1097 | /* | ||
1098 | * gcc -g -O0 -o numgame numgame.c -I.. ../{malloc,tree234,nullfe}.c -lm | ||
1099 | */ | ||
1100 | int main(int argc, char **argv) | ||
1101 | { | ||
1102 | int doing_opts = true; | ||
1103 | const struct rules *rules = NULL; | ||
1104 | char *pname = argv[0]; | ||
1105 | int got_target = false, target = 0; | ||
1106 | int numbers[10], nnumbers = 0; | ||
1107 | int verbose = false; | ||
1108 | int pathcounts = false; | ||
1109 | int multiple = false; | ||
1110 | int debug_bfs = false; | ||
1111 | int got_range = false, rangemin = 0, rangemax = 0; | ||
1112 | |||
1113 | struct output *o; | ||
1114 | struct sets *s; | ||
1115 | int i, start, limit; | ||
1116 | |||
1117 | while (--argc) { | ||
1118 | char *p = *++argv; | ||
1119 | int c; | ||
1120 | |||
1121 | if (doing_opts && *p == '-') { | ||
1122 | p++; | ||
1123 | |||
1124 | if (!strcmp(p, "-")) { | ||
1125 | doing_opts = false; | ||
1126 | continue; | ||
1127 | } else if (*p == '-') { | ||
1128 | p++; | ||
1129 | if (!strcmp(p, "debug-bfs")) { | ||
1130 | debug_bfs = true; | ||
1131 | } else { | ||
1132 | fprintf(stderr, "%s: option '--%s' not recognised\n", | ||
1133 | pname, p); | ||
1134 | } | ||
1135 | } else while (p && *p) switch (c = *p++) { | ||
1136 | case 'C': | ||
1137 | rules = &rules_countdown; | ||
1138 | break; | ||
1139 | case 'B': | ||
1140 | rules = &rules_3388; | ||
1141 | break; | ||
1142 | case 'D': | ||
1143 | rules = &rules_four4s; | ||
1144 | break; | ||
1145 | case 'A': | ||
1146 | rules = &rules_anythinggoes; | ||
1147 | break; | ||
1148 | case 'v': | ||
1149 | verbose = true; | ||
1150 | break; | ||
1151 | case 'p': | ||
1152 | pathcounts = true; | ||
1153 | break; | ||
1154 | case 'm': | ||
1155 | multiple = true; | ||
1156 | break; | ||
1157 | case 't': | ||
1158 | case 'r': | ||
1159 | { | ||
1160 | char *v; | ||
1161 | if (*p) { | ||
1162 | v = p; | ||
1163 | p = NULL; | ||
1164 | } else if (--argc) { | ||
1165 | v = *++argv; | ||
1166 | } else { | ||
1167 | fprintf(stderr, "%s: option '-%c' expects an" | ||
1168 | " argument\n", pname, c); | ||
1169 | return 1; | ||
1170 | } | ||
1171 | switch (c) { | ||
1172 | case 't': | ||
1173 | got_target = true; | ||
1174 | target = atoi(v); | ||
1175 | break; | ||
1176 | case 'r': | ||
1177 | { | ||
1178 | char *sep = strchr(v, '-'); | ||
1179 | got_range = true; | ||
1180 | if (sep) { | ||
1181 | rangemin = atoi(v); | ||
1182 | rangemax = atoi(sep+1); | ||
1183 | } else { | ||
1184 | rangemin = 0; | ||
1185 | rangemax = atoi(v); | ||
1186 | } | ||
1187 | } | ||
1188 | break; | ||
1189 | } | ||
1190 | } | ||
1191 | break; | ||
1192 | default: | ||
1193 | fprintf(stderr, "%s: option '-%c' not" | ||
1194 | " recognised\n", pname, c); | ||
1195 | return 1; | ||
1196 | } | ||
1197 | } else { | ||
1198 | if (nnumbers >= lenof(numbers)) { | ||
1199 | fprintf(stderr, "%s: internal limit of %d numbers exceeded\n", | ||
1200 | pname, (int)lenof(numbers)); | ||
1201 | return 1; | ||
1202 | } else { | ||
1203 | numbers[nnumbers++] = atoi(p); | ||
1204 | } | ||
1205 | } | ||
1206 | } | ||
1207 | |||
1208 | if (!rules) { | ||
1209 | fprintf(stderr, "%s: no rule set specified; use -C,-B,-D,-A\n", pname); | ||
1210 | return 1; | ||
1211 | } | ||
1212 | |||
1213 | if (!nnumbers) { | ||
1214 | fprintf(stderr, "%s: no input numbers specified\n", pname); | ||
1215 | return 1; | ||
1216 | } | ||
1217 | |||
1218 | if (got_range) { | ||
1219 | if (got_target) { | ||
1220 | fprintf(stderr, "%s: only one of -t and -r may be specified\n", pname); | ||
1221 | return 1; | ||
1222 | } | ||
1223 | if (rangemin >= rangemax) { | ||
1224 | fprintf(stderr, "%s: range not sensible (%d - %d)\n", pname, rangemin, rangemax); | ||
1225 | return 1; | ||
1226 | } | ||
1227 | } | ||
1228 | |||
1229 | s = do_search(nnumbers, numbers, rules, (got_target ? &target : NULL), | ||
1230 | debug_bfs, multiple); | ||
1231 | |||
1232 | if (got_target) { | ||
1233 | o = findrelpos234(s->outputtree, &target, outputfindcmp, | ||
1234 | REL234_LE, &start); | ||
1235 | if (!o) | ||
1236 | start = -1; | ||
1237 | o = findrelpos234(s->outputtree, &target, outputfindcmp, | ||
1238 | REL234_GE, &limit); | ||
1239 | if (!o) | ||
1240 | limit = -1; | ||
1241 | assert(start != -1 || limit != -1); | ||
1242 | if (start == -1) | ||
1243 | start = limit; | ||
1244 | else if (limit == -1) | ||
1245 | limit = start; | ||
1246 | limit++; | ||
1247 | } else if (got_range) { | ||
1248 | if (!findrelpos234(s->outputtree, &rangemin, outputfindcmp, | ||
1249 | REL234_GE, &start) || | ||
1250 | !findrelpos234(s->outputtree, &rangemax, outputfindcmp, | ||
1251 | REL234_LE, &limit)) { | ||
1252 | printf("No solutions available in specified range %d-%d\n", rangemin, rangemax); | ||
1253 | return 1; | ||
1254 | } | ||
1255 | limit++; | ||
1256 | } else { | ||
1257 | start = 0; | ||
1258 | limit = count234(s->outputtree); | ||
1259 | } | ||
1260 | |||
1261 | for (i = start; i < limit; i++) { | ||
1262 | char buf[256]; | ||
1263 | |||
1264 | o = index234(s->outputtree, i); | ||
1265 | |||
1266 | sprintf(buf, "%d", o->number); | ||
1267 | |||
1268 | if (pathcounts) | ||
1269 | sprintf(buf + strlen(buf), " [%d]", o->npaths); | ||
1270 | |||
1271 | if (got_target || verbose) { | ||
1272 | int j, npaths; | ||
1273 | |||
1274 | if (multiple) | ||
1275 | npaths = o->npaths; | ||
1276 | else | ||
1277 | npaths = 1; | ||
1278 | |||
1279 | for (j = 0; j < npaths; j++) { | ||
1280 | printf("%s = ", buf); | ||
1281 | print(j, s, o); | ||
1282 | putchar('\n'); | ||
1283 | } | ||
1284 | } else { | ||
1285 | printf("%s\n", buf); | ||
1286 | } | ||
1287 | } | ||
1288 | |||
1289 | free_sets(s); | ||
1290 | |||
1291 | return 0; | ||
1292 | } | ||
1293 | |||
1294 | /* vim: set shiftwidth=4 tabstop=8: */ | ||