Thothの日誌

日々の活動や読んだ本について書き綴っていこうと思います

「パーティーに行くタイミング」を解いてみた

プログラミング

こちらの本の第2章「パーティーに行くタイミング」の練習問題及び、パズル問題の（自分なりの）解答を掲載します。
これよりも良い解答、誤りがございましたら指摘していただけると幸いです。

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

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

Amazon

前回はこちら


ちなみに下記のコードの関数には""" """で囲まれた文字列がありますが、これはdocstringというものでして、関数の説明文にあたる物になります。
help(func)で出力される文字列を埋め込むことができます。確か、Fluent Python によると作成した関数オブジェクトの__doc__属性に入れられたと思います。

練習問題１

ｻﾝﾌﾟﾙｺｰﾄﾞに自分がパーティに居られる時間の引数を追加してその時間内で会うことができる有名人の最大人数を出力する問題ですね。

from copy import deepcopy

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)]

sched2 = [(6.0, 8.0), (6.5, 12.0), (6.5, 7.0), (7.0, 8.0),
          (7.5, 10.0), (8.0, 9.0), (8.0, 10.0), (9.0, 12.0),
          (9.5, 10.0), (10.0, 11.0), (10.0, 12.0), (11.0, 12.0)]

# P23パズル問題３用
sched3 = [(6.0, 8.0, 2), (6.5, 12.0, 1), (6.5, 7.0, 2), (7.0, 8.0, 2),
          (7.5, 10.0, 3), (8.0, 9.0, 2), (8.0, 10.0, 1), (9.0, 12.0, 2),
          (9.5, 10.0, 4), (10.0, 11.0, 2), (10.0, 12.0, 3), (11.0, 12.0, 7)]

def your_time(sched, ystart, yend):
    """P22の問題①用"""
    count = [0] * (yend + 1)
    for i in range(ystart, yend):
        count[i] = 0
        for c in sched:
            if c[0] <= i and c[1] > i:
                count[i] += 1
    return count

def your_best_time(schedule, ystart, yend):
    """P22の問題１用"""
    count = your_time(schedule, ystart, yend)
    maxcount = 0
    for i in range(ystart, yend + 1):
        if count[i] > maxcount:
            maxcount = count[i]
            time = i
    print(f'{ystart}時から{yend}時までの場合、{time}時に{maxcount}人の有名人が来ています')

your_best_time(sched2, 5, 13)

出力が

5時から13時までの場合、8時に4人の有名人が来ています

練習問題２

別のやり方で有名人が最大になる時間帯を求める問題です。

def practice2(sched):
    """P22練習問題２用。有名人の滞在時間を順に選び、
他の有名人で滞在時間中にその選んだ有名人の開始時間を含むのが何人いるかを数える。
パーティーに行く時間は他の有名人が一番多くいる滞在時間の有名人の開始時間にする。
"""
    sorted_time = deepcopy(sched)
    sortlist(sorted_time)
    count_dict = {} # 人数: 開始時間の辞書
    max_count = 0
    for c in sorted_time: # タイムリストからセレブ一人を選ぶ
        count = 0
        check_list = deepcopy(sorted_time)
        check_list.remove(c) # 自分自身は除外する
        for t in check_list: # 他の有名人の滞在時間中に選んだセレブの開始時間を含むのが何人いるか
            if t[0] <= c[0] < t[1]:
                count += 1
        if count > max_count:
            max_count = count
        if count_dict.get(max_count, 0) == 0:
            count_dict[max_count] = c[0]

    print(f"""{count_dict[max_count]}時に行くと一番有名人が多くなり、{max_count + 1}人います""") # 選んだセレブも足すのでmax_count + 1

practice2(sched)

これの出力はｻﾝﾌﾟﾙｺｰﾄﾞでやっていたものと同様になります。

9時に行くと一番有名人が多くなり、5人います

パズル問題３

各有名人ごとにもどれだけ好ましいか、重みが付属されているものとして、その重みが最大になる時間帯を見つける問題です。

def bias(sched):
    """P23パズル問題用。
各有名人には重みがある為、重みが最大になる時間帯はいつになるかを判定する"""
    sorted_time = deepcopy(sched)
    sortlist(sorted_time)
    dignity_dict = {} # 重み: 開始時間の辞書
    dignity = 0
    count = 0
    max_count = 0
    for c in sorted_time: # タイムリストからセレブ一人を選ぶ
        count = c[2]
        check_list = deepcopy(sorted_time)
        check_list.remove(c) # 自分自身は除外する
        for t in check_list: # 他の有名人の滞在時間中に選んだセレブの開始時間を含むのが何人いるか
            if t[0] <= c[0] < t[1]:
                count += t[2]
        if count > dignity:
            dignity = count
        if dignity_dict.get(dignity, 0) == 0:
            dignity_dict[dignity] = c[0]
    print(f"""{dignity_dict[dignity]}時に行くと、最も威厳のある方々が来られます。
その重みの合計は{dignity}です""")

bias(sched3)

その出力が

11.0時に行くと、最も威厳のある方々が来られます。

その重みの合計は13です

次回↓
thothlog.hatenablog.com