ある日ふと思いました。
プログラミングを用いて日常をもっと豊かにできないものかと。
と、いうことで企画しました。「Pythonで日常を解くシリーズ」、そのままですね。ただいま筆者がハマっているPythonで日常に起きうるあらゆる課題問題を解決、また最適化していこうというシリーズです。
記念すべき一発目はコインゲームについての問題に取り組んでいきたいと思います。
それでは行ってみましょう！
※この記事はPythonの基礎知識が必要となる場合があります。
問題定義
左から順番に0,1,2,…,13,14とそれぞれ番号が振られている15個のコインが表裏ランダムで横一列に並んでいる。この15個全てのコインの表裏を合わせたい(全て表または全て裏)。ここでコインを裏返していく際、隣あうコイン同士なら一気に裏返すことが可能とする。つまり0:表、1:裏、2:裏、3:表…..ならば1と2のコインを同時に表にできる。手数を一番少なくするにはどのように裏返していけばよいか。
思考
考察の前にまずコインの表裏をどのようにデータとして扱うか定義しましょう。
今回は表をHeadから’H’、裏をTailから’T’ とそれぞれ文字列として定義し、それらを15個要素を持つリストに格納することで表現しましょう。
coins = [‘H’, ‘T’, ‘H’, ‘H’, ‘T’, ‘T’, ‘H’, ‘T’, ‘T’, ‘H’, ‘H’, ‘H’, ‘T’, ‘H’, ‘H’]
と行った具合です。
案①
第一案はとりあえず単純に考えてみましょう。
１つ以上続いている’H’または’T’を何らかの形でシーケンス化できれば良さそうではないでしょうか。具体的に言いますと、
coins = [‘H’, ‘T’, ‘H’, ‘H’, ‘T’, ‘T’, ‘H’, ‘T’, ‘T’, ‘H’, ‘H’, ‘H’, ‘T’, ‘H’, ‘H’]
を左から‘H’/’T’/’H”H’/’T”T’/’H’/’T”T’/’H”H”H’/’T’/’H”H’と分割して１つのシーケンスとして管理するのです。そのシーケンスの’H’要素と’T’要素を比較した時少ない方を裏返せば15枚表裏揃いそうですね。
そのシーケンスですがただ単にタプルのリストとかにしてもいいですが何かと不便ですよね。
[('H'), ('T'), ('H', 'H'), ('T', 'T'), ('H'), ('T', 'T'), ('H', 'H', 'H'), ('T'), ('H', 'H')] #扱いずらい...そこでコインの表裏が同じ「区間」のリストを作ると考えましょう。リストのそれぞれの要素で開始位置、終了位置を管理することにします。それだけじゃそれが表なのか裏なのかわからないので’H’または’T’のラベルも忘れずに。そうすると最適なシーケンスは以下のようになるでしょう。
[(0, 0, 'H'), (1, 1, 'T'), (2, 3, 'H'), (4, 5, 'T'), (6, 6, 'H'), (7, 8, 'T'), (9, 11, 'H'), (12, 12, 'T'), (13, 14, 'H')] #多くの使える情報を持つ、便利！それでは上記のような区間のリストはどのように作るのでしょうか。ここで注目すべきはコインの表裏が変わった時、つまり別の区間が始まった時です。この転換点を判定してリストを作成していきましょう。
最後に作成した区間のリストの表向き区間の個数(ラベル’H’を持つ要素数)と裏向き区間の個数(ラベル’T’をもつ要素数)を計算して、区間集合の少ない方を選択し、表裏を変える命令をして終了です。今回の場合表向き区間が5つ、裏向き区間が4つなので裏向きのコインの表裏を変えるよう命令します。
大体のアルゴリズムはこんな感じでしょうか。それではコードにおこしていきましょう。
def flipCoins(coins):
start = head = tail = 0
intervals = []
count = 0
for i in range(1, len(coins)):
if coins[start] != coins[i]:
intervals.append((start, i-1, coins[start]))
if coins[start] == 'H':
head += 1
else:
tail += 1
start = i
intervals.append((start, len(coins)-1, coins[start]))
if coins[start] == 'H':
head += 1
else:
tail += 1
if head < tail:
flip = 'H'
else:
flip = 'T'
for t in intervals:
if t[2] == flip:
print(t[0], 'から', t[1], 'までのコインを裏返します')
count += 1
print(count, '手かかりました')
‘H’,’T’で構成されたリストを引数にとるflipCoins関数です。startは各区間が始まる位置(インデックス)、headは表向き区間の個数、tailは裏向き区間の個数をそれぞれ表します。
5〜12行目で区間のリストintervalsを作成しています。同時にhead,tailに区間の個数のカウントも行なっています(8〜11行目)。ここではstartが大きな役割を担っていて次の要素は自分と同じ向きなのかを判定し続けてくれるのです。そこで違えば区間のタプルが作られintervalsにappendされるわけです。
ここで一番最後の区間に注目してみてください。区間のタプルは次の要素(表裏)が今と違う時作られるのでした。でも最後なので次の要素がありません。そこで最後の区間をループの外で別途追加しなければなりません(13〜16行目)。
最後にheadとtailを比較し、少ない方を裏返すよう命令します。
このflipCoins関数を実際に呼び出してみましょう。
coinsA = ['H', 'T', 'H', 'H', 'T', 'T', 'H', 'T', 'T', 'H', 'H', 'H', 'T', 'H', 'H']
flipCoins(coinsA)1 から 1 までのコインを裏返します
4 から 5 までのコインを裏返します
7 から 8 までのコインを裏返します
12 から 12 までのコインを裏返します
4 手かかりました機構は上手く動きましたが「1から1までのコインを裏返します」は嫌ですね…。気になるので修正しましょう。flipCoins関数定義のコードの24,25行目を消して以下のコードを挿入します。
if t[0] == t[1]:
print(t[0], 'のコインを裏返します')
else:
print(t[0], 'から', t[1], 'までのコインを裏返します')
count += 11 のコインを裏返します
4 から 5 までのコインを裏返します
7 から 8 までのコインを裏返します
12 のコインを裏返します
4 手かかりました一件落着。引数変えて色々試してみてください。
案②
第一案では最後の区間は特別にループの外で追加しました。これはcoins[start]と異なるラベルが来て初めて区間を追加するためです。
それではcoinsの最後の要素にわざと異なるラベルを追加すればかなり良さそうです。
13〜17行目を削除し、4行目の後に新たに以下を追加します。
coins = coins + ['END']coins.append(‘END’)でもいいですがappendは既存のリストをそのまま変更してしまうので引数のリストcoinsAも変更されてしまいます。そこで新たに別にメモリを確保してリストを作成してくれるcoins = coins + [‘END’]を採用します。
これで要素を１つ追加したことでループが一回多くなります。一番最後のループのcoins[start] != coins[i] はcoins[start]が’H’であっても’T’であってもTrueになります。その時coins[i]は’END’なので。
これをすることによる”いいこと”はコード行数が短くなるだけではありません。実は第一案のプログラムでは引数が空リストの場合、13行目でcoins[start]で範囲外の要素にアクセスしていることになりエラーが出ます。第二案はcoinsに’END’を追加しているため引数coinsが空リストでもエラーが出なくなります。
改めてコードをかき直しましょう。
def flipCoins2(coins):
start = head = tail = 0
intervals = []
count = 0
coins = coins + ['END']
for i in range(1, len(coins)):
if coins[start] != coins[i]:
intervals.append((start, i-1, coins[start]))
if coins[start] == 'H':
head += 1
else:
tail += 1
start = i
if head < tail:
flip = 'H'
else:
flip = 'T'
for t in intervals:
if t[2] == flip:
if t[0] == t[1]:
print(t[0], 'のコインを裏返します')
else:
print(t[0], 'から', t[1], 'までのコインを裏返します')
count += 1
print(count, '手かかりました')coinsAを引数に渡して実行します。
1 のコインを裏返します
4 から 5 までのコインを裏返します
7 から 8 までのコインを裏返します
12 のコインを裏返します
4 手かかりましたちゃんと動きました。
案③
さて、このコインゲーム注目すべきある大きな特徴があります。それは表向き区間と裏向き区間の数は高々1つしか違わないのです。つまり先頭区間のラベルが表向きだった場合、表向き区間の個数が裏向き区間の個数より少ないことはあり得ません。逆も然りです。
現に引数にcoinsAを取った時、coinsAの先頭区間のラベルは’H’、つまり表向きのため結果的な区間の個数headが5、tailが4となっています。
これらから「先頭区間のラベルと逆の方向に裏返せばいい。」と言えます。最初の区間ラベルが’H’でhead+=1をしても最終的にheadはtailとせいぜい個数が同じになるだけでtailを裏返すことになるのでそれらのコードは取っ払っても構わないということです。
ということでこんなアルゴリズムはどうでしょう。
def flipCoins3(coins):
coins = coins + ['END']
count = 0
for i in range(1, len(coins)):
if coins[i] != coins[i-1]:
if coins[i-1] != coins[0]:
if start == i-1:
print(i-1, 'のコインを裏返します')
else:
print(start, 'から', i-1, 'までのコインを裏返します')
count += 1
start = i
print(count, '手かかりました')以前のプログラムでは区間のリストをループを回して作って、その後再びループを回して命令を表示していました。今回は区間のリストは作りません。「先頭区間のラベルと逆の方向に裏返せばいい」という隠れた決まりを見つけたのでそれを利用し１つのループで全てを解決しました。
2行目でcoinsに’END’を追加します。これは第二案で出てきた技です。
5行目で表裏が変わった転換点を見つけ出します。これは今までと同じですが6行目で転換点の1つ前の区間のラベルが先頭区間のラベルと一致しないかどうかを判定します。一致しない場合隠れた決まりに従いその区間を裏返します。
12行目で変数startに各区間の先頭位置を管理させているので、start == i-1つまり区間に１つしかコインがない場合と2つ以上持つ場合で命令の方法を分岐させています(7〜10行目)。
それでは実際に動かしてみましょう。今回は新たなリストcoinsBバージョンも動かします。
coinsA = ['H', 'T', 'H', 'H', 'T', 'T', 'H', 'T', 'T', 'H', 'H', 'H', 'T', 'H', 'H']
coinsB = ['T', 'T', 'H', 'T', 'H', 'T', 'T', 'H', 'H', 'T', 'H', 'H', 'T', 'H', 'T']
flipCoins3(coinsA)
print('----------------------')
flipCoins3(coinsB)1 のコインを裏返します
4 から 5 までのコインを裏返します
7 から 8 までのコインを裏返します
12 のコインを裏返します
4 手かかりました
----------------------
2 のコインを裏返します
4 のコインを裏返します
7 から 8 までのコインを裏返します
10 から 11 までのコインを裏返します
13 のコインを裏返します
5 手かかりましたちゃんと動きました。ゲームの本質を見極め攻略しアルゴリズムに取り入れることで以前のプログラムよりかなり簡略化されました。
最後に
今回はコインゲームを使っていかに情報を少なく命令ができるかということに挑戦していきました。コードとにらめっこしてアルゴリズムを考察するよりもゲームの仕組みと向き合い攻略法を見出していくことがとても重要だと感じましたね。いつか今回のような圧縮技術を本格的に学んでいきたいものです。
今回の「Pythonで”コインゲーム”を解く。-Pythonで日常を解くシリーズ-」、以上で終わりになります。ありがとうございました。
Pythonで日常を解くシリーズはこの「問題解決のPythonプログラミング」を大変参考にさせていただいています。Pythonを使いプログラミングにおけるアルゴリズム的思考を強化する良書です。読み物としてもピッタリなので是非チェックのほどよろしくお願いします。
 |
問題解決のPythonプログラミング 数学パズルで鍛えるアルゴリズム的思考 [ Srini Devadas ] 価格:3,024円 |
コメント