152 lines
3.9 KiB
C
152 lines
3.9 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <malloc.h>
|
|
#include <values.h>
|
|
#include <signal.h>
|
|
#include "lceb.h"
|
|
|
|
static int target=0;
|
|
static int bestdiff=MAXINT;
|
|
static int bestops=MAXINT;
|
|
|
|
static BEST bests[1024*10]; /* TODO: should be dynamic */
|
|
static int nbests=0;
|
|
extern int displaytimer, firstonly;
|
|
int displayintermediate=0;
|
|
int displaytype=0;
|
|
|
|
#define DIFF(a, b) ((a)>(b)?(a)-(b):(b)-(a))
|
|
|
|
void set_target(n)
|
|
int n;
|
|
{
|
|
target=n;
|
|
# ifdef DEBUG
|
|
printf("target assigned (%d).\n", target);
|
|
# endif
|
|
}
|
|
|
|
int check_best(res, nops, node, values, ops)
|
|
int res;
|
|
int nops;
|
|
NODE *node;
|
|
int *values;
|
|
char *ops;
|
|
{
|
|
int diff, found=0, i=0;
|
|
|
|
diff=DIFF(target, res);
|
|
# ifdef DEBUG_BEST1
|
|
printf("check_best: res=%d diff=%d nops=%d\n", res, diff, nops);
|
|
# endif
|
|
if (diff < bestdiff || (diff == bestdiff && nops < bestops)) {
|
|
//best=res;
|
|
// clear old bests
|
|
for (i=0; i<nbests; ++i) {
|
|
found=free_node(bests[i].root);
|
|
# ifdef DEBUG_TREE
|
|
printf("check_best: freed %d nodes\n", found);
|
|
# endif
|
|
}
|
|
|
|
bestdiff=diff;
|
|
bestops=nops;
|
|
nbests=0;
|
|
found=1;
|
|
//return 1;
|
|
} else if (diff == bestdiff && nops == bestops) {
|
|
// if (nbests) {
|
|
found=2;
|
|
for (i=0; i<nbests; ++i) {
|
|
if (compare_nodes(node, bests[i].root, 0)) {
|
|
found=0;
|
|
break;
|
|
}
|
|
}
|
|
# ifdef DEBUG_BEST
|
|
if (found==2) {
|
|
printf("new diff solution (%d): res=%d diff=%d nops=%d\n",
|
|
nbests+1, res, diff, nops);
|
|
print_node(node, TREE_TOP, 0, 0);
|
|
} else {
|
|
printf("skipping duplicate solution (%d): res=%d diff=%d nops=%d\n",
|
|
nbests+1, res, diff, nops);
|
|
}
|
|
# endif
|
|
}
|
|
if (found) {
|
|
set_timer(&(bests[nbests].timer));
|
|
bests[nbests].res=res;
|
|
bests[nbests].diff=diff;
|
|
bests[nbests].nops=nops;
|
|
bests[nbests].oper=ops;
|
|
bests[nbests].root=dup_node(node);
|
|
bests[nbests].values=values;
|
|
if (displayintermediate) {
|
|
if (displaytimer) {
|
|
printf("%.5f secs: ", get_timer(bests[nbests].timer));
|
|
}
|
|
printf("diff=%d nops=%d %d=", diff, nops, res);
|
|
print_node(node, TREE_TOP, 0, displaytype);
|
|
putchar('\n');
|
|
}
|
|
nbests++;
|
|
return diff;
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
void print_best(node, values, pops, depth)
|
|
NODE *node;
|
|
int *values;
|
|
char *pops;
|
|
int depth;
|
|
{
|
|
static int *vals;
|
|
static char *ops;
|
|
|
|
if (depth == 0) {
|
|
vals=values;
|
|
ops=pops;
|
|
}
|
|
if (node->type == TREE_LEAF) {
|
|
printf("%d ", *vals);
|
|
vals++;
|
|
} else {
|
|
print_best(node->left, vals, ops, depth+1);
|
|
print_best(node->right, vals, ops, depth+1);
|
|
printf(" %c ", *ops);
|
|
ops++;
|
|
}
|
|
if (depth == 0)
|
|
putchar('\n');
|
|
}
|
|
|
|
void print_bests()
|
|
{
|
|
int i=0, j=firstonly? 1: nbests;
|
|
if (bestdiff==0) {
|
|
printf("Le compte est bon: %d solutions with %d ops ", nbests, bestops);
|
|
} else {
|
|
printf("Found %d results with difference %d and %d ops ", nbests, bestdiff, bestops);
|
|
}
|
|
//if (displaytimer)
|
|
printf("(1st after %.5f secs).", get_timer(bests[i].timer));
|
|
putchar('\n');
|
|
for (i=0; i<j; ++i) {
|
|
//print_best(bests[i].root, bests[i].values, bests[i].oper, 0);
|
|
//printf("%5d =", bests[i].res);
|
|
if (displaytimer)
|
|
printf("%.5f secs: ", get_timer(bests[i].timer));
|
|
print_node(bests[i].root, TREE_TOP, 0, displaytype);
|
|
putchar('\n');
|
|
//printf("%3d: %d = ", i, bests[i].res);
|
|
//print_node(bests[i].root, TREE_TOP, 0, 1);
|
|
//putchar('\n');
|
|
//printf("%3d: %d = ", i, bests[i].res);
|
|
//print_node(bests[i].root, TREE_TOP, 0, 4);
|
|
//putchar('\n');
|
|
}
|
|
}
|