記事の内容
「問題解決のPythonプログラミング 数学パズルで鍛えるアルゴリズム的思考法」という本を紹介します。
この本に載っているパズルを解きながら、楽しくアルゴリズムを学べる記事になります。
Python初心者の方にも、プログラミング初心者の方にもおすすめな記事です。
今回とくパズルは、「パーティーに行くタイミング」というパズルです。
パーティーに行くタイミング
有名人が集まるパーティーがある。それぞれの有名人がいる時間帯のリストは手に入っている。それでは、どの時間に行くのが最も有名人に会うことができるだろうか？
有名人A 6~7時
有名人B 7~9時
有名人C 10~11時
・・・というイメージだ。[ (6,8), (6,12), (6,7), (7,8), (7,10), (8,9), (8,10),(9,12), (9,10), (10,11), (10,12), (11,12) ]という有名人がいる時間帯のリストが分かっている。
押さえておきたい基礎
・タプル
・タプルのリスト
・入れ子forループ
・ソート
こういった基礎を知っているならば解けるパズルだ。
方針
素直に考えれば、各時刻について何人有名人がいるか順にチェックしていくというもの。この方針での実装は次の通り。
]sched = [ (6,8), (6,12), (6,7), (7,8), (7,10), (8,9), (8,10),(9,12), (9,10), (10,11), (10,12), (11,12) ] def celebrityDensity(sched, start, end): count = [0] * (end +1) #各時刻に何人いるかのリストを作るのが目標 for i in range(start , end + 1): count[i] = 0 for c in sched: if c[0] <= i and c[1] > i: #この式で一気に時刻 i にいる人を識別できる count[i] += 1 #countリストの時刻 i の部分を増やす return count def bestTimeToParty(schedule): #有名人が来る最初の時刻、有名人が帰る最後の時刻を求める start = schedule[0][0] end = schedule[0][1] for c in schedule: start = min(c[0], start) end = max(c[1], end) count = celebrityDensity(schedule, start, end) maxcount = 0 for i in range(start, end + 1): if count[i] > maxcount: maxcount = count[i] time = i print(time, maxcount)
改良版 方針
もっとシンプルに解く方法はないだろうか？そのためにも、コーディングする前に問題そのものの本質を考えてみるのがいい。そうして、簡単な形に読み替えることができる場合がある。
今回はどうだろう？
・有名人の滞在期間の開始時刻と終了時刻だけを調べればいい。
・有名人の滞在時刻を早い方からソートしておけば、順に時刻を増やしていくことで、その時刻にいる有名人の数をカウントできる。
def bestTimeToPartySmart(schedule): times =[] for c in schedule: times.append((c[0], 'start')) times.append((c[1], 'end')) sortList(times) maxcount, time = chooseTime(times) print(time, maxcount) #開始時刻を小さい順にソート def sortList(tlist): for ind in range(len(tlist)- 1): iSm = ind for i in range(ind, len(tlist)): if tlist[iSm][0] > tlist[i][0]: iSm = i tlist[ind], tlist[iSm] = tlist[iSm], tlist[ind] #その時刻に開始する場合はカウントし、その時刻に終了する場合は-1する。パーティに出るべき最良の時間は、誰か有名人が到着した時。 def chooseTime(times): rcount = 0 maxcount = time = 0 for t in times: if t[1] == 'start': rcount = rcount + 1 elif t[1] == 'end': rcount = rcount - 1 if rcount > maxcount: maxcount = rcount time = t[0] return maxcount, time
先に問題を処理しやすい状態にソートしておくという考え方は重要だと思う。だからこそ、何種類かある「ソート」のアルゴリズムには慣れておきたい。
さらに楽しみたい方は、ぜひ本書に進んでみてほしい。
