プログラミングパズルをPythonで解いてみた
プログラミングパズル¶
プログラムで解く数学パズル: 囚人とスイッチの部屋の問題 - 解答の自動チェックのしくみの記事で見つけた問題を解いてみました。クラスの作成の良い練習になったと思います。
問題¶
あなたは100人の囚人の一人です. 全員で以下のようなゲームをして, 見事勝利できれば全員釈放, 負ければ全員死刑となります.
ゲーム開始と同時に全員別々の独房に入ります
- 独房内や通路で他の囚人とやりとりすることはできません
ランダムに1人ずつスイッチの部屋に呼ばれます
十分な時間待てば同じ人が何度でも呼ばれます
いま誰が呼ばれているかは本人以外にはわかりません
部屋にはスイッチが2つ(AとB)ある以外はなにもありません
ゲームに参加中の囚人以外がこの部屋に入ることはありません
スイッチの部屋では以下のことができます
2つあるスイッチのon/offの状態を確認する
2つあるスイッチのいずれか, もしくは両方のon/offを切り替える
囚人はいつでも「全員スイッチの部屋に入った!」と宣言することができます
本当であれば勝利となります
まだ一度も部屋に入っていない人がいたらその時点で負けです
ゲーム開始時点でのスイッチの状態はランダムに決められます
ゲームを開始する前に, 囚人全員で集まって作戦を立てることができます. 必ず勝利できる作戦を考えてください.
答えがわかって物足りなければ以下についても考えてください.
スイッチの部屋に入った総回数(の期待値)がなるべく少なくなるような作戦を立ててください
スイッチを1つしか使わずに勝利する方法を考えてください
作戦¶
この問題を以下の作戦で解きました。
- ゲームの終了を宣言する囚人を一人決める。
- スイッチ二つで0から3までの整数と対応させる。
- 宣言者は以下のように行動する。
- 部屋に入るたびにスイッチを一つ加算させる。3だった場合は0にする。
- 以前自分が入出したときのスイッチから増えていたら、以前入室したときのスイッチとの差をカウントする。 *このとき、スイッチを0に戻すか戻さないかのいずれかの操作が考えられる。今回はそれぞれの比較も行った。
- カウントが99になった時点でゲーム終了を宣言する。
- 宣言者以外は以下のように行動する。
- 以前自分が入室したときのスイッチから減少していたらswitchを一つ加算させる。
- switchの加算は一度だけする。
以上の作戦で確実に勝利することができるはずです。間違っていたら教えてください・・・
コード¶
以下にコードを書きます。まずは、必要なスイッチ(Switch)、囚人(Prisoner)、宣言者(Declarator)のクラスを作ります。
In [1]:
import random
import statistics as stat
import matplotlib.pyplot as plt
In [2]:
class Switch():
"""
switchの挙動をするクラス。
switchの数が一つの場合の問題も解けるように、switchの数を指定する引数を与えた。
インスタンスの初期化メソッドでスイッチの初期状態をランダムに選んでstatusアトリビュートに登録。
turn()メソッドはスイッチを一つ加算させる。
initialize()は宣言者がswitchの加算を認識した際に、switchの状態を0に戻す。（この操作はあってもなくてもゲームには勝てる。正直、これをやったからと言って早くなるかは確信はない。）
"""
def __init__(self, switch_num):
self.switch_num = switch_num
self.status = random.choice([i for i in range(2**(switch_num))])
def turn(self):
self.status = (self.status + 1) % (2**(self.switch_num))
def initialize(self):
self.status = 0
In [3]:
class Prisoner():
"""
宣言者以外の囚人のクラス。
flagはswitchの加算を行ったことを管理する。
strategy()で上記の戦略を実行する。
"""
def __init__(self):
self.flag = 0
self.switch = None
def strategy(self, switch, switch_num):
if self.switch == None: # 初めて入室するときにスイッチの状態を記憶する。
self.switch = switch.status
else:
if self.switch > switch.status and self.flag == 0: # 以前入室したときに記憶したスイッチの状態よりもスイッチの状態が減少していて、かつflagが立っていなければ
switch.turn() # スイッチを一つ加算し、
self.flag += 1 # flagを立てて二度とスイッチを操作しないようにする。
self.switch = switch.status
In [4]:
class Declarator():
"""
宣言者のクラス。
counterでスイッチの増加を管理する。
strategy()で上記の戦略を実行する。
"""
def __init__(self, initalize):
self.counter = 0
self.initialize = initalize
self.switch = None
def strategy(self, switch, switch_num):
if self.switch == None: # 初めて入室するときにスイッチを記憶する。
self.switch = switch.status
if switch.status - self.switch == 0: # 以前入室したときに記憶したスイッチと比べて部屋のスイッチの状態が増加していないときのスイッチの操作。
switch.turn() # 宣言者は入室するたびにスイッチを加算する。
self.switch = switch.status
else: # 以前入室したときに記憶したスイッチの状態よりもスイッチが増加していた時の操作。
self.counter += switch.status - self.switch # その差をcountに加算する。
if self.initialize: # initializeの指定に応じて
switch.initialize() # switchを初期化する。
self.switch = switch.status
else: # initialize=Falseのときはスイッチを0にしないで
switch.turn() # 宣言者はスイッチを加算する。
self.switch = switch.status
さて、以上のクラスの下、実際に以下の関数でゲームをさせることにします。入室回数をカウント返すようにしました。
In [5]:
def play_game(switch_num, prisoner_num, initialize = True):
entry_counter = 0
prisoners = []
declarator = Declarator(initialize)
prisoners.append(declarator)
for i in range(prisoner_num-1):
prisoners.append(Prisoner())
switch = Switch(switch_num)
while True:
entry_counter += 1
entry = random.choice(prisoners)
entry.strategy(switch, switch_num)
if type(entry) == Declarator:
if entry.counter == prisoner_num-1:
break
return entry_counter
以下の関数で指定した回数のゲームをやらせて、入室回数の平均と標準偏差を出してみました。
In [6]:
def game_sim(play_game, switch_num, prisoner_num, simNum, initialize=False):
entory_counter_list = []
for i in range(simNum):
entory_counter_list.append(play_game(switch_num, prisoner_num, initialize))
plt.hist(entory_counter_list)
entory_mean = stat.mean(entory_counter_list)
entory_stdev = stat.stdev(entory_counter_list)
print(f'mean: {entory_mean}')
print(f'stdev: {entory_stdev}')
まず、
initialize=Falseの作戦でゲームをやってみました。In [7]:
game_sim(play_game, 2, 100, 4000, initialize=False)
次に、
initialize=Trueの作戦でゲームをやってみました。In [8]:
game_sim(play_game, 2, 100, 4000, initialize=True)
どうやらinitialize=Trueの作戦の方が少しだけ優秀だったそうです。おそらく、初期化をする方が、宣言者以外の囚人がスイッチを増加させる機会を増やすことができるからでしょう。
これ期待値の計算はどうやるんだろう・・・だれか計算出来たら教えてください。
ちなみに、スイッチ一個の時は約1.1万回ほどでゲームが終わるそうです。
In [9]:
game_sim(play_game, 1, 100, 4000)
おまけ¶
スイッチの数が多ければもっと早く終わるんじゃ？と安直に思ってはいけないようです。どうやら、これは、宣言者がスイッチを増加させ続け、初めて0に戻るまでの回数が増えるため、他の囚人がスイッチを押せるのが結果として遅くなってしまうためです。100人の囚人の場合はスイッチが4つの時に最も早くゲームが終わるようです。うーん、味わい深い。
In [10]:
game_sim(play_game, 3, 100, 4000, initialize=True)
In [11]:
game_sim(play_game, 4, 100, 4000, initialize=True)
In [12]:
game_sim(play_game, 5, 100, 4000, initialize=True)
In [13]:
game_sim(play_game, 6, 100, 4000, initialize=True)
- 作者: Bill Lubanovic,斎藤康毅,長尾高弘
- 出版社/メーカー: オライリージャパン
- 発売日: 2015/12/01
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (3件) を見る
