Algorithm - Python - 帽子を全員で揃える(命令のスキップ)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple
• Emacs (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の1章(帽子を全員で揃える)、練習問題、パズル問題3.を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3

caps0 = []
caps1 = ['F']
caps2 = ['F', 'F', 'B', 'B', 'B', 'F', 'B', 'B', 'B', 'F', 'F', 'B']
caps3 = ['F', 'F', 'B', 'H', 'B', 'F', 'B', 'B', 'B', 'F', 'H', 'F', 'F']
caps4 = ['H', 'F', 'B', 'H', 'B', 'F', 'B', 'B', 'F', 'H', 'F', 'F']
caps5 = ['F', 'F', 'B', 'H', 'B', 'F', 'B', 'B', 'F', 'H', 'F', 'H']


def please_conform(caps):
    n = len(caps)
    if n == 0:
        return
    start = 0
    forward = 0
    backward = 0
    intervals = []
    while True:
        if caps[start] != 'H':
            break
        start += 1
    for i in range(start + 1, n):
        if start < i and caps[start] != caps[i]:
            if caps[start] == 'F':
                forward += 1
            else:
                backward += 1
            if caps[i] != 'H':
                intervals.append((start, i - 1, caps[start]))
                start = i
            else:
                if i - 1 == start:
                    intervals.append((start, start, caps[start]))
                else:
                    intervals.append((start, i - 2, caps[start]))
                start = i + 1
    if start < n:
        intervals.append((start, n - 1, caps[start]))
        if caps[start] == 'F':
            forward += 1
        else:
            backward += 1
    print(f'forward = {forward}, backward = {backward}')
    if forward < backward:
        flip = 'F'
    else:
        flip = 'B'

    for t in intervals:
        if t[2] == flip:
            if t[0] == t[1]:
                print(f'Person at position {t[0]} flip your cap!')
            else:
                print(
                    f'People in positions {t[0]} through {t[1]} flip your caps!'
                )


for caps in [caps0, caps1, caps2, caps3, caps4, caps5]:
    print(caps)
    please_conform(caps)
    print()

入出力結果(Terminal, Jupyter(IPython))

$ ./sample3.py
[]

['F']
forward = 1, backward = 0

['F', 'F', 'B', 'B', 'B', 'F', 'B', 'B', 'B', 'F', 'F', 'B']
forward = 3, backward = 3
People in positions 2 through 4 flip your caps!
People in positions 6 through 8 flip your caps!
Person at position 11 flip your cap!

['F', 'F', 'B', 'H', 'B', 'F', 'B', 'B', 'B', 'F', 'H', 'F', 'F']
forward = 4, backward = 3
Person at position 2 flip your cap!
Person at position 4 flip your cap!
People in positions 6 through 8 flip your caps!

['H', 'F', 'B', 'H', 'B', 'F', 'B', 'B', 'F', 'H', 'F', 'F']
forward = 4, backward = 3
Person at position 2 flip your cap!
Person at position 4 flip your cap!
People in positions 6 through 7 flip your caps!

['F', 'F', 'B', 'H', 'B', 'F', 'B', 'B', 'F', 'H', 'F', 'H']
forward = 4, backward = 3
Person at position 2 flip your cap!
Person at position 4 flip your cap!
People in positions 6 through 7 flip your caps!

$