「帽子を全員で揃える」を解いてみる

オライリーの本でPythonを用いてアルゴリズムについて学べるものがあったのでやってみました。

作者:Srini Devadas
オライリー・ジャパン

全部で21もの単元があるのでかなりやりごたえのある本でした。
今回は1章の「帽子を全員で揃える」の練習問題をやってみました。

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

cap2 = ['F','F','B','B','B','F','B',
        'B','B','F','F','F','F']

cap3 = 'F F B H B F B B B F H F F'.split() # これでもリストを作成できます

def change(caps):
    """
Fは前向き、Bは後ろ向き。
列の中で帽子の向きが変わっていたら向きを変えるように指摘する
P12の問題１の答え
"""
    start = 0
    forward = 0
    backward = 0
    intervals = []
    for i in range(1, len(caps)):
        if caps[start] != caps[i]:
            intervals.append((start, i - 1, caps[start]))
            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:
            if t[0] == t[1]:
                print(F'{t[0]}のポジションの人は帽子の向きを変えてください')
            else:
                print(F'{t[0]}から{t[1]}のポジションの人は帽子の向きを変えてください')

def onepass_change2(caps: list) ->None:
    """これがP12の問題２の答え"""
    if len(caps) > 0:
        caps = caps + [caps[0]]
    else:
        return
    for i in range(1, len(caps)):
        if caps[i] != caps[i-1]:
            if caps[i] != caps[0]:
                print(f'{i}のポジションの人', end='')
                start = i
            else:
                end = i - 1
                if start - end == 0:
                    print('は帽子を変えてください')
                else:
                    print(F"から{i-1}のポジションの人は帽子の向きを変えてください")

def ignore_change(caps):
    """
P12の問題3用
Hは帽子をかぶってない人を表す。Hの人は無視して行う
"""
    start = 0
    forward = 0
    backward = 0
    intervals = []
    for i in range(1, len(caps)):
        if caps[start] != caps[i]:
            intervals.append((start, i - 1, caps[start]))
            if caps[start] == 'F':
                forward += 1
            elif caps[start] == 'B':
                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:
            if t[0] == t[1]:
                print(F'{t[0]}のポジションの人は帽子の向きを変えてください')
            else:
                print(F'{t[0]}から{t[1]}のポジションの人は帽子の向きを変えてください')

if __name__ == '__main__':
    change(cap1)
    print()
    onepass_change2(cap1)
    print()
    ignore_change(cap3)

見やすくなるように各解答の間に空白を出力させました。
その出力がそれぞれ、



2から4のポジションの人は帽子の向きを変えてください

6から8のポジションの人は帽子の向きを変えてください

11のポジションの人は帽子の向きを変えてください



2のポジションの人から4のポジションの人は帽子の向きを変えてください

6のポジションの人から8のポジションの人は帽子の向きを変えてください

11のポジションの人は帽子を変えてください



2のポジションの人は帽子の向きを変えてください

4のポジションの人は帽子の向きを変えてください

6から8のポジションの人は帽子の向きを変えてください

のようになります。

Thothの日誌

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

「帽子を全員で揃える」を解いてみる