Below [Tower of Hanoi-Wikipedia](http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1% From 94)
Complete if you can move all the disks to the rightmost stake according to the following rules.
- Consists of three stakes and multiple discs of different sizes with a hole in the center.
- Initially, all the disks are stacked on the leftmost stake in order, with the smaller ones on top.
- You can move a disc to one of the stakes one at a time, but you cannot put a large disc on top of a small one.
--The direction of turning the stakes of each disk alternates
--The recursive code is a process that repeats the movement of three disks (n, n-1, n-2) in a certain phase.
--The non-recursive code is a process that repeats the movement while judging whether or not the disk can be moved by using the feature that the movement directions of the disks alternate.
--The number of moves is 2 ^ n --1
# coding: utf-8
def hanoi(disk_number, f, t, w, tower_dict):
if disk_number > 0:
hanoi(disk_number-1, f, w, t, tower_dict)
tower_dict[t].insert(0, tower_dict[f].pop(0))
print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
hanoi(disk_number-1, w, t, f, tower_dict)
if __name__ == '__main__':
disk_number = int(input())
tower_dict = {'left': [i for i in range(1, disk_number+1)], 'center': [], 'right': []}
print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
hanoi(disk_number, 'left', 'right', 'center', tower_dict)
def hanoi(tower_list, pile_list, disk_number):
cnt = 0
passed_list = [tower_list[:]]
while True:
for disk in range(1, disk_number+1):
#If the current disk is not on the top of the stake, move to the next disk
if tower_list.index(tower_list[disk-1]) != disk-1:
continue
idx = pile_list.index(tower_list[disk-1])
#Clockwise-> center -> right -> left ...Turn in the order of)
if (disk_number % 2 == 0 and disk % 2 == 1) or (disk_number % 2 == 1 and disk % 2 == 0) :
if idx+1 >= len(pile_list):
idx = -1
if pile_list[idx+1] not in tower_list or tower_list.index(pile_list[idx+1]) > disk-1:
tower_list[disk-1] = pile_list[idx+1]
passed_list.append(tower_list[:])
cnt += 1
#Counterclockwise-> right -> center -> left ...Turn in the order of)
else:
if 0 >= idx:
idx = len(pile_list)
if pile_list[idx-1] not in tower_list or tower_list.index(pile_list[idx-1]) > disk-1:
tower_list[disk-1] = pile_list[idx-1]
passed_list.append(tower_list[:])
cnt += 1
if tower_list == ['r'] * disk_number:
return cnt, passed_list
if __name__ == '__main__':
disk_number = int(input())
pile_list = ['l', 'c', 'r']
tower_list = ['l'] * (disk_number)
cnt, passed_list = hanoi(tower_list, pile_list, disk_number)
print(passed_list)
# coding: utf-8
import unittest
class HanoiTest(unittest.TestCase):
def setUp(self):
self.pile_list = ['l', 'c', 'r']
def test_first(self):
disk_number = 3
tower_list = ['l'] * (disk_number)
cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
self.assertEqual(cnt, 2 ** disk_number - 1)
self.assertEqual(passed_list, [
['l', 'l', 'l'],
['r', 'l', 'l'],
['r', 'c', 'l'],
['c', 'c', 'l'],
['c', 'c', 'r'],
['l', 'c', 'r'],
['l', 'r', 'r'],
['r', 'r', 'r']
])
def test_second(self):
disk_number = 4
tower_list = ['l'] * (disk_number)
cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
self.assertEqual(cnt, 2 ** disk_number - 1)
self.assertEqual(passed_list, [
['l', 'l', 'l', 'l'],
['c', 'l', 'l', 'l'],
['c', 'r', 'l', 'l'],
['r', 'r', 'l', 'l'],
['r', 'r', 'c', 'l'],
['l', 'r', 'c', 'l'],
['l', 'c', 'c', 'l'],
['c', 'c', 'c', 'l'],
['c', 'c', 'c', 'r'],
['r', 'c', 'c', 'r'],
['r', 'l', 'c', 'r'],
['l', 'l', 'c', 'r'],
['l', 'l', 'r', 'r'],
['c', 'l', 'r', 'r'],
['c', 'r', 'r', 'r'],
['r', 'r', 'r', 'r']
])
def test_third(self):
disk_number = 5
tower_list = ['l'] * (disk_number)
cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
self.assertEqual(cnt, 2 ** disk_number - 1)
self.assertEqual(passed_list, [
['l', 'l', 'l', 'l', 'l'],
['r', 'l', 'l', 'l', 'l'],
['r', 'c', 'l', 'l', 'l'],
['c', 'c', 'l', 'l', 'l'],
['c', 'c', 'r', 'l', 'l'],
['l', 'c', 'r', 'l', 'l'],
['l', 'r', 'r', 'l', 'l'],
['r', 'r', 'r', 'l', 'l'],
['r', 'r', 'r', 'c', 'l'],
['c', 'r', 'r', 'c', 'l'],
['c', 'l', 'r', 'c', 'l'],
['l', 'l', 'r', 'c', 'l'],
['l', 'l', 'c', 'c', 'l'],
['r', 'l', 'c', 'c', 'l'],
['r', 'c', 'c', 'c', 'l'],
['c', 'c', 'c', 'c', 'l'],
['c', 'c', 'c', 'c', 'r'],
['l', 'c', 'c', 'c', 'r'],
['l', 'r', 'c', 'c', 'r'],
['r', 'r', 'c', 'c', 'r'],
['r', 'r', 'l', 'c', 'r'],
['c', 'r', 'l', 'c', 'r'],
['c', 'l', 'l', 'c', 'r'],
['l', 'l', 'l', 'c', 'r'],
['l', 'l', 'l', 'r', 'r'],
['r', 'l', 'l', 'r', 'r'],
['r', 'c', 'l', 'r', 'r'],
['c', 'c', 'l', 'r', 'r'],
['c', 'c', 'r', 'r', 'r'],
['l', 'c', 'r', 'r', 'r'],
['l', 'r', 'r', 'r', 'r'],
['r', 'r', 'r', 'r', 'r']
])
Tower of Hanoi-Wikipedia Capture the Tower of Hanoi Solving the Tower of Hanoi by recursion
Recommended Posts