Tag Archives: Python

ハノイの塔を解く(Solving Towers of Hanoi)

ハノイの塔というのはパズルだが、リカージョンというアルゴリズムによくなじむのでプログラミングの教科書に出ていることがある。 自分がこれを見たのは”Oh Pascal!”というパスカルの入門書で30年くらい前に発行された学生向けの教科書だ。
パズルの内容はこんな具合。
1.3本の棒が立っている。仮にこれを右からA,B,Cとする。
2.Aには真ん中に穴のあいた円盤が積み上げてある。円盤の直径は底にあるものが一番大きく、上に行くほど小さくなる。
3.一度に一個ずつこのこの円盤を取り出して他の棒に移すことができる。最終的には全部の円盤をCに移したい。
4.ただし、大きな円盤を小さな円盤の上に置くことはできない。

Hanoiの塔というのはこの”金の”円盤を64枚積み上げたものだそうで、このパズルが解けたときには世の中が終焉を迎える、というオトロしい落ちがついている。

これをコンピュータープログラムを使って解くとどうなるか、という話である。 パターンを見つけるために少ない枚数で実際に解くことを試みる。
Disk(円盤)の数が一枚の時には簡単だ。円盤をAからCに移せばよい。

Move(1disk from A to C) = Move a Disk from A to C

では2枚の時にはどうなるか

Move(2disks from A to C) = 
 Move a Disk from A to B
 Move a Disk from A to C
 Move a Disk from B to C

ここで棒Bを使うことになる。 つまり、まず上の円盤を棒AからBに移し、下の円盤をAからCへ、最後にBに移してあった円盤をCに移して完成だ。

Move (2 disks from A to C) = Move (2 disks from A to C using B)

3枚はどうか。 すでに2枚を動かす方法はわかっているのその方法を使ってまずは2枚をBに動かしておき、最後の一枚をAからCに移動、さらに2枚を動かす方法を使ってBからCに移動するという方法で動かせる。

Move(3 disks from A to C using B) =
 Move(2 disks from A to B using C)
 Move a disk from A to C
 Move (2 disks from B to c using A)

4枚の場合も同様に考えられるのでパターンとしては (n-1)枚の円盤をAからBに移す。最後の円盤をAからCに移動し、その後(n-1)枚の円盤をBからCに移す。 ということになる。

Move (n disks from A to C using B) =
 if n>2 Move (n-1 disks from A to B using C)
 Move a disk from A to C
 if n>2 Move (n-1 disks from B to C using A)

このパタ-ンを使って関数を書くと、自分で自分自身を呼びだす関数になる。これがいわゆるRecursion と呼ばれるプログラムテクニックだがCでもPascalでもPHPでもいまどきのプログラムなら軒並みサポートされている。ただし普通のループに比べるとスタックにどんどん自分のコピーを積んでいくためメモリーを消費し、昔の8ビットパソコンでは何せRAMが32キロバイトあれば高級機、計算しているうちにメモリーが足りなくなる、なんてこともあったりして、Loopで記述できるものはRecursionをさける、というのが常識だった。
しかしながらこの記述の簡便さ、短さは感動ものである。今のパソコンはそんなにメモリを気にしなくてもよいので、改めて組んでみよう。
上のパターンは条件判定を何度も呼ぶことになるので少し工夫して

function Move (n, from, to , using) =
 if n=1 "Move a Disk from 'from' to 'to'"
else
 Move (n-1,from, using,to)
 "Move a Disk from 'from' to 'to'"
 Move (n-1,using, to, from)

というようなロジックを使うこととし、
Free Pascalで書いた例

program hanoi;
             {Recursively solve the towers of Hanoi problem.  Moves disks from A to C.
             The code from "Oh Pascal" by Doug Cooper}
var height:integer;
  procedure Move (Height: integer; FromPeg,ToPeg,UsingPeg:char);
  begin
    if Height = 1
    then writeln('Move disk from ', FromPeg,' to ',ToPeg)
    else begin
      Move (Height-1, FromPeg,UsingPeg,ToPeg);
      writeln('Move a disk from ',FromPeg,' to ',ToPeg);
      Move (Height-1,UsingPeg,ToPeg,FromPeg)
    end;
  end;

begin
  writeln('How Many disks are you going to start with?');
  readln(Height);
  Move (Height,'A','C','B');
  readln()
end.

C++で書いた例

#include < iostream >

using namespace std;
void move(int numberOfDisk, char fromPin,char toPin,char usePin);


int main() {
    int numberOfDisk;
    char fromPin = 'A',usePin='B',toPin='C';
    cout << "How many disk do you want to move from pin A to pin C?: " ;
    cin >> numberOfDisk;
    move (numberOfDisk,fromPin,toPin,usePin);

    return 0;
}
void move(int numberOfDisk, char fromPin,char toPin,char usePin) {
    if(numberOfDisk == 1) cout << "Move a Disk from "<< fromPin << " to " << toPin<< endl;
    else {
        move(numberOfDisk-1,fromPin,usePin,toPin);
        cout << "Move a Disk from " << fromPin << " to " << toPin << endl;
        move(numberOfDisk-1,usePin,toPin,fromPin);
    }

}

Pythonで書いた例

'''Towers of Hanoi'''
def move(numberOfDisk, fromPin, toPin, usingPin):
    if (numberOfDisk == 1):
        print ("Move a Disk from ",fromPin," to ",toPin)
    else:
        move(numberOfDisk-1,fromPin,usingPin,toPin)
        print ("Move a Disk from ",fromPin," to ",toPin)
        move(numberOfDisk-1,usingPin,toPin,fromPin)

if __name__ == '__main__':
    numberOfDisk = input("How many Disk would you like to move? ")
    move(int(numberOfDisk),'A','B','C')


Python で円盤の数を4とした場合の実行例


~ $ python3 hanoi.py
How many Disk would you like to move? 4
Move a Disk from  A  to  C
Move a Disk from  A  to  B
Move a Disk from  C  to  B
Move a Disk from  A  to  C
Move a Disk from  B  to  A
Move a Disk from  B  to  C
Move a Disk from  A  to  C
Move a Disk from  A  to  B
Move a Disk from  C  to  B
Move a Disk from  C  to  A
Move a Disk from  B  to  A
Move a Disk from  C  to  B
Move a Disk from  A  to  C
Move a Disk from  A  to  B
Move a Disk from  C  to  B

動かす回数は円盤の数が1の時は1、2の時は3、3の時は7、4の時は上の出力のように15となり、円盤の数がnのときは

2のn乗から1を引いた値

となる。枚数が多ければ多いほど全部のステップの数がどんどん大きくなっていく。
Python version で試してみると、手持ちのややくたびれたノートブックパソコンではステップの出力が終わるのに 円盤の数が23枚で30秒、24枚で1分、25枚で2分かかった。(下の出力結果参照)実行時間がここの調子で倍々で増えていくとすると入力が64枚のときに解法を出力するのに2の38乗の分がかかるということになるが、これを年に直すと、なんと52万年というとんでもない数字になる。 ので上のプログラムに64と入力しようものなら計算が終わらない。 なるほど、これでは世界が滅びるわけだ。

~ $ time echo 23 | python3 hanoi.py >/dev/null
real	0m29.308s
user	0m29.225s
sys	0m0.054s
~ $ time echo 24 | python3 hanoi.py>/dev/null
real	0m58.437s
user	0m58.237s
sys	0m0.122s
~ $ time echo 25 | python3 hanoi.py>/dev/null
real	1m55.068s
user	1m54.540s
sys	0m0.320s

Python、comprehension を使った一括処理

Pythonには” … for … in”という構文を使った、一括でメンバー要素を処理する機能がある。Comprehensionと呼ばれ、リスト、セット、辞書に使える。
リストの使用例

>>> a_list =list(range(10))
>>> a_list
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a_list = [x**2 for x in a_list]  --List comprehension
>>> a_list
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

If を使い、要素のFilteringをしてから処理することもできる。下はリスト中、偶数だけを処理して新しいリストを作成した例。 

>>> a_list = list(range(10))
>>> a_list = [x**2 for x in a_list if (x%2 ==0)]
>>> a_list
[0, 4, 16, 36, 64]

Python Dictionary の キーと値をスワップして新しい辞書を作る。

>>> week_dict={'Mon':'月','Tue':'火','Wed':'水','Thu':'木','Fri':'金','Sat':'土','Sun':'日'}
>>> youbi_dict={value:key for key,value in week_dict.items()}
>>> youbi_dict
{'木': 'Thu', '土': 'Sat', '月': 'Mon', '火': 'Tue', '水': 'Wed', '日': 'Sun', '金': 'Fri'}
>>> week_dict
{'Mon': '月', 'Fri': '金', 'Tue': '火', 'Sat': '土', 'Sun': '日', 'Wed': '水', 'Thu': '木'}
>>> week_dict['Fri']
'金'
>>> youbi_dict['日']
'Sun'

辞書は順番はキープしないのだ。

Python でテクストファイルを読み書きする。

With と For iterater を使うとファイルを明示的にクローズしないでもよいそうだ。
例題でやっているのはTest.txtというファイルから一行ずつ読み込んでリストを作成し、それをリストオブジェクトのSortedメソドで並び替えをしたのち、test2.txtというファイルに書き戻す、という作業。 なんか簡単にできるし(簡単だけど)、コメントを入れなくても読み解きやすい感じ。このあたりがPythonの強みか。

a_list=[]
with open("test.txt", mode="r",encoding='utf-8') as a_file:
     for a_line in a_file:
         a_list.append(a_line.rstrip())

a_list = sorted(a_list)

with open("test2.txt", mode="w", encoding='utf-8') as a_file:
    for a_line in a_list:
        a_file.write(a_line+'\n')

Pythonの関数定義とパラメーター

Python3 をいじっていく中で、気が付いたことをこのプログにぼちぼち書き留めておこうと思う。

Pythonの関数定義ではパラメーターも戻り値もタイプを指定しない。C++,Java,Pascalなどの知識のある学習者には異常に見えるが、Python は loosely typed language なんである。

>>> def foo(a,b,c):
	return a*100 + b*10 + c

>>> foo(3,2,1)
321

パラメーターに初期値を持たせることができる。 パラメーターを指定しない場合はその初期値が使用される。

>>> def bar(a=1, b=1, c=1):
	return a*100 + b*10 + c

>>> bar()
111
>>> bar(3)
311
>>> bar(3,4)
341
>>> bar(3,4,1)
341

さらにはパラメーターを明示すれば、カッコ内に現れる順序を気にする必要がなくなる。

>>> foo (a=5,c=2,b=1)
512
>>> bar(c=3,b=2)
123
>>> bar(c=9)
119
>>> bar(c=6,b=4,a=2)
246

Ruby と Python

どちらもInterpreter Languageだが、ひとつを選べと言われたらどちらを覚えたほうがよいのだろう。 
日本ではRubyがかなり人気があるようだが、WorldwideのUser BaseではPythonのほうが多い。 多いと言ってもPHPとかに比べるとかなり少ない。

Ruby

# Old "coke" program from 80's Basic programming book in Ruby
answer = Random.rand(1..100)
count,guess = 0,0
puts 'I am thinking about number between 1 and 100. Can you guess?'
while (answer != guess) 
  guess = gets.to_i
  count += 1
  if guess > answer 
     puts "#{guess} is too high"
  elsif guess < answer
     puts "#{guess} is too low"
  else 
    puts "you got it right in #{count} try!"
  end
end

Python

"""Old "coke" program from 80's Basic programming book, in Python"""
import random
answer = random.randrange(1,100)
print ("I am thinking a number between 1 and 100. Hope you can guess")
guess, count = 0,0
while (answer != guess ):
    guess = input ("what number am I thinking? ")
    guess = int(guess)
    count += 1
    if answer < guess:
        print ( guess, " is too high, try again")
    elif answer > guess:
        print ( guess," is too low. Try again")
    else:
        print ("Bingo! you guessed it right in ",count," tries!")

とりあえず調べて見えてきた部分で大昔、Basicで初期に書いた練習用プログラムを移植してみたが、ごらんのとおり、これくらいのサイズのプログラムなら、どちらで書いてもほとんど差がない。言語のパワフルなところを使ってみないとその差がわからない、という感じだが、 ルーズに行くならPythonかな?インデントでブロックを明示している、つまり単なる書式ではなく、言語の一部になっているのが、なんとも割り切っているところ。 これで{}も"End"も必要ない。 個人的には好きである。 どちらの言語も読み解きやすいのはまちがいなく、これをC++ で書こうとすると、

#include <iostream>
#include <cstdlib> //need this to use rand() 
#include <ctime> //need this to use time() 
using namespace std;

int main(){
    int answer, guess=0, count=0;
    srand(time(NULL));
    answer = rand()%100 + 1;
    cout << "I am thinking about the number between 1 and 100. Can you guess?";
    while (guess != answer) {
        ++count;
        cin >> guess;
        if (guess > answer) 
            cout << guess << "is too high";
        else if (guess < answer) 
            cout << guess << "is too low";
        else
            cout <<"You have it right in " << count << "  times!";
        cout << endl;
                    
    }
    return 0;
}

これよりは楽ですよ。