homeword04-word search
0. 摘要
本次作业，要求完成一个word search的程序，具体要求是： 输入：一个包含20-60个单词的文件，各单词不大于20个字母，无空格。
输出：一个猜词游戏的字母矩阵，满足如下条件：
1. 每个单词在矩阵中出现，且只出现1次
2. 上下、下上、左右、右左及对角线共8个方向，每个方向均不少于2个单词排布。
3. 矩阵长宽可以不同
4. 不存在无效行或列
5. （进阶要求）矩阵为正方形
6. (进阶要求）矩阵四角有单词覆盖
对于这个题目的实现，在可解的基础上，最重要的是以一种相对高效的方式给出结果。为此，老师讲解了“简单粗暴”法、我也参与到同学们的讨论中。我认为，首先选择一个合适的骨架，在此基础上进行拓展是一个优秀的方法，在实现过程中，骨架的恰当选择和随机化算法的应用都将用来提高效率。
1. 程序框架
这样一个程序，我首先想到类似枚举的算法显然是不行的，为此我们必须找到某些优化条件，在大量的重试中，这会显现出很大的价值。通过观察成品word search的例子，我发现很多长单词都被放置在竖直方向。也许，先选出这样一个竖直的单词作为基础，是一个不错的切入点。为此，在第一阶段，我写了复杂而精准的评估函数。此函数将为每个骨架评估一个值，值越大，越理想，此后的工作就是循环调用产生函数，优先以优选的骨架为基础进行填充，直到得出结果。这里面，“骨架”定义为一个竖直放置的单词（主骨）加上其上搭出的一个方向的其他单词（次骨）。其具体实现，请看下一章详细说明。以下，简要介绍程序框架：
模式匹配函数，若给定的字符串与模式串不能匹配，返回-1。这里面模式串为“不完整的字符串”,如模式串”bei*ang*ni***sity”匹配于”beihanguniversity”。
int compare (string pattern,string ith)
绘图函数，负责将抽象表示的骨架映射到二维数组中，便于后面的函数调用来寻找出骨架的全部模式串string pattern[].参数中 num 表示骨架中主骨在str中的序号。skl[i][0]表示与主骨第i下标字母连接的次骨单词序号。skl[i][1]表示这个次骨与主骨公共字母在次骨串的下标。
void plot_skl_mtrcs(int num, int skl[60][2])
给定一个骨架，找出其全部模式串string pattern[]，用于后期评估骨架的可拓展性。
void find_all_prtn(int num, int skl[60][2])
骨架评估函数，调用上述程序，给定一个骨架，返回一个评估值。该值的大小能够评估选定骨架的理想程度，使得程序能够以较好的切入点进行尝试。
int esimate(int num, int skl[60][2])
作图函数，用于输出结果
void plot()
初始的读取
void init()
骨架选取与迭代
void set_skeleton()
然而，当这些过程完成后，我们还是发现矩阵的大小不够理想。这已经不可以在评估上解决了，因为我们遇到了一个瓶颈，对优化的考虑过于复杂但是在实现中逻辑及其复杂，实现难度很大，而即使不怎么进行骨架的选取，我们发现对于结果的影响也微乎其微。为此，我们进入第二阶段，淡化前期评估的复杂逻辑，转向随机化和大量枚举。第二阶段，我负责的评估部分400行代码大量精简（精简了也没有太大改变，计算机速度快），转而写出一个验证的程序，此程序不断调用前面写出的代码得到一个矩阵，指导矩阵符合要求停止。第二阶段，前面的代码被包装成头文件，验证部分调用之。最终效果姑且令人满意。
我也请教过鲁海浩和肖俊鹏一组，他们告诉我即使全部随机化，也比认真的优化差不到哪里，最多只会多一行一列矩阵而已。这与我的认识完全一致。这个程序启发我，在情况量大、难以入手的程序面前，其实最好的办法就是随机化。
2. 具体代码解释
因为最开始想得不对，我的核心工作在后面都精简了，而个人认为这个评估写的还是比较好，所以这一部分，我将主要解释自己之前写的部分的思路，之前的代码虽然与最终版本不用，但是更加清晰独立能说明功能。至于控制以及修改后的部分，请参阅我的队友熊英夫的博客 http://www.cnblogs.com/yuzuka
难度和复杂度较大的是void find_all_prtn(int num, int skl[60][2]) 和int esimate(int num, int skl[60][2])两个函数，前者找到四个方向的全部模式串，后者进行评估：
void find_all_prtn(int num, int skl[60][2])
首先调用plot_skl_mtrcs(num, skl)将骨架映射至二维数组skl_mtrcs，然后分别在4个方向上定义[beginY][beginX]和[endX][endY]两个点向中间夹逼，直到遇到彼此或者遇到字母。begin,end之间的部分用空格替换‘\0’得到当前位置的一个模式串。
针对不同情况，begin，end两点的横纵坐标的变化规律不同。代码如下：
/*
* 找出四个方向全部模式串，写入string pattern[]，pattern[i][0] = '\0'表示后面没有了。
* 四个方向为水平左到右，竖直上到下，还有左上到右下，和右上到左下。
*/
void find_all_prtn(int num, int skl[][])
{
int i_ptn = , i, j, k;
int beginX, beginY, endX, endY;
char c;
plot_skl_mtrcs(num, skl);
//horizontal
for (i = ; i < ; ++i){
endX = ;
endY = ;
while (beginX <= endX){
if (skl_mtrcs[beginX][i] == '\0'){
beginX++;
}
if (skl_mtrcs[endX][i] == '\0'){
endX--;
}
if (skl_mtrcs[beginX][i] != '\0' && skl_mtrcs[endX][i] != '\0'){
break;
}
}
if (skl_mtrcs[i][beginX] != '\0'){
for (j = ; j <= endX - beginX; j++){
c = skl_mtrcs[beginX + j][i];
if (c = '\0'){
c = ' ';
}
pattern[i_ptn][j] = c;
}
pattern[i_ptn++][j] = '\0';
}
}
//vertical
for (i = ; i < ; ++i){
beginY = ;
endY = ;
while (beginY <= endY){
if (skl_mtrcs[i][beginY] == '\0'){
beginY++;
}
if (skl_mtrcs[i][endY] == '\0'){
endY--;
}
if (skl_mtrcs[i][beginY] != '\0' && skl_mtrcs[i][endY] != '\0'){
break;
}
}
if (skl_mtrcs[beginY][i] != '\0'){
for (j = ; j <= endY - beginY; j++){
c = skl_mtrcs[beginY + j][i];
if (c = '\0'){
c = ' ';
}
pattern[i_ptn][j] = c;
}
pattern[i_ptn++][j] = '\0';
}
}
//左上到右下
//stage 1
for (i = ; i >= ; --i){
beginX = i;
beginY = ;
endX = i;
endY = ;
while (beginX <= endX && beginY <= endY){
if (skl_mtrcs[beginY][beginX] == '\0' && beginX < endX && beginY < endY){
beginX++;
beginY++;
}
if (skl_mtrcs[endY][endX] == '\0' && endX > beginX && endY > endY){
endX--;
endY--;
}
if (skl_mtrcs[beginX][beginY] != '\0' && skl_mtrcs[endX][endY] != '\0'){
break;
}
}
if (skl_mtrcs[beginY][beginX] != '\0'){
j = ;
while (beginX <= endX && beginY <= endY){
c = skl_mtrcs[beginY][beginX];
if (c = '\0'){
c = ' ';
}
pattern[i_ptn][j] = c;
j++;
beginX++;
beginY++;
}
pattern[i_ptn++][j] = '\0';
}
}
//stage 2
for (i = ; i <= ; ++i){
beginX = ;
beginY = i;
endX = - i;
endY = ;
while (beginX <= endX && beginY <= endY){
if (skl_mtrcs[beginY][beginX] == '\0' && beginX < endX && beginY < endY){
beginX++;
beginY++;
}
if (skl_mtrcs[endY][endX] == '\0' && endX > beginX && endY > beginY){
endX--;
endY--;
}
if (skl_mtrcs[beginX][beginY] != '\0' && skl_mtrcs[endX][endY] != '\0'){
break;
}
}
if (skl_mtrcs[beginY][beginX] != '\0'){
j = ;
while (beginX <= endX && beginY <= endY){
c = skl_mtrcs[beginY][beginX];
if (c = '\0'){
c = ' ';
}
pattern[i_ptn][j] = c;
j++;
beginX++;
beginY++;
}
pattern[i_ptn++][j] = '\0';
}
}
//右上到左下
//stage 1
for (i = ; i <= ; ++i){
beginX = i;
beginY = ;
endX = ;
endY = i;
while (beginX <= endX && beginY >= endY){
if (skl_mtrcs[beginY][beginX] == '\0' && beginX < endX && beginY > endY){
beginX--;
beginY++;
}
if (skl_mtrcs[endY][endX] == '\0' && endX > beginX && endY < endY){
endX++;
endY--;
}
if (skl_mtrcs[beginX][beginY] != '\0' && skl_mtrcs[endX][endY] != '\0'){
break;
}
}
if (skl_mtrcs[beginY][beginX] != '\0'){
j = ;
while (beginX >= endX && beginY <= endY){
c = skl_mtrcs[beginY][beginX];
if (c = '\0'){
c = ' ';
}
pattern[i_ptn][j] = c;
j++;
beginX--;
beginY++;
}
pattern[i_ptn++][j] = '\0';
}
}
//stage 2
for (i = ; i >= ; --i){
beginX = ;
beginY = - i;
endX = i;
endY = ;
while (beginX <= endX && beginY >= endY){
if (skl_mtrcs[beginY][beginX] == '\0' && beginX < endX && beginY > endY){
beginX--;
beginY++;
}
if (skl_mtrcs[endY][endX] == '\0' && endX > beginX && endY < endY){
endX++;
endY--;
}
if (skl_mtrcs[beginX][beginY] != '\0' && skl_mtrcs[endX][endY] != '\0'){
break;
}
}
if (skl_mtrcs[beginY][beginX] != '\0'){
j = ;
while (beginX >= endX && beginY <= endY){
c = skl_mtrcs[beginY][beginX];
if (c = '\0'){
c = ' ';
}
pattern[i_ptn][j] = c;
j++;
beginX--;
beginY++;
}
pattern[i_ptn++][j] = '\0';
}
}
pattern[i_ptn][] = '\0';
}
int esimate(int num, int skl[60][2])
此函数从三个方面评估一个骨架：
est_amnt值：该骨架直接解决了多少单词的连接问题。我认为一个好的骨架，其主骨应当有较好的长度，并又较多经常出现的单词。比如单词see中出现2次最常见字母e，一定比ant这样的词更易拼接，当然这是长度一定的情况下。因此，est_amnt值越高，能够体现主骨架长度和可拓展性优秀，这样的骨架被选出，剩下没解决的问题就会少。
est_extnd值：表示整个骨架（次骨架展开出去的部分）的可拓展性如何。这个值越高，这个骨架为基础产生的矩阵就越小，满足条件的概率就越高。est_extnd的值，由骨架外的单词中能够与pattern[]模式串匹配的个数决定。能够匹配的越多，可拓展性就越好。
ext_shp:最后一个方面是骨架形状是否理想。如果一个骨架在某个方向分布十分不均匀，则结果很可能难以满足没有无效行无效列并且四角均有单词的要求。这里面，我们定义重心这个概念。重心定位于竖直放置的主骨之上，次骨左右分配的不均衡量累加到est_shp这个值中。est_shp是个小于零的值，其绝对值越大，表示形状越不理想。
此外，我定义ESTIMATE_WEIGHT_AMNT，ESTIMATE_WEIGHT_EXTND，STIMATE_WEIGHT_SHP_H，ESTIMATE_WEIGHT_SHP_V4个宏定义。他们是上述三个方面的加权值。这么做的原因是便于后期调试过程中便捷的修改其比重，以此调整评估函数各个考虑方面的权重，达到一个合适的比例，使得函数返回的值能有较好的评估性能。
这部分代码为：
/*
* 评估函数。返回值越大越好，正负都有可能。
* num主骨架序号，skl[][0]次骨架序号，skl[][1]次骨架与主骨架连接的字母在次骨架串中的下标。
*/
int esimate(int num, int skl[][])
{
string s;
string skl_main = strs[num]; // 主骨架
int i, j, k;
int est_rslt, est_amnt = , est_extnd = , est_shp_h = , est_shp_v; // 各个小方面的评估值
char c; //主骨架连接出的次骨架的个数
if(ESTIMATE_WEIGHT_AMNT != )
{
for(i = ; i < skl_main.length(); ++i)
{
if(skl[i][] != -)
est_amnt++;
}
} //骨架可拓展性
int flag;
if(ESTIMATE_WEIGHT_EXTND != )
{
find_all_prtn(num, skl);
for(i = ; pattern[i][] != '\0'; i++) // every pattern
{
for(j = ; j < n; j++) // every pattern with every word
{ //omit main skeleton
if(j == num)
continue;
//omit deputy skeletons
flag = ;
for(k = ; k < skl_main.length(); ++k)
{
if(j == skl[k][])
{
flag = ;
break;
}
}
if(flag)
continue; //compare
if(compare(pattern[i], strs[j]) != - && compare(pattern[i],strrev( &(strs[j][]) )) != -)
{
est_extnd++;
break;
}
}
}
} //骨架形状 est_shp < 0,绝对值越小越好
//考虑水平方向失衡程度
if(ESTIMATE_WEIGHT_SHP_H != )
{
int unbalance_h, p, l;
for(i = ; i <= est_amnt; ++i)
{
s = strs[ skl[i][] ];
l = s.length();
for(int mid = l / , j = ; mid - j >=; ++j)
{
if(s[mid - j] == skl_main[i])
{
p = mid - j;
break;
}
else if(s[mid + j] == skl_main[i])
{
p = mid + j;
break;
}
}
unbalance_h = * p - l + ;
if(unbalance_h < )
unbalance_h *= -;
est_shp_h -= unbalance_h;
}
est_shp_h /= est_amnt;
} return ESTIMATE_WEIGHT_AMNT * est_amnt
+ ESTIMATE_WEIGHT_EXTND * est_extnd
+ ESTIMATE_WEIGHT_SHP_H * est_shp_h
+ ESTIMATE_WEIGHT_SHP_V * est_shp_v; }
此处附上辅助函数plot_skl_mtrcs.
char pattern[][]; //storage tmp matrics for finding patterns
char skl_mtrcs[][];
/*
* 把骨架画出来，供分析所有模式串使用
* skl[i][j], j = 0 表示次骨架单词的序号，j = 1表示副骨架这个单词的第几个字母与主骨架结合。所有序号以0开始。
*/
void plot_skl_mtrcs(int num, int skl[][])
{
int Lm, L, p, mid, i, j;
int X, Y;
char c;
string s;
//plot main skeleton
s = strs[num];
Lm = s.length();
for(int mid = Lm / , k = ; mid - k >=; ++k)
{
skl_mtrcs[][ - k] = s[mid - k];
skl_mtrcs[][ + k] = s[mid + k]; // 主骨架偶数个元素，最后一个该是 /0 再验证
}
//plot each word on main skeleton
for (i = ; i < strs[num].length(); ++i){
if (skl[i][] == -){
continue;
}
L = strs[skl[i][]].length();
p = skl[i][];
for (j = ; j < L; j++){
c = strs[skl[i][]][j];
X = - p + j;
Y = - (Lm / - i) - (p - j);
skl_mtrcs[X][Y] = c;
}
}
}
第二阶段，使用下面代码循环调用前述修改的函数并且验证：
int main()
{
FILE * fout = fopen(output,"w");
int i,j;
char *a;
bool visited[];
string ss1,ss2,ss3;
srand(time());
int minx=,miny=,maxx=,maxy=,sum,maxsum;
a = (char *)malloc(sizeof(char)*);
for (int times=;times<;times++)
{
deal(a,&minx,&miny,&maxx,&maxy,&sum,ss1,ss2,ss3);
}
for (i=minx;i<=maxx;i++)
{ for (j=miny;j<=maxy;j++)
{
if (a[i*+j]!=' ')
{
fprintf(fout,"%c ",a[i*+j]);
}
else {fprintf(fout," ");}
}
fprintf(fout,"\n"); }
cout<<ss1<<endl<<ss2<<endl<<ss3<<endl;
}
3. 结果与说明
未填充空白的运行结果是：（其实是正方形）
虽然已经写得头痛..程序还是不完美，在四角均有单词这个问题上还不能完全满足要求。
Personal Software Process Stages | 时间百分比(%) | 实际花费的时间 (分钟) | 原来估计的时间 (分钟) | |
Planning | 计划 | |||
· Estimate | · 估计这个任务需要多少时间，把工作细化并大致排序 | 5 | 30 | 30 |
Development | 开发 | |||
· Analysis | · 需求分析 (包括学习新技术) | 15 | 90 | 90 |
· Design Spec | · 生成设计文档 | 0 | ||
· Design Review | · 设计复审 (和同事审核设计文档) | |||
· Coding Standard | · 代码规范 (制定合适的规范) | 5 | 30 | 30 |
· Design | · 具体设计 | 15 | 90 | 90 |
· Coding | · 具体编码 | 30 | 大于一天 | 180 |
· Code Review | · 代码复审 | 5 | 30 | 30 |
· Test | · 测试（自我测试，修改代码，提交修改） | 15 | 90 | 90 |
Reporting | 总结报告 | |||
· Test Report | · 测试报告 | 5 | 30 | 30 |
· Size Measurement | · 计算工作量 | 1 | 6 | 6 |
· Postmortem & Improvement Plan | · 事后总结, 并提出改进 | 4 | 25 | 25 |
Total | 总计 | 100% | 总用时 | 一周啊 |