今年我参与了Advent of Code 2018解题活动。（代码在此）

Advent of Code源自于降临节日历（Advent calendar），用来倒数圣诞节的来临。这个活动已经搞了4年了，但我是今年才知道的。从12月1日开始，到12月25日圣诞节，每天一道题目。

每道题都分为两部分，前100名做出来的人可以进入排行榜，还有一个总的排行榜。每天题目开放时间是北京时间下午1点。我没有追求速度，而是等排行榜出来以后，看一下前100的用时，乘以两到三倍，作为我需要花的时间的估计，然后再慢慢的做题。

题目和leetcode的纯算法题还是有差别的。首先是题目（需求）超级长，还编排的有小故事，什么精灵训鹿之类的，很拗口难读，看着头疼，基本上需要看给的例子才能明白。然后是每个人有一个不同的输入。要求的结果是一个数字或者小字符串。因为输入（测试用例）只有一个，所以即使你的代码得到了正确结果，代码的逻辑也可能是有问题的，不能保证其他的输入下的正确性。程序的边界情况也不用考虑，我们也可以看输入数据的情况来写程序。

总的来看，题目的难度还是可以接受的。我这次用python完成了所有题目，基本上每天的题目当天能做出来（15日和23日除外）。

我花时间和精力比较多的是第15日，20日和23日的题目。

15日：需要类似A*算法进行寻路。我先看了排行榜，第一百名用时两个多小时。果然写的我快崩溃了，逻辑太复杂，两天后才强行写完。。

20日：我对题目的理解有了偏差，以为每个房间只会路过一次，不会走回头路，detour也是会走新的房间，就没有判断房间是否路过，结果第一部分正确，第二部分死活得不到正确答案。看排行榜，第二部分的时间平均几分钟，而我搞了个把钟头。。最后终于发现输入有...WNNNNNNNNESSSSS(NNNNNWESSSSS|)...这样的情况，中间括号里的就是走的回头路，而我之前直接当新的房间处理了。

23日：第二部分完全没有头绪，搜索空间太大，暴力穷举不可行。想了两三天，尝试用Octree来搞，但没有做出来。无奈只好看网上别人的解决方案了。网上貌似也没有优雅的保证绝对正确的好的算法，我就先抄了一个，以后有时间再继续研究吧。。

代码效率方面，我原来的计划是，在我弱鸡Atom CPU笔记本上，每道题耗时控制在1秒以内。但是有很多题目并没有能够达到这个目标。我也尝试用pypy来加速，算是把耗时都控制在了大概5秒以内。

下面是耗时大于1秒的题目的数据：

题目 CPython 3.6.7 pypy3 6.0.0 (Python 3.5.3) 加速比
9 4.2s 1.6s 2.6
11 15.3s 0.6s 25.5
14 40.2s 2.3s 17.5
15 5.9s 3.6s 1.6
18 17.9s 1.9s 9.4
19 12.3s 0.6s 20.5
22 1.3s 1.3s 1
23 42s 5.0s 8.4
24 8.7s 5.2s 1.7
25 1.7s 0.7s 2.4