Pythonで数学パズル リストとタプルのちょっとした応用

記事の内容

今回の記事では、「問題解決のPythonプログラミング　数学パズルで鍛えるアルゴリズム的思考」という本で紹介されている簡単な数学パズルを解きたいと思う。

難易度も優しく、基礎的なコードを知っていれば楽しむことができる。
プログラミング初心者や、Python初心者も、楽しく取り組むことができるはずだ。

問題解決のPythonプログラミング　数学パズルで鍛えるアルゴリズム的思考

こちらの本から問題を引用させてもらう。

使う要素

・リスト

・タプル

・関数

・制御フロー（if、for）

基礎がわかればできる問題。

問題設定　1章　帽子を全員で揃える

一列に人が並んでいる。彼らは帽子のかぶり方のむきが2種類（前向きか後ろ向きか）ある。全員の帽子の向きを揃えたい。

できることは、次の命令のみ。

・i番目の人は帽子の向きを変えてください

・i番目からj番目の人は、帽子の向きを変えてください

どうすれば、命令回数を最小にすることができるか？

方針

帽子の向きが同じ人が続いている区間をリストにする。

区間は、前向き区間か後ろ向き区間かの2択しかない。

比べれば、どちらの区間の個数が少ないのかがわかる。少ない区間の向きを変えればいい。

区間は、（開始位置、終了位置、前向きか後ろ向きかのラベル）のタプルで表す。

解答

列はリストで表す。

cap1 = ['F', 'F', 'B', 'B', 'B', 'F', 'B', 'B','B', 'F','F', 'B', 'F' ]

def pleaseConform(caps):
  start = forward = backward = 0
  intervals = [] #区間タプルのリスト
  
  for i in range(1, len(caps)): #区間の計算
    if caps[start] != caps[i]: #今のstartから始まる区間はi-1まで
      intervals.append((start, i-1, caps[start])) #区間は、3つの値を持つタプル
      if caps[start] == 'F':
        forward += 1
      else:
        backward += 1
      start = i
      
  intervals.append((start, len(caps)-1, caps[start])) #最後の区間をループの外で追加
  if caps[start] == 'F':
        forward += 1
  else:
        backward += 1

  if forward < backward: #区間数が少ない方を記憶
    flip = 'F'
  else:
    flip = 'B'
  
  for t in intervals: #区間数が少ない区間の者へ命令
    if t[2] == flip: #t[2]は種類。forでタプルのリストも扱えるのかあ！！
      print ('People in positions', t[0], 'through', t[1], 'flip your caps!')

意外だったのが、for文でタプルのリストの中身まで取り出せること。リストの中身を取り出すのはよく使うと思うが、タプルの中身まで取り出すのはあまり経験がなかった。

さらに簡単に解けるか？

よくよく問題の設定を考えてみる。すると、前向き区間と後ろ向き区間の個数は１つしか違わない。ということは、列の最初の人の向きから始まる区間が前向きだとしたら、後ろ向き区間よりも、個数が同じか多くなる。

つまり、リストの先頭の帽子の向きとは異なる向きの区間に、変更命令を出せばいい。つまり、リストの最初を見れば、どちらの区間が少ないのか調べなくてもわかる。リストの一番目が「前向き」なら、「後ろ向き」区間の要素の向きを変えてやればいい。

先頭の区間をスキップして、再度実装。

def pleaseConformOnepass(caps):
  caps = caps + [caps[0]]
  for i in range(1, len(caps)):
    if caps[i] != caps[i-1]: #直前の要素と違う要素が出てきたら
      if caps[i] != caps[0]:
        print('People in positions', i, end= ' ')
      else:
        print(' through', i-1, 'flip your caps!')
  

このように、アルゴリズムに慣れるいい練習になる。問題も豊富なので、ぜひチャレンジしてみてほしい。

おすすめ記事

interaction.hatenadiary.jp
interaction.hatenadiary.jp
interaction.hatenadiary.jp
interaction.hatenadiary.jp