标签档案:计算机科学

编程++:建立在过去的基础上

在学习编程时,最早的困难通常是简单地生成有效代码的机制。这可能会让新手非常沮丧,因为编程语言翻译者(编译器)对于他们准备接受的东西是毫不动摇地僵化的,而对于任何不符合他们的东西,他们将予以拒绝。但是,一旦掌握了这些语法基础,就可以创建以前没有人编写过的令人兴奋的新程序。

程序员创建新程序的方法之一是注意别人过去写过的东西。通过借鉴别人已经写过的东西,他们通常可以节省很多时间,从而将他们的创造力集中在他们自己的特定程序中新颖的部分上。作为一名教师,当我建议我的学生使用图书馆类来存储数据集合时,我很早就鼓励这种方法。虽然理解这些库类的工作方式当然很重要,但这并不意味着每次需要使用集合时都必须从头开始编写代码。关键是选择可用的东西,然后围绕它编写代码,或者对其进行调整以满足您的需求。

我最近应用了这个原则,当我被要求为一个我在过去20年里一直断断续续维护的程序添加一些新功能时。它是一个用C语言编写的开源项目pgn-extract。它允许棋手根据各种不同的标准搜索棋局文件,比如特定的棋手、开局、结局等。该程序的一个用户(JS)问我是否有可能让它寻找游戏中出现的特定棋盘位置。举个例子来说明,在一个复杂的终局中,专家玩家的棋子是如何在一个特定的配置中完成的,这可能会很有趣。复杂的部分是JS不希望用户指定每个棋子在棋盘上的确切位置。相反,他们会对一些作品感兴趣,但其他的都不重要。

据我所知,当时还没有这样的东西存在,但这个任务让我想起了熟悉的计算机科学主题模式匹配。在这种情况下,您需要寻找与模糊模式相匹配的东西,而不是精确的东西,通常使用正则表达式符号。例如,使用模式“(cC)在*”匹配以“cat”或“cat”开头的单词,比如“cattle”和“Catcher”。这种符号在通过Unix命令进行计算时是众所周知的grep。虽然这种表示法通常用于匹配普通文本,但我认为也可以将其用于匹配棋盘—特别是如果棋盘可以用类似文本的形式表示的话。

我的出发点是一个很好的描述Rob Pike编写的grep的实现(由Brian Kernighan记录)。以文本形式呈现棋盘其实相当简单,象棋玩家一直都在这么做。例如P6r意思是:“白卒,六个空方格,然后一个黑车”。我调整了熟悉的grep符号,使其更适合国际象棋上下文,以便能够区分黑白棋子,然后将其添加到我的程序中——当然,要承认对Rob Pike的依赖!

令人高兴的是,最初的请求者JS对结果很满意,但随后他继续演示了我从未想到的新功能的一个很好的偶然使用。他发给我一张前世界冠军米哈伊尔·塔尔(Mikhail Tal)盯着一个看不见的对手的照片。这张照片是众所周知的,但是谁是Tal威胁目光下的对手呢?JS使用新的符号对图中可见的部分进行编码(*/*/*/*/???? b ? ? q / * / ? ? N ? ? P / R ? ?Q1BR1),然后在Mikhail Tal玩过的所有游戏中运行这个程序!结果是1960年在莱比锡对阵尼古拉·帕德夫斯基的比赛。

编程不仅仅是关于编写正确代码的机制,它是关于采用和调整现有的想法来创造新的东西,有时是一些有趣的东西!