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