プログラム理論特論

情報

2001.12.17 小テストの解答例
・成績は、授業中に実施している小テストと2回のレポートによりつけます。
gofer.el にエラー発生行にジャンプする機能が追加されました。
レポート2問題を掲載しました。
レポート2 カウントダウンを掲載しました。
レポート2 解答例を掲載しました。


シラバス


レポート

レポート1 提出期限 1月11日

大きさ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
以下省略


レポート2 提出期限 2月8日

ペントミノは以下の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


ICEにおける gofer の使い方

その1 gofer コマンドを使う方法

端末エミュレータを開いて、gofer とタイプする。

その2 mule から使う方法

市村さんの貢献で、シンプルな 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 エラー発生行にジャンプ

ice で mule のフォントが変で画面が乱れるのを防止する方法

.cshrc に以下の行を追加する
    alias mule mule -fn fontset-standard
(ただし、変更後再ログインするまでは有効にならない)


資料など

gofer main page へのリンク

gofer英文マニュアル(長い)
Mark P. Jones, Gofer (reference manual) 1991. (goferdoc.pdf, 342KByte)   (goferdoc.ps, 856KByte)

補足資料
酒井、関数型プログラミング言語Goferについて、 (onGofer.pdf, 35KByte)   (onGofer.ps, 164KByte)

Haskellインタプリタ Hugs(goferの後継) へのリンク


Last modified: Sep.27.2002 by Masahiko Sakai(mail: sakai at i.nagoya-u.ac.jp).