・ 2001.12.17 小テストの解答例
・成績は、授業中に実施している小テストと2回のレポートによりつけます。
・gofer.el にエラー発生行にジャンプする機能が追加されました。
・ レポート2問題を掲載しました。
・ レポート2 カウントダウンを掲載しました。
・ レポート2 解答例を掲載しました。
大きさ3の魔方陣の解を求めるプログラムを作成せよ。
動作例(大きさ3) ? mahos [[2, 7, 6, 9, 5, 1, 4, 3, 8], [2, 9, 4, 7, 5, 3, 6, 1, 8], [4, 3, 8, 9, 5, 1, 2, 7, 6], [4, 9, 2, 3, 5, 7, 8, 1, 6], [6, 1, 8, 7, 5, 3, 2, 9, 4], [6, 7, 2, 1, 5, 9, 8, 3, 4], [8, 1, 6, 3, 5, 7, 4, 9, 2], [8, 3, 4, 1, 5, 9, 6, 7, 2]] (171541 reductions, 305348 cells, 3 garbage collections)
大きさ4の場合の動作例(上のプログラム中の rank の値を 4 に変更したもの) ? head mahos [1, 2, 15, 16, 12, 14, 3, 5, 13, 7, 10, 4, 8, 11, 6, 9] (3336011 reductions, 5769120 cells, 59 garbage collections)
私の出題の意図からはずれて、サイズ3固有の性質を使った解答が増えてしま いました。。。。みなさん楽しんで頂けたようなのでよいのですが。
名前 | reductions |
---|---|
鈴木 | 2141 |
加治 | 2942 |
市村 | 7221 |
市村 | 11392 |
李 | 12021 |
市村 | 14787 |
澤井 | 29771 |
加治 | 34517 |
堀江 | 37717 |
戸板 | 184434 |
澤井 | 289542 |
三浦 | 347745 |
高橋 | 347878 |
福田 | 389905 |
岩崎 | 448419 |
望月 | 456524 |
星野 | 508163 |
市村 | 661281 |
佐藤 | 687450 |
堀江 | 891904 |
伊藤 | 983128 |
水野 | 1206143 |
西尾 | 1885317 |
ペントミノは以下の12個のピースを6x10の枠内に埋め込む問題である。 F OO I O L O N O OO O O OO O O O O O OO O O P OO T OOO U O O V O OO O OOO O O O OOO X O W O Y O Z OO OOO OO OO O O OO O OO O これを解くプログラムを以下のように作成しなさい。 (1) それぞれのピースのデータの構造を設計し、ピースのデータを作成しなさい。 また、1個のピースデータを表示する関数を作成しなさい。 (2) ピースを部分的に埋め込んだ枠を設計しなさい。また、これを表示する 関数を作成しなさい。 (3) 解を求める関数を作成しなさい。 (Note 効率よく動かすためには部分解としてどんな情報を持つべきか 考えよ) (4) テトロミノで(3)のアルゴリズムをテストせよ。テトロミノには解がないので T の代わりに L を使え。つまり、Z,I,L,L,O で試せ。 Z OO I O L O O OO T OOO OO O O OO O O OO O 枠は 4x5 とする。 (5) 以下の項目について reduction 数を含む動作例を示せ。 テトロミノ ・最初の解のみ ・全解 (長いので「中略」をして提出する) ペントミノ ・最初の解のみ (全解は時間がかかりすぎるので測定しなくてよい) reduction数が多すぎて測定できない場合には、測定できる項目のみ提出せよ。
動作例(テトロミノ、全解) ? printsolutions 4 (sols 4) IIIIZ LOOZZ LOOZY LLYYY IIIIY LZYYY LZZOO LLZOO 中略 ZIIII ZZOOL YZOOL YYYLL (428286 reductions, 782333 cells, 8 garbage collections)
動作例(ペントミノ、最初の解のみ) ? printsolutions 5 [(head (sols 5))] FIIIIIZVVV FFFNNNZZZV LFNNYYYYZV LLLLWTYXUU PPPWWTXXXU PPWWTTTXUU (185586 reductions, 324968 cells, 3 garbage collections)
動作例(テトロミノ、ピースを3つ埋め込んだ部分解の最初の解) ? printsolutions 4 [(head (map thd3 (solutions 4 (alltypepieces 4) 3)))] IIII LLL L Y YYY (3867 reductions, 8227 cells)
ペントミノの全解 ? printsolutions 5 (sols 5) FIIIIIZVVV FFFNNNZZZV LFNNYYYYZV LLLLWTYXUU PPPWWTXXXU PPWWTTTXUU 中略 ZZUUUIIIII YZUFUNNVVV YZZFFFNNNV YYWTFXPPPV YWWTXXXPPL WWTTTXLLLL (2304489180 reductions, 2894214995 cells, 7174 garbage collections)
名前 | テトロ最初の解 | テトロ全解 | ペント最初の解 |
---|---|---|---|
戸板 | 97,607 | 426,342 | 297,908 |
岩崎 | 40,545 | 500,325 | 18,174,842 |
水野 | 220,182 | 999,711 | 22,415,105 |
佐藤 | 9,816 | 1,071,034 | 922,585 |
三浦 | 101,858 | 1,074,573 | 727,054 |
星野 | 235,611 | 1,387,988 | 52,644,668 |
福田 | 14,415 | 1,611,200 | - |
加治 | 20,662 | 1,755,690 | 388,172,503 |
鈴木 | 66,593 | 1,826,115 | 3,137,654 |
伊藤 | 411,334 | 1,832,715 | 704,564,258 |
森 | 12,504 | 3,612,574 | - |
高橋 | 1,072,867 | 6,699,977 | 1,570,287,169 |
澤井 | 4,390,622 | 8,868,241 | - |
西尾 | 782,645 | 13,035,684 | 4,155,576,370 |
藤岡 | 585,166 | 24,550,992 | - |
望月 | 3,009,352 | 51,132,639 | - |
レポートは 電子メールで
sakai@nuie.nagoya-u.ac.jp
宛に。subjectに学籍番号とレポート番号を(半角文字で)書くこと。
例
Subject: 28013499-9 report 2
端末エミュレータを開いて、gofer とタイプする。
市村さんの貢献で、シンプルな gofer.el ( ダウンロード) が利用できるようになりました。
市村さんの貢献で、gofer.el にエラー発生個所にジャンプする機能が追加 されました。(ダウンロード)
1. ファイル gofer.elを、mule のパスの通っている
ところに置く。例えば以下のようにする。
1.1 ファイル .emacs に以下の行がなければ追加する。
(setq load-path (cons (expand-file-name "~/elisp") load-path))1.2 ディレクトリ elisp を作って、その下に gofer.el を置く。
2. ファイル .emacs に以下の行を追加する。
(autoload 'gofer-mode "gofer" "Go into gofer mode" t) (autoload 'gofer-run "gofer" "Run gofer as inferior process" t) (set-variable 'auto-mode-alist (append '( ("\\.gs$" . gofer-mode) ;; gofer source ) auto-mode-alist))
3. mule でサフィックスが .gs のファイルを開くと、自動的に gofer のモー ドになる。コマンドは以下の通り。
In gofer source files \C-c l ソースの読み込み(必要ならgoferプロセスを起動) \C-c r goferプロセスの起動 \C-x ` エラー発生行にジャンプ \M-x next-error エラー発生行にジャンプ
alias mule mule -fn fontset-standard(ただし、変更後再ログインするまでは有効にならない)
gofer英文マニュアル(長い)
Mark P. Jones, Gofer (reference manual) 1991.
(goferdoc.pdf, 342KByte)  
(goferdoc.ps, 856KByte)
補足資料
酒井、関数型プログラミング言語Goferについて、
(onGofer.pdf, 35KByte)  
(onGofer.ps, 164KByte)
Haskellインタプリタ Hugs(goferの後継) へのリンク