f278dcf4 |
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 <limits.h> |
41 | #include <assert.h> |
42 | |
43 | #include "puzzles.h" |
44 | #include "tree234.h" |
45 | |
46 | /* |
47 | * To search for numbers we can make, we employ a breadth-first |
48 | * search across the space of sets of input numbers. That is, for |
49 | * example, we start with the set (3,6,25,50,75,100); we apply |
50 | * moves which involve combining two numbers (e.g. adding the 50 |
51 | * and the 75 takes us to the set (3,6,25,100,125); and then we see |
52 | * if we ever end up with a set containing (say) 952. |
53 | * |
54 | * If the rules are changed so that all the numbers must be used, |
55 | * this is easy to adjust to: we simply see if we end up with a set |
56 | * containing _only_ (say) 952. |
57 | * |
58 | * Obviously, we can vary the rules about permitted arithmetic |
59 | * operations simply by altering the set of valid moves in the bfs. |
60 | * However, there's one common rule in this sort of puzzle which |
61 | * takes a little more thought, and that's _concatenation_. For |
62 | * example, if you are given (say) four 4s and required to make 10, |
63 | * you are permitted to combine two of the 4s into a 44 to begin |
64 | * with, making (44-4)/4 = 10. However, you are generally not |
65 | * allowed to concatenate two numbers that _weren't_ both in the |
66 | * original input set (you couldn't multiply two 4s to get 16 and |
67 | * then concatenate a 4 on to it to make 164), so concatenation is |
68 | * not an operation which is valid in all situations. |
69 | * |
70 | * We could enforce this restriction by storing a flag alongside |
71 | * each number indicating whether or not it's an original number; |
72 | * the rules being that concatenation of two numbers is only valid |
73 | * if they both have the original flag, and that its output _also_ |
74 | * has the original flag (so that you can concatenate three 4s into |
75 | * a 444), but that applying any other arithmetic operation clears |
76 | * the original flag on the output. However, we can get marginally |
77 | * simpler than that by observing that since concatenation has to |
78 | * happen to a number before any other operation, we can simply |
79 | * place all the concatenations at the start of the search. In |
80 | * other words, we have a global flag on an entire number _set_ |
81 | * which indicates whether we are still permitted to perform |
82 | * concatenations; if so, we can concatenate any of the numbers in |
83 | * that set. Performing any other operation clears the flag. |
84 | */ |
85 | |
86 | #define SETFLAG_CONCAT 1 /* we can do concatenation */ |
87 | |
88 | struct sets; |
89 | |
90 | struct set { |
91 | int *numbers; /* rationals stored as n,d pairs */ |
92 | short nnumbers; /* # of rationals, so half # of ints */ |
93 | short flags; /* SETFLAG_CONCAT only, at present */ |
94 | struct set *prev; /* index of ancestor set in set list */ |
95 | unsigned char pa, pb, po, pr; /* operation that got here from prev */ |
96 | int npaths; /* number of ways to reach this set */ |
97 | }; |
98 | |
99 | struct output { |
100 | int number; |
101 | struct set *set; |
102 | int index; /* which number in the set is it? */ |
103 | int npaths; /* number of ways to reach this */ |
104 | }; |
105 | |
106 | #define SETLISTLEN 1024 |
107 | #define NUMBERLISTLEN 32768 |
108 | #define OUTPUTLISTLEN 1024 |
109 | struct operation; |
110 | struct sets { |
111 | struct set **setlists; |
112 | int nsets, nsetlists, setlistsize; |
113 | tree234 *settree; |
114 | int **numberlists; |
115 | int nnumbers, nnumberlists, numberlistsize; |
116 | struct output **outputlists; |
117 | int noutputs, noutputlists, outputlistsize; |
118 | tree234 *outputtree; |
119 | const struct operation *const *ops; |
120 | }; |
121 | |
122 | #define OPFLAG_NEEDS_CONCAT 1 |
123 | #define OPFLAG_KEEPS_CONCAT 2 |
124 | |
125 | struct operation { |
126 | /* |
127 | * Most operations should be shown in the output working, but |
128 | * concatenation should not; we just take the result of the |
129 | * concatenation and assume that it's obvious how it was |
130 | * derived. |
131 | */ |
132 | int display; |
133 | |
134 | /* |
135 | * Text display of the operator. |
136 | */ |
137 | char *text; |
138 | |
139 | /* |
140 | * Flags dictating when the operator can be applied. |
141 | */ |
142 | int flags; |
143 | |
144 | /* |
145 | * Priority of the operator (for avoiding unnecessary |
146 | * parentheses when formatting it into a string). |
147 | */ |
148 | int priority; |
149 | |
150 | /* |
151 | * Associativity of the operator. Bit 0 means we need parens |
152 | * when the left operand of one of these operators is another |
153 | * instance of it, e.g. (2^3)^4. Bit 1 means we need parens |
154 | * when the right operand is another instance of the same |
155 | * operator, e.g. 2-(3-4). Thus: |
156 | * |
157 | * - this field is 0 for a fully associative operator, since |
158 | * we never need parens. |
159 | * - it's 1 for a right-associative operator. |
160 | * - it's 2 for a left-associative operator. |
161 | * - it's 3 for a _non_-associative operator (which always |
162 | * uses parens just to be sure). |
163 | */ |
164 | int assoc; |
165 | |
166 | /* |
167 | * Whether the operator is commutative. Saves time in the |
168 | * search if we don't have to try it both ways round. |
169 | */ |
170 | int commutes; |
171 | |
172 | /* |
173 | * Function which implements the operator. Returns TRUE on |
174 | * success, FALSE on failure. Takes two rationals and writes |
175 | * out a third. |
176 | */ |
177 | int (*perform)(int *a, int *b, int *output); |
178 | }; |
179 | |
180 | struct rules { |
181 | const struct operation *const *ops; |
182 | int use_all; |
183 | }; |
184 | |
185 | #define MUL(r, a, b) do { \ |
186 | (r) = (a) * (b); \ |
187 | if ((b) && (a) && (r) / (b) != (a)) return FALSE; \ |
188 | } while (0) |
189 | |
190 | #define ADD(r, a, b) do { \ |
191 | (r) = (a) + (b); \ |
192 | if ((a) > 0 && (b) > 0 && (r) < 0) return FALSE; \ |
193 | if ((a) < 0 && (b) < 0 && (r) > 0) return FALSE; \ |
194 | } while (0) |
195 | |
196 | #define OUT(output, n, d) do { \ |
197 | int g = gcd((n),(d)); \ |
198 | if ((d) < 0) g = -g; \ |
199 | (output)[0] = (n)/g; \ |
200 | (output)[1] = (d)/g; \ |
201 | assert((output)[1] > 0); \ |
202 | } while (0) |
203 | |
204 | static int gcd(int x, int y) |
205 | { |
206 | while (x != 0 && y != 0) { |
207 | int t = x; |
208 | x = y; |
209 | y = t % y; |
210 | } |
211 | |
212 | return abs(x + y); /* i.e. whichever one isn't zero */ |
213 | } |
214 | |
215 | static int perform_add(int *a, int *b, int *output) |
216 | { |
217 | int at, bt, tn, bn; |
218 | /* |
219 | * a0/a1 + b0/b1 = (a0*b1 + b0*a1) / (a1*b1) |
220 | */ |
221 | MUL(at, a[0], b[1]); |
222 | MUL(bt, b[0], a[1]); |
223 | ADD(tn, at, bt); |
224 | MUL(bn, a[1], b[1]); |
225 | OUT(output, tn, bn); |
226 | return TRUE; |
227 | } |
228 | |
229 | static int perform_sub(int *a, int *b, int *output) |
230 | { |
231 | int at, bt, tn, bn; |
232 | /* |
233 | * a0/a1 - b0/b1 = (a0*b1 - b0*a1) / (a1*b1) |
234 | */ |
235 | MUL(at, a[0], b[1]); |
236 | MUL(bt, b[0], a[1]); |
237 | ADD(tn, at, -bt); |
238 | MUL(bn, a[1], b[1]); |
239 | OUT(output, tn, bn); |
240 | return TRUE; |
241 | } |
242 | |
243 | static int perform_mul(int *a, int *b, int *output) |
244 | { |
245 | int tn, bn; |
246 | /* |
247 | * a0/a1 * b0/b1 = (a0*b0) / (a1*b1) |
248 | */ |
249 | MUL(tn, a[0], b[0]); |
250 | MUL(bn, a[1], b[1]); |
251 | OUT(output, tn, bn); |
252 | return TRUE; |
253 | } |
254 | |
255 | static int perform_div(int *a, int *b, int *output) |
256 | { |
257 | int tn, bn; |
258 | |
259 | /* |
260 | * Division by zero is outlawed. |
261 | */ |
262 | if (b[0] == 0) |
263 | return FALSE; |
264 | |
265 | /* |
266 | * a0/a1 / b0/b1 = (a0*b1) / (a1*b0) |
267 | */ |
268 | MUL(tn, a[0], b[1]); |
269 | MUL(bn, a[1], b[0]); |
270 | OUT(output, tn, bn); |
271 | return TRUE; |
272 | } |
273 | |
274 | static int perform_exact_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 | |
291 | /* |
292 | * Exact division means we require the result to be an integer. |
293 | */ |
294 | return (output[1] == 1); |
295 | } |
296 | |
297 | static int perform_concat(int *a, int *b, int *output) |
298 | { |
299 | int t1, t2, p10; |
300 | |
301 | /* |
302 | * We can't concatenate anything which isn't an integer. |
303 | */ |
304 | if (a[1] != 1 || b[1] != 1) |
305 | return FALSE; |
306 | |
307 | /* |
308 | * For concatenation, we can safely assume leading zeroes |
309 | * aren't an issue. It isn't clear whether they `should' be |
310 | * allowed, but it turns out not to matter: concatenating a |
311 | * leading zero on to a number in order to harmlessly get rid |
312 | * of the zero is never necessary because unwanted zeroes can |
313 | * be disposed of by adding them to something instead. So we |
314 | * disallow them always. |
315 | * |
316 | * The only other possibility is that you might want to |
317 | * concatenate a leading zero on to something and then |
318 | * concatenate another non-zero digit on to _that_ (to make, |
319 | * for example, 106); but that's also unnecessary, because you |
320 | * can make 106 just as easily by concatenating the 0 on to the |
321 | * _end_ of the 1 first. |
322 | */ |
323 | if (a[0] == 0) |
324 | return FALSE; |
325 | |
326 | /* |
327 | * Find the smallest power of ten strictly greater than b. This |
328 | * is the power of ten by which we'll multiply a. |
329 | * |
330 | * Special case: we must multiply a by at least 10, even if b |
331 | * is zero. |
332 | */ |
333 | p10 = 10; |
334 | while (p10 <= (INT_MAX/10) && p10 <= b[0]) |
335 | p10 *= 10; |
336 | if (p10 > INT_MAX/10) |
337 | return FALSE; /* integer overflow */ |
338 | MUL(t1, p10, a[0]); |
339 | ADD(t2, t1, b[0]); |
340 | OUT(output, t2, 1); |
341 | return TRUE; |
342 | } |
343 | |
344 | const static struct operation op_add = { |
345 | TRUE, "+", 0, 10, 0, TRUE, perform_add |
346 | }; |
347 | const static struct operation op_sub = { |
348 | TRUE, "-", 0, 10, 2, FALSE, perform_sub |
349 | }; |
350 | const static struct operation op_mul = { |
351 | TRUE, "*", 0, 20, 0, TRUE, perform_mul |
352 | }; |
353 | const static struct operation op_div = { |
354 | TRUE, "/", 0, 20, 2, FALSE, perform_div |
355 | }; |
356 | const static struct operation op_xdiv = { |
357 | TRUE, "/", 0, 20, 2, FALSE, perform_exact_div |
358 | }; |
359 | const static struct operation op_concat = { |
360 | FALSE, "", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT, |
361 | 1000, 0, FALSE, perform_concat |
362 | }; |
363 | |
364 | /* |
365 | * In Countdown, divisions resulting in fractions are disallowed. |
366 | * http://www.askoxford.com/wordgames/countdown/rules/ |
367 | */ |
368 | const static struct operation *const ops_countdown[] = { |
369 | &op_add, &op_mul, &op_sub, &op_xdiv, NULL |
370 | }; |
371 | const static struct rules rules_countdown = { |
372 | ops_countdown, FALSE |
373 | }; |
374 | |
375 | /* |
376 | * A slightly different rule set which handles the reasonably well |
377 | * known puzzle of making 24 using two 3s and two 8s. For this we |
378 | * need rational rather than integer division. |
379 | */ |
380 | const static struct operation *const ops_3388[] = { |
381 | &op_add, &op_mul, &op_sub, &op_div, NULL |
382 | }; |
383 | const static struct rules rules_3388 = { |
384 | ops_3388, TRUE |
385 | }; |
386 | |
387 | /* |
388 | * A still more permissive rule set usable for the four-4s problem |
389 | * and similar things. Permits concatenation. |
390 | */ |
391 | const static struct operation *const ops_four4s[] = { |
392 | &op_add, &op_mul, &op_sub, &op_div, &op_concat, NULL |
393 | }; |
394 | const static struct rules rules_four4s = { |
395 | ops_four4s, TRUE |
396 | }; |
397 | |
398 | #define ratcmp(a,op,b) ( (long long)(a)[0] * (b)[1] op \ |
399 | (long long)(b)[0] * (a)[1] ) |
400 | |
401 | static int addtoset(struct set *set, int newnumber[2]) |
402 | { |
403 | int i, j; |
404 | |
405 | /* Find where we want to insert the new number */ |
406 | for (i = 0; i < set->nnumbers && |
407 | ratcmp(set->numbers+2*i, <, newnumber); i++); |
408 | |
409 | /* Move everything else up */ |
410 | for (j = set->nnumbers; j > i; j--) { |
411 | set->numbers[2*j] = set->numbers[2*j-2]; |
412 | set->numbers[2*j+1] = set->numbers[2*j-1]; |
413 | } |
414 | |
415 | /* Insert the new number */ |
416 | set->numbers[2*i] = newnumber[0]; |
417 | set->numbers[2*i+1] = newnumber[1]; |
418 | |
419 | set->nnumbers++; |
420 | |
421 | return i; |
422 | } |
423 | |
424 | #define ensure(array, size, newlen, type) do { \ |
425 | if ((newlen) > (size)) { \ |
426 | (size) = (newlen) + 512; \ |
427 | (array) = sresize((array), (size), type); \ |
428 | } \ |
429 | } while (0) |
430 | |
431 | static int setcmp(void *av, void *bv) |
432 | { |
433 | struct set *a = (struct set *)av; |
434 | struct set *b = (struct set *)bv; |
435 | int i; |
436 | |
437 | if (a->nnumbers < b->nnumbers) |
438 | return -1; |
439 | else if (a->nnumbers > b->nnumbers) |
440 | return +1; |
441 | |
442 | if (a->flags < b->flags) |
443 | return -1; |
444 | else if (a->flags > b->flags) |
445 | return +1; |
446 | |
447 | for (i = 0; i < a->nnumbers; i++) { |
448 | if (ratcmp(a->numbers+2*i, <, b->numbers+2*i)) |
449 | return -1; |
450 | else if (ratcmp(a->numbers+2*i, >, b->numbers+2*i)) |
451 | return +1; |
452 | } |
453 | |
454 | return 0; |
455 | } |
456 | |
457 | static int outputcmp(void *av, void *bv) |
458 | { |
459 | struct output *a = (struct output *)av; |
460 | struct output *b = (struct output *)bv; |
461 | |
462 | if (a->number < b->number) |
463 | return -1; |
464 | else if (a->number > b->number) |
465 | return +1; |
466 | |
467 | return 0; |
468 | } |
469 | |
470 | static int outputfindcmp(void *av, void *bv) |
471 | { |
472 | int *a = (int *)av; |
473 | struct output *b = (struct output *)bv; |
474 | |
475 | if (*a < b->number) |
476 | return -1; |
477 | else if (*a > b->number) |
478 | return +1; |
479 | |
480 | return 0; |
481 | } |
482 | |
483 | static void addset(struct sets *s, struct set *set, struct set *prev) |
484 | { |
485 | struct set *s2; |
486 | int npaths = (prev ? prev->npaths : 1); |
487 | |
488 | assert(set == s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN); |
489 | s2 = add234(s->settree, set); |
490 | if (s2 == set) { |
491 | /* |
492 | * New set added to the tree. |
493 | */ |
494 | set->prev = prev; |
495 | set->npaths = npaths; |
496 | s->nsets++; |
497 | s->nnumbers += 2 * set->nnumbers; |
498 | } else { |
499 | /* |
500 | * Rediscovered an existing set. Update its npaths only. |
501 | */ |
502 | s2->npaths += npaths; |
503 | } |
504 | } |
505 | |
506 | static struct set *newset(struct sets *s, int nnumbers, int flags) |
507 | { |
508 | struct set *sn; |
509 | |
510 | ensure(s->setlists, s->setlistsize, s->nsets/SETLISTLEN+1, struct set *); |
511 | while (s->nsetlists <= s->nsets / SETLISTLEN) |
512 | s->setlists[s->nsetlists++] = snewn(SETLISTLEN, struct set); |
513 | sn = s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN; |
514 | |
515 | if (s->nnumbers + nnumbers * 2 > s->nnumberlists * NUMBERLISTLEN) |
516 | s->nnumbers = s->nnumberlists * NUMBERLISTLEN; |
517 | ensure(s->numberlists, s->numberlistsize, |
518 | s->nnumbers/NUMBERLISTLEN+1, int *); |
519 | while (s->nnumberlists <= s->nnumbers / NUMBERLISTLEN) |
520 | s->numberlists[s->nnumberlists++] = snewn(NUMBERLISTLEN, int); |
521 | sn->numbers = s->numberlists[s->nnumbers / NUMBERLISTLEN] + |
522 | s->nnumbers % NUMBERLISTLEN; |
523 | |
524 | /* |
525 | * Start the set off empty. |
526 | */ |
527 | sn->nnumbers = 0; |
528 | |
529 | sn->flags = flags; |
530 | |
531 | return sn; |
532 | } |
533 | |
534 | static int addoutput(struct sets *s, struct set *ss, int index, int *n) |
535 | { |
536 | struct output *o, *o2; |
537 | |
538 | /* |
539 | * Target numbers are always integers. |
540 | */ |
541 | if (ss->numbers[2*index+1] != 1) |
542 | return FALSE; |
543 | |
544 | ensure(s->outputlists, s->outputlistsize, s->noutputs/OUTPUTLISTLEN+1, |
545 | struct output *); |
546 | while (s->noutputlists <= s->noutputs / OUTPUTLISTLEN) |
547 | s->outputlists[s->noutputlists++] = snewn(OUTPUTLISTLEN, |
548 | struct output); |
549 | o = s->outputlists[s->noutputs / OUTPUTLISTLEN] + |
550 | s->noutputs % OUTPUTLISTLEN; |
551 | |
552 | o->number = ss->numbers[2*index]; |
553 | o->set = ss; |
554 | o->index = index; |
555 | o->npaths = ss->npaths; |
556 | o2 = add234(s->outputtree, o); |
557 | if (o2 != o) { |
558 | o2->npaths += o->npaths; |
559 | } else { |
560 | s->noutputs++; |
561 | } |
562 | *n = o->number; |
563 | return TRUE; |
564 | } |
565 | |
566 | static struct sets *do_search(int ninputs, int *inputs, |
567 | const struct rules *rules, int *target) |
568 | { |
569 | struct sets *s; |
570 | struct set *sn; |
571 | int qpos, i; |
572 | const struct operation *const *ops = rules->ops; |
573 | |
574 | s = snew(struct sets); |
575 | s->setlists = NULL; |
576 | s->nsets = s->nsetlists = s->setlistsize = 0; |
577 | s->numberlists = NULL; |
578 | s->nnumbers = s->nnumberlists = s->numberlistsize = 0; |
579 | s->outputlists = NULL; |
580 | s->noutputs = s->noutputlists = s->outputlistsize = 0; |
581 | s->settree = newtree234(setcmp); |
582 | s->outputtree = newtree234(outputcmp); |
583 | s->ops = ops; |
584 | |
585 | /* |
586 | * Start with the input set. |
587 | */ |
588 | sn = newset(s, ninputs, SETFLAG_CONCAT); |
589 | for (i = 0; i < ninputs; i++) { |
590 | int newnumber[2]; |
591 | newnumber[0] = inputs[i]; |
592 | newnumber[1] = 1; |
593 | addtoset(sn, newnumber); |
594 | } |
595 | addset(s, sn, NULL); |
596 | |
597 | /* |
598 | * Now perform the breadth-first search: keep looping over sets |
599 | * until we run out of steam. |
600 | */ |
601 | qpos = 0; |
602 | while (qpos < s->nsets) { |
603 | struct set *ss = s->setlists[qpos / SETLISTLEN] + qpos % SETLISTLEN; |
604 | struct set *sn; |
605 | int i, j, k, m; |
606 | |
607 | /* |
608 | * Record all the valid output numbers in this state. We |
609 | * can always do this if there's only one number in the |
610 | * state; otherwise, we can only do it if we aren't |
611 | * required to use all the numbers in coming to our answer. |
612 | */ |
613 | if (ss->nnumbers == 1 || !rules->use_all) { |
614 | for (i = 0; i < ss->nnumbers; i++) { |
615 | int n; |
616 | |
617 | if (addoutput(s, ss, i, &n) && target && n == *target) |
618 | return s; |
619 | } |
620 | } |
621 | |
622 | /* |
623 | * Try every possible operation from this state. |
624 | */ |
625 | for (k = 0; ops[k] && ops[k]->perform; k++) { |
626 | if ((ops[k]->flags & OPFLAG_NEEDS_CONCAT) && |
627 | !(ss->flags & SETFLAG_CONCAT)) |
628 | continue; /* can't use this operation here */ |
629 | for (i = 0; i < ss->nnumbers; i++) { |
630 | for (j = 0; j < ss->nnumbers; j++) { |
631 | int n[2]; |
632 | |
633 | if (i == j) |
634 | continue; /* can't combine a number with itself */ |
635 | if (i > j && ops[k]->commutes) |
636 | continue; /* no need to do this both ways round */ |
637 | if (!ops[k]->perform(ss->numbers+2*i, ss->numbers+2*j, n)) |
638 | continue; /* operation failed */ |
639 | |
640 | sn = newset(s, ss->nnumbers-1, ss->flags); |
641 | |
642 | if (!(ops[k]->flags & OPFLAG_KEEPS_CONCAT)) |
643 | sn->flags &= ~SETFLAG_CONCAT; |
644 | |
645 | for (m = 0; m < ss->nnumbers; m++) { |
646 | if (m == i || m == j) |
647 | continue; |
648 | sn->numbers[2*sn->nnumbers] = ss->numbers[2*m]; |
649 | sn->numbers[2*sn->nnumbers + 1] = ss->numbers[2*m + 1]; |
650 | sn->nnumbers++; |
651 | } |
652 | sn->pa = i; |
653 | sn->pb = j; |
654 | sn->po = k; |
655 | sn->pr = addtoset(sn, n); |
656 | addset(s, sn, ss); |
657 | } |
658 | } |
659 | } |
660 | |
661 | qpos++; |
662 | } |
663 | |
664 | return s; |
665 | } |
666 | |
667 | static void free_sets(struct sets *s) |
668 | { |
669 | int i; |
670 | |
671 | freetree234(s->settree); |
672 | freetree234(s->outputtree); |
673 | for (i = 0; i < s->nsetlists; i++) |
674 | sfree(s->setlists[i]); |
675 | sfree(s->setlists); |
676 | for (i = 0; i < s->nnumberlists; i++) |
677 | sfree(s->numberlists[i]); |
678 | sfree(s->numberlists); |
679 | for (i = 0; i < s->noutputlists; i++) |
680 | sfree(s->outputlists[i]); |
681 | sfree(s->outputlists); |
682 | sfree(s); |
683 | } |
684 | |
685 | /* |
686 | * Construct a text formula for producing a given output. |
687 | */ |
688 | void mkstring_recurse(char **str, int *len, |
689 | struct sets *s, struct set *ss, int index, |
690 | int priority, int assoc, int child) |
691 | { |
692 | if (ss->prev && index != ss->pr) { |
693 | int pi; |
694 | |
695 | /* |
696 | * This number was passed straight down from this set's |
697 | * predecessor. Find its index in the previous set and |
698 | * recurse to there. |
699 | */ |
700 | pi = index; |
701 | assert(pi != ss->pr); |
702 | if (pi > ss->pr) |
703 | pi--; |
704 | if (pi >= min(ss->pa, ss->pb)) { |
705 | pi++; |
706 | if (pi >= max(ss->pa, ss->pb)) |
707 | pi++; |
708 | } |
709 | mkstring_recurse(str, len, s, ss->prev, pi, priority, assoc, child); |
710 | } else if (ss->prev && index == ss->pr && |
711 | s->ops[ss->po]->display) { |
712 | /* |
713 | * This number was created by a displayed operator in the |
714 | * transition from this set to its predecessor. Hence we |
715 | * write an open paren, then recurse into the first |
716 | * operand, then write the operator, then the second |
717 | * operand, and finally close the paren. |
718 | */ |
719 | char *op; |
720 | int parens, thispri, thisassoc; |
721 | |
722 | /* |
723 | * Determine whether we need parentheses. |
724 | */ |
725 | thispri = s->ops[ss->po]->priority; |
726 | thisassoc = s->ops[ss->po]->assoc; |
727 | parens = (thispri < priority || |
728 | (thispri == priority && (assoc & child))); |
729 | |
730 | if (parens) { |
731 | if (str) |
732 | *(*str)++ = '('; |
733 | if (len) |
734 | (*len)++; |
735 | } |
736 | mkstring_recurse(str, len, s, ss->prev, ss->pa, thispri, thisassoc, 1); |
737 | for (op = s->ops[ss->po]->text; *op; op++) { |
738 | if (str) |
739 | *(*str)++ = *op; |
740 | if (len) |
741 | (*len)++; |
742 | } |
743 | mkstring_recurse(str, len, s, ss->prev, ss->pb, thispri, thisassoc, 2); |
744 | if (parens) { |
745 | if (str) |
746 | *(*str)++ = ')'; |
747 | if (len) |
748 | (*len)++; |
749 | } |
750 | } else { |
751 | /* |
752 | * This number is either an original, or something formed |
753 | * by a non-displayed operator (concatenation). Either way, |
754 | * we display it as is. |
755 | */ |
756 | char buf[80], *p; |
757 | int blen; |
758 | blen = sprintf(buf, "%d", ss->numbers[2*index]); |
759 | if (ss->numbers[2*index+1] != 1) |
760 | blen += sprintf(buf+blen, "/%d", ss->numbers[2*index+1]); |
761 | assert(blen < lenof(buf)); |
762 | for (p = buf; *p; p++) { |
763 | if (str) |
764 | *(*str)++ = *p; |
765 | if (len) |
766 | (*len)++; |
767 | } |
768 | } |
769 | } |
770 | char *mkstring(struct sets *s, struct output *o) |
771 | { |
772 | int len; |
773 | char *str, *p; |
774 | |
775 | len = 0; |
776 | mkstring_recurse(NULL, &len, s, o->set, o->index, 0, 0, 0); |
777 | str = snewn(len+1, char); |
778 | p = str; |
779 | mkstring_recurse(&p, NULL, s, o->set, o->index, 0, 0, 0); |
780 | assert(p - str <= len); |
781 | *p = '\0'; |
782 | return str; |
783 | } |
784 | |
785 | int main(int argc, char **argv) |
786 | { |
787 | int doing_opts = TRUE; |
788 | const struct rules *rules = NULL; |
789 | char *pname = argv[0]; |
790 | int got_target = FALSE, target = 0; |
791 | int numbers[10], nnumbers = 0; |
792 | int verbose = FALSE; |
793 | int pathcounts = FALSE; |
794 | |
795 | struct output *o; |
796 | struct sets *s; |
797 | int i, start, limit; |
798 | |
799 | while (--argc) { |
800 | char *p = *++argv; |
801 | int c; |
802 | |
803 | if (doing_opts && *p == '-') { |
804 | p++; |
805 | |
806 | if (!strcmp(p, "-")) { |
807 | doing_opts = FALSE; |
808 | continue; |
809 | } else while (*p) switch (c = *p++) { |
810 | case 'C': |
811 | rules = &rules_countdown; |
812 | break; |
813 | case 'B': |
814 | rules = &rules_3388; |
815 | break; |
816 | case 'D': |
817 | rules = &rules_four4s; |
818 | break; |
819 | case 'v': |
820 | verbose = TRUE; |
821 | break; |
822 | case 'p': |
823 | pathcounts = TRUE; |
824 | break; |
825 | case 't': |
826 | { |
827 | char *v; |
828 | if (*p) { |
829 | v = p; |
830 | p = NULL; |
831 | } else if (--argc) { |
832 | v = *++argv; |
833 | } else { |
834 | fprintf(stderr, "%s: option '-%c' expects an" |
835 | " argument\n", pname, c); |
836 | return 1; |
837 | } |
838 | switch (c) { |
839 | case 't': |
840 | got_target = TRUE; |
841 | target = atoi(v); |
842 | break; |
843 | } |
844 | } |
845 | break; |
846 | default: |
847 | fprintf(stderr, "%s: option '-%c' not" |
848 | " recognised\n", pname, c); |
849 | return 1; |
850 | } |
851 | } else { |
852 | if (nnumbers >= lenof(numbers)) { |
853 | fprintf(stderr, "%s: internal limit of %d numbers exceeded\n", |
854 | pname, lenof(numbers)); |
855 | return 1; |
856 | } else { |
857 | numbers[nnumbers++] = atoi(p); |
858 | } |
859 | } |
860 | } |
861 | |
862 | if (!rules) { |
863 | fprintf(stderr, "%s: no rule set specified; use -C,-B,-D\n", pname); |
864 | return 1; |
865 | } |
866 | |
867 | if (!nnumbers) { |
868 | fprintf(stderr, "%s: no input numbers specified\n", pname); |
869 | return 1; |
870 | } |
871 | |
872 | s = do_search(nnumbers, numbers, rules, (got_target ? &target : NULL)); |
873 | |
874 | if (got_target) { |
875 | o = findrelpos234(s->outputtree, &target, outputfindcmp, |
876 | REL234_LE, &start); |
877 | if (!o) |
878 | start = -1; |
879 | o = findrelpos234(s->outputtree, &target, outputfindcmp, |
880 | REL234_GE, &limit); |
881 | if (!o) |
882 | limit = -1; |
883 | assert(start != -1 || limit != -1); |
884 | if (start == -1) |
885 | start = limit; |
886 | else if (limit == -1) |
887 | limit = start; |
888 | limit++; |
889 | } else { |
890 | start = 0; |
891 | limit = count234(s->outputtree); |
892 | } |
893 | |
894 | for (i = start; i < limit; i++) { |
895 | o = index234(s->outputtree, i); |
896 | |
897 | printf("%d", o->number); |
898 | |
899 | if (pathcounts) |
900 | printf(" [%d]", o->npaths); |
901 | |
902 | if (got_target || verbose) { |
903 | char *p = mkstring(s, o); |
904 | printf(" = %s", p); |
905 | sfree(p); |
906 | } |
907 | |
908 | printf("\n"); |
909 | } |
910 | |
911 | free_sets(s); |
912 | |
913 | return 0; |
914 | } |