#
# Using four '4's, find
# equations using unary and binary operators
# which compute ever integer from 1 to 100
#

typedef struct {
    string	s;  /* string equation */
    rational	v;  /* equation value */
    int		p;  /* higher are preferred forms */
} v_t;

/* generator for primitive operands */
poly() argloop() { 
    int	i = 0;
    static poly[] a = {
	(v_t) { .s =  "4",    .v =   4, .p = 25 },
	(v_t) { .s = ".4",    .v =  .4, .p =  5 },
	(v_t) { .s = ".{4}",  .v =.{4}, .p =  1 },
	(v_t) { .s = "4!",    .v =  4!, .p = 25 },
	(v_t) { .s = "√4",    .v =  sqrt(4), .p = 25 },
	(v_t) { .s = "√.{4}", .v = sqrt(.{4}), .p =  1 },
	◊
    };
    return poly func() = a[i++ % dim(a)];
}

/* generator for binary operators */
poly () binloop(poly() l, poly() r) {
    int i = 0;
    poly la = ◊, ra = ◊;
    static (poly(poly, poly))[] a = { 
	poly func(x,y) = (v_t) { .s = "(" + x.s + " + " + y.s + ")", .v = x.v + y.v, .p = x.p + y.p },
	poly func(x,y) = (v_t) { .s = "(" + x.s + " - " + y.s + ")", .v = x.v - y.v, .p = x.p + y.p },
	poly func(x,y) = (v_t) { .s = "(" + x.s + " * " + y.s + ")", .v = x.v * y.v, .p = x.p + y.p },
	poly func(x,y) = (v_t) { .s = "(" + x.s + " / " + y.s + ")", .v = x.v / y.v, .p = x.p + y.p },
	poly func(x,y) {
	    if (y.v > 4)
		raise invalid_argument ("rhs of ** too large", 1, y.v);
	    return (v_t) { .s = "(" + x.s + " ^ " + y.s + ")", .v =x.v ** y.v, .p = x.p + y.p };
	}
    };
    return poly func() {
	for (;;)
	    try {
		if (i % dim(a) == 0) {
		    ra = r ();
		    if (ra == ◊ || la == ◊) {
			la = l ();
			if (la == ◊)
			    return ◊;
			if (ra == ◊)
			    ra = r ();
		    }
		}
		return a[i++ % dim(a)](la, ra);
	    }
	    catch divide_by_zero (real x, real y) {	continue; }
	    catch invalid_argument (string a, int i, poly p) { continue; }
	    catch invalid_binop_values (string a, poly l, poly r) { continue; }
    };
}

/* generator for associating operations */
poly() parenloop(poly() x, poly() y, poly() z) {
    int	i = 0;
    (poly())[]	a = { binloop (x, binloop(y,z)), binloop (binloop(x,y), z) };
    return poly func() {
	for (;;) {
	    poly v = a[i]();
	    if (v != ◊)
		return v;
	    if (++i == dim(a)) {i = 0; return ◊; }
	}
    };
}

/* find equations which compute all values */
void main () {
    int limit = 100;
    v_t[limit + 1] values = { { .s = "no solution", .v = 0, .p = 0 } ... };
    poly() f = parenloop (binloop(argloop(), argloop()),
			  argloop(), argloop());
    while (((poly value) = f()) != ◊) {
	if (is_int(value.v) && 1 <= value.v && value.v <= limit) {
	    if (values[value.v].p < value.p)
		values[value.v] = value;
	}
    }
    for (int i = 1; i <= limit; i++)
	printf ("%3d (score %3d) = %s\n", i, values[i].p, values[i].s);
}

main();