2018年12月16日日曜日

Algorithm - Python - ひねりを加えたバラモンの塔(円環型ハノイの塔、制約(時計回り、反時計回り)、再帰的に1つ減らして探索)

コード(Emacs)

Python 3

```#!/usr/bin/env python3

def hanoi(ring_number: int, origin: int,
peg1: int, peg2: int, peg3: int) -> int:
num_moves = 0
if ring_number > 0:
num_moves += hanoi(ring_number - 1, origin, peg1, peg3, peg2)
print(
f'Move ring {ring_number + origin} from peg {peg1} to peg {peg3}')
num_moves += 1
num_moves += hanoi(ring_number - 1, origin, peg2, peg1, peg3)
return num_moves

def hanoi1(ring_number: int, peg1: int, peg2: int, peg3: int, peg4: int) -> int:
num_moves = 0
if ring_number > 0:
num_moves += hanoi1(ring_number - 2, peg1, peg3, peg4, peg2)
print(f'Move ring {ring_number - 1} from peg {peg1} to peg {peg3}')
num_moves += 1
print(f'Move ring {ring_number} from peg {peg1} to peg {peg4}')
num_moves += 1
print(f'Move ring {ring_number - 1} from peg {peg3} to peg {peg4}')
num_moves += 1
num_moves += hanoi1(ring_number - 2, peg2, peg1, peg3, peg4)
return num_moves

def hanoi_four_peg(ring_number: int,
peg1: int, peg2: int, peg3: int, peg4: int) -> int:
num_moves = 0
if ring_number > 0:
num_moves += hanoi1(ring_number // 2, peg1, peg2, peg3, peg4)
num_moves += hanoi(ring_number // 2, ring_number // 2,
peg1, peg2, peg3)
num_moves += hanoi1(ring_number // 2, peg4, peg1, peg2, peg3)
return num_moves

def clockwise(ring_number: int, start_peg: int) -> int:
num_moves = 0
if ring_number > 0:
end_peg = start_peg % 3 + 1
other_peg = 6 - start_peg - end_peg
num_moves += counterclockwise(ring_number - 1, start_peg)
print(f'Move ring {ring_number} from peg {start_peg} to peg {end_peg}')
num_moves += 1
num_moves += counterclockwise(ring_number - 1, other_peg)
return num_moves

def counterclockwise(ring_number: int, start_peg: int) -> int:
num_moves = 0
if ring_number > 0:
other_peg = start_peg % 3 + 1
end_peg = 6 - start_peg - other_peg
num_moves += counterclockwise(ring_number - 1, start_peg)
print(
f'Move ring {ring_number} from peg {start_peg} to peg {other_peg}')
num_moves += 1
num_moves += clockwise(ring_number - 1, end_peg)
print(
f'Move ring {ring_number} from peg {other_peg} to peg {end_peg}')
num_moves += 1
num_moves += counterclockwise(ring_number - 1, start_peg)

return num_moves

def hanoi_ring(n: int) -> int:
num_moves = clockwise(n, 1)
return num_moves

if __name__ == '__main__':
num = hanoi_ring(3)
print(num, num == 15)
```

```\$ ./sample3.py
Move ring 1 from peg 1 to peg 2
Move ring 1 from peg 2 to peg 3
Move ring 2 from peg 1 to peg 2
Move ring 1 from peg 3 to peg 1
Move ring 2 from peg 2 to peg 3
Move ring 1 from peg 1 to peg 2
Move ring 1 from peg 2 to peg 3
Move ring 3 from peg 1 to peg 2
Move ring 1 from peg 3 to peg 1
Move ring 1 from peg 1 to peg 2
Move ring 2 from peg 3 to peg 1
Move ring 1 from peg 2 to peg 3
Move ring 2 from peg 1 to peg 2
Move ring 1 from peg 3 to peg 1
Move ring 1 from peg 1 to peg 2
15 True
\$
```