KLIC PROGRAMMING CONTEST '97

Programming Subjects

INDEX
  1. Category 1 : Sequential Environment
    1. Problem: Solitaire Poker (or Patience Poker)
    2. Program
    3. Judgment
    4. Programs for Your Aids (Updated on Nov. 13.)
  2. Category 2 : Parallel Environment
    1. Problem: John Conway's Game of Life
    2. Program
    3. Judgment
    4. Programs for Your Aids
  3. Category 3 : Free Subject
    You can program on any subject either in a sequential or in a parallel environment.
    (No subject in this category)

Category 1 : Sequential Environment

Problem: Solitaire Poker (or Patience Poker)

You are dealt 25 cards from a deck of cards which does not include jokers. Place your cards on a board which is divided into a 5-by-5 square pattern. Aim for the best total score with the board. The board makes 12 hands with 5 columns, 5 rows, and 2 diagonals per round, each hand generates its own score.

1. How to mark the total score of a board

The total score is the sum total of the scores from the 12 individual hands. Each score of the 12 individual hands is the sum total of the "hand score" and the "additional score."

1.1 Hand Score

The following point scores are allotted to the following winning hands.

Note) An ace can be used as a low card, as well as a high card.

Possible straights with an ace are therefore 10, J, Q, K, A or A, 2, 3, 4, 5.

1.2 Additional Score

When a hand gets a hand score as stated above, additional points are added to the hand score for cards which play a role in the winning hand. These additional points are added up for each individual hand; the same card may be counted in other hands on the board.

ex. "K, K, 8, 8, A" gets 888 points for the hand score for winning with 'Two Pairs', and gets 42 points as an additional score for using two kings and two 8's to form the two pairs.

"10, J, Q, K, A" gets 10,767 points for the hand score for winning with a 'Straight', and gets 60 points as an additional score since the following points are allotted for the cards used in making that straight, 10+11+12+13+14.

"A, 2, 3, 4, 5", all in the same suit, gets 2,745,600 points for the hand score for winning with a 'Straight Flush', and gets 15 points as an additional score since the following points are allotted for the cards used in making that straight flush, 1+2+3+4+5.

2. Program

2.1 Interface

You should provide a predicate 'poker/2' in module 'solitaire'. It should accept 25 cards as the first argument and return a list of solution candidates as the second argument. You can define any auxiliary modules but they must have the name 'solitaire_xxxx' where you can name anything for 'xxxx'.

ex. ?- solitaire:poker([card(8,spades),card(2,diamonds),...],Result)

may return solution candidates as follows;

Result = [X1,X2,....],

X1 = [card(2,diamonds),....,card(8,spades),...],

X2 = [card(8,spades),...,card(2,diamonds),....],

(1) Input: The first argument is a list of 25 elements, each representing a card.

Each element has a functor structure of the form 'card(Rank, Suit)'. 'Rank' represents the rank of the card, which is either 2, 3, 4, 5, 6, 7, 8, 9,10, jack, queen, king, or ace. 'Suit' represents the suit of the card, which is either spades, hearts, diamonds, or clubs. The same card never appears twice in the list.

ex. card(10, spades), card(jack, clubs), card(ace, hearts)

(2) Output: The second argument is a stream to which solution candidates are sent.

Each solution sent has the same format as its input. The cards in a solution are regarded as a board consisting of cards in the following order.

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

The total score is summed up with scores for rows(1,2,3,4,5), ..., (21,22,23,24,25), columns (1,6,11,16,21), ...,(5,10,15,20,25), and diagonals (1,7,13,19,25), (5,9,13,17,21). Therefore anything symmetrical or rotational wins the same total score.

ex. A candidate:

[card(10,spades), card(ace,clubs), card(queen,diamonds),

card(9,hearts), card(ace,hearts), card(6,diamonds),

card(jack,spades), card(7,hearts), card(ace,diamonds),

card(5,diamonds), card(4,hearts), card(10,clubs),

card(queen,spades), card(9,spades), card(9,diamonds),

card(2,spades), card(8,spades), card(8,hearts),

card(7,spades), card(king,diamonds), card(8,clubs),

card(queen,clubs), card(jack,diamonds), card(3,clubs),

card(6,spades)]

This candidate equates to the following board formation and scores. Here, the suits- spades, hearts, diamonds, and clubs are represented as S, H, D, C, and the ranks- 10, jack, queen, king, and ace are represented as T, J, Q, K, and A, respectively.

columns

0

0

124

118

0

932

diagonal

ST

CA

DQ

H9

HA

128

D6

SJ

H7

DA

D5

0

H4

CT

SQ

S9

D9

118

rows

S2

S8

H8

S7

DK

116

C8

CQ

DJ

C3

S6

0

21546

diagonal

TOTAL=23082

Remark) Every candidate must be instantiated completely before it is put to the output stream. Never use incomplete messages and unbound variables for any of the candidates. Any number of candidates may be sent to the output stream, but only the last one sent within the time limit is considered. (To send only completely instantiated candidates to the stream, you should make sure that the whole data structure is instantiated by using the guard predicate 'wait /1' for each element of the structure.)

2.2 Programming Restrictions

(1) Never use inline C codes.

(2) Never use priority specification of the form:

'GOAL@priority(ABSPRIO)'.

Only use the forms:

'GOAL@lower_priority' and

`GOAL@lower_priority(RELPRIO)'

3. Judgment

The judging committee will select the winners mainly considering the score of the last complete solution obtained, also taking excellence of program construction and quality of attached documents into account.

4. Programs for Your Aids

For your programming aids, you can ftp a sample program for evaluating hands and an evaluation program for 'Solitaire Poker'. The programs are compressed by 'tar' and 'gzip' . For details, consult the file 'README.e' after decompressing. The programs may be revised without notices. You can get revision information if you subscribe to the mailing list prepared for this contest. These programs themselves may or may not be used for the judgment, but the scoring rule will remain the same. For more information, please contact the contest secretariat. (klic-contest@icot.or.jp)

Program for Hand Evaluation(ftp)(Updated on Oct. 22.)

README of Program for Hand Evaluation: [Japanese] [English]

Evaluation Program for 'Solitaire Poker'(ftp)(Updated on Nov. 13)

README of Evaluation Program for 'Solitaire Poker' : [Japanese], [English]

Category 2 : Parallel Environment

Problem: John Conway's Game of Life

Let's write a parallel program in KL1 solving "Conway's Game of Life". Given an initial state and the number of generations, the answer is the final state that the program computes. What load balancing strategy do you employ? How fast a program can you write?

1. About The Game of Life

The Game of Life is played on a square board which is a possibly infinite grid of cells. Each cell can have either of two states, ON and OFF. The game proceeds generation by generation, and the new state of a cell is determined by the states of cells at the previous generation. A user determines which cells are ON at generation 0, and subsequently, various patterns may appear, disappear, and evolve on the board. A cell's state changes according to a set of the following transition rules.

About transition rules:

In the Figure 1, the central cell "o" is surrounded by eight neighbor (adjacent) cells "+". 

+++
+0+
+++
Figure 1.  Surrounding neighbor cells

[Rule 1]

Suppose that a cell is ON at generation N. If the number of ON cells surrounding the cell is two or three, the state of the cell at generation N+1 is ON. Otherwise, the state becomes OFF.

[Rule 2]

Suppose that a cell is OFF at generation N. If the number of ON cells surrounding the cell is just three, the state of the cell at generation N+1 becomes ON. Otherwise, the cell keeps OFF.

Examples:

In the following figures, "0" stands for ON, and "+" OFF.

[Example 1 (Blinker)]

Here is a pattern called "Blinker", the cycle time of which is two generations. 

+++++  
+++++ 
+000+  
+++++  
+++++ 
+++++ 
++0++ 
++0++ 
++0++ 
+++++ 
+++++
+++++
+000+
+++++
+++++

Generation

N

N+1

N+2

Figure 2. Blinker
[Example 2 (Stable patterns)]

Here are stable patterns which do not change in any generation. 

++++++ 
++00++ 
+0++0+ 
++00++ 
++++++   
++++
+00+
+00+
++++
Figure 3. Stable patterns
[Example 3 (Glider)]

Here is a pattern called "the Glider", which moves around on a board. 

++++++ 
++0+++ 
+++0++ 
+000++
++++++ 
++++++  

++++++
++++++ 
+0+0++
++00++ 
++0+++
++++++

 

++++++
++++++ 
+++0++
+0+0++ 
++00++ 
++++++

 

++++++ 
++++++
++0+++ 
+++00+
++00++
++++++

 

++++++
++++++
+++0++
++++0+
++000+
++++++

Generation

N

N+1

N+2

N+3

N+4

Figure 4. Glider
2. Program

2.1 Interface

Please provide a predicate 'compute/3' in the module 'life' as such:

life: compute (Number Of Generations, InitialState, FinalState)

where the first and second arguments are input, and the third argument is output.

The first argument, "NumberOfGenerations" takes an integer, "N," as input, which lets the predicates compute the answer, N generations later.

The second argument, "InitialState" takes a list as input, which means ON cells in an initial state.

And the third argument, "FinalState," returns a list as output,which represents ON cells in a final state where time goes for N generations.

In the lists at the second and third arguments, an ON cell is represented by p(X,Y), where two integers X and Y correspond to X and Y positions on a board, respectively.

Besides, a list of ON cells should be sorted in ascending order, where the comparison of p(X0,Y0) and p(X1,Y1) is defined as: p(X0,Y0) < p(X1,Y1) iff Y0 < Y1 or Y0 = Y1 and X0 < X1.

Example (Glider): 

	
?- life:compute(4,[           p(2,1),
		                                p(3,2),
			      p(1,3),  p(2,3),  p(3,3)],Result).
yields:

	Result = [            p(3,2),
                                     p(4,3),
	  	     p(2,4), p(3,4), p(4,4)].

2.2 The Range of Input Data

We suppose that the size of a grid of cells is -2^20 to 2^20; so is the range of X and Y for p(X,Y) as above.

2.3 Programming Restriction

The contestants have to

(1) use the @node pragma for parallelization and

(2) not use 'Inline C code'.

3. Judgment

A jury will select winners mainly by taking into account execution timing for several input patterns provided by AITEC; in addition, program construction, the development of algorithms, programming skill, the quality of attached documents, and so on will be considered.

4. Programs for Your Aids

For your programming aids, a sample program including a main routine and GUI software is provided, and a sample session script is enclosed together.

The software package is made by 'tar' and 'gzip' commands.

Please see the README.e file in detail after uncompression.

The software may be revised without previous notice, but you will be able to get up-to-date information if you subscribe to the mailing list dedicated to this contest. Please contact the contest secretariat. (klic-contest@icot.or.jp)

Program for Your Aids(ftp)

README of Program for Your Aids: [Japanese] [English]