Le-Compte-est-Bon/lceb.c

/* lceb - Countdown game solver.
 *
 *   $ make lceb
 *   $ ./lceb target n1 n2 [...n6]
 *
 * At least 2 "n" are mandatory, and no more than 6 are allowed.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <malloc.h>
#include <string.h>
#include <locale.h>
#include "lceb.h"

#define TREE_CATALAN    0
#define TREE_WEDDERBURN 1

static char *cmd;
static int treetype=TREE_CATALAN;
static int maxmillisecs=0;
extern int displaytimer, displayintermediate, displaytype, firstonly;
int displaysummary=1;

void print_results()
{
    struct timespec end;
    print_bests();
    set_timer(&end);
    if (displaysummary)
        printf("Total time elapsed: %.5f secs, nodes/leaves evaluated:%'d/%'d\n",
               get_timer(end), get_totnodes(), get_totleaves());
}

void usage()
{
    fprintf(stderr, "usage: %s [options] target n1 n2 [...n%d]\n", cmd, MAXINPUT);
}

void help()
{
    usage();
    fprintf(stderr, "Countdown game solver.\n");
    fprintf(stderr, "  -1: Show only one solution (immediate stop when exact solution found\n");
    fprintf(stderr, "  -c: Show solutions timer\n");
    fprintf(stderr, "  -d TYPE: Solutions display type. TYPE can be:\n");
    fprintf(stderr, "           r: RPN (default)\n");
    fprintf(stderr, "           p: Polish\n");
    fprintf(stderr, "           l: Lisp (binary operators)\n");
    fprintf(stderr, "           i: Infix (full parentheses)\n");
    fprintf(stderr, "           d: Suitable for dc(1) input\n");
    fprintf(stderr, "           t: Tree\n");
    fprintf(stderr, "  -i: Show intermediate solutions\n");
    fprintf(stderr, "  -s: Do not show summary (time, nodes evaluated)\n");
    fprintf(stderr, "  -t: Use less trees (Wedderburn–Etherington instead of Catalan)\n");
    fprintf(stderr, "  -T TIMER: Will stop after TIMER 1/10th seconds\n");
    fprintf(stderr, "  -h: This help\n");
}

int main(ac, av)
    int ac;
    char **av;
{
    unsigned target;
    STACK inputstack = {
        .name="initial",
        .size=MAXINPUT,
        .last=0,
        .next=NULL,
        .stack={0}
    };
    STACK *stack;
    int i, j, k, stacksize, val;
    int ncombs, nstacks, ntrees, nops;
    TREE *tree;
    char intarray[1024];
    char *comb;
    char *options="1thcisd:T:";
    int option;
#   ifdef DEBUG_MAINLOOP
    int eval;
#   endif

    cmd=*av;

    while ((option = getopt(ac, av, options)) != -1) {
        //printf("opt: %c\n", option);
        switch (option) {
            case '1':
                firstonly=1;
                break;
            case 'd':
                switch(*optarg) {
                    case 'r':
                        displaytype=0;
                        break;
                    case 'p':
                        displaytype=1;
                        break;
                    case 'l':
                        displaytype=3;
                        break;
                    case 'i':
                        displaytype=4;
                        break;
                    case 't':
                        displaytype=2;
                        break;
                    case 'd':
                        displaytype=5;
                        break;
                    default:
                        fprintf(stderr, "unknown display type: %c\n", *optarg);
                        fprintf(stderr, "Try '%s -h' for help\n", cmd);
                        exit(1);
                }
                break;
            case 'i':
                displayintermediate=1;
                break;
            case 'c':
                displaytimer=1;
                break;
            case 's':
                displaysummary=0;
                break;
            case 'T':
                maxmillisecs=atoi(optarg)*100;
                break;
            case 't':
                treetype=TREE_WEDDERBURN;
                break;
            case '?':
                fprintf(stderr, "unknown option: %c\n", optopt);
                fprintf(stderr, "%s: -%c: invalid option\n", cmd, optopt);
                exit(1);
            case 'h':
                help();
                exit(0);
        }
    }

    if (ac-optind < 3 || ac-optind > MAXINPUT+1) {
        usage();
        exit(1);
    }
    setlocale(LC_ALL, "");                        /* to use "%'d" in printf */
    start_timer();
    if (maxmillisecs)
        set_alarm(maxmillisecs);
    target=atoi(av[optind]);
    stacksize=ac-optind-1;
    nops=stacksize-1;

    for (i=optind+1; i<ac; ++i) {
        val=atoi(av[i]);
        push_stack(&inputstack, val);
    }
    gen_stacks(&inputstack);

    gen_combinations(nops);
    ncombs=n_combs();

    if (treetype==TREE_CATALAN) {
        gen_tree(intarray, nops, 0, 0, 0);
    } else {
        gen_tree(intarray, nops, 0, 0, 1);
        //gen_reduced_trees(nops);
    }
    set_target(target);
    set_intr();

    nstacks=n_stacks();
    ntrees=n_trees();
#   ifdef DEBUG_MAIN
    printf("stacks          :%'15d\n", nstacks);
    printf("ops combinations:%'15d\n", ncombs);
    printf("trees           :%'15d\n", ntrees);
    printf("max evaluations :%'15d\n", nstacks*ncombs*ntrees*stacksize);
#   endif
    for (i=0; i<ntrees; ++i) {
        tree=nth_tree(i);
        for (j=0; j<ncombs; ++j) {
            comb=nth_comb(j);
            for (k=0; k<nstacks; ++k) {
                int ncalcs=0;
                stack=nth_stack(k);
#               ifdef DEBUG_MAINLOOP
                eval=eval_node(tree->head, 0, stack->stack, comb, &ncalcs);
                if (eval > 0) {
                    printf("================= mainloop tree=%d, comb=%d, stack=%d\n", i, j, k);
                    printf("mainloop: ");print_tree(tree, 0);
                    printf("mainloop: ");print_comb(j);
                    printf("mainloop: "); print_stack(stack, 0);
                    printf("mainloop: eval=%d - calcs=%d\n", eval, ncalcs);
                }
#               else
                eval_node(tree->head, 0, stack->stack, comb, &ncalcs);
#               endif
#               ifdef DEBUG_MAINSLEEP
                sleep(1);
#               endif
            }
        }
        //opscomb=combination(ops, nops, i);
        //printf("OPS=%s\n", opscomb);
        //eval=eval_node(tree->head, 0, stack->stack, nth_comb(0));
        //printf("eval=%d\n", eval);

        //set_ops_stack(stack, opscomb);
        //print_stack(stack, 0);
        //res=eval_stack(stack);
        //printf("EVAL=%d\n", res);
    }
    //printf("\n");
    print_results();
    exit(0);
}