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
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.
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.
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.
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.
86 #define SETFLAG_CONCAT 1 /* we can do concatenation */
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 */
102 int index; /* which number in the set is it? */
103 int npaths; /* number of ways to reach this */
106 #define SETLISTLEN 1024
107 #define NUMBERLISTLEN 32768
108 #define OUTPUTLISTLEN 1024
111 struct set **setlists;
112 int nsets, nsetlists, setlistsize;
115 int nnumbers, nnumberlists, numberlistsize;
116 struct output **outputlists;
117 int noutputs, noutputlists, outputlistsize;
119 const struct operation *const *ops;
122 #define OPFLAG_NEEDS_CONCAT 1
123 #define OPFLAG_KEEPS_CONCAT 2
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
135 * Text display of the operator.
140 * Flags dictating when the operator can be applied.
145 * Priority of the operator (for avoiding unnecessary
146 * parentheses when formatting it into a string).
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:
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).
167 * Whether the operator is commutative. Saves time in the
168 * search if we don't have to try it both ways round.
173 * Function which implements the operator. Returns TRUE on
174 * success, FALSE on failure. Takes two rationals and writes
177 int (*perform)(int *a, int *b, int *output);
181 const struct operation *const *ops;
185 #define MUL(r, a, b) do { \
187 if ((b) && (a) && (r) / (b) != (a)) return FALSE; \
190 #define ADD(r, a, b) do { \
192 if ((a) > 0 && (b) > 0 && (r) < 0) return FALSE; \
193 if ((a) < 0 && (b) < 0 && (r) > 0) return FALSE; \
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); \
204 static int gcd(int x, int y)
206 while (x != 0 && y != 0) {
212 return abs(x + y); /* i.e. whichever one isn't zero */
215 static int perform_add(int *a, int *b, int *output)
219 * a0/a1 + b0/b1 = (a0*b1 + b0*a1) / (a1*b1)
229 static int perform_sub(int *a, int *b, int *output)
233 * a0/a1 - b0/b1 = (a0*b1 - b0*a1) / (a1*b1)
243 static int perform_mul(int *a, int *b, int *output)
247 * a0/a1 * b0/b1 = (a0*b0) / (a1*b1)
255 static int perform_div(int *a, int *b, int *output)
260 * Division by zero is outlawed.
266 * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
274 static int perform_exact_div(int *a, int *b, int *output)
279 * Division by zero is outlawed.
285 * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
292 * Exact division means we require the result to be an integer.
294 return (output[1] == 1);
297 static int perform_concat(int *a, int *b, int *output)
302 * We can't concatenate anything which isn't an integer.
304 if (a[1] != 1 || b[1] != 1)
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.
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.
327 * Find the smallest power of ten strictly greater than b. This
328 * is the power of ten by which we'll multiply a.
330 * Special case: we must multiply a by at least 10, even if b
334 while (p10 <= (INT_MAX/10) && p10 <= b[0])
336 if (p10 > INT_MAX/10)
337 return FALSE; /* integer overflow */
344 const static struct operation op_add = {
345 TRUE, "+", 0, 10, 0, TRUE, perform_add
347 const static struct operation op_sub = {
348 TRUE, "-", 0, 10, 2, FALSE, perform_sub
350 const static struct operation op_mul = {
351 TRUE, "*", 0, 20, 0, TRUE, perform_mul
353 const static struct operation op_div = {
354 TRUE, "/", 0, 20, 2, FALSE, perform_div
356 const static struct operation op_xdiv = {
357 TRUE, "/", 0, 20, 2, FALSE, perform_exact_div
359 const static struct operation op_concat = {
360 FALSE, "", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT,
361 1000, 0, FALSE, perform_concat
365 * In Countdown, divisions resulting in fractions are disallowed.
366 * http://www.askoxford.com/wordgames/countdown/rules/
368 const static struct operation *const ops_countdown[] = {
369 &op_add, &op_mul, &op_sub, &op_xdiv, NULL
371 const static struct rules rules_countdown = {
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.
380 const static struct operation *const ops_3388[] = {
381 &op_add, &op_mul, &op_sub, &op_div, NULL
383 const static struct rules rules_3388 = {
388 * A still more permissive rule set usable for the four-4s problem
389 * and similar things. Permits concatenation.
391 const static struct operation *const ops_four4s[] = {
392 &op_add, &op_mul, &op_sub, &op_div, &op_concat, NULL
394 const static struct rules rules_four4s = {
398 #define ratcmp(a,op,b) ( (long long)(a)[0] * (b)[1] op \
399 (long long)(b)[0] * (a)[1] )
401 static int addtoset(struct set *set, int newnumber[2])
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++);
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];
415 /* Insert the new number */
416 set->numbers[2*i] = newnumber[0];
417 set->numbers[2*i+1] = newnumber[1];
424 #define ensure(array, size, newlen, type) do { \
425 if ((newlen) > (size)) { \
426 (size) = (newlen) + 512; \
427 (array) = sresize((array), (size), type); \
431 static int setcmp(void *av, void *bv)
433 struct set *a = (struct set *)av;
434 struct set *b = (struct set *)bv;
437 if (a->nnumbers < b->nnumbers)
439 else if (a->nnumbers > b->nnumbers)
442 if (a->flags < b->flags)
444 else if (a->flags > b->flags)
447 for (i = 0; i < a->nnumbers; i++) {
448 if (ratcmp(a->numbers+2*i, <, b->numbers+2*i))
450 else if (ratcmp(a->numbers+2*i, >, b->numbers+2*i))
457 static int outputcmp(void *av, void *bv)
459 struct output *a = (struct output *)av;
460 struct output *b = (struct output *)bv;
462 if (a->number < b->number)
464 else if (a->number > b->number)
470 static int outputfindcmp(void *av, void *bv)
473 struct output *b = (struct output *)bv;
477 else if (*a > b->number)
483 static void addset(struct sets *s, struct set *set, struct set *prev)
486 int npaths = (prev ? prev->npaths : 1);
488 assert(set == s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN);
489 s2 = add234(s->settree, set);
492 * New set added to the tree.
495 set->npaths = npaths;
497 s->nnumbers += 2 * set->nnumbers;
500 * Rediscovered an existing set. Update its npaths only.
502 s2->npaths += npaths;
506 static struct set *newset(struct sets *s, int nnumbers, int flags)
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;
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;
525 * Start the set off empty.
534 static int addoutput(struct sets *s, struct set *ss, int index, int *n)
536 struct output *o, *o2;
539 * Target numbers are always integers.
541 if (ss->numbers[2*index+1] != 1)
544 ensure(s->outputlists, s->outputlistsize, s->noutputs/OUTPUTLISTLEN+1,
546 while (s->noutputlists <= s->noutputs / OUTPUTLISTLEN)
547 s->outputlists[s->noutputlists++] = snewn(OUTPUTLISTLEN,
549 o = s->outputlists[s->noutputs / OUTPUTLISTLEN] +
550 s->noutputs % OUTPUTLISTLEN;
552 o->number = ss->numbers[2*index];
555 o->npaths = ss->npaths;
556 o2 = add234(s->outputtree, o);
558 o2->npaths += o->npaths;
566 static struct sets *do_search(int ninputs, int *inputs,
567 const struct rules *rules, int *target)
572 const struct operation *const *ops = rules->ops;
574 s = snew(struct sets);
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);
586 * Start with the input set.
588 sn = newset(s, ninputs, SETFLAG_CONCAT);
589 for (i = 0; i < ninputs; i++) {
591 newnumber[0] = inputs[i];
593 addtoset(sn, newnumber);
598 * Now perform the breadth-first search: keep looping over sets
599 * until we run out of steam.
602 while (qpos < s->nsets) {
603 struct set *ss = s->setlists[qpos / SETLISTLEN] + qpos % SETLISTLEN;
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.
613 if (ss->nnumbers == 1 || !rules->use_all) {
614 for (i = 0; i < ss->nnumbers; i++) {
617 if (addoutput(s, ss, i, &n) && target && n == *target)
623 * Try every possible operation from this state.
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++) {
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 */
640 sn = newset(s, ss->nnumbers-1, ss->flags);
642 if (!(ops[k]->flags & OPFLAG_KEEPS_CONCAT))
643 sn->flags &= ~SETFLAG_CONCAT;
645 for (m = 0; m < ss->nnumbers; m++) {
646 if (m == i || m == j)
648 sn->numbers[2*sn->nnumbers] = ss->numbers[2*m];
649 sn->numbers[2*sn->nnumbers + 1] = ss->numbers[2*m + 1];
655 sn->pr = addtoset(sn, n);
667 static void free_sets(struct sets *s)
671 freetree234(s->settree);
672 freetree234(s->outputtree);
673 for (i = 0; i < s->nsetlists; i++)
674 sfree(s->setlists[i]);
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);
686 * Construct a text formula for producing a given output.
688 void mkstring_recurse(char **str, int *len,
689 struct sets *s, struct set *ss, int index,
690 int priority, int assoc, int child)
692 if (ss->prev && index != ss->pr) {
696 * This number was passed straight down from this set's
697 * predecessor. Find its index in the previous set and
701 assert(pi != ss->pr);
704 if (pi >= min(ss->pa, ss->pb)) {
706 if (pi >= max(ss->pa, ss->pb))
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) {
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.
720 int parens, thispri, thisassoc;
723 * Determine whether we need parentheses.
725 thispri = s->ops[ss->po]->priority;
726 thisassoc = s->ops[ss->po]->assoc;
727 parens = (thispri < priority ||
728 (thispri == priority && (assoc & child)));
736 mkstring_recurse(str, len, s, ss->prev, ss->pa, thispri, thisassoc, 1);
737 for (op = s->ops[ss->po]->text; *op; op++) {
743 mkstring_recurse(str, len, s, ss->prev, ss->pb, thispri, thisassoc, 2);
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.
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++) {
770 char *mkstring(struct sets *s, struct output *o)
776 mkstring_recurse(NULL, &len, s, o->set, o->index, 0, 0, 0);
777 str = snewn(len+1, char);
779 mkstring_recurse(&p, NULL, s, o->set, o->index, 0, 0, 0);
780 assert(p - str <= len);
785 int main(int argc, char **argv)
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;
793 int pathcounts = FALSE;
803 if (doing_opts && *p == '-') {
806 if (!strcmp(p, "-")) {
809 } else while (*p) switch (c = *p++) {
811 rules = &rules_countdown;
817 rules = &rules_four4s;
834 fprintf(stderr, "%s: option '-%c' expects an"
835 " argument\n", pname, c);
847 fprintf(stderr, "%s: option '-%c' not"
848 " recognised\n", pname, c);
852 if (nnumbers >= lenof(numbers)) {
853 fprintf(stderr, "%s: internal limit of %d numbers exceeded\n",
854 pname, lenof(numbers));
857 numbers[nnumbers++] = atoi(p);
863 fprintf(stderr, "%s: no rule set specified; use -C,-B,-D\n", pname);
868 fprintf(stderr, "%s: no input numbers specified\n", pname);
872 s = do_search(nnumbers, numbers, rules, (got_target ? &target : NULL));
875 o = findrelpos234(s->outputtree, &target, outputfindcmp,
879 o = findrelpos234(s->outputtree, &target, outputfindcmp,
883 assert(start != -1 || limit != -1);
886 else if (limit == -1)
891 limit = count234(s->outputtree);
894 for (i = start; i < limit; i++) {
895 o = index234(s->outputtree, i);
897 printf("%d", o->number);
900 printf(" [%d]", o->npaths);
902 if (got_target || verbose) {
903 char *p = mkstring(s, o);