大塞车游戏活动的算法解

最近在公司组织的培训上，遇到了一个很有意思的算法题，这篇文章就借这个为题提供一个解。

首先感谢李培英老师，《职业化研讨》这门课非常值得公司内的一线管理人员去学习。在讲到职业化内涵里的“规则意识”一节时，让大家做了一个简单的大塞车游戏，规则如下：

1、邀请10人以上的学员（注意是偶数，当然越多越好），列成两队，面对面的坐在椅子上。

3、在“鸿沟”的一端，有一把空椅子，暂且把靠近这一端的队叫做队头。

4、要求两队只能通过空椅子这条路来交换位置，自己只允许两种行动方式，第一往前走一步，第二可以隔着对方跳一步。

A8 | A7 | A6 | A5 | A4 | A3 | A2 | A1 |
-------------------------------------- 鸿沟 | |
--------------------------------------
B8 | B7 | B6 | B5 | B4 | B3 | B2 | B1 |

A8 | A7 | A6 | A5 | A4 | A3 | A2 | A1 | -------------------------------------- 鸿沟 | | -------------------------------------- B8 | B7 | B6 | B5 | B4 | B3 | B2 | B1 |

那么第一步只有一种选择，A1或者B1有一个人去空位，然后下面的继续，按照规则，要达到这种最终状态：

B8 | B7 | B6 | B5 | B4 | B3 | B2 | B1 |
-------------------------------------- 鸿沟 | |
--------------------------------------
A8 | A7 | A6 | A5 | A4 | A3 | A2 | A1 |

B8 | B7 | B6 | B5 | B4 | B3 | B2 | B1 | -------------------------------------- 鸿沟 | | -------------------------------------- A8 | A7 | A6 | A5 | A4 | A3 | A2 | A1 |

可以走的规则如下，出现下面的两种情况A4可以行动，要么走要么跳，也就是走或者跳到空格，否则A4是动不了的。

| A4 | | A3|
 
| A4 | B3 | | A3 |

| A4 | | A3| | A4 | B3 | | A3 |

有兴趣的读者可以自己组织一些同学试试，会非常容易陷入迷茫的，走不下去了。当然不排除聪明的学员们能够很快的解决:-)

这道题老师想表达的是规则一部分是看得见的客观存在，另外一大部分是看不见的，总结其规律往往较为困难，但是我们应用尊重规则，这里面的道理可能很多人看不到，但是他是简单有效的，anyway，圆规正传，本文是解题：

如果你让1万人做这个游戏，你怎么用通俗的语言告诉每一个人规则，让他们怎么行动？

1、任意一方先行动，做到空椅子，行动权转移到另一方。

3、如果前面的前面是对方，或者前面全是自己人，或者前面就是终点了，则“贪婪地”往前走一步。

4、如果前面的前面是自己人，就别动了，交换行动权到对方的队头。

按照这种规则，我的算法放到了github上，具体演示见下面的gif图。

这道题目，重点在于总结这个行动的规则，并且用算法描述实现，大言不惭的说可以post到leetcode上了，看谁能解了，我的解法不一定最好，边界条件的判断非常多，需要小心处理。

算法入口如下，BigTrafficJam构造函数是两队人数加上空椅子的个数，所以是一个大于等于3的奇数，调用solve方法即可：

new BigTrafficJam(17).solve();
//new BigTrafficJam(17).setDebug(false).solve(); //用于打印中间状态的debug信息与否
//new BigTrafficJam(17).setPrintOutIntervalMs(1200).solve(); //如果打印debug信息，中间停顿的毫秒数

new BigTrafficJam(17).solve(); //new BigTrafficJam(17).setDebug(false).solve(); //用于打印中间状态的debug信息与否 //new BigTrafficJam(17).setPrintOutIntervalMs(1200).solve(); //如果打印debug信息，中间停顿的毫秒数

最后，还是回到《职业化研讨》这门课上，体会最深的一句管理的话就是“管理就是激发人善意的潜能”。

回调下另外读后感作者鲍老师的博文再谈大塞车游戏活动，证明了本文所述的最优解法，同时给出了模拟算法的时间复杂度为O(n^2)。