「KLIC プログラミングコンテスト」は、第五世代プロジェクトで 開発された並列論理型言語 KL1 で書かれたプログラムを、 以下の３部門について募集しています。
- (1)逐次環境部門
- (2)並列環境部門
- (3)自由課題部門
- (2)並列環境部門
(1)、(2) は与えられた課題の仕様を満たすプログラムが、(1) は 逐次環境で、(2) は並列環境で動作するように作成して下さい。
今年度の課題は、「逐次環境部門」と「並列環境部門」で異なります。
以下、「逐次環境部門」、「並列環境部門」の順に課題を説明します。
まず、一組のトランプ52枚（ジョーカーは含まないものとする）から、
25枚のカードが配られる。 この25枚のカードを5×5の桝目に並べるとする。
並べた桝目の各列それぞれをポーカーの手札として評価したとき、
より高い総合点となる並び方を、できるだけ早く求めよ。
なお、これら縦5列、横5列、対角線2列の合計12列によって構成される各手札は、
「１．総合点の計算方法」による手役とその評価値によって総合点を計算すること。
１．総合点の計算方法
３．応募作品に対する判定について
４．参考（手札の評価実験プログラム, 動作確認プログラムについて）
- 【役の基準点】
- ストレートフラッシュ （同一組の札の5枚続きの手）
- Straight Flush 2745600 点
- フォーカード （同じ数の札の 4 枚ぞろい）
- Four of a Kind 176000 点
- フルハウス（3枚の同位札と2枚の同位札からなる手）
- Full House 29333 点
- フラッシュ（同一組の札の5枚ぞろいの手）
- Flush 21500 点
- ストレート（異なる組の5枚続きの手）
- Straight 10767 点
- スリーカード（同じ数の札の 3 枚そろい）
- Three of a Kind 2000 点
- ツーペア（2枚の同位札2組からなる手）
- Two Pairs 888 点
- ワンペア（同じ数の札の2枚そろい）
- One Pair 100 点
- Straight Flush 2745600 点
- 【加点】
- 手札のうち、役を構成するのに用いられた札についてのみ、次の点を加える。
- なおこの加点は、各手役ごとに独立して計算されるため、同じ札が別の（縦、横、
- 対角線）の役に用いられた場合にも計算対象となる。
- A エース 14 点 （エースとして用いたとき）
- K キング 13 点
- Q クイーン 12 点
- J ジャック 11 点
- 10〜2は、その位の札の数 をそのまま加点とする
- A 1 点 （ストレートで1として用いたとき）
- K キング 13 点
- なおこの加点は、各手役ごとに独立して計算されるため、同じ札が別の（縦、横、
- 計算例： ツーペア K,K,8,8,A は、基準点 888点、
- 加点はKの2枚と8の2枚について 13×2+8×2 = 42 点 となる。
- よって、888+42 = 930 点 となる。
- ストレート 10,J,Q,K,A は、基準点 10767 点に
- 加点は 10+11+12+13+14 = 60 点 より、10767+60 = 10827点 となる。
- ストレートフラッシュ A,2,3,4,5 は、基準点 2745600 点に
- 加点が 1+2+3+4+5 = 15点 より、2745600 + 15 = 2745615点となる。
- よって、888+42 = 930 点 となる。
２.１ インタフェース
２.２ プログラミング上の制限
３. 応募作品に対する判定について
入賞は審査委員会の定める制限時間以内に得た最後の完全な
４. 参考（手札の評価実験プログラム, 動作確認プログラムについて）
参考として以下の２つのプログラムが FTP できます。
なお これらのプログラムは、変更されることがある。
1, 2, 3, 4, 5,
6, 7, 8, 9,10,
11,12,13,14,15,
16,17,18,19,20,
21,22,23,24,25
縦
0 | 0 | 124 | 118 | 0 | 932 対角線
------+------+------+------+------+--
ST | CA | DQ | H9 | HA | 128
D6 | SJ | H7 | DA | D5 | 0
H4 | CT | SQ | S9 | D9 | 118 横
S2 | S8 | H8 | S7 | DK | 116
C8 | CQ | DJ | C3 | S6 | 0
------+------+------+------+------+--
| 21546 対角線
TOTAL=23082
解について、その総合点の高さを主たる基準に、プログラム
の構成、添付文書のわかりやすさなどを考慮に入れて審査の上、
決定する。
（tar, gzip されている）
利用方法等の詳細については、解凍後 README.jを参照されたい。
変更については、本コンテストのメイリングリストにより通知される。
また審査時に以下のプログラムがそのまま用いられるとは限らないが、
点数計算方法は同じである。
評価実験プログラム(ftp)(10/22 修正)
（なお、希望者には mail にておくります。宛先(klic-contest@icot.or.jp)に
「逐次環境部門、評価実験プログラム希望」とメールして下さい）
評価実験プログラムの README 参照 →
[日本語],
[English]
動作確認プログラム(ftp)(但し、変更される場合があります)(11/13 更新)
（なお、希望者には mail にておくります。宛先(klic-contest@icot.or.jp)に
「逐次環境部門、動作確認プログラム希望」とメールして下さい）
動作確認プログラムの README 参照 →
[日本語],
[English]
コンウェイ(John Horton Conway)のライフゲームを作りましょう。入力で初
期状態と世代数が指定されるものとし, 最終状態を出力するものとします。
負荷分散をするのにどういうようにプログラムを書いたらいいでしょうか。ど
れくらい高速に計算できるでしょうか。
１．ライフゲームについて
３．応募作品に対する判定について
４．参考（グラフィカルユーザインターフェースなどについて）
１. ライフゲームについて
ライフゲームは, (理想的には無限の) 2 次元の格子状に並んだセルの状態
が規則によって自動的に変化していくゲームです。すべてのセルはオンとオフ
との 2 種類の状態のいずれかを取ります(以下ではオンのセルを ■ で, オフ
のセルを □ で表します)。そして, 時間の流れは離散的で, 世代から世代に
進みます。ある世代の状態によって次の世代の状態が決り, 続けて, 次の世代
の状態からその次の世代の状態が決り... というように進みます。
規則は以下の通りです。一つのセルに注目すると, 隣り合うセルに縦横斜め
あわせて 8 つのセルがあります(図 1. 参照)。★ を注目するセルとすると
☆ が隣り合うセルです。
☆☆☆
☆★☆
☆☆☆
図 1. 隣り合うセル
【規則 その 1】
注目するセルがオンの場合, 隣り合うセルでオンのものが 2 つ,
あるいは 3 つの場合, 次の世代でもオンとなります。隣り合う
セルでオンのものが 0, 1, 4, 5, 6, 7, 8 の場合, 次の世代で
はオフになります。
【規則 その 2】
注目するセルがオフの場合, 隣り合うセルでオンのものが 3 つ
の場合, 次の世代でオンとなります。隣り合うセルでオンのもの
が 0, 1, 2, 4, 5, 6, 7, 8 の場合, 次の世代でもオフのままで
す。
具体例をあげてみます。
【例 その 1 (ブリンカー)】
ブリンカーと呼ばれる周期 2 のパターンです。
□□□□□ □□□□□ □□□□□
□□□□□ □□■□□ □□□□□
□■■■□ □□■□□ □■■■□
□□□□□ □□■□□ □□□□□
□□□□□ □□□□□ □□□□□
世代 N 世代 N+1 世代 N+2
図 2. ブリンカー
【例 その 2 (安定なパターン)】
世代によって変化しない安定なパターンです。
□□□□□□ □□□□
□□■■□□ □■■□
□■□□■□ □■■□
□□■■□□ □□□□
□□□□□□
図 3. 安定なパターン
【例 その 3 (グライダー)】
移動していくパターンです。
□□□□□□ □□□□□□ □□□□□□ □□□□□□ □□□□□□
□□■□□□ □□□□□□ □□□□□□ □□□□□□ □□□□□□
□□□■□□ □■□■□□ □□□■□□ □□■□□□ □□□■□□
□■■■□□ □□■■□□ □■□■□□ □□□■■□ □□□□■□
□□□□□□ □□■□□□ □□■■□□ □□■■□□ □□■■■□
□□□□□□ □□□□□□ □□□□□□ □□□□□□ □□□□□□
世代 N 世代 N+1 世代 N+2 世代 N+3 世代 N+4
図 4. グライダー
２. プログラムについて
2.1 プログラムのインタフェース
応募作品では, モジュール名を life, 述語名を compute とする 3 引数の
述語を用意して下さい。
life:compute(世代数, 初期状態, 最終状態)
第 1 引数, 第 2 引数が入力で, 第 3 引数が出力となります。
第 1 引数は, 世代数として, 何世代後まで計算するかの整数が渡ります。
第 2 引数は, 初期状態としてオンのセルのリストが渡ります。
第 3 引数は, 最終状態としてオンのセルのリストが返るとします。
ここで, オンのセルは, X, Y を座標を示す整数とした時, p(X,Y) というファ
ンクタ p/2 のデータ構造とします。
また, オンのセルのリストは, それらの座標にしたがって昇順にソートされて
いるとします。ここで, 二つの座標 p(X0,Y0), p(X1,Y1) は, Y0 < Y1 あるいは
Y0 = Y1 で X0 < X1 のとき, そしてそのときのみ, p(X0,Y0) < p(X1,Y1) である
とします。
例(グライダー):
?- life:compute(4,[ p(2,1),
p(3,2),
p(1,3), p(2,3), p(3,3)],Result).
に対して,
Result = [ p(3,2),
p(4,3),
p(2,4), p(3,4), p(4,4)].
が求まります。
2.2 入力データの範囲について
入力データ中, および指定した最終世代までの間の各世代におけるオンのセル
座標は -2^20 から 2^20 の範囲にあるものとします。
2.3 プログラミング上の制限および注意点。
・C 言語のインライン挿入を使わないで下さい。
・並列なので, @node 使わないと意味がないことに留意して下さい。
３. 応募作品に対する判定について
入賞は審査委員会の定めるいくつかの初期状態パターンに対して要した計算
時間を主たる基準に, プログラムの構成と美しさ, 利用している手法の面白さ,
添付文書のわかりやすさなどを考慮に入れて審査の上, 決定します。
４. 参考（グラフィカルユーザインターフェースなどについて）
参考としてメインルーチンとグラフィカルユーザインターフェースのプログ
ラム, およびサンプル入力とその出力を添付します。tar, gzip されています。
(Mail で受けとる場合はさらに uuencode されています。)利用方法等の詳細
については, 解凍後 README を参照して下さい。
添付プログラム(ftp)
（なお、希望者には mail にておくります。宛先(klic-contest@icot.or.jp)に
「並列環境部門、添付プログラム希望」とメールして下さい）
添付プログラムの README 参照 → [日本語], [English]
このプログラムは, 変更されることがあります。その際, 変更については,
本コンテストの応募者のメイリングリストにより通知されます。
www-admin@icot.or.jp