zakarya/puzzles
1
0
Fork 0
mirror of git://git.tartarus.org/simon/puzzles.git synced 2025-04-20 07:31:30 -07:00
Code Issues Packages Projects Releases Wiki Activity
Files
puzzles/unfinished/numgame.c
Simon Tatham 3b9cafa09f Fall back to <math.h> if <tgmath.h> doesn't work. 
This fixes a build failure introduced by commit 2e48ce132e011e8
yesterday.

When I saw that commit I expected the most likely problem would be in
the NestedVM build, which is currently the thing with the most most
out-of-date C implementation. And indeed the NestedVM toolchain
doesn't have <tgmath.h> - but much more surprisingly, our _Windows_
builds failed too, with a compile error inside <tgmath.h> itself!

I haven't looked closely into the problem yet. Our Windows builds are
done with clang, which comes with its own <tgmath.h> superseding the
standard Windows one. So you'd _hope_ that clang could make sense of
its own header! But perhaps the problem is that this is an unusual
compile mode and hasn't been tested.

My fix is to simply add a cmake check for <tgmath.h> - which doesn't
just check the file's existence, it actually tries compiling a file
that #includes it, so it will detect 'file exists but is mysteriously
broken' just as easily as 'not there at all'. So this makes the builds
start working again, precisely on Ben's theory of opportunistically
using <tgmath.h> where possible and falling back to <math.h>
otherwise.

It looks ugly, though! I'm half tempted to make a new header file
whose job is to include a standard set of system headers, just so that
that nasty #ifdef doesn't have to sit at the top of almost all the
source files. But for the moment this at least gets the build working
again.
2023-04-06 07:08:04 +01:00

1295 lines
34 KiB
C
Raw Permalink Blame History

/*
* This program implements a breadth-first search which
* exhaustively solves the Countdown numbers game, and related
* games with slightly different rule sets such as `Flippo'.
*
* Currently it is simply a standalone command-line utility to
* which you provide a set of numbers and it tells you everything
* it can make together with how many different ways it can be
* made. I would like ultimately to turn it into the generator for
* a Puzzles puzzle, but I haven't even started on writing a
* Puzzles user interface yet.
*/
/*
* TODO:
*
* - start thinking about difficulty ratings
* + anything involving associative operations will be flagged
* as many-paths because of the associative options (e.g.
* 2*3*4 can be (2*3)*4 or 2*(3*4), or indeed (2*4)*3). This
* is probably a _good_ thing, since those are unusually
* easy.
* + tree-structured calculations ((a*b)/(c+d)) have multiple
* paths because the independent branches of the tree can be
* evaluated in either order, whereas straight-line
* calculations with no branches will be considered easier.
* Can we do anything about this? It's certainly not clear to
* me that tree-structure calculations are _easier_, although
* I'm also not convinced they're harder.
* + I think for a realistic difficulty assessment we must also
* consider the `obviousness' of the arithmetic operations in
* some heuristic sense, and also (in Countdown) how many
* numbers ended up being used.
* - actually try some generations
* - at this point we're probably ready to start on the Puzzles
* integration.
*/
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
#ifdef NO_TGMATH_H
# include <math.h>
#else
# include <tgmath.h>
#endif
#include "puzzles.h"
#include "tree234.h"
/*
* To search for numbers we can make, we employ a breadth-first
* search across the space of sets of input numbers. That is, for
* example, we start with the set (3,6,25,50,75,100); we apply
* moves which involve combining two numbers (e.g. adding the 50
* and the 75 takes us to the set (3,6,25,100,125); and then we see
* if we ever end up with a set containing (say) 952.
*
* If the rules are changed so that all the numbers must be used,
* this is easy to adjust to: we simply see if we end up with a set
* containing _only_ (say) 952.
*
* Obviously, we can vary the rules about permitted arithmetic
* operations simply by altering the set of valid moves in the bfs.
* However, there's one common rule in this sort of puzzle which
* takes a little more thought, and that's _concatenation_. For
* example, if you are given (say) four 4s and required to make 10,
* you are permitted to combine two of the 4s into a 44 to begin
* with, making (44-4)/4 = 10. However, you are generally not
* allowed to concatenate two numbers that _weren't_ both in the
* original input set (you couldn't multiply two 4s to get 16 and
* then concatenate a 4 on to it to make 164), so concatenation is
* not an operation which is valid in all situations.
*
* We could enforce this restriction by storing a flag alongside
* each number indicating whether or not it's an original number;
* the rules being that concatenation of two numbers is only valid
* if they both have the original flag, and that its output _also_
* has the original flag (so that you can concatenate three 4s into
* a 444), but that applying any other arithmetic operation clears
* the original flag on the output. However, we can get marginally
* simpler than that by observing that since concatenation has to
* happen to a number before any other operation, we can simply
* place all the concatenations at the start of the search. In
* other words, we have a global flag on an entire number _set_
* which indicates whether we are still permitted to perform
* concatenations; if so, we can concatenate any of the numbers in
* that set. Performing any other operation clears the flag.
*/
#define SETFLAG_CONCAT 1 /* we can do concatenation */
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 */
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 {
int number;
struct set *set;
int index; /* which number in the set is it? */
int npaths; /* number of ways to reach this */
};
#define SETLISTLEN 1024
#define NUMBERLISTLEN 32768
#define OUTPUTLISTLEN 1024
struct operation;
struct sets {
struct set **setlists;
int nsets, nsetlists, setlistsize;
tree234 *settree;
int **numberlists;
int nnumbers, nnumberlists, numberlistsize;
struct output **outputlists;
int noutputs, noutputlists, outputlistsize;
tree234 *outputtree;
const struct operation *const *ops;
};
#define OPFLAG_NEEDS_CONCAT 1
#define OPFLAG_KEEPS_CONCAT 2
#define OPFLAG_UNARY 4
#define OPFLAG_UNARYPREFIX 8
#define OPFLAG_FN 16
struct operation {
/*
* Most operations should be shown in the output working, but
* concatenation should not; we just take the result of the
* concatenation and assume that it's obvious how it was
* derived.
*/
int display;
/*
* Text display of the operator, in expressions and for
* debugging respectively.
*/
const char *text, *dbgtext;
/*
* Flags dictating when the operator can be applied.
*/
int flags;
/*
* Priority of the operator (for avoiding unnecessary
* parentheses when formatting it into a string).
*/
int priority;
/*
* Associativity of the operator. Bit 0 means we need parens
* when the left operand of one of these operators is another
* instance of it, e.g. (2^3)^4. Bit 1 means we need parens
* when the right operand is another instance of the same
* operator, e.g. 2-(3-4). Thus:
*
* - this field is 0 for a fully associative operator, since
* we never need parens.
* - it's 1 for a right-associative operator.
* - it's 2 for a left-associative operator.
* - it's 3 for a _non_-associative operator (which always
* uses parens just to be sure).
*/
int assoc;
/*
* Whether the operator is commutative. Saves time in the
* search if we don't have to try it both ways round.
*/
int commutes;
/*
* Function which implements the operator. Returns true on
* success, false on failure. Takes two rationals and writes
* out a third.
*/
int (*perform)(int *a, int *b, int *output);
};
struct rules {
const struct operation *const *ops;
int use_all;
};
#define MUL(r, a, b) do { \
(r) = (a) * (b); \
if ((b) && (a) && (r) / (b) != (a)) return false; \
} while (0)
#define ADD(r, a, b) do { \
(r) = (a) + (b); \
if ((a) > 0 && (b) > 0 && (r) < 0) return false; \
if ((a) < 0 && (b) < 0 && (r) > 0) return false; \
} while (0)
#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); \
} while (0)
static int gcd(int x, int y)
{
while (x != 0 && y != 0) {
int t = x;
x = y;
y = t % y;
}
return abs(x + y); /* i.e. whichever one isn't zero */
}
static int perform_add(int *a, int *b, int *output)
{
int at, bt, tn, bn;
/*
* a0/a1 + b0/b1 = (a0*b1 + b0*a1) / (a1*b1)
*/
MUL(at, a[0], b[1]);
MUL(bt, b[0], a[1]);
ADD(tn, at, bt);
MUL(bn, a[1], b[1]);
OUT(output, tn, bn);
return true;
}
static int perform_sub(int *a, int *b, int *output)
{
int at, bt, tn, bn;
/*
* a0/a1 - b0/b1 = (a0*b1 - b0*a1) / (a1*b1)
*/
MUL(at, a[0], b[1]);
MUL(bt, b[0], a[1]);
ADD(tn, at, -bt);
MUL(bn, a[1], b[1]);
OUT(output, tn, bn);
return true;
}
static int perform_mul(int *a, int *b, int *output)
{
int tn, bn;
/*
* a0/a1 * b0/b1 = (a0*b0) / (a1*b1)
*/
MUL(tn, a[0], b[0]);
MUL(bn, a[1], b[1]);
OUT(output, tn, bn);
return true;
}
static int perform_div(int *a, int *b, int *output)
{
int tn, bn;
/*
* Division by zero is outlawed.
*/
if (b[0] == 0)
return false;
/*
* a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
*/
MUL(tn, a[0], b[1]);
MUL(bn, a[1], b[0]);
OUT(output, tn, bn);
return true;
}
static int perform_exact_div(int *a, int *b, int *output)
{
int tn, bn;
/*
* Division by zero is outlawed.
*/
if (b[0] == 0)
return false;
/*
* a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
*/
MUL(tn, a[0], b[1]);
MUL(bn, a[1], b[0]);
OUT(output, tn, bn);
/*
* Exact division means we require the result to be an integer.
*/
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 a non-negative
* integer.
*/
if (a[1] != 1 || b[1] != 1 || a[0] < 0 || b[0] < 0)
return false;
/*
* For concatenation, we can safely assume leading zeroes
* aren't an issue. It isn't clear whether they `should' be
* allowed, but it turns out not to matter: concatenating a
* leading zero on to a number in order to harmlessly get rid
* of the zero is never necessary because unwanted zeroes can
* be disposed of by adding them to something instead. So we
* disallow them always.
*
* The only other possibility is that you might want to
* concatenate a leading zero on to something and then
* concatenate another non-zero digit on to _that_ (to make,
* for example, 106); but that's also unnecessary, because you
* can make 106 just as easily by concatenating the 0 on to the
* _end_ of the 1 first.
*/
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;
/*
* 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.
*
* - 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)) {
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);
}
static const struct operation op_add = {
true, "+", "+", 0, 10, 0, true, perform_add
};
static const struct operation op_sub = {
true, "-", "-", 0, 10, 2, false, perform_sub
};
static const struct operation op_mul = {
true, "*", "*", 0, 20, 0, true, perform_mul
};
static const struct operation op_div = {
true, "/", "/", 0, 20, 2, false, perform_div
};
static const struct operation op_xdiv = {
true, "/", "/", 0, 20, 2, false, perform_exact_div
};
static const struct operation op_concat = {
false, "", "concat", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT,
1000, 0, false, perform_concat
};
static const struct operation op_exp = {
true, "^", "^", 0, 30, 1, false, perform_exp
};
static const struct operation op_factorial = {
true, "!", "!", OPFLAG_UNARY, 40, 0, false, perform_factorial
};
static const struct operation op_decimal = {
true, ".", ".", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT, 50, 0, false, perform_decimal
};
static const struct operation op_recur = {
true, "...", "recur", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 2, false, perform_recur
};
static const struct operation op_root = {
true, "v~", "root", 0, 30, 1, false, perform_root
};
static const struct operation op_perc = {
true, "%", "%", OPFLAG_UNARY | OPFLAG_NEEDS_CONCAT, 45, 1, false, perform_perc
};
static const struct operation op_gamma = {
true, "gamma", "gamma", OPFLAG_UNARY | OPFLAG_UNARYPREFIX | OPFLAG_FN, 1, 3, false, perform_gamma
};
static const struct operation op_sqrt = {
true, "v~", "sqrt", OPFLAG_UNARY | OPFLAG_UNARYPREFIX, 30, 1, false, perform_sqrt
};
/*
* In Countdown, divisions resulting in fractions are disallowed.
* http://www.askoxford.com/wordgames/countdown/rules/
*/
static const struct operation *const ops_countdown[] = {
&op_add, &op_mul, &op_sub, &op_xdiv, NULL
};
static const struct rules rules_countdown = {
ops_countdown, false
};
/*
* A slightly different rule set which handles the reasonably well
* known puzzle of making 24 using two 3s and two 8s. For this we
* need rational rather than integer division.
*/
static const struct operation *const ops_3388[] = {
&op_add, &op_mul, &op_sub, &op_div, NULL
};
static const struct rules rules_3388 = {
ops_3388, true
};
/*
* A still more permissive rule set usable for the four-4s problem
* and similar things. Permits concatenation.
*/
static const struct operation *const ops_four4s[] = {
&op_add, &op_mul, &op_sub, &op_div, &op_concat, NULL
};
static const struct rules rules_four4s = {
ops_four4s, true
};
/*
* The most permissive ruleset I can think of. Permits
* exponentiation, and also silly unary operators like factorials.
*/
static const 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
};
static const 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] )
static int addtoset(struct set *set, int newnumber[2])
{
int i, j;
/* Find where we want to insert the new number */
for (i = 0; i < set->nnumbers &&
ratcmp(set->numbers+2*i, <, newnumber); i++);
/* Move everything else up */
for (j = set->nnumbers; j > i; j--) {
set->numbers[2*j] = set->numbers[2*j-2];
set->numbers[2*j+1] = set->numbers[2*j-1];
}
/* Insert the new number */
set->numbers[2*i] = newnumber[0];
set->numbers[2*i+1] = newnumber[1];
set->nnumbers++;
return i;
}
#define ensure(array, size, newlen, type) do { \
if ((newlen) > (size)) { \
(size) = (newlen) + 512; \
(array) = sresize((array), (size), type); \
} \
} while (0)
static int setcmp(void *av, void *bv)
{
struct set *a = (struct set *)av;
struct set *b = (struct set *)bv;
int i;
if (a->nnumbers < b->nnumbers)
return -1;
else if (a->nnumbers > b->nnumbers)
return +1;
if (a->flags < b->flags)
return -1;
else if (a->flags > b->flags)
return +1;
for (i = 0; i < a->nnumbers; i++) {
if (ratcmp(a->numbers+2*i, <, b->numbers+2*i))
return -1;
else if (ratcmp(a->numbers+2*i, >, b->numbers+2*i))
return +1;
}
return 0;
}
static int outputcmp(void *av, void *bv)
{
struct output *a = (struct output *)av;
struct output *b = (struct output *)bv;
if (a->number < b->number)
return -1;
else if (a->number > b->number)
return +1;
return 0;
}
static int outputfindcmp(void *av, void *bv)
{
int *a = (int *)av;
struct output *b = (struct output *)bv;
if (*a < b->number)
return -1;
else if (*a > b->number)
return +1;
return 0;
}
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);
assert(set == s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN);
s2 = add234(s->settree, set);
if (s2 == set) {
/*
* New set added to the tree.
*/
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.
*/
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 set *newset(struct sets *s, int nnumbers, int flags)
{
struct set *sn;
ensure(s->setlists, s->setlistsize, s->nsets/SETLISTLEN+1, struct set *);
while (s->nsetlists <= s->nsets / SETLISTLEN)
s->setlists[s->nsetlists++] = snewn(SETLISTLEN, struct set);
sn = s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN;
if (s->nnumbers + nnumbers * 2 > s->nnumberlists * NUMBERLISTLEN)
s->nnumbers = s->nnumberlists * NUMBERLISTLEN;
ensure(s->numberlists, s->numberlistsize,
s->nnumbers/NUMBERLISTLEN+1, int *);
while (s->nnumberlists <= s->nnumbers / NUMBERLISTLEN)
s->numberlists[s->nnumberlists++] = snewn(NUMBERLISTLEN, int);
sn->numbers = s->numberlists[s->nnumbers / NUMBERLISTLEN] +
s->nnumbers % NUMBERLISTLEN;
/*
* Start the set off empty.
*/
sn->nnumbers = 0;
sn->flags = flags;
return sn;
}
static int addoutput(struct sets *s, struct set *ss, int index, int *n)
{
struct output *o, *o2;
/*
* Target numbers are always integers.
*/
if (ss->numbers[2*index+1] != 1)
return false;
ensure(s->outputlists, s->outputlistsize, s->noutputs/OUTPUTLISTLEN+1,
struct output *);
while (s->noutputlists <= s->noutputs / OUTPUTLISTLEN)
s->outputlists[s->noutputlists++] = snewn(OUTPUTLISTLEN,
struct output);
o = s->outputlists[s->noutputs / OUTPUTLISTLEN] +
s->noutputs % OUTPUTLISTLEN;
o->number = ss->numbers[2*index];
o->set = ss;
o->index = index;
o->npaths = ss->npaths;
o2 = add234(s->outputtree, o);
if (o2 != o) {
o2->npaths += o->npaths;
} else {
s->noutputs++;
}
*n = o->number;
return true;
}
static struct sets *do_search(int ninputs, int *inputs,
const struct rules *rules, int *target,
int debug, int multiple)
{
struct sets *s;
struct set *sn;
int qpos, i;
const struct operation *const *ops = rules->ops;
s = snew(struct sets);
s->setlists = NULL;
s->nsets = s->nsetlists = s->setlistsize = 0;
s->numberlists = NULL;
s->nnumbers = s->nnumberlists = s->numberlistsize = 0;
s->outputlists = NULL;
s->noutputs = s->noutputlists = s->outputlistsize = 0;
s->settree = newtree234(setcmp);
s->outputtree = newtree234(outputcmp);
s->ops = ops;
/*
* Start with the input set.
*/
sn = newset(s, ninputs, SETFLAG_CONCAT);
for (i = 0; i < ninputs; i++) {
int newnumber[2];
newnumber[0] = inputs[i];
newnumber[1] = 1;
addtoset(sn, newnumber);
}
addset(s, sn, multiple, NULL, 0, 0, 0, 0);
/*
* Now perform the breadth-first search: keep looping over sets
* until we run out of steam.
*/
qpos = 0;
while (qpos < s->nsets) {
struct set *ss = s->setlists[qpos / SETLISTLEN] + qpos % SETLISTLEN;
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
* state; otherwise, we can only do it if we aren't
* required to use all the numbers in coming to our answer.
*/
if (ss->nnumbers == 1 || !rules->use_all) {
for (i = 0; i < ss->nnumbers; i++) {
int n;
if (addoutput(s, ss, i, &n) && target && n == *target)
return s;
}
}
/*
* Try every possible operation from this state.
*/
for (k = 0; ops[k] && ops[k]->perform; k++) {
if ((ops[k]->flags & OPFLAG_NEEDS_CONCAT) &&
!(ss->flags & SETFLAG_CONCAT))
continue; /* can't use this operation here */
for (i = 0; i < ss->nnumbers; i++) {
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, newnn, ss->flags);
if (!(ops[k]->flags & OPFLAG_KEEPS_CONCAT))
sn->flags &= ~SETFLAG_CONCAT;
for (m = 0; m < ss->nnumbers; m++) {
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++;
}
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");
}
}
}
}
qpos++;
}
return s;
}
static void free_sets(struct sets *s)
{
int i;
freetree234(s->settree);
freetree234(s->outputtree);
for (i = 0; i < s->nsetlists; i++)
sfree(s->setlists[i]);
sfree(s->setlists);
for (i = 0; i < s->nnumberlists; i++)
sfree(s->numberlists[i]);
sfree(s->numberlists);
for (i = 0; i < s->noutputlists; i++)
sfree(s->outputlists[i]);
sfree(s->outputlists);
sfree(s);
}
/*
* Print a text formula for producing a given output.
*/
static void print_recurse(struct sets *s, struct set *ss, int pathindex,
int index, int priority, int assoc, int child);
static void print_recurse_inner(struct sets *s, struct set *ss,
struct ancestor *a, int pathindex, int index,
int priority, int assoc, int child)
{
if (a->prev && index != a->pr) {
int pi;
/*
* This number was passed straight down from this set's
* predecessor. Find its index in the previous set and
* recurse to there.
*/
pi = index;
assert(pi != a->pr);
if (pi > a->pr)
pi--;
if (pi >= min(a->pa, a->pb)) {
pi++;
if (pi >= max(a->pa, a->pb))
pi++;
}
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
* write an open paren, then recurse into the first
* operand, then write the operator, then the second
* operand, and finally close the paren.
*/
const char *op;
int parens, thispri, thisassoc;
/*
* Determine whether we need parentheses.
*/
thispri = s->ops[a->po]->priority;
thisassoc = s->ops[a->po]->assoc;
parens = (thispri < priority ||
(thispri == priority && (assoc & child)));
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.
*/
printf("%d", ss->numbers[2*index]);
if (ss->numbers[2*index+1] != 1)
printf("/%d", ss->numbers[2*index+1]);
}
}
static 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;
}
}
}
static void print(int pathindex, struct sets *s, struct output *o)
{
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;
const struct rules *rules = NULL;
char *pname = argv[0];
int got_target = false, target = 0;
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;
int i, start, limit;
while (--argc) {
char *p = *++argv;
int c;
if (doing_opts && *p == '-') {
p++;
if (!strcmp(p, "-")) {
doing_opts = false;
continue;
} 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 'B':
rules = &rules_3388;
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) {
v = p;
p = NULL;
} else if (--argc) {
v = *++argv;
} else {
fprintf(stderr, "%s: option '-%c' expects an"
" argument\n", pname, c);
return 1;
}
switch (c) {
case 't':
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;
default:
fprintf(stderr, "%s: option '-%c' not"
" recognised\n", pname, c);
return 1;
}
} else {
if (nnumbers >= lenof(numbers)) {
fprintf(stderr, "%s: internal limit of %d numbers exceeded\n",
pname, (int)lenof(numbers));
return 1;
} else {
numbers[nnumbers++] = atoi(p);
}
}
}
if (!rules) {
fprintf(stderr, "%s: no rule set specified; use -C,-B,-D,-A\n", pname);
return 1;
}
if (!nnumbers) {
fprintf(stderr, "%s: no input numbers specified\n", pname);
return 1;
}
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,
REL234_LE, &start);
if (!o)
start = -1;
o = findrelpos234(s->outputtree, &target, outputfindcmp,
REL234_GE, &limit);
if (!o)
limit = -1;
assert(start != -1 || limit != -1);
if (start == -1)
start = limit;
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);
sprintf(buf, "%d", o->number);
if (pathcounts)
sprintf(buf + strlen(buf), " [%d]", o->npaths);
if (got_target || verbose) {
int j, npaths;
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: */
Reference in New Issue View Git Blame Copy Permalink