PROGRAMMING SUBJECTS for the KLIC Programming Contest'96
1 What is "multiset?"
Please read the following explanation on the notion of "multisets"
first.
A radio network recently offered several giveaway packages to its listeners.
Each of the packages attracted much interest, and some people applied for more than one package.
To pigeonhole the applications, they asked applicants to write down their
contact telephone number. Let us assume that an applicant is identified
by this telephone number. If more than one person from the same family applies
for the same package or one person applies more than once using the names
of family members, then all the applications are assumed to be from the
same person, but we decided to ignore this.
Lists of applicants are primarily used when drawing lots, but in addition,
information on who wanted what are of great value when deciding prizes in
future giveaway packages and, more importantly, for marketing purposes.
For ease of explanation, we'll assume that telephone numbers consist of
only one digit in the following.
Assume, for example, that package A is applied for by those with telephone
numbers 7, 1, 2, 7, and 7.
Here, the one with number 7 applied three times
for the same package.
Those who applied for package B had numbers 5, 7, 2, and 7.
The applicants can be represented by two multisets: A = {7,1,2,7,7} and
B = {5,7,2,7}. With multisets, the order of elements is not significant.
Thus, all {7,1,2,7,7}, {2,1,7,7,7}, and {7,2,7,1,7} mean the same multiset
A.
By applying operations to multisets, we can obtain various information.
The
following shows several operations and their examples.
Union:
Packages A and B are different packages but some drawing lots should
be made in common.
We need a joint list of those who applied for both
of the packages.
With the above values of two multisets, the union
operation is as follows:
{7,1,2,7,7}\cup{5,7,2,7}={7,7,2,7,7,5,1,7,2}
Contraction:
For some drawing lots, multiple applications from one person
should be regarded as a single application.
The contraction operation,
denoted by |{}|, removes all the duplicated elements as follows:
|{7,1,2,7,7}| = {2,1,7}
|{5,7,2,7}| ={5,7,2}
Intersection:
We'd like to know who applied for both packages A and B.
If one applies multiple times to both, we also want to know this.
This
information can be obtained by computing the intersection that
enumerates common elements of two multisets, as follows:
{7,1,2,7,7}\cap{5,7,2,7}= {7,2,7}
Difference:
We'd like to know who prefers one product to another and how
strongly.
A guess is made by knowing who applied for package A more
times than for package B.
The following difference operation fulfills
this need.
{7,1,2,7,7}\{5,7,2,7}= {7,1}
{5,7,2,7}\{7,1,2,7,7}= {5}
2 These are the problems you should solve.
Now comes the main body of the problem.
Write a program module multi_set that has the following seven predicates:
- A predicate that converts a multiset given as a list L into some
appropriate internal representation M: encode(L, M)
- A predicate that converts internal representation M back to list
representation L: decode(M, L)
- A predicate that computes the union of two multisets in internal
representation M0 and M1, M0 \cup M1, into M: union(M0, M1, M)
- A predicate that computes the intersection of two multisets in
internal representation M0 and M1, M0 \cap M1, into M: intersection(M0, M1, M)
- A predicate that computes the difference of two multisets in
internal representation M0 and M1, M0 \ M1, into M: difference(M0, M1, M)
- A predicate that removes duplicated elements of a multiset in
internal representation M0 to M, M = |M0|,: contraction(M0, M)
- A predicate that chooses one arbitrary element from a multiset in
internal representation M, and returns the element E and the rest of the
multiset S, M = {E} \cup S: choose(M, E, S)
Cases when M is an empty multiset may be neglected.
3 Your program(s) will be checked as follows:
Programs are examined by calling the predicates 1 through 7 from testing
programs provided by AITEC.
The testing programs give multiset data as a list of integer numbers
possibly with duplicates.
In this contest, the elements of multisets are restricted to integer
numbers. Applicants' programs may convert data in list format to their own
format for various operations. The final answer will be converted back to
the list format.
To give an idea of the examination method, a sample test program is
enclosed in this document. Note that this is not the program used in the
official examination.
The size of the data will be considerably large. The handling data of
invalid format need not be considered. For example, the encoding predicate
can assume that the input is a list of integers and other predicates can
assume that all the input parameters are the results of encoding or other
operations performed by the program itself.
Our interest in concurrent and parallel programming is in realizing
programs that can handle a variety of input data on a variety of
architecture elegantly and efficiently. Please keep such variety in mind
when constructing your program.
No single criteria is sufficient for estimating concurrent and parallel
programs. Please bear in mind that the examination process includes reading
the source code through.
Please do not forget to attach documents describing why you thought the
way you programmed it was appropriate.
4 An example of the checking program
To give an idea of the examination, a sample test program is enclosed
in this document. Note that this is not the program used in the official
examination.
:- module main.
main:-
go1(A1),
io:outstream([print(A1),nl]).
go1(L):-
gen_3_ms(L0,L1,L2), % 3 multi sets generated by random numbers
multi_set:encode(L0,M0),
multi_set:encode(L1,M1),
multi_set:encode(L2,M2),
% symmetrical set operations done at the following 6 lines
multi_set:intersection(M0,M1,M0i),
multi_set:intersection(M1,M2,M1i),
multi_set:intersection(M2,M0,M2i),
multi_set:difference(M0i,M1i,Md0),
multi_set:difference(M1i,M2i,Md1),
multi_set:difference(M2i,M0i,Md2),
multi_set:contraction(Md2,Mc), % a slightly irregular operation
multi_set:union(Md0,Md1,M01),
multi_set:union(M01,Mc,Mu),
multi_set:decode(Mu,L).
gen_3_ms(L0,L1,L2):-
gen_ms_list(97,~(2 << 6 - 1),3,L),
% in the official examination, different parameters will be used
( L = [M0,M1,M2] -> M0 = L0, M1 = L1, M2 = L2 ).
% decompose a list and pick up elements
/*
* create a list, each element of which is a multi set (the max value of
* its elements is Max, the number of its elements is Card) and the length
* is ListLen
*/
gen_ms_list(Max,Card,ListLen,MSs):- true |
generic:new(random_numbers)+RDM+97,
gen_ms_list_0(Max,Card,ListLen,MSs)-RDM.
gen_ms_list_0(Max,Card,ListLen,MSs)-RDM:- ListLen =:= 0 |
MSs = [].
gen_ms_list_0(Max,Card,ListLen,MSs)-RDM:- ListLen >= 1 |
gen_ms(Max,Card,MS)-RDM,
MSs = [MS|N],
gen_ms_list_0(Max,Card,~(ListLen-1),N)-RDM.
/* create a multi set, the max value of its elements is Max and the number
of its elements is Card */
gen_ms(Max,Card,MS)-RDM:- Card =:= 0 |
MS = [].
gen_ms(Max,Card,MS)-RDM:- Card >= 1 |
RDM <= Random, % generate a random number on demand
MS = [~(Random mod Max)|N],
gen_ms(Max,~(Card-1),N)-RDM.