## 2018年11月8日木曜日

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

コード(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']

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 == flip:
if t == t:
print(f'Person at position {t} flip your cap!')
else:
print(
f'People in positions {t} through {t} flip your caps!'
)

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

```\$ ./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!

\$
```