去年做了做Google Code Jam的入围题，挺好玩的。今年早早的就收到了邮件，并且还附上了四道练习题。
1. [74%/80%] Alien Number：给定源语言以及目标语言，要求翻译一个数字。
这题按最自然的思路就行了。为方便起见，把源数字先转换成十进制，然后再用和十进制转二进制相同的辗转相除法，求得目标数字的表示。
2. [80%/84%] Always Turn Left：给定总是左转的规则及实际路线，要求实际的迷宫。
如果你身陷迷宫，“总是左转”的规则，或者说“手不离墙，摸着墙走”的规则，兴许能救你一命。
其实，这道题中，我们能得到的所有讯息，都在来回走的路径里面。所以只要跟着路径实际来回走一遍，并沿路，总结迷宫信息，最后得到的便是整个迷宫。
对于左右转及方向的表示，一堆if-else，时空都坏；归纳到一个表里面查表，空间效率也不高；其实就四个方向，如果NESW分别表示为0123的话，简单的加减取模，就能实现左右转了。至于walk through的坐标处理，选择一个简单的闭包最为理想。
另外，在处理路径的时候，维护一个x、y坐标的最大、最小值，以便于最后输出迷宫。
在输出迷宫的时候，不用先存储那张转换表，而直接把YES当成1，NO当成0，作为4位的二进制数，再表示为16进制，刚好就是那张表。
==== 从题目前括号里表示的人们的成功率上来看，前两题比较简单，后两题比较困难 ====
3. [68%/49%] Egg Drop：给定某个可解扔蛋问题的三个参量，在保持可解的情况下，求每个参量的极大值或极小值
这道题有很自然的思路，那便是Fmax的递推式：
设想现在在第 i 层扔蛋，那么第 i 层扔了，就能确定状态，因此本身算一层 ( 1 )；
如果蛋没碎，往上验，最多还能验F( D – 1, B )层[ 因为第 i 层扔了一次，D减1；蛋没碎，B不变 ]；
如果蛋碎了，往下验，最多还能验F( D – 1, B – 1 )层[ 因为第 i 层扔了一次，D减1；蛋碎了，B也减1 ]。
由于每次验证，蛋只能处于碎或不碎状态中的一种，所以二者并不互相影响。故：
F(D, B) = 1 + F( D – 1, B ) + F( D – 1, B – 1 )
接下来如何计算这个递推式，是个问题。如果这个问题解决了，那么要找到最小的D和B，直接查表既可。
容易看出，递推式中有大量重复的子问题，动态规划应该效果不错。不过，我们还是先来看看数据膨胀速度如何：
[B]
1 3 7 15
1 3 7 14
1 3 6 10
1 2 3 4 [D]
左上部分不用计算，就是对角线上的数字，因为能打碎的数量，如果超过总的实验次数，多出来的这部分就没意义了。故：
F( D, B ) = F( D, D ) if( B > D )
直接观察对角线上的数字，容易看出，对角线上的数字为 2^D – 1。
即使没有看出来，也可以推出来。只用由F(D, B)的递推式和上面B>D的性质，得出递推式 A(n)=2A(n-1)+1，并求解既可。
由此可见，这张表的数字膨胀速度相当快(2^n)。因此，我们得充分利用一个很不起眼的条件，那便是F有2^32的大小限制。
B再大，在应用上面B>D的性质后，也不会超过32。整张表的纵向高度就限制得很小了。
但整张表的横向高度依然可以很大，比如F( 2000000000, 1 )，这种情况即使动态规划会很吃苦头。
观察每一列，都是从 D ~ (2 ^ D – 1)，之间的每个数的差值，刚好是杨辉三角。
1—————–0
1 1————-1
1 2 1———–2
1 3 3 1——-3
1 4 6 4 1—-4
0Cr4 1Cr4 2Cr4 3Cr4 4Cr4
15 – 1 = 14
14 – 4 = 10
10 – 6 = 4
所以，从D开始往上累加各个组合数，既可得出某一位的值。而这个累加过程，一旦大于2 ^ 32便可退出。
算出了Fmax，Bmin可以直接挨个找，因为表的纵向高度有限。而Dmin，则需要一个简单的折半查找，以应对F( 2000000000, 1 )类似的情况。
4. [64%/31%] Shopping Plan：给定商店、油费和要买的东西，求最低花费
31%的大数据集通过率，可见这道题的时间或者空间复杂度比较高。
这道题乍看之下，容易让人想起Dijkstra算法[王选貌似还谈论过Dijkstra这个人]。但我很难想到简单的一个数，来指征当前选择的优劣。因为要考虑的因素，实在很多，离家的远近、当前购买物的价格、路径、还有买了是否需要立刻回家等等。
另外，最优子结构的寻找，也颇为困难。因为容易理解，买abcd的最佳路径不一定包括买abc的最优路径。
在这种情况下，我们不得不增强条件。我们以a. 从某个商店出发，b. 买完某些商品，c. 并且当前是否需要回家为基准计算最小值。
这里面依然可以看出，有大量的重复子问题，可以动态规划。
我们遍历当前商店里能买到的并且当前需要购买的商品，买之，然后再遍历所有商店作为下一个商店，并且考虑当前买的商品是否需要立刻放回家。如果已经买完了，则立刻回家。
这里有一个想法很诱惑，那便是走过的商店便不需要再走。因为非perishable的商品始终能顺带带走，perishable的商品始终要立刻回家，也不需要第二次光顾来买。所以，如果以空间换时间，在过程中排除掉某些商店，效果应该不错。但再仔细想想就会发现，这里的空间开销很大，即使用bit set，也需要2 ^50。而所换来的时间并不多，因为我们依然得处理这个比特集。
这样实现的一个perl脚本的性能如下：
[小数据集 100 cases] – 工作很好
real 0m0.297s
user 0m0.260s
sys 0m0.040s
[大数据集 20 cases] – 严重超时
real 35m4.110s
user 34m20.661s
sys 0m42.387s
0.297s已经是对perl脚本做性能调校之后的结果，所以不更改算法或者更改编程语言，很难有所提高了。这里我选择了后面一种方式，用纯C实现了一个相同的算法：
由于perl处理文本始终还是方便很多，所以先用preprocess.pl脚本把input文本解析为利于C解析的格式。[这里是每行一个数字，并处理掉商品名称]
然后用纯C的程序读入处理后的文本，并输出，[ $gcc –O3 run.c –lm ]下面是一些性能数据：
[小数据集 100 cases]
real 0m0.223s
user 0m0.220s
sys 0m0.004s
完全没有缓存的版本，已然比perl的要好，接下来为算路费的函数添加缓存：
real 0m0.128s
user 0m0.124s
sys 0m0.004s
再为递归函数添加缓存：
real 0m0.004s
user 0m0.004s
sys 0m0.000s
这里就已经相当理想了，可以预见大数据集性能也不会差。
[大数据集 20 cases]
real 0m16.551s
user 0m16.501s
sys 0m0.048s
16s，算是很完美的性能了。同样的算法，动态脚本和纯C还是没法比啊，呵呵。即使在极限情况，50个商店，15个待购商品的case，也能在0m12.260s内解决。