我一直向我 11 岁的孩子承诺，我会编写一个程序，让你可以根据用户给出的单词列表构建自定义的单词搜索。多年前，我用 C 语言写过一个，但由于我再也找不到那个代码了，并且想为本专栏处理另一个有趣的项目，这就是我将在此处探讨的内容。

关于单词搜索，没有任何成熟的算法，所以这也是一个从头开始创造的好机会，这意味着与大多数有趣的项目一样，我们实际上需要在开始编码之前考虑程序。这是一个很好的纪律！

我还应该承认，自从我还是个小孩子起，我就喜欢解决单词搜索谜题，所以这个项目对我来说也有一种乐趣的成分，不仅仅是为了我的女儿做一些事情的乐趣！

以防你从未见过单词搜索，它通常是一个字母网格，其中是一组列出的单词，可以在水平、垂直或对角线方向找到，拼写可以是正向或反向。图 1 显示了一个小例子。

图 1. 单词搜索示例

查看图 1，你能找到多少个单词？我能找到 CAT、DOG、GOD（当然，GOD 是 DOG 的反向）、TIC、COP，以及更书呆子的 ROM 和 ARG。这引出了单词搜索的一个有趣的特点：总是会出现偶然的单词，因此最终程序的一个重要任务是确保不出现淫秽词语。

乍一看单词搜索，似乎方法是随机填充网格，然后翻转字母以使单词适合。但是，在我看来，更好的策略本质上是制作一个纵横字谜，然后用随机字母填充空白孔。

因此，这将是我们构建单词搜索的首要策略。每个单词也将随机定向为水平、垂直或对角线，以及正向或反向。现在，我们先只担心正向或反向，这意味着初始单词方向代码将如下所示

orient()
{
   # randomly pick an orientation and 
   # shift the word to match
   local direction;
   word=$1   # to make things neat and tidy
  if [ $(( RANDOM % 2 )) -eq 1 ] ; then
     # we need to reverse the value of $word
     word="$(echo $word | rev )"
   fi
}

数组是通过在 Bash shell 中初始化它们来创建的，格式如下所示

arrayname=( value1, value2, ... valueN )

由于这将是关于数组的很多内容，让我们首先加载单词列表作为数组，在我们进行的过程中随机定向单词。

首先，这里有一个非常简单的方法将文件读取为单词值数组

wordlist=( $(cat $1) )

很简单，但现在让我们逐字遍历数组，以反转 orient() 函数随机选择的任何单词

count=0
while [ ! -z "${wordlist[count]}" ]
do
   orient ${wordlist[count]};
   wordlist[$count]=$word
   echo "word $count = ${wordlist[count]}"
   count=$(( $count + 1 ))
done

仅使用此代码片段和一个包含“cat”、“dog”和“car”的单词文件，一个简单的调用看起来像这样

$ sh wordsearch.sh wordlist.txt 
word 0 = cat
word 1 = god
word 2 = rac

这是一个足够合理的开始。我们现在可以读入单词列表文件，并在进行过程中随机反转单个单词。现在，让我们创建一个网格数组，并尝试逐个插入单词。

这是与 Bash shell 相关的难题：虽然它支持数组，但它不支持多维数组，这真是令人头疼。因此，为了拥有一个 5x5 的网格，我们将需要五个包含五个元素的数组。首先，让我们在脚本的开头初始化它们

row1=( "-" "-" "-" "-" "-" )
row2=( "-" "-" "-" "-" "-" )
row3=( "-" "-" "-" "-" "-" )
row4=( "-" "-" "-" "-" "-" )
row5=( "-" "-" "-" "-" "-" )

然后，在稍后，一个简单的函数将允许我们以有吸引力的格式打印出网格

showgrid()
{
   echo "${row1[0]}  ${row1[1]}  ${row1[2]}  ${row1[3]}  
         ${row1[4]}"
   echo "${row2[0]}  ${row2[1]}  ${row2[2]}  ${row2[3]}  
         ${row2[4]}"
   echo "${row3[0]}  ${row3[1]}  ${row3[2]}  ${row3[3]}  
         ${row3[4]}"
   echo "${row4[0]}  ${row4[1]}  ${row4[2]}  ${row4[3]}  
         ${row4[4]}"
   echo "${row5[0]}  ${row5[1]}  ${row5[2]}  ${row5[3]}  
         ${row5[4]}"
}

我们最终将在稍后重写此函数，使其对于 N x M 大小的网格更加灵活，但现在，让我们继续使用 5x5，以便我们可以深入了解算法本身。

现在是脚本的实际工作：将单词插入网格。

最初，当然，这很容易，因为我们几乎可以保证单词如果小于五个字母长，就可以适合，但是随着越来越多的单词被放入网格中，要使每个单词都适合变得更加困难。

为了简化事情，我们首先只考虑水平或垂直插入单词。事实证明，对角线插入有点微妙。没关系，一旦我们使基本功能正常运行，我们将回过头来添加它。

首先，函数 fitword()，给定一个单词（可能已经被反转），随机选择一个方向和起始位置，使其适合，然后将其交给水平或垂直插入函数进行实际放置测试

fitword()
{
    # fit word "$1" into the grid with a random orientation
    success=0
    wordlength=$( echo $1 | wc -c )     # always +1
    wordlength=$(( $wordlength -1 ))    #  and now it's fixed
    case $(( $RANDOM % 2 )) in
      0 ) # horizontal
         until [ $success -eq 1 ] ; do
           startpoint=$(( $cols - $wordlength ))
           col=$(( $RANDOM % $startpoint ))
           row=$(( $RANDOM % 5 ))
           Hinsert $1 $col $row
           success=$?                # what does Hinsert return?
         done
         ;;

      1 ) # vertical
         until [ $success -eq 1 ] ; do
           startpoint=$(( $rows - $wordlength ))
           row=$(( $RANDOM % $startpoint ))
           col=$(( $RANDOM % 5 ))
           Vinsert $1 $row $col
           success=$?
         done
         ;;
  esac
}

目前，Hinsert() 和 Vinsert() 都可以只返回数值成功值“1”，因此它们超级容易编写。但是，让我们关注 fitword()，因为那是到目前为止真正发生操作的地方。

考虑使用我们的三个单词到 5x5 网格中的快速调用

$ sh wordsearch.sh wordlist.txt 
word 0 = cat
Hinsert called with word cat and startloc 0, 0
word 1 = god
Hinsert called with word god and startloc 0, 0
word 2 = rac
Vinsert called with word rac and startloc 0, 1

仔细观察会发现，前两个单词（第二个单词已经被反转）将水平放置，都在相同的起始点 0,0。显然这行不通，但我们会回到它（这就是为什么插入语句在重复循环中的原因：因为我们需要利用暴力插入的元素）。

第三个单词将垂直插入，并且它也已经被反转，尝试的第一个位置是行 0，列 1（这也行不通：“cat”插入在 0,0 意味着 0,1 将是“a”）。

这是一个棘手的脚本，不是吗？让我们在下个月进一步深入研究它，因为我已经没有空间了，但在同时，开始思考你将如何解决这个有趣的问题，如果你有非暴力解决方案，请给我留言。