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'.
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.
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
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
49 * To search for numbers we can make, we employ a breadth-first
50 * search across the space of sets of input numbers. That is, for
51 * example, we start with the set (3,6,25,50,75,100); we apply
52 * moves which involve combining two numbers (e.g. adding the 50
53 * and the 75 takes us to the set (3,6,25,100,125); and then we see
54 * if we ever end up with a set containing (say) 952.
56 * If the rules are changed so that all the numbers must be used,
57 * this is easy to adjust to: we simply see if we end up with a set
58 * containing _only_ (say) 952.
60 * Obviously, we can vary the rules about permitted arithmetic
61 * operations simply by altering the set of valid moves in the bfs.
62 * However, there's one common rule in this sort of puzzle which
63 * takes a little more thought, and that's _concatenation_. For
64 * example, if you are given (say) four 4s and required to make 10,
65 * you are permitted to combine two of the 4s into a 44 to begin
66 * with, making (44-4)/4 = 10. However, you are generally not
67 * allowed to concatenate two numbers that _weren't_ both in the
68 * original input set (you couldn't multiply two 4s to get 16 and
69 * then concatenate a 4 on to it to make 164), so concatenation is
70 * not an operation which is valid in all situations.
72 * We could enforce this restriction by storing a flag alongside
73 * each number indicating whether or not it's an original number;
74 * the rules being that concatenation of two numbers is only valid
75 * if they both have the original flag, and that its output _also_
76 * has the original flag (so that you can concatenate three 4s into
77 * a 444), but that applying any other arithmetic operation clears
78 * the original flag on the output. However, we can get marginally
79 * simpler than that by observing that since concatenation has to
80 * happen to a number before any other operation, we can simply
81 * place all the concatenations at the start of the search. In
82 * other words, we have a global flag on an entire number _set_
83 * which indicates whether we are still permitted to perform
84 * concatenations; if so, we can concatenate any of the numbers in
85 * that set. Performing any other operation clears the flag.
88 #define SETFLAG_CONCAT 1 /* we can do concatenation */
93 struct set *prev; /* index of ancestor set in set list */
94 unsigned char pa, pb, po, pr; /* operation that got here from prev */
98 int *numbers; /* rationals stored as n,d pairs */
99 short nnumbers; /* # of rationals, so half # of ints */
100 short flags; /* SETFLAG_CONCAT only, at present */
101 int npaths; /* number of ways to reach this set */
102 struct ancestor a; /* primary ancestor */
103 struct ancestor *as; /* further ancestors, if we care */
110 int index; /* which number in the set is it? */
111 int npaths; /* number of ways to reach this */
114 #define SETLISTLEN 1024
115 #define NUMBERLISTLEN 32768
116 #define OUTPUTLISTLEN 1024
119 struct set **setlists;
120 int nsets, nsetlists, setlistsize;
123 int nnumbers, nnumberlists, numberlistsize;
124 struct output **outputlists;
125 int noutputs, noutputlists, outputlistsize;
127 const struct operation *const *ops;
130 #define OPFLAG_NEEDS_CONCAT 1
131 #define OPFLAG_KEEPS_CONCAT 2
132 #define OPFLAG_UNARY 4
133 #define OPFLAG_UNARYPREFIX 8
138 * Most operations should be shown in the output working, but
139 * concatenation should not; we just take the result of the
140 * concatenation and assume that it's obvious how it was
146 * Text display of the operator, in expressions and for
147 * debugging respectively.
149 char *text, *dbgtext;
152 * Flags dictating when the operator can be applied.
157 * Priority of the operator (for avoiding unnecessary
158 * parentheses when formatting it into a string).
163 * Associativity of the operator. Bit 0 means we need parens
164 * when the left operand of one of these operators is another
165 * instance of it, e.g. (2^3)^4. Bit 1 means we need parens
166 * when the right operand is another instance of the same
167 * operator, e.g. 2-(3-4). Thus:
169 * - this field is 0 for a fully associative operator, since
170 * we never need parens.
171 * - it's 1 for a right-associative operator.
172 * - it's 2 for a left-associative operator.
173 * - it's 3 for a _non_-associative operator (which always
174 * uses parens just to be sure).
179 * Whether the operator is commutative. Saves time in the
180 * search if we don't have to try it both ways round.
185 * Function which implements the operator. Returns TRUE on
186 * success, FALSE on failure. Takes two rationals and writes
189 int (*perform)(int *a, int *b, int *output);
193 const struct operation *const *ops;
197 #define MUL(r, a, b) do { \
199 if ((b) && (a) && (r) / (b) != (a)) return FALSE; \
202 #define ADD(r, a, b) do { \
204 if ((a) > 0 && (b) > 0 && (r) < 0) return FALSE; \
205 if ((a) < 0 && (b) < 0 && (r) > 0) return FALSE; \
208 #define OUT(output, n, d) do { \
209 int g = gcd((n),(d)); \
211 if ((d) < 0) g = -g; \
212 if (g == -1 && (n) < -INT_MAX) return FALSE; \
213 if (g == -1 && (d) < -INT_MAX) return FALSE; \
214 (output)[0] = (n)/g; \
215 (output)[1] = (d)/g; \
216 assert((output)[1] > 0); \
219 static int gcd(int x, int y)
221 while (x != 0 && y != 0) {
227 return abs(x + y); /* i.e. whichever one isn't zero */
230 static int perform_add(int *a, int *b, int *output)
234 * a0/a1 + b0/b1 = (a0*b1 + b0*a1) / (a1*b1)
244 static int perform_sub(int *a, int *b, int *output)
248 * a0/a1 - b0/b1 = (a0*b1 - b0*a1) / (a1*b1)
258 static int perform_mul(int *a, int *b, int *output)
262 * a0/a1 * b0/b1 = (a0*b0) / (a1*b1)
270 static int perform_div(int *a, int *b, int *output)
275 * Division by zero is outlawed.
281 * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
289 static int perform_exact_div(int *a, int *b, int *output)
294 * Division by zero is outlawed.
300 * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
307 * Exact division means we require the result to be an integer.
309 return (output[1] == 1);
312 static int max_p10(int n, int *p10_r)
315 * Find the smallest power of ten strictly greater than n.
317 * Special case: we must return at least 10, even if n is
318 * zero. (This is because this function is used for finding
319 * the power of ten by which to multiply a number being
320 * concatenated to the front of n, and concatenating 1 to 0
321 * should yield 10 and not 1.)
324 while (p10 <= (INT_MAX/10) && p10 <= n)
326 if (p10 > INT_MAX/10)
327 return FALSE; /* integer overflow */
332 static int perform_concat(int *a, int *b, int *output)
337 * We can't concatenate anything which isn't a non-negative
340 if (a[1] != 1 || b[1] != 1 || a[0] < 0 || b[0] < 0)
344 * For concatenation, we can safely assume leading zeroes
345 * aren't an issue. It isn't clear whether they `should' be
346 * allowed, but it turns out not to matter: concatenating a
347 * leading zero on to a number in order to harmlessly get rid
348 * of the zero is never necessary because unwanted zeroes can
349 * be disposed of by adding them to something instead. So we
350 * disallow them always.
352 * The only other possibility is that you might want to
353 * concatenate a leading zero on to something and then
354 * concatenate another non-zero digit on to _that_ (to make,
355 * for example, 106); but that's also unnecessary, because you
356 * can make 106 just as easily by concatenating the 0 on to the
357 * _end_ of the 1 first.
362 if (!max_p10(b[0], &p10)) return FALSE;
370 #define IPOW(ret, x, y) do { \
371 int ipow_limit = (y); \
372 if ((x) == 1 || (x) == 0) ipow_limit = 1; \
373 else if ((x) == -1) ipow_limit &= 1; \
375 while (ipow_limit-- > 0) { \
382 static int perform_exp(int *a, int *b, int *output)
387 * Exponentiation is permitted if the result is rational. This
390 * - first we see whether we can take the (denominator-of-b)th
391 * root of a and get a rational; if not, we give up.
393 * - then we do take that root of a
395 * - then we multiply by itself (numerator-of-b) times.
398 an = (int)(0.5 + pow(a[0], 1.0/b[1]));
399 ad = (int)(0.5 + pow(a[1], 1.0/b[1]));
402 if (xn != a[0] || xd != a[1])
422 static int perform_factorial(int *a, int *b, int *output)
427 * Factorials of non-negative integers are permitted.
429 if (a[1] != 1 || a[0] < 0)
433 * However, a special case: we don't take a factorial of
434 * anything which would thereby remain the same.
436 if (a[0] == 1 || a[0] == 2)
440 for (i = 1; i <= a[0]; i++) {
449 static int perform_decimal(int *a, int *b, int *output)
454 * Add a decimal digit to the front of a number;
455 * fail if it's not an integer.
456 * So, 1 --> 0.1, 15 --> 0.15,
457 * or, rather, 1 --> 1/10, 15 --> 15/100,
458 * x --> x / (smallest power of 10 > than x)
461 if (a[1] != 1) return FALSE;
463 if (!max_p10(a[0], &p10)) return FALSE;
465 OUT(output, a[0], p10);
469 static int perform_recur(int *a, int *b, int *output)
474 * This converts a number like .4 to .44444..., or .45 to .45454...
475 * The input number must be -1 < a < 1.
477 * Calculate the smallest power of 10 that divides the denominator exactly,
478 * returning if no such power of 10 exists. Then multiply the numerator
479 * up accordingly, and the new denominator becomes that power of 10 - 1.
481 if (abs(a[0]) >= abs(a[1])) return FALSE; /* -1 < a < 1 */
484 while (p10 <= (INT_MAX/10)) {
485 if ((a[1] <= p10) && (p10 % a[1]) == 0) goto found;
490 tn = a[0] * (p10 / a[1]);
497 static int perform_root(int *a, int *b, int *output)
500 * A root B is: 1 iff a == 0
501 * B ^ (1/A) otherwise
510 OUT(ainv, a[1], a[0]);
511 res = perform_exp(b, ainv, output);
515 static int perform_perc(int *a, int *b, int *output)
517 if (a[0] == 0) return FALSE; /* 0% = 0, uninteresting. */
518 if (a[1] > (INT_MAX/100)) return FALSE;
520 OUT(output, a[0], a[1]*100);
524 static int perform_gamma(int *a, int *b, int *output)
531 * special case not caught by perform_fact: gamma(1) is 1 so
534 if (a[0] == 1 && a[1] == 1) return FALSE;
536 OUT(asub1, a[0]-a[1], a[1]);
537 return perform_factorial(asub1, b, output);
540 static int perform_sqrt(int *a, int *b, int *output)
542 int half[2] = { 1, 2 };
545 * sqrt(0) == 0, sqrt(1) == 1: don't perform unary noops.
547 if (a[0] == 0 || (a[0] == 1 && a[1] == 1)) return FALSE;
549 return perform_exp(a, half, output);
552 const static struct operation op_add = {
553 TRUE, "+", "+", 0, 10, 0, TRUE, perform_add
555 const static struct operation op_sub = {
556 TRUE, "-", "-", 0, 10, 2, FALSE, perform_sub
558 const static struct operation op_mul = {
559 TRUE, "*", "*", 0, 20, 0, TRUE, perform_mul
561 const static struct operation op_div = {
562 TRUE, "/", "/", 0, 20, 2, FALSE, perform_div
564 const static struct operation op_xdiv = {
565 TRUE, "/", "/", 0, 20, 2, FALSE, perform_exact_div
567 const static struct operation op_concat = {
568 FALSE, "", "concat", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT,
569 1000, 0, FALSE, perform_concat
571 const static struct operation op_exp = {
572 TRUE, "^", "^", 0, 30, 1, FALSE, perform_exp
574 const static struct operation op_factorial = {
575 TRUE, "!", "!", OPFLAG_UNARY, 40, 0, FALSE, perform_factorial
577 const static struct operation op_decimal = {
578 TRUE, ".", ".", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT, 50, 0, FALSE, perform_decimal
580 const static struct operation op_recur = {
581 TRUE, "...", "recur", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 2, FALSE, perform_recur
583 const static struct operation op_root = {
584 TRUE, "v~", "root", 0, 30, 1, FALSE, perform_root
586 const static struct operation op_perc = {
587 TRUE, "%", "%", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 1, FALSE, perform_perc
589 const static struct operation op_gamma = {
590 TRUE, "gamma", "gamma", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_FN, 1, 3, FALSE, perform_gamma
592 const static struct operation op_sqrt = {
593 TRUE, "v~", "sqrt", OPFLAG_UNARY | OPFLAG_UNARYPREFIX, 30, 1, FALSE, perform_sqrt
597 * In Countdown, divisions resulting in fractions are disallowed.
598 * http://www.askoxford.com/wordgames/countdown/rules/
600 const static struct operation *const ops_countdown[] = {
601 &op_add, &op_mul, &op_sub, &op_xdiv, NULL
603 const static struct rules rules_countdown = {
608 * A slightly different rule set which handles the reasonably well
609 * known puzzle of making 24 using two 3s and two 8s. For this we
610 * need rational rather than integer division.
612 const static struct operation *const ops_3388[] = {
613 &op_add, &op_mul, &op_sub, &op_div, NULL
615 const static struct rules rules_3388 = {
620 * A still more permissive rule set usable for the four-4s problem
621 * and similar things. Permits concatenation.
623 const static struct operation *const ops_four4s[] = {
624 &op_add, &op_mul, &op_sub, &op_div, &op_concat, NULL
626 const static struct rules rules_four4s = {
631 * The most permissive ruleset I can think of. Permits
632 * exponentiation, and also silly unary operators like factorials.
634 const static struct operation *const ops_anythinggoes[] = {
635 &op_add, &op_mul, &op_sub, &op_div, &op_concat, &op_exp, &op_factorial,
636 &op_decimal, &op_recur, &op_root, &op_perc, &op_gamma, &op_sqrt, NULL
638 const static struct rules rules_anythinggoes = {
639 ops_anythinggoes, TRUE
642 #define ratcmp(a,op,b) ( (long long)(a)[0] * (b)[1] op \
643 (long long)(b)[0] * (a)[1] )
645 static int addtoset(struct set *set, int newnumber[2])
649 /* Find where we want to insert the new number */
650 for (i = 0; i < set->nnumbers &&
651 ratcmp(set->numbers+2*i, <, newnumber); i++);
653 /* Move everything else up */
654 for (j = set->nnumbers; j > i; j--) {
655 set->numbers[2*j] = set->numbers[2*j-2];
656 set->numbers[2*j+1] = set->numbers[2*j-1];
659 /* Insert the new number */
660 set->numbers[2*i] = newnumber[0];
661 set->numbers[2*i+1] = newnumber[1];
668 #define ensure(array, size, newlen, type) do { \
669 if ((newlen) > (size)) { \
670 (size) = (newlen) + 512; \
671 (array) = sresize((array), (size), type); \
675 static int setcmp(void *av, void *bv)
677 struct set *a = (struct set *)av;
678 struct set *b = (struct set *)bv;
681 if (a->nnumbers < b->nnumbers)
683 else if (a->nnumbers > b->nnumbers)
686 if (a->flags < b->flags)
688 else if (a->flags > b->flags)
691 for (i = 0; i < a->nnumbers; i++) {
692 if (ratcmp(a->numbers+2*i, <, b->numbers+2*i))
694 else if (ratcmp(a->numbers+2*i, >, b->numbers+2*i))
701 static int outputcmp(void *av, void *bv)
703 struct output *a = (struct output *)av;
704 struct output *b = (struct output *)bv;
706 if (a->number < b->number)
708 else if (a->number > b->number)
714 static int outputfindcmp(void *av, void *bv)
717 struct output *b = (struct output *)bv;
721 else if (*a > b->number)
727 static void addset(struct sets *s, struct set *set, int multiple,
728 struct set *prev, int pa, int po, int pb, int pr)
731 int npaths = (prev ? prev->npaths : 1);
733 assert(set == s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN);
734 s2 = add234(s->settree, set);
737 * New set added to the tree.
744 set->npaths = npaths;
746 s->nnumbers += 2 * set->nnumbers;
748 set->nas = set->assize = 0;
751 * Rediscovered an existing set. Update its npaths.
753 s2->npaths += npaths;
755 * And optionally enter it as an additional ancestor.
758 if (s2->nas >= s2->assize) {
759 s2->assize = s2->nas * 3 / 2 + 4;
760 s2->as = sresize(s2->as, s2->assize, struct ancestor);
762 s2->as[s2->nas].prev = prev;
763 s2->as[s2->nas].pa = pa;
764 s2->as[s2->nas].po = po;
765 s2->as[s2->nas].pb = pb;
766 s2->as[s2->nas].pr = pr;
772 static struct set *newset(struct sets *s, int nnumbers, int flags)
776 ensure(s->setlists, s->setlistsize, s->nsets/SETLISTLEN+1, struct set *);
777 while (s->nsetlists <= s->nsets / SETLISTLEN)
778 s->setlists[s->nsetlists++] = snewn(SETLISTLEN, struct set);
779 sn = s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN;
781 if (s->nnumbers + nnumbers * 2 > s->nnumberlists * NUMBERLISTLEN)
782 s->nnumbers = s->nnumberlists * NUMBERLISTLEN;
783 ensure(s->numberlists, s->numberlistsize,
784 s->nnumbers/NUMBERLISTLEN+1, int *);
785 while (s->nnumberlists <= s->nnumbers / NUMBERLISTLEN)
786 s->numberlists[s->nnumberlists++] = snewn(NUMBERLISTLEN, int);
787 sn->numbers = s->numberlists[s->nnumbers / NUMBERLISTLEN] +
788 s->nnumbers % NUMBERLISTLEN;
791 * Start the set off empty.
800 static int addoutput(struct sets *s, struct set *ss, int index, int *n)
802 struct output *o, *o2;
805 * Target numbers are always integers.
807 if (ss->numbers[2*index+1] != 1)
810 ensure(s->outputlists, s->outputlistsize, s->noutputs/OUTPUTLISTLEN+1,
812 while (s->noutputlists <= s->noutputs / OUTPUTLISTLEN)
813 s->outputlists[s->noutputlists++] = snewn(OUTPUTLISTLEN,
815 o = s->outputlists[s->noutputs / OUTPUTLISTLEN] +
816 s->noutputs % OUTPUTLISTLEN;
818 o->number = ss->numbers[2*index];
821 o->npaths = ss->npaths;
822 o2 = add234(s->outputtree, o);
824 o2->npaths += o->npaths;
832 static struct sets *do_search(int ninputs, int *inputs,
833 const struct rules *rules, int *target,
834 int debug, int multiple)
839 const struct operation *const *ops = rules->ops;
841 s = snew(struct sets);
843 s->nsets = s->nsetlists = s->setlistsize = 0;
844 s->numberlists = NULL;
845 s->nnumbers = s->nnumberlists = s->numberlistsize = 0;
846 s->outputlists = NULL;
847 s->noutputs = s->noutputlists = s->outputlistsize = 0;
848 s->settree = newtree234(setcmp);
849 s->outputtree = newtree234(outputcmp);
853 * Start with the input set.
855 sn = newset(s, ninputs, SETFLAG_CONCAT);
856 for (i = 0; i < ninputs; i++) {
858 newnumber[0] = inputs[i];
860 addtoset(sn, newnumber);
862 addset(s, sn, multiple, NULL, 0, 0, 0, 0);
865 * Now perform the breadth-first search: keep looping over sets
866 * until we run out of steam.
869 while (qpos < s->nsets) {
870 struct set *ss = s->setlists[qpos / SETLISTLEN] + qpos % SETLISTLEN;
876 printf("processing set:");
877 for (i = 0; i < ss->nnumbers; i++) {
878 printf(" %d", ss->numbers[2*i]);
879 if (ss->numbers[2*i+1] != 1)
880 printf("/%d", ss->numbers[2*i+1]);
886 * Record all the valid output numbers in this state. We
887 * can always do this if there's only one number in the
888 * state; otherwise, we can only do it if we aren't
889 * required to use all the numbers in coming to our answer.
891 if (ss->nnumbers == 1 || !rules->use_all) {
892 for (i = 0; i < ss->nnumbers; i++) {
895 if (addoutput(s, ss, i, &n) && target && n == *target)
901 * Try every possible operation from this state.
903 for (k = 0; ops[k] && ops[k]->perform; k++) {
904 if ((ops[k]->flags & OPFLAG_NEEDS_CONCAT) &&
905 !(ss->flags & SETFLAG_CONCAT))
906 continue; /* can't use this operation here */
907 for (i = 0; i < ss->nnumbers; i++) {
908 int jlimit = (ops[k]->flags & OPFLAG_UNARY ? 1 : ss->nnumbers);
909 for (j = 0; j < jlimit; j++) {
910 int n[2], newnn = ss->nnumbers;
913 if (!(ops[k]->flags & OPFLAG_UNARY)) {
915 continue; /* can't combine a number with itself */
916 if (i > j && ops[k]->commutes)
917 continue; /* no need to do this both ways round */
920 if (!ops[k]->perform(ss->numbers+2*i, ss->numbers+2*j, n))
921 continue; /* operation failed */
923 sn = newset(s, newnn, ss->flags);
925 if (!(ops[k]->flags & OPFLAG_KEEPS_CONCAT))
926 sn->flags &= ~SETFLAG_CONCAT;
928 for (m = 0; m < ss->nnumbers; m++) {
929 if (m == i || (!(ops[k]->flags & OPFLAG_UNARY) &&
932 sn->numbers[2*sn->nnumbers] = ss->numbers[2*m];
933 sn->numbers[2*sn->nnumbers + 1] = ss->numbers[2*m + 1];
937 if (ops[k]->flags & OPFLAG_UNARY)
938 pb = sn->nnumbers+10;
942 pr = addtoset(sn, n);
943 addset(s, sn, multiple, ss, pa, po, pb, pr);
946 if (ops[k]->flags & OPFLAG_UNARYPREFIX)
947 printf(" %s %d ->", ops[po]->dbgtext, pa);
948 else if (ops[k]->flags & OPFLAG_UNARY)
949 printf(" %d %s ->", pa, ops[po]->dbgtext);
951 printf(" %d %s %d ->", pa, ops[po]->dbgtext, pb);
952 for (i = 0; i < sn->nnumbers; i++) {
953 printf(" %d", sn->numbers[2*i]);
954 if (sn->numbers[2*i+1] != 1)
955 printf("/%d", sn->numbers[2*i+1]);
969 static void free_sets(struct sets *s)
973 freetree234(s->settree);
974 freetree234(s->outputtree);
975 for (i = 0; i < s->nsetlists; i++)
976 sfree(s->setlists[i]);
978 for (i = 0; i < s->nnumberlists; i++)
979 sfree(s->numberlists[i]);
980 sfree(s->numberlists);
981 for (i = 0; i < s->noutputlists; i++)
982 sfree(s->outputlists[i]);
983 sfree(s->outputlists);
988 * Print a text formula for producing a given output.
990 void print_recurse(struct sets *s, struct set *ss, int pathindex, int index,
991 int priority, int assoc, int child);
992 void print_recurse_inner(struct sets *s, struct set *ss,
993 struct ancestor *a, int pathindex, int index,
994 int priority, int assoc, int child)
996 if (a->prev && index != a->pr) {
1000 * This number was passed straight down from this set's
1001 * predecessor. Find its index in the previous set and
1005 assert(pi != a->pr);
1008 if (pi >= min(a->pa, a->pb)) {
1010 if (pi >= max(a->pa, a->pb))
1013 print_recurse(s, a->prev, pathindex, pi, priority, assoc, child);
1014 } else if (a->prev && index == a->pr &&
1015 s->ops[a->po]->display) {
1017 * This number was created by a displayed operator in the
1018 * transition from this set to its predecessor. Hence we
1019 * write an open paren, then recurse into the first
1020 * operand, then write the operator, then the second
1021 * operand, and finally close the paren.
1024 int parens, thispri, thisassoc;
1027 * Determine whether we need parentheses.
1029 thispri = s->ops[a->po]->priority;
1030 thisassoc = s->ops[a->po]->assoc;
1031 parens = (thispri < priority ||
1032 (thispri == priority && (assoc & child)));
1037 if (s->ops[a->po]->flags & OPFLAG_UNARYPREFIX)
1038 for (op = s->ops[a->po]->text; *op; op++)
1041 if (s->ops[a->po]->flags & OPFLAG_FN)
1044 print_recurse(s, a->prev, pathindex, a->pa, thispri, thisassoc, 1);
1046 if (s->ops[a->po]->flags & OPFLAG_FN)
1049 if (!(s->ops[a->po]->flags & OPFLAG_UNARYPREFIX))
1050 for (op = s->ops[a->po]->text; *op; op++)
1053 if (!(s->ops[a->po]->flags & OPFLAG_UNARY))
1054 print_recurse(s, a->prev, pathindex, a->pb, thispri, thisassoc, 2);
1060 * This number is either an original, or something formed
1061 * by a non-displayed operator (concatenation). Either way,
1062 * we display it as is.
1064 printf("%d", ss->numbers[2*index]);
1065 if (ss->numbers[2*index+1] != 1)
1066 printf("/%d", ss->numbers[2*index+1]);
1069 void print_recurse(struct sets *s, struct set *ss, int pathindex, int index,
1070 int priority, int assoc, int child)
1072 if (!ss->a.prev || pathindex < ss->a.prev->npaths) {
1073 print_recurse_inner(s, ss, &ss->a, pathindex,
1074 index, priority, assoc, child);
1077 pathindex -= ss->a.prev->npaths;
1078 for (i = 0; i < ss->nas; i++) {
1079 if (pathindex < ss->as[i].prev->npaths) {
1080 print_recurse_inner(s, ss, &ss->as[i], pathindex,
1081 index, priority, assoc, child);
1084 pathindex -= ss->as[i].prev->npaths;
1088 void print(int pathindex, struct sets *s, struct output *o)
1090 print_recurse(s, o->set, pathindex, o->index, 0, 0, 0);
1094 * gcc -g -O0 -o numgame numgame.c -I.. ../{malloc,tree234,nullfe}.c -lm
1096 int main(int argc, char **argv)
1098 int doing_opts = TRUE;
1099 const struct rules *rules = NULL;
1100 char *pname = argv[0];
1101 int got_target = FALSE, target = 0;
1102 int numbers[10], nnumbers = 0;
1103 int verbose = FALSE;
1104 int pathcounts = FALSE;
1105 int multiple = FALSE;
1106 int debug_bfs = FALSE;
1107 int got_range = FALSE, rangemin = 0, rangemax = 0;
1111 int i, start, limit;
1117 if (doing_opts && *p == '-') {
1120 if (!strcmp(p, "-")) {
1123 } else if (*p == '-') {
1125 if (!strcmp(p, "debug-bfs")) {
1128 fprintf(stderr, "%s: option '--%s' not recognised\n",
1131 } else while (p && *p) switch (c = *p++) {
1133 rules = &rules_countdown;
1136 rules = &rules_3388;
1139 rules = &rules_four4s;
1142 rules = &rules_anythinggoes;
1160 } else if (--argc) {
1163 fprintf(stderr, "%s: option '-%c' expects an"
1164 " argument\n", pname, c);
1174 char *sep = strchr(v, '-');
1178 rangemax = atoi(sep+1);
1189 fprintf(stderr, "%s: option '-%c' not"
1190 " recognised\n", pname, c);
1194 if (nnumbers >= lenof(numbers)) {
1195 fprintf(stderr, "%s: internal limit of %d numbers exceeded\n",
1196 pname, (int)lenof(numbers));
1199 numbers[nnumbers++] = atoi(p);
1205 fprintf(stderr, "%s: no rule set specified; use -C,-B,-D,-A\n", pname);
1210 fprintf(stderr, "%s: no input numbers specified\n", pname);
1216 fprintf(stderr, "%s: only one of -t and -r may be specified\n", pname);
1219 if (rangemin >= rangemax) {
1220 fprintf(stderr, "%s: range not sensible (%d - %d)\n", pname, rangemin, rangemax);
1225 s = do_search(nnumbers, numbers, rules, (got_target ? &target : NULL),
1226 debug_bfs, multiple);
1229 o = findrelpos234(s->outputtree, &target, outputfindcmp,
1233 o = findrelpos234(s->outputtree, &target, outputfindcmp,
1237 assert(start != -1 || limit != -1);
1240 else if (limit == -1)
1243 } else if (got_range) {
1244 if (!findrelpos234(s->outputtree, &rangemin, outputfindcmp,
1245 REL234_GE, &start) ||
1246 !findrelpos234(s->outputtree, &rangemax, outputfindcmp,
1247 REL234_LE, &limit)) {
1248 printf("No solutions available in specified range %d-%d\n", rangemin, rangemax);
1254 limit = count234(s->outputtree);
1257 for (i = start; i < limit; i++) {
1260 o = index234(s->outputtree, i);
1262 sprintf(buf, "%d", o->number);
1265 sprintf(buf + strlen(buf), " [%d]", o->npaths);
1267 if (got_target || verbose) {
1275 for (j = 0; j < npaths; j++) {
1276 printf("%s = ", buf);
1281 printf("%s\n", buf);
1290 /* vim: set shiftwidth=4 tabstop=8: */