unfinished/numgame.c

   1 /*
   2  * This program implements a breadth-first search which
   3  * exhaustively solves the Countdown numbers game, and related
   4  * games with slightly different rule sets such as `Flippo'.
   5  *
   6  * Currently it is simply a standalone command-line utility to
   7  * which you provide a set of numbers and it tells you everything
   8  * it can make together with how many different ways it can be
   9  * made. I would like ultimately to turn it into the generator for
  10  * a Puzzles puzzle, but I haven't even started on writing a
  11  * Puzzles user interface yet.
  12  */
  13
  14 /*
  15  * TODO:
  16  *
  17  *  - start thinking about difficulty ratings
  18  *     + anything involving associative operations will be flagged
  19  *       as many-paths because of the associative options (e.g.
  20  *       2*3*4 can be (2*3)*4 or 2*(3*4), or indeed (2*4)*3). This
  21  *       is probably a _good_ thing, since those are unusually
  22  *       easy.
  23  *     + tree-structured calculations ((a*b)/(c+d)) have multiple
  24  *       paths because the independent branches of the tree can be
  25  *       evaluated in either order, whereas straight-line
  26  *       calculations with no branches will be considered easier.
  27  *       Can we do anything about this? It's certainly not clear to
  28  *       me that tree-structure calculations are _easier_, although
  29  *       I'm also not convinced they're harder.
  30  *     + I think for a realistic difficulty assessment we must also
  31  *       consider the `obviousness' of the arithmetic operations in
  32  *       some heuristic sense, and also (in Countdown) how many
  33  *       numbers ended up being used.
  34  *  - actually try some generations
  35  *  - at this point we're probably ready to start on the Puzzles
  36  *    integration.
  37  */
  38
  39 #include <stdio.h>
  40 #include <string.h>
  41 #include <limits.h>
  42 #include <assert.h>
  43 #include <math.h>
  44
  45 #include "puzzles.h"
  46 #include "tree234.h"
  47
  48 /*
  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.
  55  *
  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.
  59  *
  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.
  71  *
  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.
  86  */
  87
  88 #define SETFLAG_CONCAT 1               /* we can do concatenation */
  89
  90 struct sets;
  91
  92 struct ancestor {
  93     struct set *prev;                  /* index of ancestor set in set list */
  94     unsigned char pa, pb, po, pr;      /* operation that got here from prev */
  95 };
  96
  97 struct set {
  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 */
 104     int nas, assize;
 105 };
 106
 107 struct output {
 108     int number;
 109     struct set *set;
 110     int index;                         /* which number in the set is it? */
 111     int npaths;                        /* number of ways to reach this */
 112 };
 113
 114 #define SETLISTLEN 1024
 115 #define NUMBERLISTLEN 32768
 116 #define OUTPUTLISTLEN 1024
 117 struct operation;
 118 struct sets {
 119     struct set **setlists;
 120     int nsets, nsetlists, setlistsize;
 121     tree234 *settree;
 122     int **numberlists;
 123     int nnumbers, nnumberlists, numberlistsize;
 124     struct output **outputlists;
 125     int noutputs, noutputlists, outputlistsize;
 126     tree234 *outputtree;
 127     const struct operation *const *ops;
 128 };
 129
 130 #define OPFLAG_NEEDS_CONCAT 1
 131 #define OPFLAG_KEEPS_CONCAT 2
 132 #define OPFLAG_UNARY        4
 133 #define OPFLAG_UNARYPFX     8
 134
 135 struct operation {
 136     /*
 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
 140      * derived.
 141      */
 142     int display;
 143
 144     /*
 145      * Text display of the operator.
 146      */
 147     char *text;
 148
 149     /*
 150      * Flags dictating when the operator can be applied.
 151      */
 152     int flags;
 153
 154     /*
 155      * Priority of the operator (for avoiding unnecessary
 156      * parentheses when formatting it into a string).
 157      */
 158     int priority;
 159
 160     /*
 161      * Associativity of the operator. Bit 0 means we need parens
 162      * when the left operand of one of these operators is another
 163      * instance of it, e.g. (2^3)^4. Bit 1 means we need parens
 164      * when the right operand is another instance of the same
 165      * operator, e.g. 2-(3-4). Thus:
 166      *
 167      *  - this field is 0 for a fully associative operator, since
 168      *    we never need parens.
 169      *  - it's 1 for a right-associative operator.
 170      *  - it's 2 for a left-associative operator.
 171      *  - it's 3 for a _non_-associative operator (which always
 172      *    uses parens just to be sure).
 173      */
 174     int assoc;
 175
 176     /*
 177      * Whether the operator is commutative. Saves time in the
 178      * search if we don't have to try it both ways round.
 179      */
 180     int commutes;
 181
 182     /*
 183      * Function which implements the operator. Returns TRUE on
 184      * success, FALSE on failure. Takes two rationals and writes
 185      * out a third.
 186      */
 187     int (*perform)(int *a, int *b, int *output);
 188 };
 189
 190 struct rules {
 191     const struct operation *const *ops;
 192     int use_all;
 193 };
 194
 195 #define MUL(r, a, b) do { \
 196     (r) = (a) * (b); \
 197     if ((b) && (a) && (r) / (b) != (a)) return FALSE; \
 198 } while (0)
 199
 200 #define ADD(r, a, b) do { \
 201     (r) = (a) + (b); \
 202     if ((a) > 0 && (b) > 0 && (r) < 0) return FALSE; \
 203     if ((a) < 0 && (b) < 0 && (r) > 0) return FALSE; \
 204 } while (0)
 205
 206 #define OUT(output, n, d) do { \
 207     int g = gcd((n),(d)); \
 208     if (g < 0) g = -g; \
 209     if ((d) < 0) g = -g; \
 210     if (g == -1 && (n) < -INT_MAX) return FALSE; \
 211     if (g == -1 && (d) < -INT_MAX) return FALSE; \
 212     (output)[0] = (n)/g; \
 213     (output)[1] = (d)/g; \
 214     assert((output)[1] > 0); \
 215 } while (0)
 216
 217 static int gcd(int x, int y)
 218 {
 219     while (x != 0 && y != 0) {
 220         int t = x;
 221         x = y;
 222         y = t % y;
 223     }
 224
 225     return abs(x + y);                 /* i.e. whichever one isn't zero */
 226 }
 227
 228 static int perform_add(int *a, int *b, int *output)
 229 {
 230     int at, bt, tn, bn;
 231     /*
 232      * a0/a1 + b0/b1 = (a0*b1 + b0*a1) / (a1*b1)
 233      */
 234     MUL(at, a[0], b[1]);
 235     MUL(bt, b[0], a[1]);
 236     ADD(tn, at, bt);
 237     MUL(bn, a[1], b[1]);
 238     OUT(output, tn, bn);
 239     return TRUE;
 240 }
 241
 242 static int perform_sub(int *a, int *b, int *output)
 243 {
 244     int at, bt, tn, bn;
 245     /*
 246      * a0/a1 - b0/b1 = (a0*b1 - b0*a1) / (a1*b1)
 247      */
 248     MUL(at, a[0], b[1]);
 249     MUL(bt, b[0], a[1]);
 250     ADD(tn, at, -bt);
 251     MUL(bn, a[1], b[1]);
 252     OUT(output, tn, bn);
 253     return TRUE;
 254 }
 255
 256 static int perform_mul(int *a, int *b, int *output)
 257 {
 258     int tn, bn;
 259     /*
 260      * a0/a1 * b0/b1 = (a0*b0) / (a1*b1)
 261      */
 262     MUL(tn, a[0], b[0]);
 263     MUL(bn, a[1], b[1]);
 264     OUT(output, tn, bn);
 265     return TRUE;
 266 }
 267
 268 static int perform_div(int *a, int *b, int *output)
 269 {
 270     int tn, bn;
 271
 272     /*
 273      * Division by zero is outlawed.
 274      */
 275     if (b[0] == 0)
 276         return FALSE;
 277
 278     /*
 279      * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
 280      */
 281     MUL(tn, a[0], b[1]);
 282     MUL(bn, a[1], b[0]);
 283     OUT(output, tn, bn);
 284     return TRUE;
 285 }
 286
 287 static int perform_exact_div(int *a, int *b, int *output)
 288 {
 289     int tn, bn;
 290
 291     /*
 292      * Division by zero is outlawed.
 293      */
 294     if (b[0] == 0)
 295         return FALSE;
 296
 297     /*
 298      * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
 299      */
 300     MUL(tn, a[0], b[1]);
 301     MUL(bn, a[1], b[0]);
 302     OUT(output, tn, bn);
 303
 304     /*
 305      * Exact division means we require the result to be an integer.
 306      */
 307     return (output[1] == 1);
 308 }
 309
 310 static int perform_concat(int *a, int *b, int *output)
 311 {
 312     int t1, t2, p10;
 313
 314     /*
 315      * We can't concatenate anything which isn't a non-negative
 316      * integer.
 317      */
 318     if (a[1] != 1 || b[1] != 1 || a[0] < 0 || b[0] < 0)
 319         return FALSE;
 320
 321     /*
 322      * For concatenation, we can safely assume leading zeroes
 323      * aren't an issue. It isn't clear whether they `should' be
 324      * allowed, but it turns out not to matter: concatenating a
 325      * leading zero on to a number in order to harmlessly get rid
 326      * of the zero is never necessary because unwanted zeroes can
 327      * be disposed of by adding them to something instead. So we
 328      * disallow them always.
 329      *
 330      * The only other possibility is that you might want to
 331      * concatenate a leading zero on to something and then
 332      * concatenate another non-zero digit on to _that_ (to make,
 333      * for example, 106); but that's also unnecessary, because you
 334      * can make 106 just as easily by concatenating the 0 on to the
 335      * _end_ of the 1 first.
 336      */
 337     if (a[0] == 0)
 338         return FALSE;
 339
 340     /*
 341      * Find the smallest power of ten strictly greater than b. This
 342      * is the power of ten by which we'll multiply a.
 343      *
 344      * Special case: we must multiply a by at least 10, even if b
 345      * is zero.
 346      */
 347     p10 = 10;
 348     while (p10 <= (INT_MAX/10) && p10 <= b[0])
 349         p10 *= 10;
 350     if (p10 > INT_MAX/10)
 351         return FALSE;                  /* integer overflow */
 352     MUL(t1, p10, a[0]);
 353     ADD(t2, t1, b[0]);
 354     OUT(output, t2, 1);
 355     return TRUE;
 356 }
 357
 358 #define IPOW(ret, x, y) do { \
 359     int ipow_limit = (y); \
 360     if ((x) == 1 || (x) == 0) ipow_limit = 1; \
 361     else if ((x) == -1) ipow_limit &= 1; \
 362     (ret) = 1; \
 363     while (ipow_limit-- > 0) { \
 364         int tmp; \
 365         MUL(tmp, ret, x); \
 366         ret = tmp; \
 367     } \
 368 } while (0)
 369
 370 static int perform_exp(int *a, int *b, int *output)
 371 {
 372     int an, ad, xn, xd, limit, t, i;
 373
 374     /*
 375      * Exponentiation is permitted if the result is rational. This
 376      * means that:
 377      *
 378      *  - first we see whether we can take the (denominator-of-b)th
 379      *    root of a and get a rational; if not, we give up.
 380      *
 381      *  - then we do take that root of a
 382      *
 383      *  - then we multiply by itself (numerator-of-b) times.
 384      */
 385     if (b[1] > 1) {
 386         an = 0.5 + pow(a[0], 1.0/b[1]);
 387         ad = 0.5 + pow(a[1], 1.0/b[1]);
 388         IPOW(xn, an, b[1]);
 389         IPOW(xd, ad, b[1]);
 390         if (xn != a[0] || xd != a[1])
 391             return FALSE;
 392     } else {
 393         an = a[0];
 394         ad = a[1];
 395     }
 396     if (b[0] >= 0) {
 397         IPOW(xn, an, b[0]);
 398         IPOW(xd, ad, b[0]);
 399     } else {
 400         IPOW(xd, an, -b[0]);
 401         IPOW(xn, ad, -b[0]);
 402     }
 403     if (xd == 0)
 404         return FALSE;
 405
 406     OUT(output, xn, xd);
 407     return TRUE;
 408 }
 409
 410 static int perform_factorial(int *a, int *b, int *output)
 411 {
 412     int ret, t, i;
 413
 414     /*
 415      * Factorials of non-negative integers are permitted.
 416      */
 417     if (a[1] != 1 || a[0] < 0)
 418         return FALSE;
 419
 420     ret = 1;
 421     for (i = 1; i <= a[0]; i++) {
 422         MUL(t, ret, i);
 423         ret = t;
 424     }
 425
 426     OUT(output, ret, 1);
 427     return TRUE;
 428 }
 429
 430 const static struct operation op_add = {
 431     TRUE, "+", 0, 10, 0, TRUE, perform_add
 432 };
 433 const static struct operation op_sub = {
 434     TRUE, "-", 0, 10, 2, FALSE, perform_sub
 435 };
 436 const static struct operation op_mul = {
 437     TRUE, "*", 0, 20, 0, TRUE, perform_mul
 438 };
 439 const static struct operation op_div = {
 440     TRUE, "/", 0, 20, 2, FALSE, perform_div
 441 };
 442 const static struct operation op_xdiv = {
 443     TRUE, "/", 0, 20, 2, FALSE, perform_exact_div
 444 };
 445 const static struct operation op_concat = {
 446     FALSE, "", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT,
 447         1000, 0, FALSE, perform_concat
 448 };
 449 const static struct operation op_exp = {
 450     TRUE, "^", 0, 30, 1, FALSE, perform_exp
 451 };
 452 const static struct operation op_factorial = {
 453     TRUE, "!", OPFLAG_UNARY, 40, 0, FALSE, perform_factorial
 454 };
 455
 456 /*
 457  * In Countdown, divisions resulting in fractions are disallowed.
 458  * http://www.askoxford.com/wordgames/countdown/rules/
 459  */
 460 const static struct operation *const ops_countdown[] = {
 461     &op_add, &op_mul, &op_sub, &op_xdiv, NULL
 462 };
 463 const static struct rules rules_countdown = {
 464     ops_countdown, FALSE
 465 };
 466
 467 /*
 468  * A slightly different rule set which handles the reasonably well
 469  * known puzzle of making 24 using two 3s and two 8s. For this we
 470  * need rational rather than integer division.
 471  */
 472 const static struct operation *const ops_3388[] = {
 473     &op_add, &op_mul, &op_sub, &op_div, NULL
 474 };
 475 const static struct rules rules_3388 = {
 476     ops_3388, TRUE
 477 };
 478
 479 /*
 480  * A still more permissive rule set usable for the four-4s problem
 481  * and similar things. Permits concatenation.
 482  */
 483 const static struct operation *const ops_four4s[] = {
 484     &op_add, &op_mul, &op_sub, &op_div, &op_concat, NULL
 485 };
 486 const static struct rules rules_four4s = {
 487     ops_four4s, TRUE
 488 };
 489
 490 /*
 491  * The most permissive ruleset I can think of. Permits
 492  * exponentiation, and also silly unary operators like factorials.
 493  */
 494 const static struct operation *const ops_anythinggoes[] = {
 495     &op_add, &op_mul, &op_sub, &op_div, &op_concat, &op_exp, &op_factorial, NULL
 496 };
 497 const static struct rules rules_anythinggoes = {
 498     ops_anythinggoes, TRUE
 499 };
 500
 501 #define ratcmp(a,op,b) ( (long long)(a)[0] * (b)[1] op \
 502                          (long long)(b)[0] * (a)[1] )
 503
 504 static int addtoset(struct set *set, int newnumber[2])
 505 {
 506     int i, j;
 507
 508     /* Find where we want to insert the new number */
 509     for (i = 0; i < set->nnumbers &&
 510          ratcmp(set->numbers+2*i, <, newnumber); i++);
 511
 512     /* Move everything else up */
 513     for (j = set->nnumbers; j > i; j--) {
 514         set->numbers[2*j] = set->numbers[2*j-2];
 515         set->numbers[2*j+1] = set->numbers[2*j-1];
 516     }
 517
 518     /* Insert the new number */
 519     set->numbers[2*i] = newnumber[0];
 520     set->numbers[2*i+1] = newnumber[1];
 521
 522     set->nnumbers++;
 523
 524     return i;
 525 }
 526
 527 #define ensure(array, size, newlen, type) do { \
 528     if ((newlen) > (size)) { \
 529         (size) = (newlen) + 512; \
 530         (array) = sresize((array), (size), type); \
 531     } \
 532 } while (0)
 533
 534 static int setcmp(void *av, void *bv)
 535 {
 536     struct set *a = (struct set *)av;
 537     struct set *b = (struct set *)bv;
 538     int i;
 539
 540     if (a->nnumbers < b->nnumbers)
 541         return -1;
 542     else if (a->nnumbers > b->nnumbers)
 543         return +1;
 544
 545     if (a->flags < b->flags)
 546         return -1;
 547     else if (a->flags > b->flags)
 548         return +1;
 549
 550     for (i = 0; i < a->nnumbers; i++) {
 551         if (ratcmp(a->numbers+2*i, <, b->numbers+2*i))
 552             return -1;
 553         else if (ratcmp(a->numbers+2*i, >, b->numbers+2*i))
 554             return +1;
 555     }
 556
 557     return 0;
 558 }
 559
 560 static int outputcmp(void *av, void *bv)
 561 {
 562     struct output *a = (struct output *)av;
 563     struct output *b = (struct output *)bv;
 564
 565     if (a->number < b->number)
 566         return -1;
 567     else if (a->number > b->number)
 568         return +1;
 569
 570     return 0;
 571 }
 572
 573 static int outputfindcmp(void *av, void *bv)
 574 {
 575     int *a = (int *)av;
 576     struct output *b = (struct output *)bv;
 577
 578     if (*a < b->number)
 579         return -1;
 580     else if (*a > b->number)
 581         return +1;
 582
 583     return 0;
 584 }
 585
 586 static void addset(struct sets *s, struct set *set, int multiple,
 587                    struct set *prev, int pa, int po, int pb, int pr)
 588 {
 589     struct set *s2;
 590     int npaths = (prev ? prev->npaths : 1);
 591
 592     assert(set == s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN);
 593     s2 = add234(s->settree, set);
 594     if (s2 == set) {
 595         /*
 596          * New set added to the tree.
 597          */
 598         set->a.prev = prev;
 599         set->a.pa = pa;
 600         set->a.po = po;
 601         set->a.pb = pb;
 602         set->a.pr = pr;
 603         set->npaths = npaths;
 604         s->nsets++;
 605         s->nnumbers += 2 * set->nnumbers;
 606         set->as = NULL;
 607         set->nas = set->assize = 0;
 608     } else {
 609         /*
 610          * Rediscovered an existing set. Update its npaths.
 611          */
 612         s2->npaths += npaths;
 613         /*
 614          * And optionally enter it as an additional ancestor.
 615          */
 616         if (multiple) {
 617             if (s2->nas >= s2->assize) {
 618                 s2->assize = s2->nas * 3 / 2 + 4;
 619                 s2->as = sresize(s2->as, s2->assize, struct ancestor);
 620             }
 621             s2->as[s2->nas].prev = prev;
 622             s2->as[s2->nas].pa = pa;
 623             s2->as[s2->nas].po = po;
 624             s2->as[s2->nas].pb = pb;
 625             s2->as[s2->nas].pr = pr;
 626             s2->nas++;
 627         }
 628     }
 629 }
 630
 631 static struct set *newset(struct sets *s, int nnumbers, int flags)
 632 {
 633     struct set *sn;
 634
 635     ensure(s->setlists, s->setlistsize, s->nsets/SETLISTLEN+1, struct set *);
 636     while (s->nsetlists <= s->nsets / SETLISTLEN)
 637         s->setlists[s->nsetlists++] = snewn(SETLISTLEN, struct set);
 638     sn = s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN;
 639
 640     if (s->nnumbers + nnumbers * 2 > s->nnumberlists * NUMBERLISTLEN)
 641         s->nnumbers = s->nnumberlists * NUMBERLISTLEN;
 642     ensure(s->numberlists, s->numberlistsize,
 643            s->nnumbers/NUMBERLISTLEN+1, int *);
 644     while (s->nnumberlists <= s->nnumbers / NUMBERLISTLEN)
 645         s->numberlists[s->nnumberlists++] = snewn(NUMBERLISTLEN, int);
 646     sn->numbers = s->numberlists[s->nnumbers / NUMBERLISTLEN] +
 647         s->nnumbers % NUMBERLISTLEN;
 648
 649     /*
 650      * Start the set off empty.
 651      */
 652     sn->nnumbers = 0;
 653
 654     sn->flags = flags;
 655
 656     return sn;
 657 }
 658
 659 static int addoutput(struct sets *s, struct set *ss, int index, int *n)
 660 {
 661     struct output *o, *o2;
 662
 663     /*
 664      * Target numbers are always integers.
 665      */
 666     if (ss->numbers[2*index+1] != 1)
 667         return FALSE;
 668
 669     ensure(s->outputlists, s->outputlistsize, s->noutputs/OUTPUTLISTLEN+1,
 670            struct output *);
 671     while (s->noutputlists <= s->noutputs / OUTPUTLISTLEN)
 672         s->outputlists[s->noutputlists++] = snewn(OUTPUTLISTLEN,
 673                                                   struct output);
 674     o = s->outputlists[s->noutputs / OUTPUTLISTLEN] +
 675         s->noutputs % OUTPUTLISTLEN;
 676
 677     o->number = ss->numbers[2*index];
 678     o->set = ss;
 679     o->index = index;
 680     o->npaths = ss->npaths;
 681     o2 = add234(s->outputtree, o);
 682     if (o2 != o) {
 683         o2->npaths += o->npaths;
 684     } else {
 685         s->noutputs++;
 686     }
 687     *n = o->number;
 688     return TRUE;
 689 }
 690
 691 static struct sets *do_search(int ninputs, int *inputs,
 692                               const struct rules *rules, int *target,
 693                               int multiple)
 694 {
 695     struct sets *s;
 696     struct set *sn;
 697     int qpos, i;
 698     const struct operation *const *ops = rules->ops;
 699
 700     s = snew(struct sets);
 701     s->setlists = NULL;
 702     s->nsets = s->nsetlists = s->setlistsize = 0;
 703     s->numberlists = NULL;
 704     s->nnumbers = s->nnumberlists = s->numberlistsize = 0;
 705     s->outputlists = NULL;
 706     s->noutputs = s->noutputlists = s->outputlistsize = 0;
 707     s->settree = newtree234(setcmp);
 708     s->outputtree = newtree234(outputcmp);
 709     s->ops = ops;
 710
 711     /*
 712      * Start with the input set.
 713      */
 714     sn = newset(s, ninputs, SETFLAG_CONCAT);
 715     for (i = 0; i < ninputs; i++) {
 716         int newnumber[2];
 717         newnumber[0] = inputs[i];
 718         newnumber[1] = 1;
 719         addtoset(sn, newnumber);
 720     }
 721     addset(s, sn, multiple, NULL, 0, 0, 0, 0);
 722
 723     /*
 724      * Now perform the breadth-first search: keep looping over sets
 725      * until we run out of steam.
 726      */
 727     qpos = 0;
 728     while (qpos < s->nsets) {
 729         struct set *ss = s->setlists[qpos / SETLISTLEN] + qpos % SETLISTLEN;
 730         struct set *sn;
 731         int i, j, k, m;
 732
 733         /*
 734          * Record all the valid output numbers in this state. We
 735          * can always do this if there's only one number in the
 736          * state; otherwise, we can only do it if we aren't
 737          * required to use all the numbers in coming to our answer.
 738          */
 739         if (ss->nnumbers == 1 || !rules->use_all) {
 740             for (i = 0; i < ss->nnumbers; i++) {
 741                 int n;
 742
 743                 if (addoutput(s, ss, i, &n) && target && n == *target)
 744                     return s;
 745             }
 746         }
 747
 748         /*
 749          * Try every possible operation from this state.
 750          */
 751         for (k = 0; ops[k] && ops[k]->perform; k++) {
 752             if ((ops[k]->flags & OPFLAG_NEEDS_CONCAT) &&
 753                 !(ss->flags & SETFLAG_CONCAT))
 754                 continue;              /* can't use this operation here */
 755             for (i = 0; i < ss->nnumbers; i++) {
 756                 int jlimit = (ops[k]->flags & OPFLAG_UNARY ? 1 : ss->nnumbers);
 757                 for (j = 0; j < jlimit; j++) {
 758                     int n[2];
 759                     int pa, po, pb, pr;
 760
 761                     if (!(ops[k]->flags & OPFLAG_UNARY)) {
 762                         if (i == j)
 763                             continue;  /* can't combine a number with itself */
 764                         if (i > j && ops[k]->commutes)
 765                             continue;  /* no need to do this both ways round */
 766                     }
 767                     if (!ops[k]->perform(ss->numbers+2*i, ss->numbers+2*j, n))
 768                         continue;      /* operation failed */
 769
 770                     sn = newset(s, ss->nnumbers-1, ss->flags);
 771
 772                     if (!(ops[k]->flags & OPFLAG_KEEPS_CONCAT))
 773                         sn->flags &= ~SETFLAG_CONCAT;
 774
 775                     for (m = 0; m < ss->nnumbers; m++) {
 776                         if (m == i || (!(ops[k]->flags & OPFLAG_UNARY) &&
 777                                        m == j))
 778                             continue;
 779                         sn->numbers[2*sn->nnumbers] = ss->numbers[2*m];
 780                         sn->numbers[2*sn->nnumbers + 1] = ss->numbers[2*m + 1];
 781                         sn->nnumbers++;
 782                     }
 783                     pa = i;
 784                     if (ops[k]->flags & OPFLAG_UNARY)
 785                         pb = sn->nnumbers+10;
 786                     else
 787                         pb = j;
 788                     po = k;
 789                     pr = addtoset(sn, n);
 790                     addset(s, sn, multiple, ss, pa, po, pb, pr);
 791                 }
 792             }
 793         }
 794
 795         qpos++;
 796     }
 797
 798     return s;
 799 }
 800
 801 static void free_sets(struct sets *s)
 802 {
 803     int i;
 804
 805     freetree234(s->settree);
 806     freetree234(s->outputtree);
 807     for (i = 0; i < s->nsetlists; i++)
 808         sfree(s->setlists[i]);
 809     sfree(s->setlists);
 810     for (i = 0; i < s->nnumberlists; i++)
 811         sfree(s->numberlists[i]);
 812     sfree(s->numberlists);
 813     for (i = 0; i < s->noutputlists; i++)
 814         sfree(s->outputlists[i]);
 815     sfree(s->outputlists);
 816     sfree(s);
 817 }
 818
 819 /*
 820  * Print a text formula for producing a given output.
 821  */
 822 void print_recurse(struct sets *s, struct set *ss, int pathindex, int index,
 823                    int priority, int assoc, int child);
 824 void print_recurse_inner(struct sets *s, struct set *ss,
 825                          struct ancestor *a, int pathindex, int index,
 826                          int priority, int assoc, int child)
 827 {
 828     if (a->prev && index != a->pr) {
 829         int pi;
 830
 831         /*
 832          * This number was passed straight down from this set's
 833          * predecessor. Find its index in the previous set and
 834          * recurse to there.
 835          */
 836         pi = index;
 837         assert(pi != a->pr);
 838         if (pi > a->pr)
 839             pi--;
 840         if (pi >= min(a->pa, a->pb)) {
 841             pi++;
 842             if (pi >= max(a->pa, a->pb))
 843                 pi++;
 844         }
 845         print_recurse(s, a->prev, pathindex, pi, priority, assoc, child);
 846     } else if (a->prev && index == a->pr &&
 847                s->ops[a->po]->display) {
 848         /*
 849          * This number was created by a displayed operator in the
 850          * transition from this set to its predecessor. Hence we
 851          * write an open paren, then recurse into the first
 852          * operand, then write the operator, then the second
 853          * operand, and finally close the paren.
 854          */
 855         char *op;
 856         int parens, thispri, thisassoc;
 857
 858         /*
 859          * Determine whether we need parentheses.
 860          */
 861         thispri = s->ops[a->po]->priority;
 862         thisassoc = s->ops[a->po]->assoc;
 863         parens = (thispri < priority ||
 864                   (thispri == priority && (assoc & child)));
 865
 866         if (parens)
 867             putchar('(');
 868
 869         if (s->ops[a->po]->flags & OPFLAG_UNARYPFX)
 870             for (op = s->ops[a->po]->text; *op; op++)
 871                 putchar(*op);
 872
 873         print_recurse(s, a->prev, pathindex, a->pa, thispri, thisassoc, 1);
 874
 875         if (!(s->ops[a->po]->flags & OPFLAG_UNARYPFX))
 876             for (op = s->ops[a->po]->text; *op; op++)
 877                 putchar(*op);
 878
 879         if (!(s->ops[a->po]->flags & OPFLAG_UNARY))
 880             print_recurse(s, a->prev, pathindex, a->pb, thispri, thisassoc, 2);
 881
 882         if (parens)
 883             putchar(')');
 884     } else {
 885         /*
 886          * This number is either an original, or something formed
 887          * by a non-displayed operator (concatenation). Either way,
 888          * we display it as is.
 889          */
 890         printf("%d", ss->numbers[2*index]);
 891         if (ss->numbers[2*index+1] != 1)
 892             printf("/%d", ss->numbers[2*index+1]);
 893     }
 894 }
 895 void print_recurse(struct sets *s, struct set *ss, int pathindex, int index,
 896                    int priority, int assoc, int child)
 897 {
 898     if (!ss->a.prev || pathindex < ss->a.prev->npaths) {
 899         print_recurse_inner(s, ss, &ss->a, pathindex,
 900                             index, priority, assoc, child);
 901     } else {
 902         int i;
 903         pathindex -= ss->a.prev->npaths;
 904         for (i = 0; i < ss->nas; i++) {
 905             if (pathindex < ss->as[i].prev->npaths) {
 906                 print_recurse_inner(s, ss, &ss->as[i], pathindex,
 907                                     index, priority, assoc, child);
 908                 break;
 909             }
 910             pathindex -= ss->as[i].prev->npaths;
 911         }
 912     }
 913 }
 914 void print(int pathindex, struct sets *s, struct output *o)
 915 {
 916     print_recurse(s, o->set, pathindex, o->index, 0, 0, 0);
 917 }
 918
 919 /*
 920  * gcc -g -O0 -o numgame numgame.c -I.. ../{malloc,tree234,nullfe}.c -lm
 921  */
 922 int main(int argc, char **argv)
 923 {
 924     int doing_opts = TRUE;
 925     const struct rules *rules = NULL;
 926     char *pname = argv[0];
 927     int got_target = FALSE, target = 0;
 928     int numbers[10], nnumbers = 0;
 929     int verbose = FALSE;
 930     int pathcounts = FALSE;
 931     int multiple = FALSE;
 932
 933     struct output *o;
 934     struct sets *s;
 935     int i, start, limit;
 936
 937     while (--argc) {
 938         char *p = *++argv;
 939         int c;
 940
 941         if (doing_opts && *p == '-') {
 942             p++;
 943
 944             if (!strcmp(p, "-")) {
 945                 doing_opts = FALSE;
 946                 continue;
 947             } else while (*p) switch (c = *p++) {
 948               case 'C':
 949                 rules = &rules_countdown;
 950                 break;
 951               case 'B':
 952                 rules = &rules_3388;
 953                 break;
 954               case 'D':
 955                 rules = &rules_four4s;
 956                 break;
 957               case 'A':
 958                 rules = &rules_anythinggoes;
 959                 break;
 960               case 'v':
 961                 verbose = TRUE;
 962                 break;
 963               case 'p':
 964                 pathcounts = TRUE;
 965                 break;
 966               case 'm':
 967                 multiple = TRUE;
 968                 break;
 969               case 't':
 970                 {
 971                     char *v;
 972                     if (*p) {
 973                         v = p;
 974                         p = NULL;
 975                     } else if (--argc) {
 976                         v = *++argv;
 977                     } else {
 978                         fprintf(stderr, "%s: option '-%c' expects an"
 979                                 " argument\n", pname, c);
 980                         return 1;
 981                     }
 982                     switch (c) {
 983                       case 't':
 984                         got_target = TRUE;
 985                         target = atoi(v);
 986                         break;
 987                     }
 988                 }
 989                 break;
 990               default:
 991                 fprintf(stderr, "%s: option '-%c' not"
 992                         " recognised\n", pname, c);
 993                 return 1;
 994             }
 995         } else {
 996             if (nnumbers >= lenof(numbers)) {
 997                 fprintf(stderr, "%s: internal limit of %d numbers exceeded\n",
 998                         pname, lenof(numbers));
 999                 return 1;
1000             } else {
1001                 numbers[nnumbers++] = atoi(p);
1002             }
1003         }
1004     }
1005
1006     if (!rules) {
1007         fprintf(stderr, "%s: no rule set specified; use -C,-B,-D,-A\n", pname);
1008         return 1;
1009     }
1010
1011     if (!nnumbers) {
1012         fprintf(stderr, "%s: no input numbers specified\n", pname);
1013         return 1;
1014     }
1015
1016     s = do_search(nnumbers, numbers, rules, (got_target ? &target : NULL),
1017                   multiple);
1018
1019     if (got_target) {
1020         o = findrelpos234(s->outputtree, &target, outputfindcmp,
1021                           REL234_LE, &start);
1022         if (!o)
1023             start = -1;
1024         o = findrelpos234(s->outputtree, &target, outputfindcmp,
1025                           REL234_GE, &limit);
1026         if (!o)
1027             limit = -1;
1028         assert(start != -1 || limit != -1);
1029         if (start == -1)
1030             start = limit;
1031         else if (limit == -1)
1032             limit = start;
1033         limit++;
1034     } else {
1035         start = 0;
1036         limit = count234(s->outputtree);
1037     }
1038
1039     for (i = start; i < limit; i++) {
1040         char buf[256];
1041
1042         o = index234(s->outputtree, i);
1043
1044         sprintf(buf, "%d", o->number);
1045
1046         if (pathcounts)
1047             sprintf(buf + strlen(buf), " [%d]", o->npaths);
1048
1049         if (got_target || verbose) {
1050             int j, npaths;
1051
1052             if (multiple)
1053                 npaths = o->npaths;
1054             else
1055                 npaths = 1;
1056
1057             for (j = 0; j < npaths; j++) {
1058                 printf("%s = ", buf);
1059                 print(j, s, o);
1060                 putchar('\n');
1061             }
1062         } else {
1063             printf("%s\n", buf);
1064         }
1065     }
1066
1067     free_sets(s);
1068
1069     return 0;
1070 }