日本語プログラミング言語「プロデル」でデータ構造とアルゴリズムに挑戦する
『日本語でプログラムを作りたい』
そんなシンプルな希望を実現するために、もうひとつの日本語プログラミング言語「プロデル」を開発しています。
プロデルは、例えば初心者向けとか教育用とか事務処理用とかと言った特定の用途に限定されないオブジェクト指向のプログラミング言語です。
プロデルは、プログラムを日本語で書くこと以外は、他のプログラミング言語と大きく変わりません。つまり日本語プログラミングであっても、プログラミングに必要である、データ構造やアルゴリズム、オブジェクト指向といった概念が変わることはありません。
今回は、プロデルでデータ構造とアルゴリズムに挑戦してみたいと思います。
アルゴリズムの話題では、特に有名な「ハノイの塔」の答えを探して、解法をアニメーションで描画するプログラムを作ってみます。
ハノイの塔とは
ハノイの塔とは、パズルの一種です。最初は、3つある棒(杭)のうち一番左の棒に、幅の違う円盤が下から大きい順に積み重なっている状態となっています。この状態から円盤を1枚ずつ移動して、一番右の棒へ最初と同じ順番に積み重なるようにすることがゴールです。
ルールとして、円盤を移動する時にその円盤よりも小さい円盤の上に積み重ねることができない決まりがあります。
詳しい正確な説明は、ネットで検索すると沢山記事が載っています。
円盤が3枚程度なら、少し考えれば、簡単に移動させることができるかと思います。
しかし円盤が5枚,10枚となってくると、移動回数が増えて簡単には解き方が分からなくなるかと思います。
このパズルの答えは、プログラムを作って実行させることで、簡単に調べられます。
再帰を使う
ハノイの塔の解法を調べるために、再帰を使ったプログラムを書きます。
再帰とは、ある手順(他言語では関数やメソッド)の中で同じ手順をまた呼び出す状態のことです。
n枚の円盤を移動するハノイの塔の答えは、n-1枚の円盤を移動するハノイの塔の答えが分かれば解けるので、パラメータ(引数)が異なるだけで同じ処理を呼び出すことになります
プロデルで、ハノイの塔の解法を調べるプログラムは、次のようになります。
このプログラムでは「ハノイする」という名前の手順を定義して、その中では「ハノイする」をさらに再帰的に呼び出しています。
プログラムを実行すると、答えが出力されます。
5だけ｛「A」,「B」,「C」｝をハノイする
【値:整数】だけ【塔:文字列の配列】をハノイする手順
もし値>0なら
値-1だけ｛塔(1),塔(3),塔(2)｝をハノイする
値&「番の円盤を」&塔(1)&「から」&塔(2)&「へ移動」&改行を出力する
値-1だけ｛塔(2),塔(1),塔(3)｝をハノイする
もし終わり
終わり
なお、プロデルでは、特に宣言無く変数に値を代入できますが、宣言がないとグローバル変数(広域変数)として確保されます。再帰では、その時々の変数の値を別々に持っていく必要なことがあるので、ローカル変数(局所変数)を宣言する必要があります。
仮引数は、ローカル変数となりますが、別途作業変数などでローカル変数が必要なときは【変数名】と言ったように変数宣言文を書きます。
解法を可視化する
今度は、もっと視覚的に分かるように、解法を画面上に可視化してみます。
画面上に図形を描くには、「キャンバス」というGUI部品を使います。
ロジックを考える
今回は、「円盤数」で指定した数に応じたハノイの塔の解法を、上記の再帰で調べておき、その答えを「解法」という変数に控えてきます。
「解法」には、どの棒の一番上にある円盤を、どの棒へ移動するかを数字で記録しておきます。
また、画面にハノイの塔を描画するために、キャンバス部品をウィンドウに貼り付けます。
キャンバス部品には、棒や底板、円盤を描きます。
どの棒にどの円盤が置かれているかを「塔群」配列に記憶しておきます。「塔群」配列には、棒の数だけ「スタック」というデータ構造のオブジェクトを入れておきます。
スタックへの積み出し操作が、棒の円盤の出し入れと同じなので、スタックを利用します。
最後に、控えておいた解法をもとに、円盤を移動させるアニメーションを描画します。
今回は、[戻る][進む]の2つのボタンによって、円盤の操作を一つずつ移動させるようにします。
現在、解法のどこまで進んだかを「移動番号」変数に記録しておきます。[進む]ボタンをクリックすると、移動番号が増えます。そして「解法」の(移動番号)番目にある内容を取得して実際に「塔群」配列の各スタックを出し入れします。
また、「反映する」手順には「塔群」配列の各スタックの状態に合うように図形の位置を移動します。
なお円盤の数が増えると移動の回数が膨大になるので、[自動]ボタンも作りました。[自動]ボタンは、タイマーを使って0.5秒ごとに[進む]ボタンと同じ操作を、解法の最後まで実行し続けます。
完成したプログラム
「円盤数」を変えることで、重なる円盤の数を増やせます。
円盤数=3
解法={}
円盤数だけ｛1,2,3｝をハノイする
メイン画面を表示する
待機する
【値:整数】だけ【塔:整数の配列】をハノイする手順
もし値>0なら
値-1だけ｛塔(1),塔(3),塔(2)｝をハノイする
解法に{値,塔(1),塔(3)}を加える
値-1だけ｛塔(2),塔(1),塔(3)｝をハノイする
もし終わり
終わり
メイン画面とは
ウィンドウを継承する
+塔群={}
+塔位置={120,240,360}
+移動番号=0
はじめの手順
初期化する
タイマー１というタイマーを作る
タイマー１の間隔を500に変える
ーー貼り付けた部品に対する操作をここに書きます
キャンバス1へ線を描いて棒Aとする
その始点は｛塔位置(1),50｝
その終点は｛塔位置(1),250｝
その線色を灰色に変える
その太さを10に変える
キャンバス1へ線を描いて棒Bとする
その始点は｛塔位置(2),50｝
その終点は｛塔位置(2),250｝
その線色を灰色に変える
その太さを10に変える
キャンバス1へ線を描いて棒Cとする
その始点は｛塔位置(3),50｝
その終点は｛塔位置(3),250｝
その線色を灰色に変える
その太さを10に変える
キャンバス1へ四角形を描いて底板とする
その位置と大きさは｛20,250,440,30｝
その太さを0に変える
その背景色を灰色に変える
キャンバス1へ文字を描いて回数ラベルとする
その位置は、｛300,10｝
そのフォントを「メイリオ」に変える
その文字色を緑色に変える
その文字サイズを20に変える
スタックを作って塔群(1)とする
スタックを作って塔群(2)とする
スタックを作って塔群(3)とする
//円盤を作る
長さは、120
円盤数回数にカウントして繰り返す
キャンバス1へ四角形を描いて円盤とする
その位置と大きさは｛棒Aの横-長さ/2,底板の縦-(塔群(1)の要素数+1)*20,長さ,20｝
その背景色は、HLS（{(数*360/円盤数)%360，0.8，0.6}）
塔群(1)に円盤を積む
長さは、長さ*0.8
繰り返し終わり
終わり
初期化する手順
ーー自動生成された手順です。ここにプログラムを書き加えても消える場合があります
この実質大きさを｛796,473｝に変える
この内容を「ハノイの塔」に変える
初期化開始する
自動ボタンというボタンを作る
その位置と大きさを｛293,23,112,34｝に変える
その内容を「自動」に変える
その移動順を4に変える
前ボタンというボタンを作る
その位置と大きさを｛33,23,112,34｝に変える
その内容を「戻る」に変える
次ボタンというボタンを作る
その位置と大きさを｛161,23,112,34｝に変える
その内容を「進む」に変える
その移動順を1に変える
キャンバス1というキャンバスを作る
その位置と大きさを｛0,0,796,473｝に変える
その移動順を2に変える
そのドッキング方向を「全体」に変える
初期化終了する
この設計スケール比率を｛144,144｝に変える
終わり
次ボタンがクリックされた時の手順
もし移動番号が解法の個数なら返す
移動番号を増やす
操作は、解法(移動番号)
塔群(操作(2))から取り出して塔群(操作(3))へ積む
反映する
終わり
前ボタンがクリックされた時の手順
もし移動番号が0なら返す
操作は、解法(移動番号)
塔群(操作(3))から取り出して塔群(操作(2))へ積む
移動番号を減らす
反映する
終わり
反映する手順
回数ラベルの内容は「[移動番号]回目」
塔番号は、1
塔群のすべての塔についてそれぞれ繰り返す
番号は、1
塔の全要素のすべての円盤についてそれぞれ繰り返す
円盤の位置は｛塔位置(塔番号)-円盤の幅/2,底板の縦-(塔の要素数-番号+1)*20｝
番号を増やす
繰り返し終わり
塔番号を増やす
繰り返し終わり
終わり
自動ボタンがクリックされた時の手順
もしタイマー1が動作中なら
タイマー1を停止する
そうでなければ
もし移動番号が解法の個数なら
移動番号は、0
塔群は、塔群から１番目と３番目を交換したもの
もし終わり
タイマー1を開始する
もし終わり
終わり
タイマー１が時間になった時の手順
次ボタンがクリックされた
もし移動番号が解法の個数なら
タイマー1を停止する
もし終わり
終わり
終わり
まとめ
今回は、プロデルでハノイの塔を解いてその答えをアニメーションで可視化するプログラムを作ってみました。ハノイの塔を解いていく様子を眺めるのは楽しいですね。
日本語を用いるプロデルでも、アルゴリズムを駆使したプログラムを作ることはできます。もちろんアルゴリズムやデータ構造について理解しないと、日本語であってもプログラムを理解することはできませんが、変数名や制御文に日本語が使われていることで、よりデータの動きが掴みやすくなった方もいると思います。
一方で数学が得意で記号で書き表すことに慣れていて、その方が理解しやすい人々には、日本語プログラミング言語にメリットを感じにくいと思われがちです。特にアルゴリズムが絡む例では、それが顕著になると思います。
ただ、日本語プログラミング言語であっても、本質的なアルゴリズムやデータ構造は同じなのです。日本語のプログラムを記号的に捉えることに慣れてしまえば、プログラミング言語の一種として理解してもらえるはずです。今回はその例として、ハノイの塔を取り上げてみました。
プロデルで色々なアルゴリズムとデータ構造を使ったプログラムや、キャンバスでそれを可視化するプログラムにぜひチャレンジしてみてください！見ていて楽しいですし、日本語らしい違った発見があるかもしれません。