昨天收到了奖品，2019 年限量版狼人杀。可惜只能和买了 8 年没拆封的《三国杀》放在一起——没人陪我玩。
我做完的时候，看到成功提交的数目是2，还一直以为自己是第二名，直到看到了“【可能是己亥年最有趣的比赛】最终排名&获奖名单公布”。可能在我之前的那个提交，就是官方出题人员的自验证吧。
单题排名
Q2: 狼人杀模拟器
以上三名选手每人将获得限量版狼人杀卡牌一套，出题老师说想和你们一起玩狼人杀～
我想对出题老师说，其实我不会玩《狼人杀》。当时审题就花了十几分钟，没想到能按时做出来。
一方面，我用的是 Python，而不是 C++ 或 Java。Python 的表现力，非常适合快速解决这类业务逻辑复杂、但总体复杂度不高的问题。54 人尝试却只有 6 人通过，估计大多是栽在了编程语言的选择上。C++ 和 Java 很适合做常规算法题，而不适合快速实现这种小项目 demo。
另一方面，应该是简洁的抽象。我看了一下官方题解：《【可能是己亥年最有趣的比赛】— 狼人杀模拟器》，也是 Python，接近 200 行，而我只用了 100 行出头。因为官方其实只做了两层抽象：主要流程，及其实现细节；而我则基本做到了 DRY。这种比速度的竞赛，少10行就是少很多，少 100 行……
分析
首先是设计数据结构。作为入参的 players 和 credibility 是不足以表达是否存活的。一种方案是把死人删除，但 players 可以删，credibility 却不行，因为死人的 credibility 也是有效信息，而二者是靠座位（下标）联系。我用的方案是 self.vils 和 self.wws 保存存活的村民与狼人的座位。这样，杀人就是删除元素，判断玩家存活 alive 和游戏结束条件 check 也比较方便实现。
其次是设计杀人的处理。晚上杀人是狼人杀村民 kill_vil，白天杀人是村民杀狼人 kill_wws（尽管可能杀错）。官方题解中，白天杀人是叫 vote，但不足以表达一种对称性。两种杀法，最终都会有共同操作，我定义为 kill，做真正的数据操作与公共处理。这当然不是一个好的设计，无论是从面相对象编程，还是从函数式编程的角度，但这种面向过程的简单设计，无论是思考还是实现都是最快的。
最后就是处理三种特殊情况。bear 是最麻烦的，要么死在第一天晚上，要么死在第二天晚上，而且还会有后期效果，影响 credibility；hunter 和 idiot 则简单多了，前者作用于 kill 中，后者作用于 kill_vil 中。hunter 杀人应该算第三种杀人，但基本可以复用 kill_ww，只是要处理 idiot 的情况——投票不能杀 idiot，而 hunter 可以。
如果换一个思维敏捷的高手，有《狼人杀》游戏经验以便于快速审题，并且用这个方法实现，应该可以在 1 小时内完成。
代码
class Solution:
def canVillagersWin(self, players: List[str], credibility: List[int]) -> bool:
self.players = players
self.creds = credibility
self.bear = players.index('bear')
self.vils = [i for i, player in enumerate(players) if player != 'ww']
self.wws = [i for i, player in enumerate(players) if player == 'ww']
self.bear_sides = None
for i in range(6):
for time in (self.night, self.day):
end, status = time(i)
if end:
return status
return False
def night(self, i):
if i == 1 and self.bear in self.vils:
self.kill(self.bear)
else:
self.kill_vil()
if i == 0:
self.bear_warn()
return self.check()
def day(self, _):
self.kill_ww()
return self.check()
def kill_vil(self):
index, cred = None, -math.inf
for i in self.vils:
if cred < self.creds[i]:
index, cred = i, self.creds[i]
self.creds[index] = 100
self.kill(index)
def kill_ww(self, hunter=False):
index, cred = None, math.inf
for i, j in enumerate(self.creds):
if self.alive(i) and cred > j:
index, cred = i, j
if not hunter and self.players[index] == 'idiot':
self.creds[index] = 100
self.bear_check(i)
else:
self.kill(index)
def kill(self, i):
if self.players[i] == 'ww':
self.wws.remove(i)
else:
self.vils.remove(i)
self.bear_check(i)
self.hunter_check(i)
def bear_warn(self):
if self.bear not in self.vils:
return
left = (self.bear - 1) % 12
if not self.alive(left):
left = (self.bear - 2) % 12
right = (self.bear + 1) % 12
if not self.alive(right):
right = (self.bear + 2) % 12
sides = (left, right)
warn = any(self.players[i] == 'ww' for i in sides)
if warn:
self.bear_sides = sides
for i in sides:
self.creds[i] //= 2
self.creds[i] = self.creds[i] or 1
else:
self.creds[left] = 100
self.creds[right] = 100
def bear_check(self, i):
if not self.bear_sides or i not in self.bear_sides or self.creds[i] != 100:
return
for j in self.bear_sides:
if j != i:
self.creds[j] = 0
def hunter_check(self, i):
if self.players[i] == 'hunter':
self.creds[i] = 100
self.bear_check(i)
self.kill_ww(hunter=True)
def check(self):
status = None
if not self.wws:
status = True
elif len(self.wws) >= len(self.vils):
status = False
if status is None:
return False, None
else:
return True, status
def alive(self, i):
return i in self.vils or i in self.wws我写的不是代码，而是寂寞。
