49a05a3e82ae6e9d48c542e404c00a3fee23edb2
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
137 * Most operations should be shown in the output working, but
138 * concatenation should not; we just take the result of the
139 * concatenation and assume that it's obvious how it was
145 * Text display of the operator, in expressions and for
146 * debugging respectively.
148 char *text
, *dbgtext
;
151 * Flags dictating when the operator can be applied.
156 * Priority of the operator (for avoiding unnecessary
157 * parentheses when formatting it into a string).
162 * Associativity of the operator. Bit 0 means we need parens
163 * when the left operand of one of these operators is another
164 * instance of it, e.g. (2^3)^4. Bit 1 means we need parens
165 * when the right operand is another instance of the same
166 * operator, e.g. 2-(3-4). Thus:
168 * - this field is 0 for a fully associative operator, since
169 * we never need parens.
170 * - it's 1 for a right-associative operator.
171 * - it's 2 for a left-associative operator.
172 * - it's 3 for a _non_-associative operator (which always
173 * uses parens just to be sure).
178 * Whether the operator is commutative. Saves time in the
179 * search if we don't have to try it both ways round.
184 * Function which implements the operator. Returns TRUE on
185 * success, FALSE on failure. Takes two rationals and writes
188 int (*perform
)(int *a
, int *b
, int *output
);
192 const struct operation
*const *ops
;
196 #define MUL(r, a, b) do { \
198 if ((b) && (a) && (r) / (b) != (a)) return FALSE; \
201 #define ADD(r, a, b) do { \
203 if ((a) > 0 && (b) > 0 && (r) < 0) return FALSE; \
204 if ((a) < 0 && (b) < 0 && (r) > 0) return FALSE; \
207 #define OUT(output, n, d) do { \
208 int g = gcd((n),(d)); \
210 if ((d) < 0) g = -g; \
211 if (g == -1 && (n) < -INT_MAX) return FALSE; \
212 if (g == -1 && (d) < -INT_MAX) return FALSE; \
213 (output)[0] = (n)/g; \
214 (output)[1] = (d)/g; \
215 assert((output)[1] > 0); \
218 static int gcd(int x
, int y
)
220 while (x
!= 0 && y
!= 0) {
226 return abs(x
+ y
); /* i.e. whichever one isn't zero */
229 static int perform_add(int *a
, int *b
, int *output
)
233 * a0/a1 + b0/b1 = (a0*b1 + b0*a1) / (a1*b1)
243 static int perform_sub(int *a
, int *b
, int *output
)
247 * a0/a1 - b0/b1 = (a0*b1 - b0*a1) / (a1*b1)
257 static int perform_mul(int *a
, int *b
, int *output
)
261 * a0/a1 * b0/b1 = (a0*b0) / (a1*b1)
269 static int perform_div(int *a
, int *b
, int *output
)
274 * Division by zero is outlawed.
280 * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
288 static int perform_exact_div(int *a
, int *b
, int *output
)
293 * Division by zero is outlawed.
299 * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
306 * Exact division means we require the result to be an integer.
308 return (output
[1] == 1);
311 static int max_p10(int n
, int *p10_r
)
314 * Find the smallest power of ten strictly greater than n.
316 * Special case: we must return at least 10, even if n is
317 * zero. (This is because this function is used for finding
318 * the power of ten by which to multiply a number being
319 * concatenated to the front of n, and concatenating 1 to 0
320 * should yield 10 and not 1.)
323 while (p10
<= (INT_MAX
/10) && p10
<= n
)
325 if (p10
> INT_MAX
/10)
326 return FALSE
; /* integer overflow */
331 static int perform_concat(int *a
, int *b
, int *output
)
336 * We can't concatenate anything which isn't a non-negative
339 if (a
[1] != 1 || b
[1] != 1 || a
[0] < 0 || b
[0] < 0)
343 * For concatenation, we can safely assume leading zeroes
344 * aren't an issue. It isn't clear whether they `should' be
345 * allowed, but it turns out not to matter: concatenating a
346 * leading zero on to a number in order to harmlessly get rid
347 * of the zero is never necessary because unwanted zeroes can
348 * be disposed of by adding them to something instead. So we
349 * disallow them always.
351 * The only other possibility is that you might want to
352 * concatenate a leading zero on to something and then
353 * concatenate another non-zero digit on to _that_ (to make,
354 * for example, 106); but that's also unnecessary, because you
355 * can make 106 just as easily by concatenating the 0 on to the
356 * _end_ of the 1 first.
361 if (!max_p10(b
[0], &p10
)) return FALSE
;
369 #define IPOW(ret, x, y) do { \
370 int ipow_limit = (y); \
371 if ((x) == 1 || (x) == 0) ipow_limit = 1; \
372 else if ((x) == -1) ipow_limit &= 1; \
374 while (ipow_limit-- > 0) { \
381 static int perform_exp(int *a
, int *b
, int *output
)
386 * Exponentiation is permitted if the result is rational. This
389 * - first we see whether we can take the (denominator-of-b)th
390 * root of a and get a rational; if not, we give up.
392 * - then we do take that root of a
394 * - then we multiply by itself (numerator-of-b) times.
397 an
= (int)(0.5 + pow(a
[0], 1.0/b
[1]));
398 ad
= (int)(0.5 + pow(a
[1], 1.0/b
[1]));
401 if (xn
!= a
[0] || xd
!= a
[1])
421 static int perform_factorial(int *a
, int *b
, int *output
)
426 * Factorials of non-negative integers are permitted.
428 if (a
[1] != 1 || a
[0] < 0)
432 * However, a special case: we don't take a factorial of
433 * anything which would thereby remain the same.
435 if (a
[0] == 1 || a
[0] == 2)
439 for (i
= 1; i
<= a
[0]; i
++) {
448 static int perform_decimal(int *a
, int *b
, int *output
)
453 * Add a decimal digit to the front of a number;
454 * fail if it's not an integer.
455 * So, 1 --> 0.1, 15 --> 0.15,
456 * or, rather, 1 --> 1/10, 15 --> 15/100,
457 * x --> x / (smallest power of 10 > than x)
460 if (a
[1] != 1) return FALSE
;
462 if (!max_p10(a
[0], &p10
)) return FALSE
;
464 OUT(output
, a
[0], p10
);
468 static int perform_recur(int *a
, int *b
, int *output
)
473 * This converts a number like .4 to .44444..., or .45 to .45454...
474 * The input number must be -1 < a < 1.
476 * Calculate the smallest power of 10 that divides the denominator exactly,
477 * returning if no such power of 10 exists. Then multiply the numerator
478 * up accordingly, and the new denominator becomes that power of 10 - 1.
480 if (abs(a
[0]) >= abs(a
[1])) return FALSE
; /* -1 < a < 1 */
483 while (p10
<= (INT_MAX
/10)) {
484 if ((a
[1] <= p10
) && (p10
% a
[1]) == 0) goto found
;
489 tn
= a
[0] * (p10
/ a
[1]);
496 static int perform_root(int *a
, int *b
, int *output
)
499 * A root B is: 1 iff a == 0
500 * B ^ (1/A) otherwise
509 OUT(ainv
, a
[1], a
[0]);
510 res
= perform_exp(b
, ainv
, output
);
514 const static struct operation op_add
= {
515 TRUE
, "+", "+", 0, 10, 0, TRUE
, perform_add
517 const static struct operation op_sub
= {
518 TRUE
, "-", "-", 0, 10, 2, FALSE
, perform_sub
520 const static struct operation op_mul
= {
521 TRUE
, "*", "*", 0, 20, 0, TRUE
, perform_mul
523 const static struct operation op_div
= {
524 TRUE
, "/", "/", 0, 20, 2, FALSE
, perform_div
526 const static struct operation op_xdiv
= {
527 TRUE
, "/", "/", 0, 20, 2, FALSE
, perform_exact_div
529 const static struct operation op_concat
= {
530 FALSE
, "", "concat", OPFLAG_NEEDS_CONCAT
| OPFLAG_KEEPS_CONCAT
,
531 1000, 0, FALSE
, perform_concat
533 const static struct operation op_exp
= {
534 TRUE
, "^", "^", 0, 30, 1, FALSE
, perform_exp
536 const static struct operation op_factorial
= {
537 TRUE
, "!", "!", OPFLAG_UNARY
, 40, 0, FALSE
, perform_factorial
539 const static struct operation op_decimal
= {
540 TRUE
, ".", ".", OPFLAG_UNARY
| OPFLAG_UNARYPREFIX
| OPFLAG_NEEDS_CONCAT
| OPFLAG_KEEPS_CONCAT
, 50, 0, FALSE
, perform_decimal
542 const static struct operation op_recur
= {
543 TRUE
, "...", "recur", OPFLAG_UNARY
| OPFLAG_NEEDS_CONCAT
, 45, 2, FALSE
, perform_recur
545 const static struct operation op_root
= {
546 TRUE
, "v~", "root", 0, 30, 1, FALSE
, perform_root
550 * In Countdown, divisions resulting in fractions are disallowed.
551 * http://www.askoxford.com/wordgames/countdown/rules/
553 const static struct operation
*const ops_countdown
[] = {
554 &op_add
, &op_mul
, &op_sub
, &op_xdiv
, NULL
556 const static struct rules rules_countdown
= {
561 * A slightly different rule set which handles the reasonably well
562 * known puzzle of making 24 using two 3s and two 8s. For this we
563 * need rational rather than integer division.
565 const static struct operation
*const ops_3388
[] = {
566 &op_add
, &op_mul
, &op_sub
, &op_div
, NULL
568 const static struct rules rules_3388
= {
573 * A still more permissive rule set usable for the four-4s problem
574 * and similar things. Permits concatenation.
576 const static struct operation
*const ops_four4s
[] = {
577 &op_add
, &op_mul
, &op_sub
, &op_div
, &op_concat
, NULL
579 const static struct rules rules_four4s
= {
584 * The most permissive ruleset I can think of. Permits
585 * exponentiation, and also silly unary operators like factorials.
587 const static struct operation
*const ops_anythinggoes
[] = {
588 &op_add
, &op_mul
, &op_sub
, &op_div
, &op_concat
, &op_exp
, &op_factorial
,
589 &op_decimal
, &op_recur
, &op_root
, NULL
591 const static struct rules rules_anythinggoes
= {
592 ops_anythinggoes
, TRUE
595 #define ratcmp(a,op,b) ( (long long)(a)[0] * (b)[1] op \
596 (long long)(b)[0] * (a)[1] )
598 static int addtoset(struct set
*set
, int newnumber
[2])
602 /* Find where we want to insert the new number */
603 for (i
= 0; i
< set
->nnumbers
&&
604 ratcmp(set
->numbers
+2*i
, <, newnumber
); i
++);
606 /* Move everything else up */
607 for (j
= set
->nnumbers
; j
> i
; j
--) {
608 set
->numbers
[2*j
] = set
->numbers
[2*j
-2];
609 set
->numbers
[2*j
+1] = set
->numbers
[2*j
-1];
612 /* Insert the new number */
613 set
->numbers
[2*i
] = newnumber
[0];
614 set
->numbers
[2*i
+1] = newnumber
[1];
621 #define ensure(array, size, newlen, type) do { \
622 if ((newlen) > (size)) { \
623 (size) = (newlen) + 512; \
624 (array) = sresize((array), (size), type); \
628 static int setcmp(void *av
, void *bv
)
630 struct set
*a
= (struct set
*)av
;
631 struct set
*b
= (struct set
*)bv
;
634 if (a
->nnumbers
< b
->nnumbers
)
636 else if (a
->nnumbers
> b
->nnumbers
)
639 if (a
->flags
< b
->flags
)
641 else if (a
->flags
> b
->flags
)
644 for (i
= 0; i
< a
->nnumbers
; i
++) {
645 if (ratcmp(a
->numbers
+2*i
, <, b
->numbers
+2*i
))
647 else if (ratcmp(a
->numbers
+2*i
, >, b
->numbers
+2*i
))
654 static int outputcmp(void *av
, void *bv
)
656 struct output
*a
= (struct output
*)av
;
657 struct output
*b
= (struct output
*)bv
;
659 if (a
->number
< b
->number
)
661 else if (a
->number
> b
->number
)
667 static int outputfindcmp(void *av
, void *bv
)
670 struct output
*b
= (struct output
*)bv
;
674 else if (*a
> b
->number
)
680 static void addset(struct sets
*s
, struct set
*set
, int multiple
,
681 struct set
*prev
, int pa
, int po
, int pb
, int pr
)
684 int npaths
= (prev ? prev
->npaths
: 1);
686 assert(set
== s
->setlists
[s
->nsets
/ SETLISTLEN
] + s
->nsets
% SETLISTLEN
);
687 s2
= add234(s
->settree
, set
);
690 * New set added to the tree.
697 set
->npaths
= npaths
;
699 s
->nnumbers
+= 2 * set
->nnumbers
;
701 set
->nas
= set
->assize
= 0;
704 * Rediscovered an existing set. Update its npaths.
706 s2
->npaths
+= npaths
;
708 * And optionally enter it as an additional ancestor.
711 if (s2
->nas
>= s2
->assize
) {
712 s2
->assize
= s2
->nas
* 3 / 2 + 4;
713 s2
->as
= sresize(s2
->as
, s2
->assize
, struct ancestor
);
715 s2
->as
[s2
->nas
].prev
= prev
;
716 s2
->as
[s2
->nas
].pa
= pa
;
717 s2
->as
[s2
->nas
].po
= po
;
718 s2
->as
[s2
->nas
].pb
= pb
;
719 s2
->as
[s2
->nas
].pr
= pr
;
725 static struct set
*newset(struct sets
*s
, int nnumbers
, int flags
)
729 ensure(s
->setlists
, s
->setlistsize
, s
->nsets
/SETLISTLEN
+1, struct set
*);
730 while (s
->nsetlists
<= s
->nsets
/ SETLISTLEN
)
731 s
->setlists
[s
->nsetlists
++] = snewn(SETLISTLEN
, struct set
);
732 sn
= s
->setlists
[s
->nsets
/ SETLISTLEN
] + s
->nsets
% SETLISTLEN
;
734 if (s
->nnumbers
+ nnumbers
* 2 > s
->nnumberlists
* NUMBERLISTLEN
)
735 s
->nnumbers
= s
->nnumberlists
* NUMBERLISTLEN
;
736 ensure(s
->numberlists
, s
->numberlistsize
,
737 s
->nnumbers
/NUMBERLISTLEN
+1, int *);
738 while (s
->nnumberlists
<= s
->nnumbers
/ NUMBERLISTLEN
)
739 s
->numberlists
[s
->nnumberlists
++] = snewn(NUMBERLISTLEN
, int);
740 sn
->numbers
= s
->numberlists
[s
->nnumbers
/ NUMBERLISTLEN
] +
741 s
->nnumbers
% NUMBERLISTLEN
;
744 * Start the set off empty.
753 static int addoutput(struct sets
*s
, struct set
*ss
, int index
, int *n
)
755 struct output
*o
, *o2
;
758 * Target numbers are always integers.
760 if (ss
->numbers
[2*index
+1] != 1)
763 ensure(s
->outputlists
, s
->outputlistsize
, s
->noutputs
/OUTPUTLISTLEN
+1,
765 while (s
->noutputlists
<= s
->noutputs
/ OUTPUTLISTLEN
)
766 s
->outputlists
[s
->noutputlists
++] = snewn(OUTPUTLISTLEN
,
768 o
= s
->outputlists
[s
->noutputs
/ OUTPUTLISTLEN
] +
769 s
->noutputs
% OUTPUTLISTLEN
;
771 o
->number
= ss
->numbers
[2*index
];
774 o
->npaths
= ss
->npaths
;
775 o2
= add234(s
->outputtree
, o
);
777 o2
->npaths
+= o
->npaths
;
785 static struct sets
*do_search(int ninputs
, int *inputs
,
786 const struct rules
*rules
, int *target
,
787 int debug
, int multiple
)
792 const struct operation
*const *ops
= rules
->ops
;
794 s
= snew(struct sets
);
796 s
->nsets
= s
->nsetlists
= s
->setlistsize
= 0;
797 s
->numberlists
= NULL
;
798 s
->nnumbers
= s
->nnumberlists
= s
->numberlistsize
= 0;
799 s
->outputlists
= NULL
;
800 s
->noutputs
= s
->noutputlists
= s
->outputlistsize
= 0;
801 s
->settree
= newtree234(setcmp
);
802 s
->outputtree
= newtree234(outputcmp
);
806 * Start with the input set.
808 sn
= newset(s
, ninputs
, SETFLAG_CONCAT
);
809 for (i
= 0; i
< ninputs
; i
++) {
811 newnumber
[0] = inputs
[i
];
813 addtoset(sn
, newnumber
);
815 addset(s
, sn
, multiple
, NULL
, 0, 0, 0, 0);
818 * Now perform the breadth-first search: keep looping over sets
819 * until we run out of steam.
822 while (qpos
< s
->nsets
) {
823 struct set
*ss
= s
->setlists
[qpos
/ SETLISTLEN
] + qpos
% SETLISTLEN
;
829 printf("processing set:");
830 for (i
= 0; i
< ss
->nnumbers
; i
++) {
831 printf(" %d", ss
->numbers
[2*i
]);
832 if (ss
->numbers
[2*i
+1] != 1)
833 printf("/%d", ss
->numbers
[2*i
+1]);
839 * Record all the valid output numbers in this state. We
840 * can always do this if there's only one number in the
841 * state; otherwise, we can only do it if we aren't
842 * required to use all the numbers in coming to our answer.
844 if (ss
->nnumbers
== 1 || !rules
->use_all
) {
845 for (i
= 0; i
< ss
->nnumbers
; i
++) {
848 if (addoutput(s
, ss
, i
, &n
) && target
&& n
== *target
)
854 * Try every possible operation from this state.
856 for (k
= 0; ops
[k
] && ops
[k
]->perform
; k
++) {
857 if ((ops
[k
]->flags
& OPFLAG_NEEDS_CONCAT
) &&
858 !(ss
->flags
& SETFLAG_CONCAT
))
859 continue; /* can't use this operation here */
860 for (i
= 0; i
< ss
->nnumbers
; i
++) {
861 int jlimit
= (ops
[k
]->flags
& OPFLAG_UNARY ?
1 : ss
->nnumbers
);
862 for (j
= 0; j
< jlimit
; j
++) {
866 if (!(ops
[k
]->flags
& OPFLAG_UNARY
)) {
868 continue; /* can't combine a number with itself */
869 if (i
> j
&& ops
[k
]->commutes
)
870 continue; /* no need to do this both ways round */
872 if (!ops
[k
]->perform(ss
->numbers
+2*i
, ss
->numbers
+2*j
, n
))
873 continue; /* operation failed */
875 sn
= newset(s
, ss
->nnumbers
-1, ss
->flags
);
877 if (!(ops
[k
]->flags
& OPFLAG_KEEPS_CONCAT
))
878 sn
->flags
&= ~SETFLAG_CONCAT
;
880 for (m
= 0; m
< ss
->nnumbers
; m
++) {
881 if (m
== i
|| (!(ops
[k
]->flags
& OPFLAG_UNARY
) &&
884 sn
->numbers
[2*sn
->nnumbers
] = ss
->numbers
[2*m
];
885 sn
->numbers
[2*sn
->nnumbers
+ 1] = ss
->numbers
[2*m
+ 1];
889 if (ops
[k
]->flags
& OPFLAG_UNARY
)
890 pb
= sn
->nnumbers
+10;
894 pr
= addtoset(sn
, n
);
895 addset(s
, sn
, multiple
, ss
, pa
, po
, pb
, pr
);
898 if (ops
[k
]->flags
& OPFLAG_UNARYPREFIX
)
899 printf(" %s %d ->", ops
[po
]->dbgtext
, pa
);
900 else if (ops
[k
]->flags
& OPFLAG_UNARY
)
901 printf(" %d %s ->", pa
, ops
[po
]->dbgtext
);
903 printf(" %d %s %d ->", pa
, ops
[po
]->dbgtext
, pb
);
904 for (i
= 0; i
< sn
->nnumbers
; i
++) {
905 printf(" %d", sn
->numbers
[2*i
]);
906 if (sn
->numbers
[2*i
+1] != 1)
907 printf("/%d", sn
->numbers
[2*i
+1]);
921 static void free_sets(struct sets
*s
)
925 freetree234(s
->settree
);
926 freetree234(s
->outputtree
);
927 for (i
= 0; i
< s
->nsetlists
; i
++)
928 sfree(s
->setlists
[i
]);
930 for (i
= 0; i
< s
->nnumberlists
; i
++)
931 sfree(s
->numberlists
[i
]);
932 sfree(s
->numberlists
);
933 for (i
= 0; i
< s
->noutputlists
; i
++)
934 sfree(s
->outputlists
[i
]);
935 sfree(s
->outputlists
);
940 * Print a text formula for producing a given output.
942 void print_recurse(struct sets
*s
, struct set
*ss
, int pathindex
, int index
,
943 int priority
, int assoc
, int child
);
944 void print_recurse_inner(struct sets
*s
, struct set
*ss
,
945 struct ancestor
*a
, int pathindex
, int index
,
946 int priority
, int assoc
, int child
)
948 if (a
->prev
&& index
!= a
->pr
) {
952 * This number was passed straight down from this set's
953 * predecessor. Find its index in the previous set and
960 if (pi
>= min(a
->pa
, a
->pb
)) {
962 if (pi
>= max(a
->pa
, a
->pb
))
965 print_recurse(s
, a
->prev
, pathindex
, pi
, priority
, assoc
, child
);
966 } else if (a
->prev
&& index
== a
->pr
&&
967 s
->ops
[a
->po
]->display
) {
969 * This number was created by a displayed operator in the
970 * transition from this set to its predecessor. Hence we
971 * write an open paren, then recurse into the first
972 * operand, then write the operator, then the second
973 * operand, and finally close the paren.
976 int parens
, thispri
, thisassoc
;
979 * Determine whether we need parentheses.
981 thispri
= s
->ops
[a
->po
]->priority
;
982 thisassoc
= s
->ops
[a
->po
]->assoc
;
983 parens
= (thispri
< priority
||
984 (thispri
== priority
&& (assoc
& child
)));
989 if (s
->ops
[a
->po
]->flags
& OPFLAG_UNARYPREFIX
)
990 for (op
= s
->ops
[a
->po
]->text
; *op
; op
++)
993 print_recurse(s
, a
->prev
, pathindex
, a
->pa
, thispri
, thisassoc
, 1);
995 if (!(s
->ops
[a
->po
]->flags
& OPFLAG_UNARYPREFIX
))
996 for (op
= s
->ops
[a
->po
]->text
; *op
; op
++)
999 if (!(s
->ops
[a
->po
]->flags
& OPFLAG_UNARY
))
1000 print_recurse(s
, a
->prev
, pathindex
, a
->pb
, thispri
, thisassoc
, 2);
1006 * This number is either an original, or something formed
1007 * by a non-displayed operator (concatenation). Either way,
1008 * we display it as is.
1010 printf("%d", ss
->numbers
[2*index
]);
1011 if (ss
->numbers
[2*index
+1] != 1)
1012 printf("/%d", ss
->numbers
[2*index
+1]);
1015 void print_recurse(struct sets
*s
, struct set
*ss
, int pathindex
, int index
,
1016 int priority
, int assoc
, int child
)
1018 if (!ss
->a
.prev
|| pathindex
< ss
->a
.prev
->npaths
) {
1019 print_recurse_inner(s
, ss
, &ss
->a
, pathindex
,
1020 index
, priority
, assoc
, child
);
1023 pathindex
-= ss
->a
.prev
->npaths
;
1024 for (i
= 0; i
< ss
->nas
; i
++) {
1025 if (pathindex
< ss
->as
[i
].prev
->npaths
) {
1026 print_recurse_inner(s
, ss
, &ss
->as
[i
], pathindex
,
1027 index
, priority
, assoc
, child
);
1030 pathindex
-= ss
->as
[i
].prev
->npaths
;
1034 void print(int pathindex
, struct sets
*s
, struct output
*o
)
1036 print_recurse(s
, o
->set
, pathindex
, o
->index
, 0, 0, 0);
1040 * gcc -g -O0 -o numgame numgame.c -I.. ../{malloc,tree234,nullfe}.c -lm
1042 int main(int argc
, char **argv
)
1044 int doing_opts
= TRUE
;
1045 const struct rules
*rules
= NULL
;
1046 char *pname
= argv
[0];
1047 int got_target
= FALSE
, target
= 0;
1048 int numbers
[10], nnumbers
= 0;
1049 int verbose
= FALSE
;
1050 int pathcounts
= FALSE
;
1051 int multiple
= FALSE
;
1052 int debug_bfs
= FALSE
;
1056 int i
, start
, limit
;
1062 if (doing_opts
&& *p
== '-') {
1065 if (!strcmp(p
, "-")) {
1068 } else if (*p
== '-') {
1070 if (!strcmp(p
, "debug-bfs")) {
1073 fprintf(stderr
, "%s: option '--%s' not recognised\n",
1076 } else while (*p
) switch (c
= *p
++) {
1078 rules
= &rules_countdown
;
1081 rules
= &rules_3388
;
1084 rules
= &rules_four4s
;
1087 rules
= &rules_anythinggoes
;
1104 } else if (--argc
) {
1107 fprintf(stderr
, "%s: option '-%c' expects an"
1108 " argument\n", pname
, c
);
1120 fprintf(stderr
, "%s: option '-%c' not"
1121 " recognised\n", pname
, c
);
1125 if (nnumbers
>= lenof(numbers
)) {
1126 fprintf(stderr
, "%s: internal limit of %d numbers exceeded\n",
1127 pname
, lenof(numbers
));
1130 numbers
[nnumbers
++] = atoi(p
);
1136 fprintf(stderr
, "%s: no rule set specified; use -C,-B,-D,-A\n", pname
);
1141 fprintf(stderr
, "%s: no input numbers specified\n", pname
);
1145 s
= do_search(nnumbers
, numbers
, rules
, (got_target ?
&target
: NULL
),
1146 debug_bfs
, multiple
);
1149 o
= findrelpos234(s
->outputtree
, &target
, outputfindcmp
,
1153 o
= findrelpos234(s
->outputtree
, &target
, outputfindcmp
,
1157 assert(start
!= -1 || limit
!= -1);
1160 else if (limit
== -1)
1165 limit
= count234(s
->outputtree
);
1168 for (i
= start
; i
< limit
; i
++) {
1171 o
= index234(s
->outputtree
, i
);
1173 sprintf(buf
, "%d", o
->number
);
1176 sprintf(buf
+ strlen(buf
), " [%d]", o
->npaths
);
1178 if (got_target
|| verbose
) {
1186 for (j
= 0; j
< npaths
; j
++) {
1187 printf("%s = ", buf
);
1192 printf("%s\n", buf
);