今年も残りわずかとなりました。M.Hiroi's Home Page を開設してから2年半になりますが、おかげさまでカウンタも 69,000 を突破いたしました。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様にお礼申しあげます。来年もこのページでプログラミングの楽しさを少しでもお伝えできればいいなと思っています。来年もがんばりますので、よろしくお願い申しあげます。
それでは、きたるべき年も皆様にとってよいお年でありますように。
昨日、カウンタが 68,000 を突破しました。X68000 ユーザーである M.Hiroi にとって、68,000 Hit は目標にしていた数字なのでとても嬉しいです。ホームページを開設したときは、68,000 Hit なんて夢のような数字に思えたのですが、皆様のおかげで短期間(約 2 年半)で 68,000 Hit を達成することができました。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。
第 3 回アンケート は前回と同様に Lisp 関連のコンテンツが上位を独占しましたが、その中で お気楽 Prolog プログラミング入門 は前回よりも投票数を大幅に伸ばして上位に入りました。多くの方に興味を持ってもらえたようでとても嬉しく思います。
Prolog は面白い特徴を持ったプログラミング言語です。事実と規則を定義していく、つまり、物事の関係を記述していくプログラミングスタイルは、ほかの言語にはない独自なものです。このページで多くの方に Prolog の面白さを伝えることができればいいな、と思っています。
これからもがんばりますので、よろしくお願いいたします。
本日、第 3 回アンケート の投票を締め切りました。多数のご投票、誠にありがとうございます。投票された皆様に厚くお礼申し上げます。さて、結果ですがトップ 3 は次のようになりました。
前回と同じく Lisp 関連のコンテンツが上位を独占しました。「Common Lisp 入門」は例題に M.Hiroi の趣味である「パズルの解法」を多く取り上げましたが、多くの方に興味を持ってもらえたようでとても嬉しく思います。このように Lisp 関連のコンテンツに関心を持ってもらえるのも、身近に xyzzy Lisp という優秀な処理系があるからです。フリーで利用できるのは本当にありがたいことです。作者の亀井さんに大感謝です。
最近、Lisp 関連のコンテンツは更新していませんが、Lisp は M.Hiroi の一番好きなプログラミング言語なので、これからも Lisp でプログラミングを楽しんでいきたいと思っています。もちろん、Lisp 以外のコンテンツも充実するようにがんばりますので、これからもよろしくお願いいたします。
第 3 回アンケート 興味のあるコンテンツは? を開始してから 2 ヶ月たちました。投票された皆様にお礼申しあげます。途中経過ですが、トップ 3 は次のようになっています。
1: xyzzy Lisp : Common Lisp 入門 15(16%) 2: お気楽ごくらくプログラミング入門 -- Lisper への道 -- 11(11%) 3: xyzzy Lisp : 読み物 10(10%) 3: 続・サルでも書けるCプログラム講座 10(10%)
前回と同様に Lisp 関連のコンテンツに興味を持っている方が多いようです。「Common Lisp 入門」では M.Hiroi の趣味である「パズルの解法」を例題に取り上げましたが、多くの方に興味を持ってもらえたようで安心しました。
「続・サルでも書けるCプログラム講座」は、xyzzy Lisp Programming と Prolog Programming に次いでアクセスの多いコンテンツです。現在、番外編を更新中ということもありますが、Google などの検索エンジンでアルゴリズムに関するキーワードがヒットするようで、ときどきアクセス数が急増することがあります。C言語だけではなく、この講座でアルゴリズムにも興味を持ってもらえれば嬉しいです。
なお、第 3 回アンケートは 12 月 15 日に終了する予定です。まだ投票されていない方はお気軽にどうぞ。
舩本昇竜さんが執筆された『プロテクト技術解剖学』(すばる舎)という本が発売されました。cbook24 や bk1 で内容と目次や推薦文を読みましたが、この本はいわゆる「裏系のツール」の話ではなく、プロテクト技術の真っ当な解説書 なので、M.Hiroi はとても興味があります。真正面からプロテクト技術に取り組む姿勢はまさに質実剛健、さすが舩本さんだと思いました。
M.Hiroi's Home Page はライコスのウェブガイド(ディレクトリ)のカテゴリ「コンピュータ・インターネット > プログラミング > C・C++」に登録されていましたが、11 月 7 日に行われたライコスのデータベース変更にともない、M.Hiroi's Home Page はディレクトリから削除されたようです。ライコスさん、長い間本当にありがとうございました。
TAU さん が X68k 用の新作ゲーム「Master Mind Square」を発表されました。ゲーム内容は「2次元マスターマインド」です。M.Hiroi はまだ Level 1 (3 行 3 列盤) しかプレイしていませんが、予想していたよりも難易度は低いようで、誰にでも楽しめるパズルゲームになっていると思います。
さすが TAU さん、ユニークなアイデアで感心しました。面白いパズルゲームなので、パズルが好きな X68k ユーザーはぜひ遊んでみてください。TAU さんに感謝です。
本日、カウンタが 60,000 を突破しました。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。このホームページには 5 つのメインコンテンツがあり、それぞれのトップページに すごい!!カウンター のカウンタをつけています。ここ1週間の平均アクセス数は次のようになりました。
TOP | X68k | Tcl/Tk | xyzzy | Puzzle | Prolog |
---|---|---|---|---|---|
98/day | 18/day | 31/day | 70/day | 20/day | 41/day |
あいかわらず xyzzy Lisp のアクセス数が多いですね。最近は Tcl/Tk や Perl/Tk のアクセス数も少しですが増えています。先日、続・サルでも書けるCプログラム講座に番外編を追加しましたが、これを機会にほかの X68k 関連のコンテンツも更新できればいいな、と思っています。
それから、久しぶりに アンケート を始めました。お題は第 2 回と同じく「興味のあるコンテンツは?」です。1 年前に比べて M.Hiroi's Home Page のコンテンツも少しですが増えているので、同じお題にしてみました。どうぞお気軽にご投票くださいませ。
これからもがんばりますので、よろしくお願いいたします。
9 月28 日 で示したスライドパズルの解答ですが、間違いがありましたので訂正いたします。9 月 23 日 のパズルの説明で「大きな駒 (2 マス) は動かさなくても大丈夫」と書きましたが、「大きな駒を動かしてはいけない」とは書いてありません。実は、28 日に示した手順は「大きな駒」を動かさずに解く場合の最短手順で、大きな駒を動かすとこの手順よりも短い手数で解くことができます。これは Y. N. さんにご指摘いただきました。Y. N. さん、ありがとうございます。
大きな駒を動かした場合の最短手順を Y. N. さんのメールより転載いたします。転載を快諾された Y. N. さんに感謝いたします。
step:0 step:7 step:14 ┌─┬─┬───┐ ┌─┬───┬─┐ ┌─┬─┬───┐ │┌┼─┼┐ │ │┌┼┐ │羊│ │┌┼─┼┐ │ ├┼┼─┼┼┬─┤ ├┼┼┴┬─┼┬┤ ├┼┼─┼┴┬─┤ │││ │||│羊│ ││├─┼─┤||│ ││├─┤羊│ │ ├┼┼─┼┼┼─┤ ├┼┼┬┼─┼┴┤ ├┼┼┬┼─┼┬┤ │└┼─┼┘│狼│ │└┼┘│ │狼│ │└┼┘│狼│||│ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴┴┘ step:1 step:8 step:15 ┌─┬─┬───┐ ┌─┬───┬─┐ ┌─┬─┬───┐ │┌┤ ├┐ │ │┌┼┐ │羊│ │┌┼─┼┐ │ ├┼┼─┼┼┬─┤ ├┼┼┴┬─┼┬┤ ├┼┼─┼┴┬┬┤ ││├─┤||│羊│ ││├─┼─┤||│ ││├─┤羊│||│ ├┼┼─┼┼┼─┤ ├┼┼┬┼─┼┴┤ ├┼┼┬┼─┼┴┤ │└┼─┼┘│狼│ │└┼┘│狼│ │ │└┼┘│狼│ │ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ step:2 step:9 step:16 ┌─┬───┬─┐ ┌─┬───┬─┐ ┌─┬─┬───┐ │┌┼┐ │ │ │┌┼┐ │羊│ │┌┼─┼┐ │ ├┼┼┴┬┬┼─┤ ├┼┼┴┬─┼─┤ ├┼┼─┼┴┬┬┤ ││├─┤||│羊│ ││├─┼─┤ │ ││├─┤羊│||│ ├┼┼─┼┼┼─┤ ├┼┼┬┼─┼┬┤ ├┼┼┬┼─┼┴┤ │└┼─┼┘│狼│ │└┼┘│狼│||│ │└┼┘│ │狼│ └─┴─┴─┴─┘ └─┴─┴─┴┴┘ └─┴─┴─┴─┘ step:3 step:10 step:17 ┌─┬───┬─┐ ┌─┬───┬─┐ ┌─┬─┬───┐ │┌┼┐ │羊│ │┌┼┐ │ │ │┌┼─┼┐ │ ├┼┼┴┬┬┼─┤ ├┼┼┴┬─┼─┤ ├┼┼─┼┴┬┬┤ ││├─┤||│ │ ││├─┼─┤羊│ ││├─┤羊│||│ ├┼┼─┼┼┼─┤ ├┼┼┬┼─┼┬┤ ├┼┼─┼┬┼┴┤ │└┼─┼┘│狼│ │└┼┘│狼│||│ │└┤ ├┘│狼│ └─┴─┴─┴─┘ └─┴─┴─┴┴┘ └─┴─┴─┴─┘ step:4 step:11 step:18 ┌─┬───┬─┐ ┌─┬─┬───┐ ┌─┬─┬───┐ │┌┼┐ │羊│ │┌┤ ├┐ │ │┌┼─┼┐ │ ├┼┼┴┬─┼┬┤ ├┼┼─┼┴┬─┤ ├┼┼─┼┴┬┬┤ ││├─┤ │||│ ││├─┼─┤羊│ │││ │羊│||│ ├┼┼─┼┬┼┴┤ ├┼┼┬┼─┼┬┤ ├┼┼─┼┬┼┴┤ │└┼─┼┘│狼│ │└┼┘│狼│||│ │└┼─┼┘│狼│ └─┴─┴─┴─┘ └─┴─┴─┴┴┘ └─┴─┴─┴─┘ step:5 step:12 step:19 ┌─┬───┬─┐ ┌─┬─┬───┐ ┌─┬─┬───┐ │┌┼┐ │羊│ │┌┼─┼┐ │ │┌┼─┼┐ │ ├┼┼┴┬─┼┬┤ ├┼┼─┼┴┬─┤ ├┼┼─┼┴┬┬┤ │││ ├─┤||│ │││ ├─┤羊│ │││羊│ │||│ ├┼┼─┼┬┼┴┤ ├┼┼┬┼─┼┬┤ ├┼┼─┼┬┼┴┤ │└┼─┼┘│狼│ │└┼┘│狼│||│ │└┼─┼┘│狼│ └─┴─┴─┴─┘ └─┴─┴─┴┴┘ └─┴─┴─┴─┘ step:6 step:13 step:20 ┌─┬───┬─┐ ┌─┬─┬───┐ ┌─┬─┬───┐ │┌┼┐ │羊│ │┌┼─┼┐ │ │┌┼─┼┐ │ ├┼┼┴┬─┼┬┤ ├┼┼─┼┴┬─┤ ├┼┼─┼┼┬─┤ ││├─┼─┤||│ ││├─┤ │羊│ │││羊│||│ │ ├┼┼─┼┬┼┴┤ ├┼┼┬┼─┼┬┤ ├┼┼─┼┼┼─┤ │└┤ ├┘│狼│ │└┼┘│狼│||│ │└┼─┼┘│狼│ └─┴─┴─┴─┘ └─┴─┴─┴┴┘ └─┴─┴─┴─┘ 図 : スライドパズルの解答
最短手数は 20 手になります。この場合も、2 つある駒 (─) を交換するところがポイントになります。それにしても、スライドパズルで大きな駒を動かすのは当然のことで、それがすっぽりと抜けていたとは本当に情けないことです。訂正するとともに深くお詫び申しあげます。
それから、先日出題した最長手数の問題ですが、これは大きな駒を動かさない条件で求めた局面です。この条件だと最長手数は 53 手になりますが、大きな駒を動かしてもよいことにすると、最長手数の局面は次のようになります。
┌─┬─┬───┐ ┌─┬─┬───┐ │狼│||├┐ │ │┌┼─┼┐ │ ├┬┼─┼┼┬─┤ ├┼┼─┼┼┬─┤ ├┘│羊││├─┤ │││羊│||│ │ ├─┼─┼┼┼─┤ ├┼┼─┼┼┼─┤ │ ├─┤└┤┌┤ │└┼─┼┘│狼│ └─┴─┴─┴┴┘ └─┴─┴─┴─┘ START GOAL 問題 : 最長手数の局面
最長手数は 52 手、局面は全部で 7 通りあります。大きな駒を動かすことで、最長手数は 1 手短くなりました。この問題を反復深化で解く場合、手数が長いので下限値を工夫しないと時間がかかります。いつものように駒の移動手数を下限値として、C言語でプログラムを作成した場合、M.Hiroi のオンボロマシン (Pentium 166 MHz) では約 20 分かかりました。興味のある方はぜひ挑戦してみてください。
プログラムは Puzzle DE Programming で公開する予定です。
9 月 23 日 に出題した「スライドパズル」の解答です。図では駒 (─) を ← と → で、空き場所を □ で表しています。
┌←┐ │□||羊 └→┘狼 ┌←┐ ┌←┐ ┌←┐ ┌←┐ ┌←┐ ┌←┐ ┌□┐ │||□羊 │||羊□ │||羊狼 │||羊狼 │||羊狼 │□羊狼 │←羊狼 └→┘狼 └→┘狼 └→┘□ └→□┘ └□→┘ └||→┘ └||→┘ □┌┐ │┌┐ │┌┐ │┌┐ │┌┐ │┌┐ │┌┐ │←羊狼 □←羊狼 └←羊狼 └←羊狼 └←羊狼 └←□狼 └□←狼 └||→┘ └||→┘ □||→┘ ||□→┘ ||→□┘ ||→羊┘ ||→羊┘ │┌┐ │┌┐ │┌┐ □┌┐ ┌□┐ ┌→┐ ┌→┐ └→←狼 └→←狼 □→←狼 │→←狼 │→←狼 │□←狼 │←□狼 ||□羊┘ □||羊┘ └||羊┘ └||羊┘ └||羊┘ └||羊┘ └||羊┘ ┌→┐ ┌→┐ ┌→┐ ┌→┐ ┌→┐ ┌→┐ ┌→┐ │←羊狼 │←羊狼 │□羊狼 │羊□狼 │羊||狼 │羊||狼 │羊||□ └||□┘ └□||┘ └←||┘ └←||┘ └←□┘ └←┘□ └←┘狼 図 : スライドパズルの解答
最短手数は 28 手です。 図を見ればおわかりのように、このパズルを解く鍵は 2 つある駒 (─) を交換することです。そうしないと、このパズルを解くことはできません。この証明は簡単にできるので、興味のある方は考えてみてください。
このパズルは Goat や Get My Goat と呼ばれていて、スライドパズルではよく知られている問題です。今回のパズルは駒の種類をちょっとだけ変更しています。オリジナルの Goat については、未菜実さんの 数理パズル入門 にある スライドパズル が参考になります。
それでは、もう少し難しい問題を出しましょう。次の図を見てください。
┌─┬─┬───┐ ┌─┬─┬───┐ │狼│||├┐ │ │┌┼─┼┐ │ ├┬┼─┼┼┬─┤ ├┼┼─┼┼┬─┤ ├┘│羊││├─┤ │││羊│||│ │ ├─┼─┼┼┼─┤ ├┼┼─┼┼┼─┤ ├─┤ │└┤┌┤ │└┼─┼┘│狼│ └─┴─┴─┴┴┘ └─┴─┴─┴─┘ START GOAL 問題 : 最長手数は?
羊を囲う最短手順を求めてください。実はこの問題、GOAL の局面からの最長手数になっています。つまり、一番難しい問題なのです。何手で解けるか挑戦してみてください。
今回は昔からある「スライドパズル」を出題します。
┌─┬─┬───┐ ┌─┬─┬───┐ │┌┼─┼┐ │ │┌┼─┼┐ │ ├┼┼─┼┼┬─┤ ├┼┼─┼┼┬─┤ │││ │||│羊│ │││羊│||│ │ ├┼┼─┼┼┼─┤ ├┼┼─┼┼┼─┤ │└┼─┼┘│狼│ │└┼─┼┘│狼│ └─┴─┴─┴─┘ └─┴─┴─┴─┘ START GOAL 問題 : スライドパズル
|| は扉を表します。羊を囲いの中に入れる最短手順を求めてください。
自力で解きたい方のためにヒントを出しておきましょう。まず、大きな駒 (2 マス) は動かさなくても大丈夫です。それから、このパズルには同じ種類の駒 (─) が一組ありますね。この駒がパズルを解く鍵になります。
ヒントはここまでです。それではパズルをお楽しみください。
xyzzy Lisp Programming の「Common Lisp 入門」ですが、昨日の更新で予定していた内容はすべて公開したので、ここで区切りをつけたいと思います。当初の予定では、拙作 の Lisp インタプリタ VTOL 用の入門マニュアルを Common Lisp に書き直すだけでしたが、ちょっと寄り道をしているあいだに元のマニュアルよりも長くなってしまいました。例題として取り上げたプログラムは M.Hiroi の趣味である「パズルの解法」が多くなりましたが、基本的なアルゴリズムやデータ構造は一通り説明できたのではないかと思っています。
今度再開するときは Lisp らしいプログラムを取り上げてみたいですね。Lisp の得意な分野に「記号処理」がありますが、「記号のパターンマッチング」という手法は記号処理の例題として Lisp の教科書では定番となっているプログラムです。興味のある方は、拙作のページ「エキスパートシステムの作成」をご覧ください。このプログラムは拙作の Lisp インタプリタ VTOL 用ですが、Common Lisp (xyzzy Lisp) 用に書き直してみるのもよいかな、と思っています。
まずは、X68000 Programming の更新を再開しないといけませんね。ブロックソートやレンジコーダなどの圧縮アルゴリズムを続・サルでも書けるCプログラム講座の番外編として追加したいと思っています。予定は未定ですがこれからも頑張りますので、よろしくお願いいたします。
昨日、覆面算 SEND + MORE = MONEY を Prolog のプログラムで解きました。理詰めで解くことは皆さんにお任せしましたが、さっそく M.Kamada さん が手で解く方法を 日記 で丁寧に解説されています。M.Kamada さん、どうもありがとうございます。どうしても自力で解けない方は M.Kamada さんの日記をお読みくださいませ。
面白いパズルの本が発売されましたので紹介します。
ブルーバックス B-1377
『超々難問数理パズル 解けるものなら解いてごらん』
芦ヶ原伸之 講談社
著者の芦ヶ原伸之氏は世界でも指折りのパズル作家です。この本には著者のオリジナル問題を中心に難問 101 題が掲載されています。パズル好きの方は挑戦しましょう。
最近メールで SWI-Prolog について同じ質問がありました。
質問:SWI-Prolog で実行形式ファイル (.exe) を作成できますか。
答:できません。
同じ質問に何度も答えるのは面倒なので、Prolog Programming : SWI-Prolog に上記の内容を追加しました。
ところで、Windows 上で動作するフリーな Prolog 処理系で、実行形式ファイルを生成する処理系を M.Hiroi は知りません。商用の Prolog 処理系ならばあるかもしれませんが、詳しいことは M.Hiroi もわかりません。興味のある方はご自分で調べてみてください。今のところ、M.Hiroi は SWI-Prolog で十分満足しています。
Puzzle DE Programming は予定していた内容を公開したので、ここで区切りをつけたいと思います。取り上げてみたいパズルはいろいろあるのですが、M.Hiroi の力不足でなかなかプログラムできません(苦笑)。じっくりと充電してから再開したいと思っています。
次は、しばらく更新していなかった X68000 Programming を再開しようと思っています。とりあえず、Memorandum で取り上げたコームソートや圧縮アルゴリズムのブロックソートを続・サルでも書けるCプログラム講座の番外編として追加する予定です。それから、TAU さんが作成された 『三角(菱形)リバーシ』 の M.Hiroi 版も作りたいですね。予定は未定ですが頑張りますので、よろしくお願いいたします。
M.Hiroi's Home Page を開設してから本日でちょうど 2 年になりました。1 年目で 20,000 Hit を突破しましたが、その後もアクセス数は少しずつ増えていき、おかげさまで 2 年で 50,000 Hit を達成することができました。多くの方にアクセスしていただき、とても嬉しく思います。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。
これからもがんばりますので、今後ともよろしくお願い申し上げます。
本日、カウンタが 50,000 を突破しました。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。このホームページには 5 つのメインコンテンツがあり、それぞれのトップページに すごい!!カウンター のカウンタをつけています。ここ1週間の平均アクセス数は次のようになりました。
TOP | X68k | Tcl/Tk | xyzzy | Puzzle | Prolog |
---|---|---|---|---|---|
92/day | 22/day | 26/day | 65/day | 47/day | 60/day |
あいかわらず xyzzy Lisp と Prolog のアクセス数が多いですね。また、最近更新している Puzzle のアクセス数も増えています。このほかには、続・サルでも書けるCプログラム講座の平均アクセス数が 68 Hit / day と大変多いのには驚きました。もしかすると、C言語やアルゴリズムの勉強をされている学生さんのアクセスが多いのかもしれませんね。これからもがんばりますので、よろしくお願いいたします。
奥村晴彦氏が執筆された C MAGAZINE 2002 年 7 月号 (ソフトバンク) の特集『データ圧縮の基礎から応用まで』は、わかりやすく書かれていてとても面白かったです。データ圧縮に興味をお持ちの方は一読することをおススメします。特に、M.Hiroi は「桁上げのないレンジコーダ」を読んで目からウロコが落ちました。
レンジコーダ (rangecoder) は原理的には算術符号化と同じです。一般に、算術符号化はハフマン符号化よりも性能が良いのですが、実現方法が難しくて実行速度がハフマン符号化よりも遅く、なおかつ特許の問題もあって、実際に使われることはあまりありませんでした。レンジコーダは算術符号化に比べ性能はわずかに劣化しますが、実現方法は簡単で実行速度も高速です。
実際、M.Hiroi はレンジコーダを作ったことがあります。Memorandum 2001 年 8 月では「ブロックソート+ハフマン符号化」でデータ圧縮を行いましたが、ハフマン符号化のかわりにレンジコーダを用いると圧縮率は少しですが向上しました。このとき、桁上げ(オーバーフロー)の処理に苦労したのですが、今回の特集を読んで「こんなうまい方法があるのか」と驚いてしまいました。
『パズルでプログラミング』 は先日の更新で Oh!X 2001 春号(ソフトバンク)掲載分をすべてアップいたしました。このプログラミング講座では、パズルを題材にして基本的なデータ構造とアルゴリズムを説明しているので、パズルの解法だけではなくプログラミングに興味のある方はぜひ読んでみてください。このあともしばらくの間 Puzzle DE Programming の更新は続けるつもりです。とりあえず、Memorandum で取り上げたパズルの解法プログラムを公開する予定です。お楽しみに。
卓さん、おめでとうございます。X68k のエミュレータを利用する場合、OS (Human68k) のマニュアルがないのが欠点でした。使い方がわからずに困っている方は、卓さんが書かれた Human68k マニュアルをお読みください。素晴らしいマニュアルを書かれた卓さんに感謝です。これからもがんばってください。
TAU さん の Windows Original Game の仮置き場 で 「MINE SWEEPER HEXA」 for Windows が公開されました。このゲームは「月刊・電脳倶楽部」に掲載された X68k 版の移植で、ようするに「パネルが六角形なマインスイーパー」です。M.Hiroi はこのゲームがとても気に入っていて、電脳倶楽部に掲載されたときはメチャクチャはまってしまいました。Windows でもプレイできるのはとても嬉しいことです。パズル好きな方は TAU LAND 2002 へ GO! です。
5 月 11 日 に出題したパズルの解答です。このパズルは下図のように右上のピースを上に移動すると、Puzzle DE Programming スライディングブロックパズル(1) と同様に解くことができます。
┌─┐ ┌─┐ ┌─┐ │\│ │\│ │E│ ┌─┬─┬─┼─┤ ┌─┬─┬─┼─┤ ┌─┬─┬─┼─┤ │/│\│/│ │ │/│/│\│ │ │0│1│2│3│ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │\│/│\│/│ │/│/│\│\│ │4│5│6│7│ ├─┼─┼─┼─┤=>├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │/│\│/│\│ │\│\│/│/│ │8│9│10│11│ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │\│/│\│/│ │\│\│/│/│ │12│13│14│15│ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ START GOAL 位置 図 : 右上のピースを動かした状態
この状態で START から GOAL までの最小手数が 20 手になるので、右上のピースの移動手数 (2 手) を加えた 22 手が最小手数になります。動かすパネルの位置で移動手順を表すと、最短手順は次のようになります。
(1) 3 2 1 5 4 8 9 13 14 10 11 7 3 2 6 5 9 10 11 7 3 E (2) 3 7 11 10 14 13 9 8 4 5 1 2 3 7 6 10 9 5 1 2 3 E
次は最長手数の局面を求めましょう。上図の START から探索を始める場合、空き場所の位置に注意してください。
┌─┐ ┌─┐ ┌─┐ │\│ │\│ │\│ ┌─┬─┬─┼─┤ ┌─┬─┬─┼─┤ ┌─┬─┬─┼─┤ │/│\│/│ │ │/│/│\│\│ │ │\│\│\│ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │\│/│\│/│ │/│/│\│\│ │\│\│\│\│ ├─┼─┼─┼─┤=>├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │/│\│/│\│ │/│/│\│\│ │/│/│/│/│ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │\│/│\│/│ │/│/│\│ │ │/│/│/│/│ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ START 35手 35手 図 : 最長手数の局面(間違い)
15 枚のピースで最長手数の局面を求めると上図のようになりますが、これでは右上のピースを元に戻すことができませんね。このパズルでは、空き場所の位置が 3 である局面を求めなければいけないのです。結果は次のようになります。
┌─┐ ┌─┐ ┌─┐ │\│ │\│ │\│ ┌─┬─┬─┼─┤ ┌─┬─┬─┼─┤ ┌─┬─┬─┼─┤ │/│\│/│ │ │/│\│\│ │ │\│\│\│ │ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │\│/│\│/│ │/│/│\│\│ │/│\│\│\│ ├─┼─┼─┼─┤=>├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │/│\│/│\│ │/│/│\│\│ │/│/│/│\│ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │\│/│\│/│ │/│/│/│\│ │/│/│/│/│ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ START 34手 34手 図 : 最長手数の局面
START から始めて空き場所の位置が 3 である最長手数は 34 手になりました。これに右上のピースの移動手数 (2 手) を加えるので、最長手数は 36 手になります。
ライン・パズル は、円を 4 等分した模様のピースを 16 枚使うスライディングブロックパズルです。今回は 2 つのピース / と \ を使った簡易バージョンを考えてみました。それでは問題です。
[問題] 下図の START から GOAL までの最短手順を求めてください。
┌─┐ ┌─┐ │ │ │ │ ┌─┬─┬─┼─┤ ┌─┬─┬─┼─┤ │/│\│/│\│ │/│/│\│\│ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │\│/│\│/│ │/│/│\│\│ ├─┼─┼─┼─┤=>├─┼─┼─┼─┤ │/│\│/│\│ │\│\│/│/│ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │\│/│\│/│ │\│\│/│/│ └─┴─┴─┴─┘ └─┴─┴─┴─┘ START GOAL 図 : 「ライン・パズル」簡易版
ライン・パズルの場合、最初に動かすことができるピースは盤面右上のピースしかありません。また、最後は最初に動かしたピースを元に戻して模様が完成することになります。このパズルはピースの種類が 2 つしかないので、最短手順は幅優先探索で簡単に求めることができます。また、興味のある方は START から最長手数となる局面を求めてみてください。
先日、カウンタが 45,000 を突破しました。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。このホームページには 5 つのメインコンテンツがあり、それぞれのトップページに すごい!!カウンター のカウンタをつけています。ここ1週間の平均アクセス数は次のようになりました。
TOP | X68k | Tcl/Tk | xyzzy | Puzzle | Prolog |
---|---|---|---|---|---|
91/day | 17/day | 26/day | 66/day | 19/day | 47/day |
ゴールデンウィークの間はアクセス数がガクッと落ち込むと思っていましたが、たくさんアクセスしていただき本当にありがとうざいます。4 月になってから xyzzy Lisp と Prolog のアクセス数が増えていますが、新学期が始まって Lisp や Prolog を勉強されている学生さんのアクセスが多いのかもしれません。これからも頑張りますので、よろしくお願いいたします。
Interface 6 月号 (CQ 出版) の特集『これでわかる!マイクロプロセッサのしくみ』で、M.Kamada さん が『MMU によるアドレス変換』という記事を執筆されています。マイクロプロセッサ (MPU, CPU) やメモリ管理ユニット (MMU) のしくみに興味のある方は要チェックです。
それから Interface 4 月号のアンケート結果で、拙作の『Perl/Tk を使った GUI プログラミング』が「興味のあった記事」の第 6 位に入りました。記事では Perl/Tk の機能とプログラミングの方法を駆け足で説明しましたが、多くの方に興味を持ってもらえたようでとても嬉しく思います。読者の皆様に厚くお礼申しあげます。
『自転車創業』より X68000 用ゲーム『空の浮動産』が5月下旬に発売(予定)されます。2001 年 5 月に発売された Windows 版の移植ですが、みかぜさんの 日記 (4 月 16 日) によると 水野氏のBGMのフルFM音源化とKRBK氏の書き下ろしジャケット、そして鎌田さんがプログラムを書き下ろしたX68000用ソフトという事でおつりが来る内容だと思います。マジで。 とのことです。これは本当にマジで凄いです!
Perl/Tk memo は予定していた内容を公開したので、ここで区切りをつけたいと思います。このほかにも Perl/Tk にはいろいろな機能があり、Tcl/Tk の拡張モジュール Tix のウィジェットを標準で利用することができます。Tix については、Perl/Tk よりも先に Tcl/Tk で説明しようと思っています。拡張モジュールの話題は、浦野さんの AM02:50 Tcl/Tk Scripting Laboratory で詳しく説明されていて、とても参考になります。
Tk 関連はひとまずお休みして、しばらく更新していなかった Puzzle DE Programming を再開しようと思っています。とりあえず、Oh!X 2001 春号(ソフトバンク)に掲載された拙作のプログラミング講座 『パズルでプログラミング』 を公開する予定です。全部で 3 回ありますが、まとめてアップするのは大変(面倒)なので、1 回分を前編・後編の 2 回に分けて少しずつアップしていくつもりです。週に 1 回程度の更新になると思いますが、よろしくお願いいたします。
トップページでもお願いしましたが、メールはテキスト形式にしていただけると助かります。M.Hiroi が愛用している「電信八号+ xyzzy den8-viewer」では、HTML 形式のメールを読むことができない場合があります。Outlook Express をお使いの場合、初期設定が HTML 形式になっているため、知らずに HTML 形式でメールを送信していることがあります。ご注意くださいませ。
それから、ワープロや表計算ソフトなどのデータは、データファイルを添付するのではなく、テキストファイルに変換してメール本文中にコピーしてもらえると大変助かります。せっかくファイルを添付しても、受信者が対応するソフトウェアを持っていなければ、そのファイルを読むことはできません。
また、送られてきた添付ファイルはウィルスに感染している危険性があります。内容が不明の添付ファイルは不用意に実行しない(開かない)、添付ファイルを実行する時にはウィルスチェックを必ず行うといった注意は、ウィルスから身を守るために必要なことです。受信者に負担をかけないためにも、添付ファイルは気軽に送らない方がいいですね。ファイルを添付する場合は、事前に相手の了解を得るか、添付ファイルのファイル名と内容をメール本文に明記するといいでしょう。
一般的なメールのマナーについては、岩崎宏さんの Tips for E-Mail がとても参考になります。HTML メールの問題点については、とほほさんの HTMLメールはマナー違反? が参考になると思います。また、横藤雅人さんの メールマナーを考えよう は子供向けに書かれたマニュアルですが、大人でも参考になる優れたものです。メール初心者の方は一読することをおススメします。
ゲストブックで OS-9 の話がありましたので、簡単に説明しておきましょう。OS-9 はモトローラの 8 bit MPU 6809 用の OS としてマイクロウェアによって開発され、1980 年にリリースされました。1983 年には OS-9/68000 がリリースされ、その後はインテルの CPU に対応した OS-9000 (OS-9/x86) など、各種 CPU に対応した OS-9 がリリースされています。現在ではパソコンで OS-9 を見かけることはほとんどありませんが、産業機器向けの分野 (組み込み用 OS) では評価が高く、実績のある優れた OS です。
OS-9/6809 は 8 bit MPU でリアルタイム・マルチタスクを実現し、TSS (Time Sharing System) さえもサポートしていました。簡単に言えば、8 bit MPU で UNIX ライクな機能を実現した驚異的な OS なのです。これはソフトウェアのパワーだけではなく、究極の 8 bit MPU と呼ばれる 6809 だからこそ実現できたのでしょう。
しかしながら、8 bit MPU ではパワーやメモリ容量などで限界がありました。そこで、16 bit MPU 68000 用の OS-9/68000 がリリースされ、X68000 にも移植されました。これが OS-9/X68000 です。OS-9/X68000 はマルチウィンドウシステムをサポートしていて、当時としては先進的な OS だったのですが、一般ユーザーの興味をひくアプリケーションは、残念ながらほとんどありませんでした。したがって、OS-9/X68000 を使いこなすには、UNIX に興味を持っていて、自分でプログラムを作ることが最低条件だったように思います。ようするに、一般ユーザーには敷居がとても高かったわけです。
ただし、これは一般的なパソコンユーザーの話で、X68k ユーザーの中でもパワーユーザーと呼ばれる猛者や産業機器向けの分野では、OS-9/X68000 の評価は高かったかもしれませんね。その後、GCC (GNU C Compiler) が X68000 の標準 DOS である Human68k に移植されると、M.Hiroi は OS-9/X68000 よりも GCC をメインで使うようになりました。けっきょく、OS-9/X68000 を使いこなすことはできなかったのですが、OS-9/X68000 でいろいろ勉強したことは無駄になっていないと思っています。
本日、カウンタが 40,000 を突破しました。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。このホームページには 5 つのメインコンテンツがあり、それぞれのトップページに すごい!!カウンター のカウンタをつけています。ここ1週間の平均アクセス数は次のようになりました。
TOP | X68k | Tcl/Tk | xyzzy | Puzzle | Prolog |
---|---|---|---|---|---|
96/day | 10/day | 23/day | 49/day | 10/day | 16/day |
xyzzy Lisp のアクセス数がダントツで多いのは、今までと同じですね。実はこのほかにも、X68000 Programming のC言語、Perl、Lisp の講座と Perl/Tk のページにカウンタをつけました。トップページからこれらのページへ直接リンクを張ったので、X68k のアクセスが減少したのかもしれません。各ページの平均アクセス数は次のようになりました。
C言語 | Perl/Tk | Lisp | Perl |
---|---|---|---|
22/day | 19/day | 16/day | 14/day |
Perl/Tk は最近更新していますが、ほかのページは更新が止まっているにもかかわらず、たくさんアクセスしていただき本当にありがとうございます。特に、C言語(Zしーモンキー)のアクセス数が思っていたよりも多くて驚きました。Perl や Lisp には番外編があるので、C言語でも番外編を追加したいですね。そのうちに、Memorandum で取り上げたコームソートやブロックソートをまとめてみよう、と思っています。
これからも頑張りますので、よろしくお願いいたします。
M.Hiroi のところでは、月刊誌が書店に並ぶのは一日遅れなのです。Mitsuky さん にはたいへんお世話になり、本当にありがとうございした。これからもよろしくです。Lisp ネタは M.Hiroi も考えてみますね。
TAU さん が 三角(六芒)リバーシ を Windows に移植されました。M.Hiroi のオンボロマシン (Pentium166MHz) でも、快適にプレイすることができます。普通のリバーシとは全く異なるゲーム感覚で、とても面白いです。リバーシ好きの方は、ぜひ遊んでみてください。
ところで、TAU さんの 掲示板 での情報によると、
『封印解除 (レリーズ) すると、クロスボウ+5で攻撃力超UPです。』
この攻撃には、さくらちゃん(誰?)もびっくりです。M.Hiroi のオンボロマシンではパワーが足りないかと心配しましたが、レベル 7 は何とかプレイすることができました。いやー、強い強い。M.Hiroi は途中で全滅してしまいました(涙)。X68k 版は弱くて相手にならないという方は、ぜひ Win 版でレリーズしてください。
CQ出版社 発行の月刊誌 Interface 4月号(2/25発売予定) の特集「GUIの組み込み機器への実装&活用法」で、M.Hiroi は「Perl/Tkを使ったGUIプログラミング」を執筆しました。GUI や Perl/Tk に興味のある方は読んでみてください。
『自転車創業』より Windows 用ゲーム 『あの、素晴らしい をもう一度』 が 3 月 22 日に発売されます。Win 版は X68 版のリファインバージョンで、『X68版がTV版だとするとWin版は劇場版だと思っててください。』 とのことです。期待大です!
M.Kamada さん の日記で 頭の体操「分数の問題」 が出題されています。面白い問題なので、パズル好きの人は挑戦してみましょう。
2 月 12 日にジオシティーズのシステムが一時停止します。
2002年2月12日(火)、15:00から16:00まで、ネットワーク設備の増強作業を行います。このため、この時間帯Yahoo!ジオシティーズへアクセスできない状態になります。大変ご迷惑をおかけしますが、皆様のご理解ご協力をお願い申し上げます。
この時間帯 M.Hiroi's Home Page にはアクセスできなくなります。この増設作業でアクセス環境が改善されることを期待しています。
本日、カウンタが 35,000 を突破しました。リンクしていただいているホームページ管理者の皆様、そして、なによりも M.Hiroi's Home Page に来てくださる皆様に厚くお礼申し上げます。このホームページには 5 つのメインコンテンツがあり、それぞれのトップページに すごい!!カウンター のカウンタをつけています。ここ1週間の平均アクセス数は次のようになりました。
TOP | X68k | Tcl/Tk | xyzzy | Puzzle | Prolog |
---|---|---|---|---|---|
96/day | 35/day | 18/day | 73/day | 28/day | 39/day |
先週、アクセス数が急増したのでびっくりしました。特に、xyzzy Lisp は 1 日で 100 Hit を突破することがありました。また、普段はひっそりとしている Puzzle でも、アクセス数が急増した日があったのには驚きました。もしかすると、学校の課題や演習などで、xyzzy Lisp や Puzzle を参考にされる学生さんのアクセスが多かったのかもしれません。なお、学校の課題や演習に関する質問はお答えしておりません。あしからずご了承ください。
ところで、xyzzy Lisp の「Common Lisp 入門」ですが、拙作 VTOL 用の Lisp 入門マニュアルを Common Lisp に書き直すだけでは面白くないので、ちょっと寄り道をして簡単なプログラムを追加していくことにしました。今後は寄り道をすることが多くなると思いますが、よろしくお付き合いくださいませ。
これからも頑張りますので、よろしくお願いいたします。
1 月 5 日 に出題したパズル「タイルの敷詰め」の解答です。タイルを敷き詰めることができるか否かは、チェスの盤面のように白黒の市松模様に塗り分けると簡単にわかります。次の図を見てください。
┌─┬─┬─┬─┐ ┌─┬─┬─┐ │■│□│■│□│ │□│■│□│ ├─┼─┼─┼─┤ ┌─┼─┼─┼─┤ │□│■│□│■│ │□│■│□│■│ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │■│□│■│□│ │■│□│■│□│ ├─┼─┼─┼─┤ ├─┼─┼─┼─┘ │□│■│□│■│ │□│■│□│ └─┴─┴─┴─┘ └─┴─┴─┘ (A) (B) 図 : タイルの敷詰め
1 × 2 のタイルは白と黒で塗り分けられますね。したがって、このタイルを敷き詰めることができれば、白と黒の個数は同じになるはずです。つまり、白と黒が同じ数だけないと、タイルを敷き詰めることはできないのです。図Aの場合、白と黒は 8 個ずつあるので、タイルを敷き詰めることができます。ところが図Bの場合、白は 8 個ありますが黒は 6 個しかありません。よって、タイルを敷き詰めることはできない、というわけです。
新春パズルも最後の問題になりました。簡単な問題なのでお気楽にどうぞ。
┌─┬─┬─┬─┐ ┌─┬─┬─┐ │ │ │ │ │ │ │ │ │ ├─┼─┼─┼─┤ ┌─┼─┼─┼─┤ │ │ │ │ │ │ │ │ │ │ ├─┼─┼─┼─┤ ├─┼─┼─┼─┤ │ │ │ │ │ │ │ │ │ │ ├─┼─┼─┼─┤ ├─┼─┼─┼─┘ │ │ │ │ │ │ │ │ │ └─┴─┴─┴─┘ └─┴─┴─┘ (A) (B) 図 : タイルの敷詰め
図Aの 4 × 4 の部屋を 1 × 2 のタイルで敷詰めます。マスは全部で 16 あるので、8 枚のタイルで簡単に敷詰めることができますね。それでは、図Bのように左上隅と右下隅の 1 マスが欠けている部屋を、1 × 2 のタイルで敷き詰めてください。
マスは 14 あるので、7 枚のタイルで敷詰めることができるように思われます。ところが、この問題は解くことができません。その理由を考えてください。