*/
#include <stdio.h>
+#include <string.h>
#include <limits.h>
#include <assert.h>
+#include <math.h>
#include "puzzles.h"
#include "tree234.h"
struct sets;
+struct ancestor {
+ struct set *prev; /* index of ancestor set in set list */
+ unsigned char pa, pb, po, pr; /* operation that got here from prev */
+};
+
struct set {
int *numbers; /* rationals stored as n,d pairs */
short nnumbers; /* # of rationals, so half # of ints */
short flags; /* SETFLAG_CONCAT only, at present */
- struct set *prev; /* index of ancestor set in set list */
- unsigned char pa, pb, po, pr; /* operation that got here from prev */
int npaths; /* number of ways to reach this set */
+ struct ancestor a; /* primary ancestor */
+ struct ancestor *as; /* further ancestors, if we care */
+ int nas, assize;
};
struct output {
#define OPFLAG_NEEDS_CONCAT 1
#define OPFLAG_KEEPS_CONCAT 2
+#define OPFLAG_UNARY 4
+#define OPFLAG_UNARYPREFIX 8
+#define OPFLAG_FN 16
struct operation {
/*
int display;
/*
- * Text display of the operator.
+ * Text display of the operator, in expressions and for
+ * debugging respectively.
*/
- char *text;
+ char *text, *dbgtext;
/*
* Flags dictating when the operator can be applied.
#define OUT(output, n, d) do { \
int g = gcd((n),(d)); \
+ if (g < 0) g = -g; \
if ((d) < 0) g = -g; \
+ if (g == -1 && (n) < -INT_MAX) return FALSE; \
+ if (g == -1 && (d) < -INT_MAX) return FALSE; \
(output)[0] = (n)/g; \
(output)[1] = (d)/g; \
assert((output)[1] > 0); \
return (output[1] == 1);
}
+static int max_p10(int n, int *p10_r)
+{
+ /*
+ * Find the smallest power of ten strictly greater than n.
+ *
+ * Special case: we must return at least 10, even if n is
+ * zero. (This is because this function is used for finding
+ * the power of ten by which to multiply a number being
+ * concatenated to the front of n, and concatenating 1 to 0
+ * should yield 10 and not 1.)
+ */
+ int p10 = 10;
+ while (p10 <= (INT_MAX/10) && p10 <= n)
+ p10 *= 10;
+ if (p10 > INT_MAX/10)
+ return FALSE; /* integer overflow */
+ *p10_r = p10;
+ return TRUE;
+}
+
static int perform_concat(int *a, int *b, int *output)
{
int t1, t2, p10;
/*
- * We can't concatenate anything which isn't an integer.
+ * We can't concatenate anything which isn't a non-negative
+ * integer.
*/
- if (a[1] != 1 || b[1] != 1)
+ if (a[1] != 1 || b[1] != 1 || a[0] < 0 || b[0] < 0)
return FALSE;
/*
if (a[0] == 0)
return FALSE;
+ if (!max_p10(b[0], &p10)) return FALSE;
+
+ MUL(t1, p10, a[0]);
+ ADD(t2, t1, b[0]);
+ OUT(output, t2, 1);
+ return TRUE;
+}
+
+#define IPOW(ret, x, y) do { \
+ int ipow_limit = (y); \
+ if ((x) == 1 || (x) == 0) ipow_limit = 1; \
+ else if ((x) == -1) ipow_limit &= 1; \
+ (ret) = 1; \
+ while (ipow_limit-- > 0) { \
+ int tmp; \
+ MUL(tmp, ret, x); \
+ ret = tmp; \
+ } \
+} while (0)
+
+static int perform_exp(int *a, int *b, int *output)
+{
+ int an, ad, xn, xd;
+
/*
- * Find the smallest power of ten strictly greater than b. This
- * is the power of ten by which we'll multiply a.
+ * Exponentiation is permitted if the result is rational. This
+ * means that:
+ *
+ * - first we see whether we can take the (denominator-of-b)th
+ * root of a and get a rational; if not, we give up.
*
- * Special case: we must multiply a by at least 10, even if b
- * is zero.
+ * - then we do take that root of a
+ *
+ * - then we multiply by itself (numerator-of-b) times.
*/
+ if (b[1] > 1) {
+ an = (int)(0.5 + pow(a[0], 1.0/b[1]));
+ ad = (int)(0.5 + pow(a[1], 1.0/b[1]));
+ IPOW(xn, an, b[1]);
+ IPOW(xd, ad, b[1]);
+ if (xn != a[0] || xd != a[1])
+ return FALSE;
+ } else {
+ an = a[0];
+ ad = a[1];
+ }
+ if (b[0] >= 0) {
+ IPOW(xn, an, b[0]);
+ IPOW(xd, ad, b[0]);
+ } else {
+ IPOW(xd, an, -b[0]);
+ IPOW(xn, ad, -b[0]);
+ }
+ if (xd == 0)
+ return FALSE;
+
+ OUT(output, xn, xd);
+ return TRUE;
+}
+
+static int perform_factorial(int *a, int *b, int *output)
+{
+ int ret, t, i;
+
+ /*
+ * Factorials of non-negative integers are permitted.
+ */
+ if (a[1] != 1 || a[0] < 0)
+ return FALSE;
+
+ /*
+ * However, a special case: we don't take a factorial of
+ * anything which would thereby remain the same.
+ */
+ if (a[0] == 1 || a[0] == 2)
+ return FALSE;
+
+ ret = 1;
+ for (i = 1; i <= a[0]; i++) {
+ MUL(t, ret, i);
+ ret = t;
+ }
+
+ OUT(output, ret, 1);
+ return TRUE;
+}
+
+static int perform_decimal(int *a, int *b, int *output)
+{
+ int p10;
+
+ /*
+ * Add a decimal digit to the front of a number;
+ * fail if it's not an integer.
+ * So, 1 --> 0.1, 15 --> 0.15,
+ * or, rather, 1 --> 1/10, 15 --> 15/100,
+ * x --> x / (smallest power of 10 > than x)
+ *
+ */
+ if (a[1] != 1) return FALSE;
+
+ if (!max_p10(a[0], &p10)) return FALSE;
+
+ OUT(output, a[0], p10);
+ return TRUE;
+}
+
+static int perform_recur(int *a, int *b, int *output)
+{
+ int p10, tn, bn;
+
+ /*
+ * This converts a number like .4 to .44444..., or .45 to .45454...
+ * The input number must be -1 < a < 1.
+ *
+ * Calculate the smallest power of 10 that divides the denominator exactly,
+ * returning if no such power of 10 exists. Then multiply the numerator
+ * up accordingly, and the new denominator becomes that power of 10 - 1.
+ */
+ if (abs(a[0]) >= abs(a[1])) return FALSE; /* -1 < a < 1 */
+
p10 = 10;
- while (p10 <= (INT_MAX/10) && p10 <= b[0])
- p10 *= 10;
- if (p10 > INT_MAX/10)
- return FALSE; /* integer overflow */
- MUL(t1, p10, a[0]);
- ADD(t2, t1, b[0]);
- OUT(output, t2, 1);
+ while (p10 <= (INT_MAX/10)) {
+ if ((a[1] <= p10) && (p10 % a[1]) == 0) goto found;
+ p10 *= 10;
+ }
+ return FALSE;
+found:
+ tn = a[0] * (p10 / a[1]);
+ bn = p10 - 1;
+
+ OUT(output, tn, bn);
return TRUE;
}
+static int perform_root(int *a, int *b, int *output)
+{
+ /*
+ * A root B is: 1 iff a == 0
+ * B ^ (1/A) otherwise
+ */
+ int ainv[2], res;
+
+ if (a[0] == 0) {
+ OUT(output, 1, 1);
+ return TRUE;
+ }
+
+ OUT(ainv, a[1], a[0]);
+ res = perform_exp(b, ainv, output);
+ return res;
+}
+
+static int perform_perc(int *a, int *b, int *output)
+{
+ if (a[0] == 0) return FALSE; /* 0% = 0, uninteresting. */
+ if (a[1] > (INT_MAX/100)) return FALSE;
+
+ OUT(output, a[0], a[1]*100);
+ return TRUE;
+}
+
+static int perform_gamma(int *a, int *b, int *output)
+{
+ int asub1[2];
+
+ /*
+ * gamma(a) = (a-1)!
+ *
+ * special case not caught by perform_fact: gamma(1) is 1 so
+ * don't bother.
+ */
+ if (a[0] == 1 && a[1] == 1) return FALSE;
+
+ OUT(asub1, a[0]-a[1], a[1]);
+ return perform_factorial(asub1, b, output);
+}
+
+static int perform_sqrt(int *a, int *b, int *output)
+{
+ int half[2] = { 1, 2 };
+
+ /*
+ * sqrt(0) == 0, sqrt(1) == 1: don't perform unary noops.
+ */
+ if (a[0] == 0 || (a[0] == 1 && a[1] == 1)) return FALSE;
+
+ return perform_exp(a, half, output);
+}
+
const static struct operation op_add = {
- TRUE, "+", 0, 10, 0, TRUE, perform_add
+ TRUE, "+", "+", 0, 10, 0, TRUE, perform_add
};
const static struct operation op_sub = {
- TRUE, "-", 0, 10, 2, FALSE, perform_sub
+ TRUE, "-", "-", 0, 10, 2, FALSE, perform_sub
};
const static struct operation op_mul = {
- TRUE, "*", 0, 20, 0, TRUE, perform_mul
+ TRUE, "*", "*", 0, 20, 0, TRUE, perform_mul
};
const static struct operation op_div = {
- TRUE, "/", 0, 20, 2, FALSE, perform_div
+ TRUE, "/", "/", 0, 20, 2, FALSE, perform_div
};
const static struct operation op_xdiv = {
- TRUE, "/", 0, 20, 2, FALSE, perform_exact_div
+ TRUE, "/", "/", 0, 20, 2, FALSE, perform_exact_div
};
const static struct operation op_concat = {
- FALSE, "", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT,
+ FALSE, "", "concat", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT,
1000, 0, FALSE, perform_concat
};
+const static struct operation op_exp = {
+ TRUE, "^", "^", 0, 30, 1, FALSE, perform_exp
+};
+const static struct operation op_factorial = {
+ TRUE, "!", "!", OPFLAG_UNARY, 40, 0, FALSE, perform_factorial
+};
+const static struct operation op_decimal = {
+ TRUE, ".", ".", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT, 50, 0, FALSE, perform_decimal
+};
+const static struct operation op_recur = {
+ TRUE, "...", "recur", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 2, FALSE, perform_recur
+};
+const static struct operation op_root = {
+ TRUE, "v~", "root", 0, 30, 1, FALSE, perform_root
+};
+const static struct operation op_perc = {
+ TRUE, "%", "%", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 1, FALSE, perform_perc
+};
+const static struct operation op_gamma = {
+ TRUE, "gamma", "gamma", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_FN, 1, 3, FALSE, perform_gamma
+};
+const static struct operation op_sqrt = {
+ TRUE, "v~", "sqrt", OPFLAG_UNARY | OPFLAG_UNARYPREFIX, 30, 1, FALSE, perform_sqrt
+};
/*
* In Countdown, divisions resulting in fractions are disallowed.
ops_four4s, TRUE
};
+/*
+ * The most permissive ruleset I can think of. Permits
+ * exponentiation, and also silly unary operators like factorials.
+ */
+const static struct operation *const ops_anythinggoes[] = {
+ &op_add, &op_mul, &op_sub, &op_div, &op_concat, &op_exp, &op_factorial,
+ &op_decimal, &op_recur, &op_root, &op_perc, &op_gamma, &op_sqrt, NULL
+};
+const static struct rules rules_anythinggoes = {
+ ops_anythinggoes, TRUE
+};
+
#define ratcmp(a,op,b) ( (long long)(a)[0] * (b)[1] op \
(long long)(b)[0] * (a)[1] )
return 0;
}
-static void addset(struct sets *s, struct set *set, struct set *prev)
+static void addset(struct sets *s, struct set *set, int multiple,
+ struct set *prev, int pa, int po, int pb, int pr)
{
struct set *s2;
int npaths = (prev ? prev->npaths : 1);
/*
* New set added to the tree.
*/
- set->prev = prev;
+ set->a.prev = prev;
+ set->a.pa = pa;
+ set->a.po = po;
+ set->a.pb = pb;
+ set->a.pr = pr;
set->npaths = npaths;
s->nsets++;
s->nnumbers += 2 * set->nnumbers;
+ set->as = NULL;
+ set->nas = set->assize = 0;
} else {
/*
- * Rediscovered an existing set. Update its npaths only.
+ * Rediscovered an existing set. Update its npaths.
*/
s2->npaths += npaths;
+ /*
+ * And optionally enter it as an additional ancestor.
+ */
+ if (multiple) {
+ if (s2->nas >= s2->assize) {
+ s2->assize = s2->nas * 3 / 2 + 4;
+ s2->as = sresize(s2->as, s2->assize, struct ancestor);
+ }
+ s2->as[s2->nas].prev = prev;
+ s2->as[s2->nas].pa = pa;
+ s2->as[s2->nas].po = po;
+ s2->as[s2->nas].pb = pb;
+ s2->as[s2->nas].pr = pr;
+ s2->nas++;
+ }
}
}
}
static struct sets *do_search(int ninputs, int *inputs,
- const struct rules *rules, int *target)
+ const struct rules *rules, int *target,
+ int debug, int multiple)
{
struct sets *s;
struct set *sn;
newnumber[1] = 1;
addtoset(sn, newnumber);
}
- addset(s, sn, NULL);
+ addset(s, sn, multiple, NULL, 0, 0, 0, 0);
/*
* Now perform the breadth-first search: keep looping over sets
struct set *sn;
int i, j, k, m;
+ if (debug) {
+ int i;
+ printf("processing set:");
+ for (i = 0; i < ss->nnumbers; i++) {
+ printf(" %d", ss->numbers[2*i]);
+ if (ss->numbers[2*i+1] != 1)
+ printf("/%d", ss->numbers[2*i+1]);
+ }
+ printf("\n");
+ }
+
/*
* Record all the valid output numbers in this state. We
* can always do this if there's only one number in the
!(ss->flags & SETFLAG_CONCAT))
continue; /* can't use this operation here */
for (i = 0; i < ss->nnumbers; i++) {
- for (j = 0; j < ss->nnumbers; j++) {
- int n[2];
-
- if (i == j)
- continue; /* can't combine a number with itself */
- if (i > j && ops[k]->commutes)
- continue; /* no need to do this both ways round */
+ int jlimit = (ops[k]->flags & OPFLAG_UNARY ? 1 : ss->nnumbers);
+ for (j = 0; j < jlimit; j++) {
+ int n[2], newnn = ss->nnumbers;
+ int pa, po, pb, pr;
+
+ if (!(ops[k]->flags & OPFLAG_UNARY)) {
+ if (i == j)
+ continue; /* can't combine a number with itself */
+ if (i > j && ops[k]->commutes)
+ continue; /* no need to do this both ways round */
+ newnn--;
+ }
if (!ops[k]->perform(ss->numbers+2*i, ss->numbers+2*j, n))
continue; /* operation failed */
- sn = newset(s, ss->nnumbers-1, ss->flags);
+ sn = newset(s, newnn, ss->flags);
if (!(ops[k]->flags & OPFLAG_KEEPS_CONCAT))
sn->flags &= ~SETFLAG_CONCAT;
for (m = 0; m < ss->nnumbers; m++) {
- if (m == i || m == j)
+ if (m == i || (!(ops[k]->flags & OPFLAG_UNARY) &&
+ m == j))
continue;
sn->numbers[2*sn->nnumbers] = ss->numbers[2*m];
sn->numbers[2*sn->nnumbers + 1] = ss->numbers[2*m + 1];
sn->nnumbers++;
}
- sn->pa = i;
- sn->pb = j;
- sn->po = k;
- sn->pr = addtoset(sn, n);
- addset(s, sn, ss);
+ pa = i;
+ if (ops[k]->flags & OPFLAG_UNARY)
+ pb = sn->nnumbers+10;
+ else
+ pb = j;
+ po = k;
+ pr = addtoset(sn, n);
+ addset(s, sn, multiple, ss, pa, po, pb, pr);
+ if (debug) {
+ int i;
+ if (ops[k]->flags & OPFLAG_UNARYPREFIX)
+ printf(" %s %d ->", ops[po]->dbgtext, pa);
+ else if (ops[k]->flags & OPFLAG_UNARY)
+ printf(" %d %s ->", pa, ops[po]->dbgtext);
+ else
+ printf(" %d %s %d ->", pa, ops[po]->dbgtext, pb);
+ for (i = 0; i < sn->nnumbers; i++) {
+ printf(" %d", sn->numbers[2*i]);
+ if (sn->numbers[2*i+1] != 1)
+ printf("/%d", sn->numbers[2*i+1]);
+ }
+ printf("\n");
+ }
}
}
}
}
/*
- * Construct a text formula for producing a given output.
+ * Print a text formula for producing a given output.
*/
-void mkstring_recurse(char **str, int *len,
- struct sets *s, struct set *ss, int index,
- int priority, int assoc, int child)
+void print_recurse(struct sets *s, struct set *ss, int pathindex, int index,
+ int priority, int assoc, int child);
+void print_recurse_inner(struct sets *s, struct set *ss,
+ struct ancestor *a, int pathindex, int index,
+ int priority, int assoc, int child)
{
- if (ss->prev && index != ss->pr) {
+ if (a->prev && index != a->pr) {
int pi;
/*
* recurse to there.
*/
pi = index;
- assert(pi != ss->pr);
- if (pi > ss->pr)
+ assert(pi != a->pr);
+ if (pi > a->pr)
pi--;
- if (pi >= min(ss->pa, ss->pb)) {
+ if (pi >= min(a->pa, a->pb)) {
pi++;
- if (pi >= max(ss->pa, ss->pb))
+ if (pi >= max(a->pa, a->pb))
pi++;
}
- mkstring_recurse(str, len, s, ss->prev, pi, priority, assoc, child);
- } else if (ss->prev && index == ss->pr &&
- s->ops[ss->po]->display) {
+ print_recurse(s, a->prev, pathindex, pi, priority, assoc, child);
+ } else if (a->prev && index == a->pr &&
+ s->ops[a->po]->display) {
/*
* This number was created by a displayed operator in the
* transition from this set to its predecessor. Hence we
/*
* Determine whether we need parentheses.
*/
- thispri = s->ops[ss->po]->priority;
- thisassoc = s->ops[ss->po]->assoc;
+ thispri = s->ops[a->po]->priority;
+ thisassoc = s->ops[a->po]->assoc;
parens = (thispri < priority ||
(thispri == priority && (assoc & child)));
- if (parens) {
- if (str)
- *(*str)++ = '(';
- if (len)
- (*len)++;
- }
- mkstring_recurse(str, len, s, ss->prev, ss->pa, thispri, thisassoc, 1);
- for (op = s->ops[ss->po]->text; *op; op++) {
- if (str)
- *(*str)++ = *op;
- if (len)
- (*len)++;
- }
- mkstring_recurse(str, len, s, ss->prev, ss->pb, thispri, thisassoc, 2);
- if (parens) {
- if (str)
- *(*str)++ = ')';
- if (len)
- (*len)++;
- }
+ if (parens)
+ putchar('(');
+
+ if (s->ops[a->po]->flags & OPFLAG_UNARYPREFIX)
+ for (op = s->ops[a->po]->text; *op; op++)
+ putchar(*op);
+
+ if (s->ops[a->po]->flags & OPFLAG_FN)
+ putchar('(');
+
+ print_recurse(s, a->prev, pathindex, a->pa, thispri, thisassoc, 1);
+
+ if (s->ops[a->po]->flags & OPFLAG_FN)
+ putchar(')');
+
+ if (!(s->ops[a->po]->flags & OPFLAG_UNARYPREFIX))
+ for (op = s->ops[a->po]->text; *op; op++)
+ putchar(*op);
+
+ if (!(s->ops[a->po]->flags & OPFLAG_UNARY))
+ print_recurse(s, a->prev, pathindex, a->pb, thispri, thisassoc, 2);
+
+ if (parens)
+ putchar(')');
} else {
/*
* This number is either an original, or something formed
* by a non-displayed operator (concatenation). Either way,
* we display it as is.
*/
- char buf[80], *p;
- int blen;
- blen = sprintf(buf, "%d", ss->numbers[2*index]);
+ printf("%d", ss->numbers[2*index]);
if (ss->numbers[2*index+1] != 1)
- blen += sprintf(buf+blen, "/%d", ss->numbers[2*index+1]);
- assert(blen < lenof(buf));
- for (p = buf; *p; p++) {
- if (str)
- *(*str)++ = *p;
- if (len)
- (*len)++;
+ printf("/%d", ss->numbers[2*index+1]);
+ }
+}
+void print_recurse(struct sets *s, struct set *ss, int pathindex, int index,
+ int priority, int assoc, int child)
+{
+ if (!ss->a.prev || pathindex < ss->a.prev->npaths) {
+ print_recurse_inner(s, ss, &ss->a, pathindex,
+ index, priority, assoc, child);
+ } else {
+ int i;
+ pathindex -= ss->a.prev->npaths;
+ for (i = 0; i < ss->nas; i++) {
+ if (pathindex < ss->as[i].prev->npaths) {
+ print_recurse_inner(s, ss, &ss->as[i], pathindex,
+ index, priority, assoc, child);
+ break;
+ }
+ pathindex -= ss->as[i].prev->npaths;
}
}
}
-char *mkstring(struct sets *s, struct output *o)
+void print(int pathindex, struct sets *s, struct output *o)
{
- int len;
- char *str, *p;
-
- len = 0;
- mkstring_recurse(NULL, &len, s, o->set, o->index, 0, 0, 0);
- str = snewn(len+1, char);
- p = str;
- mkstring_recurse(&p, NULL, s, o->set, o->index, 0, 0, 0);
- assert(p - str <= len);
- *p = '\0';
- return str;
+ print_recurse(s, o->set, pathindex, o->index, 0, 0, 0);
}
+/*
+ * gcc -g -O0 -o numgame numgame.c -I.. ../{malloc,tree234,nullfe}.c -lm
+ */
int main(int argc, char **argv)
{
int doing_opts = TRUE;
int numbers[10], nnumbers = 0;
int verbose = FALSE;
int pathcounts = FALSE;
+ int multiple = FALSE;
+ int debug_bfs = FALSE;
+ int got_range = FALSE, rangemin = 0, rangemax = 0;
struct output *o;
struct sets *s;
if (!strcmp(p, "-")) {
doing_opts = FALSE;
continue;
- } else while (*p) switch (c = *p++) {
+ } else if (*p == '-') {
+ p++;
+ if (!strcmp(p, "debug-bfs")) {
+ debug_bfs = TRUE;
+ } else {
+ fprintf(stderr, "%s: option '--%s' not recognised\n",
+ pname, p);
+ }
+ } else while (p && *p) switch (c = *p++) {
case 'C':
rules = &rules_countdown;
break;
case 'D':
rules = &rules_four4s;
break;
+ case 'A':
+ rules = &rules_anythinggoes;
+ break;
case 'v':
verbose = TRUE;
break;
case 'p':
pathcounts = TRUE;
break;
+ case 'm':
+ multiple = TRUE;
+ break;
case 't':
+ case 'r':
{
char *v;
if (*p) {
got_target = TRUE;
target = atoi(v);
break;
+ case 'r':
+ {
+ char *sep = strchr(v, '-');
+ got_range = TRUE;
+ if (sep) {
+ rangemin = atoi(v);
+ rangemax = atoi(sep+1);
+ } else {
+ rangemin = 0;
+ rangemax = atoi(v);
+ }
+ }
+ break;
}
}
break;
}
if (!rules) {
- fprintf(stderr, "%s: no rule set specified; use -C,-B,-D\n", pname);
+ fprintf(stderr, "%s: no rule set specified; use -C,-B,-D,-A\n", pname);
return 1;
}
return 1;
}
- s = do_search(nnumbers, numbers, rules, (got_target ? &target : NULL));
+ if (got_range) {
+ if (got_target) {
+ fprintf(stderr, "%s: only one of -t and -r may be specified\n", pname);
+ return 1;
+ }
+ if (rangemin >= rangemax) {
+ fprintf(stderr, "%s: range not sensible (%d - %d)\n", pname, rangemin, rangemax);
+ return 1;
+ }
+ }
+
+ s = do_search(nnumbers, numbers, rules, (got_target ? &target : NULL),
+ debug_bfs, multiple);
if (got_target) {
o = findrelpos234(s->outputtree, &target, outputfindcmp,
else if (limit == -1)
limit = start;
limit++;
+ } else if (got_range) {
+ if (!findrelpos234(s->outputtree, &rangemin, outputfindcmp,
+ REL234_GE, &start) ||
+ !findrelpos234(s->outputtree, &rangemax, outputfindcmp,
+ REL234_LE, &limit)) {
+ printf("No solutions available in specified range %d-%d\n", rangemin, rangemax);
+ return 1;
+ }
+ limit++;
} else {
start = 0;
limit = count234(s->outputtree);
}
for (i = start; i < limit; i++) {
+ char buf[256];
+
o = index234(s->outputtree, i);
- printf("%d", o->number);
+ sprintf(buf, "%d", o->number);
if (pathcounts)
- printf(" [%d]", o->npaths);
+ sprintf(buf + strlen(buf), " [%d]", o->npaths);
if (got_target || verbose) {
- char *p = mkstring(s, o);
- printf(" = %s", p);
- sfree(p);
- }
+ int j, npaths;
- printf("\n");
+ if (multiple)
+ npaths = o->npaths;
+ else
+ npaths = 1;
+
+ for (j = 0; j < npaths; j++) {
+ printf("%s = ", buf);
+ print(j, s, o);
+ putchar('\n');
+ }
+ } else {
+ printf("%s\n", buf);
+ }
}
free_sets(s);
return 0;
}
+
+/* vim: set shiftwidth=4 tabstop=8: */
~mdw / sgt / puzzles / blobdiff