- Published on
猜数字最佳解法
- Authors
- Name
- lzray
一份“猜数字”求解器（Tanaka）
TL;DR
- 这个程序解决的是 4 位 Bulls & Cows 的最优/近优决策树搜索问题：每次猜一个 4 位不重复的“数字组合”，根据反馈）切分候选集。
- 代码用位运算把一个 4 位数打包成
Q2（高 16 位是 10 个数字是否出现的 bitmask，低 16 位是 4 个 nibble 表示的四位数字），配合两张小表ht[]/bt[]，可以 O(1) 地求某次猜测与某个候选之间的 H/B 反馈类别。 - 搜索部分通过：预估下界
imn()、分支估价cnt()、小顶堆优先扩展、对称性消解（cp()/sp()）与节点池（QB池化），实现强力剪枝。
问题设定与两种模式
编译开关：
#ifdef MASTER时，TS = 1296：典型 Mastermind。- 否则
TS = 5040：10 个数字中选 4 个、顺序有关且不重复（10A4 = 5040）。 代码走 数字模式（5040）。
反馈类别（共
SLS = 14种），在数组cs[]里按索引给出字符串：0:"4H", 1:"2H2B", 2:"1H3B", 3:"0H4B", 4:"3H0B", 5:"2H1B", 6:"2H0B", 7:"1H2B", 8:"0H3B", 9:"0H0B", 10:"1H0B", 11:"1H1B", 12:"0H2B", 13:"0H1B"
核心数据表示（位运算友好）
Q/Q2：低 16 位：四个 nibble（每 4 bit）依次放 4 位数字（从高到低 nibble 对应千百十个位置）。
高 16 位：10-bit 的“用过数字”掩码（第 d 位为 1 意味着数字 d 出现过）。
组合构造样例在
initnt2()：nt2[index] = (((1<<i)|(1<<jj)|(1<<kk)|(1<<ll))<<16) | (i<<12)|(jj<<8)|(kk<<4)|ll;
宏
COL(q,i)：抽出第 i 位（0..3）的 nibble。小表：
ht[0x10000]：给定x = (q1 ^ q2) & 0xffff，统计其中 四个 nibble 为 0 的个数。bt[1024]：给定 10-bit 掩码，返回其中 1 的个数（用于算“共有数字”）。
反馈映射
hb(q1,q2)：hit = ht[(q1 ^ q2) & 0xffff]; blow = bt[(q1 & q2) >> 16]; // 注意是共有数字（含 hit） return cv2[hit][blow]; // 变成 0..13 的类别索引
候选全集与首/二步策略
TS个候选全部装在nt2[]中（initnt2()生成所有排列）。- 程序默认第一步固定猜
fd = 0xf0123（编码即“0123”）。 - 第二步有一个经验/策略表
sd[SIZEOF_SECOND]（19 个备选），cmp2()专门在第二层使用它做更快的分支搜索。
估价与剪枝
1）理论下界估计：imn() + limit_table
limit_table[11][3]是手工给的阈值表，结合“当前分支剩余候选数num”与“该分支内累计出现过多少不同数字n_exist（0..10）”，估计在 2/3/4/5 层能的规模，形成一个下界（lower bound）。imn(n_exist, num)返回该分支最少还需“评分项”的下界（用于 A* 式剪枝）。
2）对一个猜测的分支估价：cnt()
给定当前候选数组
ptr（长度len）与“准备试探的猜测src”，遍历计算 14 个反馈类别下的规模：dest[i]：类别i下的子树大小。exist[i]：该子树里所有候选数字位掩码的 OR，随后bt[exist[i]>>16]给出n_exist。- 每个非空类别
i的“下界”是mi[n_exist][sel_len]，这里mi由上面的imn()预先填好。
汇总并加上一些细节（比如
dest[0]表示 4H 的“命中立即结束”），得到此猜测的估价值。如果所有候选都被分到一个类别（nonzeros<=1），返回INFINITY，这种猜法直接丢弃。
3）分支扩展顺序：mkhp()/dnhp() 小顶堆
- 把本层所有可用猜法的估价值放进小顶堆，总是**先扩展“估价最小（最有希望）”**的猜法，能有效减少深入无谓分支。
4）对称性：cp() / sp() / cu()
- 核心思想：给定一套“数字→新编号”的置换和（或）“位置”置换，如果能把一个猜法映射到更小的“字典序”，那我们只保留最小代表，丢掉其它对称等价的猜法。
cp()：检查某个q在当前允许的置换族下，是否已经是最小代表（否则不必考虑）。sp()：根据当前选择，收紧可用置换（相当于把“等价类”继续细化），并把p4/p10两张置换表推进到下一层。cu()：用于约束“未使用数字”的相对顺序，进一步减少重复。
5）真正的搜索：cmp() / cmp2()
输入：当前候选
ptr/len，层数level，置换信息、已用数字掩码、当前“最好上界minval”等。流程：
计算这一层所有可用猜法（受对称性约束），对每个猜法先调用
cnt()得到估价，装堆。按堆序从优到劣依次试：
- 基于
check[level-1][sort_i]的 14 把分布，把候选分发到子数组to_child[...]。 - 只对非空子类递归
cmp()，把每个子类的最坏值取max。 - 若当前
tmpval >= minval就剪枝。
- 基于
返回该猜法的“最坏代价”，同时在
QB上建出决策树（见下）。
cmp2()是为“第二步”定制的快速版：把全体猜法替换为sd[]那 19 个候选，附带一个second_check缓存。
决策树与内存管理
结构体
QB是一个 14（=SLS）分叉的节点：typedef struct qbox{ Q2 query; // 这一层出的“问句”（猜法） struct qbox*ptr[SLS]; // 14 个反馈类别下的子指针 } QB;采用对象池（
qbs[QS]+aqb()/fqb()）做内存管理，避免频繁malloc/free。dqb()会把整棵树漂亮地打印出来（使用cs[]的标签作为分支名），这是你程序跑完后的“可读产物”。
main()
读取命令行参数
sel（0..13），表示第一步固定猜fd=0123后得到的那一类反馈（比如9代表"0H0B"）。预处理 / 初始化：
initt()会：initp()：准备置换（p4/p10）。initnt2()：生成nt2[]全候选；ht[]/bt[]两张辅助小表也在这里建好。- 预填
mi[n_exist][num] = imn(n_exist,num)表。 - 初始化
QB对象池。
用
fd把 5040 个候选切成 14 份，选择sel对应那一份进入cmp2()搜索。通过
dqb()在stdout打印整棵决策树，并在stderr打印统计信息（c_compute/c_long_compute/c_tablelen/c_selectlen等）。
运行与参数（给未来的自己留个备忘）
编译（数字模式，
TS=5040）：g++ -O3 -std=c++11 main.cpp -o solver或者（Mastermind 模式，
TS=1296）：g++ -O3 -std=c++11 -DMASTER main.cpp -o solver运行
./solver 9这会在标准输出打印整棵决策树（用 14 条边标签 ），在标准错误打印搜索统计。
sel与标签对照（来自cs[]）：
| sel | 反馈 | sel | 反馈 | sel | 反馈 | sel | 反馈 |
|---|---|---|---|---|---|---|---|
| 0 | 4H | 1 | 2H2B | 2 | 1H3B | 3 | 0H4B |
| 4 | 3H0B | 5 | 2H1B | 6 | 2H0B | 7 | 1H2B |
| 8 | 0H3B | 9 | 0H0B | 10 | 1H0B | 11 | 1H1B |
| 12 | 0H2B | 13 | 0H1B |
一些巧妙点
ht[]/bt[]两张 1KB/64KB 小表：挤成 O(1) 的查表，非常划算。- 合并编码
Q2：上半是集合掩码，下半是数字序列。 - 对称性剪枝：
cp()/sp()/cu()+p4/p10，大幅减少等价猜法，搜索速度的关键。 imn()的分段下界：配合cnt()的“子类估价”。- 对象池
QB：树大时避免堆分配碎片和系统调用开销。
完整源码（
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
int imn(int n_exist,int num);
void sbo(short a[],short index[],int nel);
#define FAST
#ifdef FAST
typedef unsigned short Q;
#define COL(q,i) ((q>>(12-4*i))&15)
#else
typedef struct{
char col[4];
} Q;
#define COL(q,i) (q.col[i])
#endif
typedef struct qhash{
Q*q;
struct qhash*next;
} QuestionHash;
#ifdef MASTER
#define TS 1296
#else
#define TS 5040
#define SIZEOF_SECOND 19
#define SLS 14
#endif
#define INFINITY 30000
#define ML 15
#define QS 30000
typedef int Q2;
Q2 nt2[TS];
char ht[0x10000];
char bt[1024];
int cv2[5][8]={
{9,13,12,8,3,-1,-1,-1},
{-1,10,11,7,2,-1,-1,-1},
{-1,-1,6,5,1,-1,-1,-1},
{-1,-1,-1,4,-1,-1,-1,-1},
{-1,-1,-1,-1,0,-1,-1,-1}
};
int cr[14]={9,13,12,8,3,10,11,7,2,6,5,1,4,0};
char*cs[14]={
"4H","2H2B","1H3B","0H4B",
"3H0B","2H1B","2H0B","1H2B","0H3B",
"0H0B","1H0B","1H1B","0H2B","0H1B"
};
int c_compute;
int c_long_compute;
int c_tablelen;
int c_selectlen;
Q2 fd=0xf0123;
Q2 sd[SIZEOF_SECOND]={
0x170124,0x0f0132,0x1b0134,0x330145,
0x170214,0x0f0231,0x1d0234,0x350245,
0x710456,0x0f1032,0x1b1034,0x331045,
0x171204,0x0f1230,0x1e1234,0x361245,
0x3a1435,0x721456,0xf04567
};
short check[ML][TS][SLS];
short p4[ML][24][4];
short p10[ML][24][10];
int mi[11][TS];
typedef struct qbox{
Q2 query;
struct qbox*ptr[SLS];
} QB;
QB qbs[QS];
QB*qbt;
int maxlevel;
void initp(){
int used[4];
int j,k,l,m,rest,nth;
for(j=0;j<24;j++){
for(k=0;k<4;k++)
used[k]=0;
for(rest=j,k=4;k>0;k--){
nth=rest%k;
for(l=m=0;l<4;l++){
if(!used[l]&&m++==nth)
break;
}
used[l]=1;
p4[1][j][4-k]=l;
p10[1][j][l]=4-k;
rest=rest/k;
}
for(k=4;k<10;k++)
p10[2][j][k]=-1;
}
}
void initnt2(){
int i,j,k,l,jj,kk,ll,index,r;
for(i=0;i<10;i++)
for(jj=j=0;j<9;j++,jj++){
if(jj==i){
j--;
} else{
for(kk=k=0;k<8;k++,kk++){
if(kk==jj||kk==i){
k--;
} else{
for(ll=l=0;l<7;l++,ll++){
if(ll==kk||ll==jj||ll==i){
l--;
} else{
index=l+7*(k+8*(j+9*i));
nt2[index]=(((1<<i)|(1<<jj)|(1<<kk)|(1<<ll))<<16)|
(i<<12)|(jj<<8)|(kk<<4)|ll;
}
}
}
}
}
}
for(i=0;i<0x10000;i++){
for(r=j=0;j<4;j++)
if(((i>>(j*4))&15)==0)
r++;
ht[i]=r;
}
for(i=0;i<1024;i++){
for(r=j=0;j<10;j++)
if((i>>j)&1)
r++;
bt[i]=r;
}
}
void initt(){
int i,j,k,l,jj,kk,ll;
initp();
initnt2();
for(j=4;j<=10;j++)
for(i=0;i<TS;i++)
mi[j][i]=imn(j,i);
for(i=0;i<QS-1;i++)
qbs[i].ptr[0]=&qbs[i+1];
qbs[QS-1].ptr[0]=NULL;
qbt=&qbs[0];
}
int used_numbers(Q2*ptr,int len){
int i,r;
for(r=0,i=0;i<len;i++)
r|=ptr[i];
return r>>16;
}
QB*aqb(){
struct qbox*tmp;
int i;
tmp=qbt;
if((qbt=qbt->ptr[0])==NULL){
fprintf(stderr,"qbox is exausted?\n");
exit(1);
}
for(i=0;i<SLS;i++)
tmp->ptr[i]=NULL;
#if 0
qbox_use++;
#endif
return tmp;
}
void fqb(QB*ptr){
int i;
for(i=0;i<SLS;i++)
if(ptr->ptr[i]!=NULL){
fqb(ptr->ptr[i]);
ptr->ptr[i]=NULL;
}
ptr->ptr[0]=qbt;
qbt=ptr;
#if 0
qbox_use--;
#endif
}
void question2str(Q2 q,char*str){
sprintf(str,"%c%c%c%c",('0'+((q>>12)&15)),('0'+((q>>8)&15)),
('0'+((q>>4)&15)),('0'+(q&15)));
}
void dqb(QB*qptr,int level,FILE*fp){
int i,j,cnt;
char buf[5];
for(j=0;j<level;j++)
putc('\t',fp);
if(qptr==NULL){
fprintf(fp,"nil\n");
} else{
for(cnt=i=0;i<SLS;i++)
if(qptr->ptr[i]!=NULL)
cnt++;
if(cnt==0){
question2str(qptr->query,buf);
fprintf(fp,"%s\n",buf);
} else{
fprintf(fp,"(%s\n",cs[0xa]);
for(j=0;j<level+1;j++)
putc('\t',fp);
question2str(qptr->query,buf);
fprintf(fp,"%s\n",buf);
for(i=0;i<SLS;i++){
#if 0
j=cr[i];
#else
j=i;
#endif
dqb(qptr->ptr[j],level+1,fp);
}
for(j=0;j<level;j++)
putc('\t',fp);
fprintf(fp,")\n");
}
}
}
int limit_table[11][3]={
{0,0,0},
{0,0,0},
{0,0,0},
{0,0,0},
{4,12,24},
{8,45,109},
{11,78,276},
{13,101,494},
{14,114,674},
{14,122,783},
{14,127,864}
};
int imn(int n_exist,int num){
if(num==0)
return 0;
else if(num<=limit_table[n_exist][0])
return num*2-1;
else if(num<=limit_table[n_exist][1])
return num*3-1-limit_table[n_exist][0];
else if(num<=limit_table[n_exist][2])
return num*4-1-limit_table[n_exist][0]-limit_table[n_exist][1];
else
return num*5-limit_table[n_exist][0]-limit_table[n_exist][1]-limit_table[n_exist][2];
}
int hb(Q2 q1,Q2 q2){
int hit,blow;
hit=ht[(q1^q2)&0xffff];
blow=bt[(q1&q2)>>16];
return cv2[hit][blow];
}
int sp(Q2 q,int level,int permlen,int used){
int i,j,k,next_n,c;
Q2 min_q,tmp_q;
min_q=q&0xffff;
for(i=k=0;i<permlen;i++){
next_n=bt[used];
for(tmp_q=0,j=0;j<4;j++){
c=(q>>(12-p4[level][i][j]*4))&15;
tmp_q<<=4;
if((used>>c)&1)
tmp_q|=p10[level][i][c];
else
tmp_q|=next_n++;
}
if(tmp_q==min_q){
for(j=0;j<4;j++){
p4[level+1][k][j]=p4[level][i][j];
}
for(j=0;j<10;j++){
p10[level+1][k][j]=p10[level][i][j];
}
next_n=bt[used];
for(j=0;j<4;j++){
p4[level+1][k][j]=p4[level][i][j];
c=(q>>(12-p4[level][i][j]*4))&15;
if(!((used>>c)&1)){
p10[level+1][k][c]=next_n++;
}
}
k++;
}
}
return k;
}
int cp(Q2 q,int level,int permlen,int used){
int i,j,next_n,c;
Q2 min_q,tmp_q;
min_q=q&0xffff;
for(i=0;i<permlen;i++){
next_n=bt[used];
for(tmp_q=0,j=0;j<4;j++){
c=(q>>(12-p4[level][i][j]*4))&15;
tmp_q<<=4;
if((used>>c)&1)
tmp_q|=p10[level][i][c];
else
tmp_q|=next_n++;
}
if(tmp_q<min_q)
return 0;
}
return 1;
}
void mkhp(short*assumed,short*index,int tablesize){
int i,j,k,v,ind;
for(i=tablesize/2;i>=1;i--){
v=assumed[ind=index[i]];
for(j=i;j<=tablesize/2;j=k){
k=j+j;
if(k<tablesize&&assumed[index[k]]>assumed[index[k+1]])
k++;
if(v<=assumed[index[k]])
break;
index[j]=index[k];
}
index[j]=ind;
}
}
void dnhp(short*assumed,short*index,int tablesize,int i){
int v,ind,j,k;
v=assumed[ind=index[i]];
for(j=i;j<=tablesize/2;j=k){
k=j+j;
if(k<tablesize&&assumed[index[k]]>assumed[index[k+1]])
k++;
if(v<=assumed[index[k]])
break;
index[j]=index[k];
}
index[j]=ind;
}
void sbo(short a[],short index[],int nel){
int i,j,k,ind,v;
for(i=0;i<nel;i++)
index[i]=i;
for(i=nel/2;i>0;i--){
ind=index[i];
v=a[ind];
for(j=i;j<=nel/2;j=k){
k=j+j;
if(k<nel&&a[index[k]]<a[index[k+1]])
k++;
if(v>=a[index[k]])
break;
index[j]=index[k];
}
index[j]=ind;
}
for(k=nel;k>1;k--){
ind=index[1];
index[1]=index[k];
for(v=a[1],i=1;i<=k/2;i=j){
j=i+i;
if(j<k&&a[index[j]]<a[index[j+1]])
j++;
if(v>=a[index[j]])
break;
index[i]=index[j];
}
index[i]=ind;
}
}
int cnt(Q2*ptr,int len,Q2 src,short*dest,short*assumed_sub){
int i,j,val,minval,nonzeros,sel_len;
Q2 q,exist[SLS];
for(i=0;i<SLS;i++){
dest[i]=0;
exist[i]=0;
}
for(i=0;i<len;i++){
q=ptr[i];
j=hb(q,src);
dest[j]++;
exist[j]|=q;
}
for(nonzeros=val=i=0;i<SLS;i++){
if((sel_len=dest[i])){
assumed_sub[i]=minval=
mi[bt[exist[i]>>16]][sel_len];
nonzeros++;
val+=minval;
}
}
if(dest[0])
val--;
if(nonzeros>1)
return val+len;
else
return INFINITY;
}
int cu(Q2 q,int*zeros,int map){
int i,v;
for(i=0;i<4;i++){
v=COL(q,i);
if(!((map>>v)&1)){
if(*zeros++!=v)
return 0;
}
}
return 1;
}
int cmp(Q2*ptr,int len,int level,int used_in_q,int permlen,QB*qbox,int minval){
int i,j,k,k1,k2;
int seltops[SLS],selptrs[SLS];
Q2 to_child[TS],src,*c_ptr;
short assumed[TS+1];
short assumed_sub[TS][SLS];
short assumed_three[SLS];
short index[TS];
short sel_order[SLS];
int uniq[10],sort_i,uniq1[10];
int maxval=0,tmpval,zerolen,map,zerolen1,used,newuse,newpermlen,tmpval1;
QB tmp_qbox,*c_qbox,*c_qbox1,*c_qbox2,*c_qbox3,*c_qbox4;
int tablesize,updated=0,sel_j;
#if 0
int cnt1=0;
#endif
c_compute++;
if(len==1){
qbox->query=ptr[0];
return 0;
}
if(len==2){
qbox->query=ptr[0];
if((tmpval=cnt(ptr,2,qbox->query,check[level][0],assumed_three))==5){
c_qbox=aqb();
qbox->ptr[0]=c_qbox;
c_qbox->query=ptr[1];
return 1;
}
qbox->query=ptr[1];
if((tmpval=cnt(ptr,2,qbox->query,check[level][0],assumed_three))==5){
c_qbox=aqb();
qbox->ptr[0]=c_qbox;
c_qbox->query=ptr[0];
return 1;
}
fprintf(stderr,"something wrong? len==2, but not 1?\n");
exit(1);
}
used=used_numbers(ptr,len)|used_in_q;
for(i=0;i<10;i++)
if(!((used>>i)&1))
break;
for(zerolen=0;i<10;i++)
if(!((used>>i)&1))
uniq[zerolen++]=i;
for(i=0;i<SLS;i++)
seltops[i]=0;
if(level==1&&bt[used]==4){
for(i=0;i<TS;i++){
if(cu(nt2[i],uniq,used)&&
cp(nt2[i],level,permlen,used_in_q)){
if((assumed[i]=cnt(ptr,len,nt2[i],check[level-1][i],assumed_sub[i]))<INFINITY)
index[++j]=i;
}
}
} else{
for(i=j=0;i<TS;i++){
if((assumed[i]=cnt(ptr,len,nt2[i],check[level-1][i],assumed_sub[i]))<INFINITY)
index[j++]=i;
}
}
tablesize=j;
mkhp(assumed,index,tablesize);
c_long_compute++;
c_tablelen+=tablesize;
#if 0
minval=INFINITY;
#endif
for(i=tablesize;i>=1;i--){
sort_i=index[1];
#if 1
if((tmpval=assumed[sort_i])>=minval)
break;
#endif
c_selectlen++;
#if 0
printf("i=%d,sort_i=%d,assumed=%d\n",i,sort_i,assumed[sort_i]);
#endif
src=nt2[sort_i];
map=src>>16;
if(bt[used_in_q]==4){
if(bt[map]==4&&((map&used_in_q)==used_in_q)){
qbox->query=src;
for(k=0;k<SLS;k++)
seltops[k]+=check[level-1][sort_i][k];
uniq1[0]=uniq1[1]=uniq1[2]=uniq1[3]=uniq1[4]=uniq1[5]=
uniq1[6]=uniq1[7]=uniq1[8]=uniq1[9]=-1;
for(newuse=used,k=0;k<4;k++){
j=COL(src,k);
if(!((newuse>>j)&1)){
newuse|=1<<j;
uniq1[j]=bt[newuse]-1;
}
}
newpermlen=sp(qbox->query,level,permlen,used_in_q);
for(j=1;j<SLS;j++)
seltops[j]=selptrs[j]=seltops[j-1]+check[level-1][sort_i][j-1];
for(j=0;j<len;j++)
to_child[selptrs[hb(src,ptr[j])]++]=ptr[j];
sbo(check[level-1][sort_i],sel_order,SLS);
for(j=0;j<SLS;j++){
sel_j=sel_order[j];
switch(check[level-1][sort_i][sel_j]){
case 0:
break;
case 1:
c_qbox=aqb();
question2str(ptr[seltops[sel_j]],(char*)&uniq1[0]);
c_qbox->query=ptr[seltops[sel_j]];
c_qbox1=aqb();
qbox->ptr[sel_j]=c_qbox;
c_qbox->ptr[0]=c_qbox1;
c_qbox1->query=
to_child[seltops[sel_j]];
if(sel_j==0){
c_qbox2=aqb();
c_qbox3=aqb();
c_qbox4=aqb();
c_qbox->ptr[1]=c_qbox2;
c_qbox->ptr[2]=c_qbox3;
c_qbox->ptr[3]=c_qbox4;
c_qbox2->query=
to_child[seltops[sel_j]+1];
c_qbox3->query=
to_child[seltops[sel_j]+2];
c_qbox4->query=
to_child[seltops[sel_j]+3];
tmpval+=3;
}
tmpval++;
break;
case 2:
c_ptr=&to_child[seltops[sel_j]];
c_qbox=aqb();
c_qbox1=aqb();
c_qbox2=aqb();
tmp_qbox.ptr[sel_j]=c_qbox;
c_qbox->query=c_ptr[0];
c_qbox1->query=c_ptr[0];
c_qbox2->query=c_ptr[1];
c_qbox->ptr[0]=c_qbox1;
c_qbox->ptr[hb(c_ptr[1],c_ptr[0])]=c_qbox2;
tmpval+=3;
break;
case 3:
c_ptr=&to_child[seltops[sel_j]];
c_qbox=aqb();
c_qbox1=aqb();
c_qbox2=aqb();
c_qbox3=aqb();
tmp_qbox.ptr[sel_j]=c_qbox;
c_qbox->query=c_ptr[0];
c_qbox1->query=c_ptr[0];
c_qbox2->query=c_ptr[1];
c_qbox3->query=c_ptr[2];
c_qbox->ptr[0]=c_qbox1;
c_qbox->ptr[hb(c_ptr[1],c_ptr[0])]=c_qbox2;
k=hb(c_ptr[2],c_ptr[0]);
if(k==0){
k1=hb(c_ptr[2],c_ptr[1]);
c_qbox3->ptr[0]=c_qbox2;
c_qbox3->ptr[k1]=c_qbox1;
} else{
c_qbox3->ptr[0]=c_qbox1;
c_qbox3->ptr[k]=c_qbox2;
}
tmpval+=5;
break;
default:
c_qbox=aqb();
tmp_qbox.ptr[sel_j]=c_qbox;
c_qbox->query=to_child[seltops[sel_j]];
tmpval1=cmp(&to_child[seltops[sel_j]],check[level-1][sort_i][sel_j],
level+1,newuse,newpermlen,c_qbox,assumed_sub[sort_i][sel_j]+(minval-tmpval));
if(tmpval1>=minval){
fqb(tmp_qbox.ptr[sel_j]);
tmp_qbox.ptr[sel_j]=NULL;
tmpval=minval;
break;
}
tmpval+=tmpval1;
}
if(tmpval>=minval){
i=0;
break;
}
}
}
} else{
seltops[0]=selptrs[0]=0;
for(j=1;j<SLS;j++)
seltops[j]=selptrs[j]=seltops[j-1]+check[level-1][sort_i][j-1];
for(j=0;j<len;j++)
to_child[selptrs[hb(src,ptr[j])]++]=ptr[j];
tmp_qbox.query=src;
for(j=0;j<SLS;j++){
switch(check[level-1][sort_i][j]){
case 0:
break;
case 1:
c_qbox=aqb();
tmp_qbox.ptr[j]=c_qbox;
c_qbox1=aqb();
c_qbox->ptr[0]=c_qbox1;
c_qbox->query=
to_child[seltops[j]];
c_qbox1->query=
to_child[seltops[j]];
tmpval++;
break;
case 2:
c_ptr=&to_child[seltops[j]];
c_qbox=aqb();
c_qbox1=aqb();
c_qbox2=aqb();
tmp_qbox.ptr[j]=c_qbox;
c_qbox->query=c_ptr[0];
c_qbox1->query=c_ptr[0];
c_qbox2->query=c_ptr[1];
c_qbox->ptr[0]=c_qbox1;
c_qbox->ptr[hb(c_ptr[1],c_ptr[0])]=c_qbox2;
tmpval+=3;
break;
case 3:
c_ptr=&to_child[seltops[j]];
c_qbox=aqb();
c_qbox1=aqb();
c_qbox2=aqb();
c_qbox3=aqb();
tmp_qbox.ptr[j]=c_qbox;
c_qbox->query=c_ptr[0];
c_qbox1->query=c_ptr[0];
c_qbox2->query=c_ptr[1];
c_qbox3->query=c_ptr[2];
c_qbox->ptr[0]=c_qbox1;
c_qbox->ptr[hb(c_ptr[1],c_ptr[0])]=c_qbox2;
k=hb(c_ptr[2],c_ptr[0]);
if(k==0){
k1=hb(c_ptr[2],c_ptr[1]);
c_qbox3->ptr[0]=c_qbox2;
c_qbox3->ptr[k1]=c_qbox1;
} else{
c_qbox3->ptr[0]=c_qbox1;
c_qbox3->ptr[k]=c_qbox2;
}
tmpval+=5;
break;
default:
c_qbox=aqb();
tmp_qbox.ptr[j]=c_qbox;
c_qbox->query=to_child[seltops[j]];
tmpval1=cmp(&to_child[seltops[j]],check[level-1][sort_i][j],
level+1,used_in_q,permlen,c_qbox,assumed_sub[sort_i][j]+(minval-tmpval));
if(tmpval1>=minval){
fqb(tmp_qbox.ptr[j]);
tmp_qbox.ptr[j]=NULL;
tmpval=minval;
break;
}
tmpval+=tmpval1;
}
if(tmpval>=minval){
i=0;
break;
}
}
}
if(tmpval<minval){
*qbox=tmp_qbox;
minval=tmpval;
updated=1;
} else{
for(j=0;j<SLS;j++){
if(tmp_qbox.ptr[j]!=NULL)
fqb(tmp_qbox.ptr[j]);
}
if(updated)
break;
}
index[1]=index[i];
dnhp(assumed,index,i=--tablesize,1);
}
if(!updated){
qbox->query=0;
}
return minval;
}
int cmp2(Q2*ptr,int len,QB*qbox,int minval){
int i,j,k,k1,k2;
int seltops[SLS],selptrs[SLS];
Q2 to_child[TS],src,*c_ptr;
short assumed[SIZEOF_SECOND];
short assumed_sub[SIZEOF_SECOND][SLS];
short assumed_three[SLS];
short index[TS];
short sel_order[SLS];
short second_check[SIZEOF_SECOND][SLS];
short second_check_three[SLS];
int maxval=0,tmpval,use,permlen,updated=0,tmpval1,sel_j;
QB tmp_qbox,*c_qbox,*c_qbox1,*c_qbox2,*c_qbox3,*c_qbox4;
for(i=0;i<SIZEOF_SECOND;i++){
assumed[i]=cnt(ptr,len,sd[i],second_check[i],assumed_sub[i]);
}
sbo(assumed,index,SIZEOF_SECOND);
for(i=SIZEOF_SECOND;i>=1;i--){
j=index[1];
if((tmpval=assumed[j])>=minval){
break;
}
src=sd[j];
qbox->query=src;
use=(src>>16)|0xf;
permlen=sp(src,1,24,0xf);
for(j=1;j<SLS;j++)
seltops[j]=selptrs[j]=seltops[j-1]+second_check[i][j-1];
for(j=0;j<len;j++)
to_child[selptrs[hb(src,ptr[j])]++]=ptr[j];
sbo(second_check[i],sel_order,SLS);
for(j=0;j<SLS;j++){
sel_j=sel_order[j];
switch(second_check[i][sel_j]){
case 0:
break;
case 1:
c_qbox=
qbox->ptr[sel_j]=aqb();
c_qbox1=aqb();
c_qbox->ptr[0]=c_qbox1;
c_qbox->query=
to_child[seltops[sel_j]];
c_qbox1->query=
to_child[seltops[sel_j]];
tmpval++;
break;
case 2:
c_ptr=&to_child[seltops[sel_j]];
c_qbox=aqb();
c_qbox1=aqb();
c_qbox2=aqb();
qbox->ptr[sel_j]=c_qbox;
c_qbox->query=c_ptr[0];
c_qbox1->query=c_ptr[0];
c_qbox2->query=c_ptr[1];
c_qbox->ptr[0]=c_qbox1;
c_qbox->ptr[hb(c_ptr[1],c_ptr[0])]=c_qbox2;
tmpval+=3;
break;
case 3:
c_ptr=&to_child[seltops[sel_j]];
c_qbox=aqb();
c_qbox1=aqb();
c_qbox2=aqb();
c_qbox3=aqb();
qbox->ptr[sel_j]=c_qbox;
c_qbox->query=c_ptr[0];
c_qbox1->query=c_ptr[0];
c_qbox2->query=c_ptr[1];
c_qbox3->query=c_ptr[2];
c_qbox->ptr[0]=c_qbox1;
c_qbox->ptr[hb(c_ptr[1],c_ptr[0])]=c_qbox2;
k=hb(c_ptr[2],c_ptr[0]);
if(k==0){
k1=hb(c_ptr[2],c_ptr[1]);
c_qbox3->ptr[0]=c_qbox2;
c_qbox3->ptr[k1]=c_qbox1;
} else{
c_qbox3->ptr[0]=c_qbox1;
c_qbox3->ptr[k]=c_qbox2;
}
tmpval+=5;
break;
default:
c_qbox=aqb();
qbox->ptr[sel_j]=c_qbox;
c_qbox->query=to_child[seltops[sel_j]];
tmpval1=cmp(&to_child[seltops[sel_j]],second_check[i][sel_j],
2,use,permlen,c_qbox,assumed_sub[i][sel_j]+(minval-tmpval));
if(tmpval1>=minval){
fqb(qbox->ptr[sel_j]);
qbox->ptr[sel_j]=NULL;
tmpval=minval;
break;
}
tmpval+=tmpval1;
}
if(tmpval>=minval){
i=0;
break;
}
}
if(tmpval<minval){
minval=tmpval;
updated=1;
} else{
for(j=0;j<SLS;j++){
if(qbox->ptr[j]!=NULL)
fqb(qbox->ptr[j]);
}
if(updated)
break;
}
index[1]=index[i];
dnhp(assumed,index,i=--SIZEOF_SECOND,1);
}
return minval;
}
int main(int ac,char**ag){
int i,j,tmpval,val;
short check[SLS];
int seltops[SLS],selptrs[SLS];
Q2 to_child[TS];
short assumed_one[SLS];
FILE*fp;
char filename[256];
int map[256];
QB*qbox,*c_qbox;
int sel;
if(ac>1){
sel=atoi(ag[1]);
} else{
exit(1);
}
initt();
maxlevel=0;
qbox=aqb();
for(i=0;i<SLS;i++)
seltops[i]=0;
for(i=0;i<SLS;i++)
check[i]=0;
for(j=0;j<TS;j++)
check[hb(fd,nt2[j])]++;
for(j=1;j<SLS;j++)
seltops[j]=selptrs[j]=seltops[j-1]+check[j-1];
assumed_one[0]=1;
for(i=1;i<SLS;i++)
assumed_one[i]=INFINITY;
#if 1
val=1;
#else
val=0;
#endif
sprintf(filename,"%s-%s.txt",cs[0xa],cs[sel]);
fp=fopen(filename,"w");
fflush(stdout);
for(j=0;j<TS;j++)
to_child[selptrs[hb(fd,nt2[j])]++]=nt2[j];
tmpval=0;
j=sel;
#if 1
tmpval+=(val=cmp2(&to_child[seltops[j]],check[j],qbox,minvals[j]+1));
#else
tmpval+=(val=cmp2(&to_child[seltops[j]],check[j],qbox,INFINITY));
#endif
dqb(qbox,0,stdout);
fprintf(stderr,"%d: val=%d,type=%s,len=%d,c_compute=%d\n",j,tmpval,cs[j],check[j],c_compute);
fprintf(stderr," c_long_compute=%d,c_tablelen=%d,c_selectlen=%d\n",c_long_compute,c_tablelen,c_selectlen);
exit(0);
}