关于ICFP 2012编程赛的那点事情
by
at 2012-08-05 15:00:00
original http://www.soimort.org/tech-blog/2012/08/05/icfp.html
ICFP Programming Contest 2012的结果出来了。不出所料，第1轮惨遭淘汰。
不过总算是混到了整整1200分，居然还不是最垫底，哥真是太感动了
221支参赛队提交了最终程序，拿到正分值的是194支，真的有人敢拿零分和负分的说（汗）
(・U・)
今年比赛的题目，简单地概括就是：操纵机器人在地底环境采矿。输入一个完全已知的由ASCII字符组成的地图（可能是标准的m×n矩形也可能是不规则形状什么的），地图上有许多叫做“lambda”的矿物（当然位置是已知的），机器人的初始位置也是给定在地图上的，你的任务就是要给出一串机器人行动的指令序列，使机器人依照这个指令序列所走的路径能够采完地图上所有矿点、并且最终抵达地图上的“升降井”位置以顺利完成整个采矿过程（在最理想的情况下）。机器人每采集一个矿点加25分，中途主动放弃的话每个采集到的矿点可以再额外增加25分，最终完成全部开采（抵达升降井）则每个矿点可以额外增加50分，当然作为代价，每执行一步指令要相应地扣除1分。
当然啦，问题不可能设得这么没难度，才不会拿简简单单的动态规划来作比赛题呢。所以地图上的每个格子会有不同的地形，比如墙壁，比如泥土，比如石头，机器人的行动会造成各种后效性。泥土是可以被机器人钻开的，石头是可以被机器人推动的，石头下面如果没有别的物体支撑会以固定速率向下坠落，石头落到别的石头上因为无法支撑会滚向旁边，然后，如果机器人刚好在石头落下的时候处于下面格子的位置，就会被砸坏掉，采矿被迫终止并且得不到额外的加分。
当然啦，即使这样问题还是太简单了，命题委员会（今年是University of St Andrews）于是充分发挥了一把苏格兰人的幽默感（黑色幽默？）：由于最近在苏格兰肆虐的洪水，在比赛开始后不久，我们的地下矿藏被水淹了！水位将以某给定的速率从地图下方开始上升，机器人在水下连续活动的时间由一个防水参数给定，超过这个时间仍然处于水下的机器人将会报废。
当然啦，命题组还是觉得问题太简单了，于是在水灾的第二天，他们在地图里追加了一种叫做“蹦床”的元素。与其说是蹦床，不如说成是传送门更合适，当机器人走到一个蹦床的位置，它会被瞬间转移到地图上的另一个目标点。（宏观物质传输这不科学啊喂……）
当然啦，命题组还是觉得……问题太简单了。于是接下来，地下矿藏里长出了一种奇葩的生物，叫做“Wadler的胡须”。这种生活在地底的诡异植物会以某个固定的速率疯长，每过一段时间就会向四周蔓延一格，这些被胡须占据的格子阻碍了机器人的行动，因此机器人必须使用有限的“Hutton的剃刀”来进行除草。一把剃刀只能使用一次，不过好在地图上也是分布有一些剃刀可以去拿的。（是不是有点像魔塔之类的游戏）
一点小插曲，关于胡须和剃刀这两个名字：Philip Wadler，Univ of Edinburgh的教授，是Haskell语言和XQuery的主要设计者之一；Graham Hutton，Univ of Nottingham的教授，ICFP（The International Conference on Functional Programming，国际函数式编程会议）组委会的主席，那本《Programming in Haskell》的作者。
Hutton的剃刀（Hutton's Razor）的概念（和名称）仿照自奥卡姆剃刀原理（Occam's Razor）：“用较少的东西，同样可以做好的事情”。假定存在这么一种极小化的编程语言，它由两种元素构成：
- 常量，包括从0开始的全部自然数；
一个“
+”运算符，从而我们可以写出(37 + 5) + 15 + (42 + 0)这样的语句。data Exp = Const Int | Add Exp Exp eval :: Exp -> Int eval (Const i) = i eval (Add x y) = eval x + eval y
显然，从定义来看，这并不是一种图灵完全的语言，在实际中几乎没有什么用处。但是通过必要的扩展，可以基于它一步步实现更多的算法。顾名思义，这个东西是Graham Hutton最早提出来的，用来让学生练习使用Haskell做语义分析。
有了Hutton的剃刀，就有了Wadler的胡须（Wadler's Beard）。这个，真的只是在调侃Wadler教授那标志性的大胡子而已……
（貌似偏离主题了）
当然啦，事情还没有完。命题组大概还是觉得，问题太简单了……在比赛第三天，一种叫做“高阶石（horock, higher-order rock）”的新矿物被发现了。它在通常形态下的性质与石头完全相同，唯一特别的是在从空中坠落并且落地之后，会释放出里面潜藏的lambda（大概可以类比成higher-order function？），然后就可以被机器人当作普通的矿物收集了。
比赛分为Lighting division和Full division两部分。Lighting division相当于快速原型开发，想参加这个division评奖的队伍需要在比赛开始后24小时内提交原型程序（参加比赛的队伍可以自由选择参加或者不参加这个division），作为精神上的奖励，第一名队伍所用的语言将被宣布为“非常适合快速原型”的语言。Full division则是正式的比赛评奖，取前三名队伍，所用的语言分别被宣布为“挑剔黑客的编程工具最佳选择”“适合于许多方面应用的优秀工具”和“不太烂的编程语言”（基本上这个比赛的目的就是让优胜者拥有秀一下自己编程语言的bragging rights……）
由此可见，比赛本身的精神鼓励大于物质奖励，而且比起函数式编程的学术主题，这个比赛更强调“编程工具”这一点，所以即使不使用函数式语言，甚至不使用函数式编程范式，都是完全允许的。评分方式是黑箱测试，无论提交二进制文件还是可执行的脚本都可以（源代码一般是不会看的），因此完全没有编程语言上的限制（和Google Code Jam一样）。
每一轮的计分方式相同，比赛方选定五张地图（当然参赛队伍事先是不知道这些地图长什么样子的），每个队伍的程序需要跑这同样的五张地图，根据输出的解评分，按总分计算排名。每个程序的运行环境是一个单独的沙箱（虚拟机上的Debian），内存大小受限，硬盘空间受限，然后时间限制上是每张地图150秒，之后程序收到一个SIGINT信号，10秒后SIGKILL强制结束，如果仍然没有输出结果，则该地图按0分计算。
大概是因为对效率要求高的原因，历年来比赛队伍的首选差不多都是ML或者Haskell，近年来更多地倾向于C++，选择Lisp/Scheme的可以说是少之又少。
比赛前一天刚好看到一篇文章叫Admitting that Functional Programming Can Be Awkward，觉得有点意思，顺手就翻译过来了。文章里面举了一个例子是平面上的sprite游戏，作者的结论是这种涉及到复杂行为模拟和状态判断的应用，更加适合于依赖内存变量读写的过程式编程，并不适合函数式范式。这次的比赛，恰好也是一个类似的2D游戏问题求解。
第一天，我尝试着用Standard ML写出一个原型，后来发现这么做有两个问题：
ML里对二维数组的处理是极其繁琐的（从语法上）。如果我要定义一个函数，找出某个坐标周围邻近格子里某种元素的数目和位置，在C语言里面简简单单几层循环、取下标操作加上累加器变量就能清晰地解决的事情，在ML里需要函数调用层层嵌套，可读性会变得比较差。
当然我相信ML是可以找到更加优雅可读（而且避免对副作用的依赖）的方案的，那就需要在类型系统上大作文章。要在比赛的几天中完成这些，无疑只会加重我的编程负担。比起C，ML是非常high-level的语言。你不可能像在C中那样轻松地手动分配内存、赋值指针，不可能进行代码级别的时间和空间优化，一切都得交给编译器（MLton）来完成。
在ML里，一段代码一旦写出来，就必然如公式般正确，剩下来的事情？优化，那种底层的事务是不应该在ML程序员的考虑范围内的。相比之下，C对于底层事务就有完全的控制权，当然作为代价，C语言：一、程序更难写，因为要纠缠与问题本质无关的细节实现；二、算法正确性难以从数学上证明，这是所有过程式语言的共同点。
这种状态空间搜索的问题，对时间和空间的要求显然不会低，只有用C这样底层的语言来写才能保证最高的自由度。
后来发生的事情让我更加深刻地理解了“A C program is like a fast dance on a newly waxed dance floor by people carrying razors（一个C程序就像是一个身上带着剃刀的人在刚打过蜡的地板上跳快节奏的舞蹈）”这句话……
再看一眼官方的5张地图，我的程序得分依次是：338，237，337，-3，291。
啊咧，-3？
我的算法几乎就是最原始的分支限界搜索找最优解，指令一开始Abort得0分，考虑到这个下限的保底解，程序怎么可能会得负分呢？
（基于同样的理由，不太能理解为什么还有其他一些队伍也得了负分……）
虽然觉得可能是地图的问题，但是并没有发现任何奇特之处。
######
#....#############
#.**.. .. ..*@ \\#
#.**.. . ... \\#
#.**.. . . 3 #
######.\\......#****###
#**....*.......# #
#\\...BL\\\....# #
#A......*****..# 2\C#
######R.....###########
###.....*.....\\\#
#\\\\#..1...\\\#
#\\\\#......\\\#
################
Trampoline A targets 1
Trampoline B targets 2
Trampoline C targets 3
于是下载了这5张地图，在自己的机器上分别跑一遍150秒，拿自己的validator计分，结果如下：
[soimort@Seele icfp-2012]$ ./lifter < full1.map
RDRRRDDRDRDRRA
387
[soimort@Seele icfp-2012]$ ./lifter < full2.map
LLUURUUUUUURRA
237
[soimort@Seele icfp-2012]$ ./lifter < full3.map
RRUUULLUUUUURA
337
[soimort@Seele icfp-2012]$ ./lifter < full4.map
FATAL ERROR: illegal input
[soimort@Seele icfp-2012]$ ./lifter < full5.map
RRDDRRRRRRA
340
第二张和第三张地图的分值和官方结果一致，第一个和第五个略高于官方分值，要么是官方用的虚拟机配置比我低所以没能跑出更好的结果（今年测评用的虚拟机系统是32位x86）；要么就是我自己的validator有问题。暂时不去追究这些。然后第四张地图，我的输出解是：FATAL ERROR: illegal input。
说是此输入不合规范什么的，这不是我自己在处理地图时加的错误输出嘛！官方的测试系统显然是把它当作我解出来的指令序列来评分了（囧囧囧囧）
调试之，问题出在蹦床的相关处理上：
这段代码的目的是当机器人到达蹦床位置时，找到传送目标点的坐标，然后把机器人移到该目标点的位置。这中间有一个对c->size的判断，因为一个蹦床必须和一个目标点对应，如果找到的目标点数目不为1，说明输入的原地图不合法，输出错误并终止程序。
但是，不知道为什么getCells返回的目标点总是2个：一个点位于(18, 6)，一个点位于(18, 14)。
从地图上看来，(18, 6)的值是ASCII字符'2'，确实是对应于蹦床B的目标点。不过(18, 14)事实上是不存在于地图上的。地图上标有'2'的目标点，只有(18, 6)一个而已。也就是说，难道是越界的数组下标访问的问题？但是为什么不是别的值刚刚好是'2'呢？
观察越界访问的结果，看出了点端倪：
c->elem[0]是getCells返回的目标点之一的坐标值，newMap->elem[newMap->height - c->elem[0].y]这个字符串显示地图上该目标点所在行的完整内容，即：“ ######\n”。
该数组空间的最后一个字节是newMap->elem[newMap->height - c->elem[0].y][12] == '\0'，字符串结束。其后的下标引用都没有意义。由于编译器未定义的内存分配机制，在newMap->elem[0][13]后面本不存在的下标因为越界访问而指向了别的地方（实际上是newMap->elem[8][13]）。
于是找到了原因，应该是getCells里面的越界下标访问造成了返回值的重复，实际上找到的两个目标点是同一个：
造成这个bug是由于不规则形状的地图，在读取的时候某些行具有较短的长度，但在访问时却统一按最长行处理，数组下标越界的时候编译器又没报错，于是就造成了隐蔽的错误。比赛的时候只用了自己写的几个规则矩形地图做测试，于是这样的错误并不能及时发现。
修改后的程序段：
再次运行，找到个比-3稍微好一点的解……
[soimort@Seele icfp-2012]$ ./lifter < full4.map
RRDDRRRDLLLA
389
算法部分暂时不想再回头看了，毫无亮点。因为比赛的时间仓促，命题方不断追加条件（于是要不断地改模拟），再加上一个人做做玩玩，到了最后一天下午才赶出来个能用的分支限界算法，编译通过，于是差不多就提交了。总的来说，这种比赛的形式还是很不错的，给出几天的时间用来编码，允许组队合作，比起Code Jam和TopCoder自由度高很多。命题方随时更改需求、最后根据算法接近最优解的程度给分而不是只有一个唯一解，这也更接近现实中的问题求解过程。(・U・)