大塞车游戏活动的算法解

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

解的代码用Java实现,并配有演示,已经放到了github上https://github.com/neoremind/big-traffic-jam-solver
 
首先感谢李培英老师,《职业化研讨》这门课非常值得公司内的一线管理人员去学习。在讲到职业化内涵里的“规则意识”一节时,让大家做了一个简单的大塞车游戏,规则如下:
 
1、邀请10人以上的学员(注意是偶数,当然越多越好),列成两队,面对面的坐在椅子上。
2、中间叫做“鸿沟”,是不允许越过的。
3、在“鸿沟”的一端,有一把空椅子,暂且把靠近这一端的队叫做队头。
4、要求两队只能通过空椅子这条路来交换位置,自己只允许两种行动方式,第一往前走一步,第二可以隔着对方跳一步。
 
例如,分为A,B两队,每队8人,初始状态如下:
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 |
可以走的规则如下,出现下面的两种情况A4可以行动,要么走要么跳,也就是走或者跳到空格,否则A4是动不了的。
| A4 |    | A3|
 
| A4 | B3 |   | A3 |
有兴趣的读者可以自己组织一些同学试试,会非常容易陷入迷茫的,走不下去了。当然不排除聪明的学员们能够很快的解决:-)
 
这道题老师想表达的是规则一部分是看得见的客观存在,另外一大部分是看不见的,总结其规律往往较为困难,但是我们应用尊重规则,这里面的道理可能很多人看不到,但是他是简单有效的,anyway,圆规正传,本文是解题:
 
如果你让1万人做这个游戏,你怎么用通俗的语言告诉每一个人规则,让他们怎么行动?
 
我总结的规律如下:
1、任意一方先行动,做到空椅子,行动权转移到另一方。
2、如果前面是对方,则跳过去。
3、如果前面的前面是对方,或者前面全是自己人,或者前面就是终点了,则“贪婪地”往前走一步。
4、如果前面的前面是自己人,就别动了,交换行动权到对方的队头。
 
按照这种规则,我的算法放到了github上,具体演示见下面的gif图。
 
每队1人:
每队2人:
每队3人:
每队4人:
每队5人:
这道题目,重点在于总结这个行动的规则,并且用算法描述实现,大言不惭的说可以post到leetcode上了,看谁能解了,我的解法不一定最好,边界条件的判断非常多,需要小心处理。
 

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

new BigTrafficJam(17).solve();
//new BigTrafficJam(17).setDebug(false).solve(); //用于打印中间状态的debug信息与否
//new BigTrafficJam(17).setPrintOutIntervalMs(1200).solve();  //如果打印debug信息,中间停顿的毫秒数
最后,还是回到《职业化研讨》这门课上,体会最深的一句管理的话就是“管理就是激发人善意的潜能”。
 
转载请注明转自neoremind.com
 
附录:
回调下另外读后感作者鲍老师的博文再谈大塞车游戏活动,证明了本文所述的最优解法,同时给出了模拟算法的时间复杂度为O(n^2)。

1 Comment on this Post.

  1. 我这里有个思路:
    第一阶段:将AAAAAAAAA……A*B……BBBBBBBBB经过特定步骤后转化为*BABABABA………BA或者BABABA…….BA*
    第二阶段:将第一阶段的结果经过特定步骤后转化为BBBBBBBBBBB……B*A……AAAAAAAAA
    两阶段整体的思路都类似于数学归纳法,或者计算机上讲也可以叫分治。
    先讲第一阶段,通俗点用数学归纳法的步骤:
    1. 初始状态AAAAAAAAAA……A*B……BBBBBBBBBB,A向右走一步,然后B向左跳过A,变成了AAAAAAAAA……ABA*B……BBBBBBBBB
    2. 若中间状态为AAAAAA……ABABABA……BA*B……BBBBBB,则B向左一步后,左边的A都向右跳过来,变成了AAAAAA……A*BABABA……BAB……BBBBBB,其中,BA对组合多了一对;
    3. 若中间状态为AAAAAA……A*BABABA……BAB……BBBBBB,则A向右一步后,右边的B都向左跳过来,变成了AAAAAA……ABABABA……BA*B……BBBBBB,其中,BA对组合多了一对;
    4. 不断重复2、3过程,最终可以达到第一阶段的两种情况之一;
    第二阶段其实是第一阶段反操作的过程,仔细推敲下也能从理论上证明出来,不再详述

Leave a Comment.