Dear participants,
welcome in a new year of the CSP. Deadline for submitting solutions of this serires is October 20, 1997.
We wish you many good ideas.
The riots in our prisons are growing beyond admissible limits. And it is not only because they are crowded: much trouble causes the fact, that prisoners (recidivists) are always given new numbers, not the numbers they are used to. This actuality is not very welcome in jails, where averyone accosts each other by numbers.
A brand new project, Alcatras II., is supposed to solve this problem. When new prisoner arrives, the guards enter his name into the computer and software responds with NEW, if he was not here before or RECIDIVIST, if he does not come for the first time. The software also shows his number: It could be any free number (that is not any other's number) for a newcomer, but for a recidivist computer must choose his old number. You can assume that numbers are assigned only by this software.
Task: Write the software described above, so that it could run as fast and for as many prisoners as possible. Your software will be executed along with opening of the jail, so the jail is empty at the beginning. Software can run in everlasting cycle, becouse Alcatras II. is never going to crash. Names are composed of capital letters and spaces.
Example:
Input and output:
? LEX LUTHOR
NEW 3560
? JAMES BOND
NEW 007
? LEX LUTHOR
RECIDIVIST 3560
? LUISE LANE
NEW 806070
? JAMES BOND
RECIDIVIST 007
Sarge Serghei is the chief-commander of castle-guards. He is responsible for that always there will be K guards by gate. Sarge is a very thoughtful person, and so that he would not wrong anyone of his men by setting him to duty more than others, he decided to keep a precise account. It would be very time- and space- consuming to write the names of all guarding soldiers. So he decided to encode groups of guards as efficiently as possible - by numbers.
Task: Write procedures for guard-group encoding and decoding for him. Guards are numbered by natural numbers 1... N where N is the number of sarge's guards. Procedure Encode gets N - the number of guards, K - number of guards in one patrol (N>K) and list of K (different) guard numbers. Its output will be a natural number from 1... (N choose K), distinctly coding given group of guards. On the contrary, procedure Decode gets number N, number K and a code (number from 1... (N choose K)), generated by Encode and writes all the guard-numbers in patrol.
Tiribaki Air Ltd, a new airline, has it is great aim: driving all competition out of the marketplace. The fact, that Tiribaki Air has hired many programmers so that they ensured perfect services for the customers, indicates that they mean it business.
Task: Write a program for calculating minimal travel-time from one city to another. Because an airline operation is very money-demanding, there is no direct link between each two cities - there are occasions, when pasengers need to change airliners even more than once. One flight does not take more than 20 hours, airliners fly every day according to exact schedule. Kiribati Air Ltd airliners never delay, there is no storm, no fog and no breakdown, that would stop them.
On input, program gets flight schedule (contains number of links, for every link, there is departure city and time, arrival city and time), following by some question like "where from, where to". For every pair, output contains minimal time (in hours and minutes) needed for flight, or message, that journey is not possible.
Example:
Input:
3
Bratislava 15:00 Moskva 23:00
Moskva 05:00 BurundiDC 17:33
Moskva 22:00 Tokio 00:00
Bratislava Tokio
BurundiDc Moskva
Output:
Bratislava-Tokio: 33h 00m
BurundiDC-Moskva: Impossible
Notes: The time is global. City name is one word.
One teacher of sports had very stupid pupils. He had a lesson of sports with two groups of pupils at the same time. At the start of the lesson he wanted his pupils to line up so that group A will be in a left part of a line and group B will be in a right part. But it took a long time to his pupils to line up as he wanted and so he decided it would be quicker if he reorders them on his own. And also it must be quicker (as he thought) if he moves two neighbouring pupils at the same time. Now he wonders how to rearrange the pupils using the smallest possible number of such moves. Help him before he becomes angry.
Task: Write a program which gets as an input 2N characters (N < 36). N-1 of these characters are letters A, N-1 characters are letters B and two neighbouring ones are letters m. Characters mm denote the possition of free space in the line of pupils. The task is to find any shortest sequence of moves after which all the letters A are on the left of all the letters B (it does not matter where the free space is at the end). Each move consist of taking two neighbouring letters and putting them to a free space. Their place will be after a move occupied by a free space. It is not possible to exchange the left and right letter during a move. If no such sequence exists the program should write a message Impossible.
Example:
Input:
N=5
ABBAmmABAB
Output:
ABBAmmABAB
ABBABAAmmB
AmmABAABBB
AAAABmmBBB
Another input:
N=2
BmmA
Output:
Impossible
Each program written in the functional programming language consists of definitions of several functions. Each function has one or more inout variables. These variables, as well as the result of a function, are natural numbers (in this problem we consider 0 to be a natural number). This is an example of such program:
m(x,y)=0 <- x=0
m(x,y)=m(x-1,y)+y <- x>0
Clauses.
Definition of each function consists of several lines called
clauses. Each clause has this structure:
< function >(< arguments >)=< expression > <-
< condition >
where function is a name of a function, arguments is alist of
its input variables, successive variables are separated by commas.
expression gives the value which the function return if the
conditition condition holds. If the condition is always true, it can
be ommited.
Example: Let us see what value the function from our example returns for input variables x=2 a y=3:
m(2,3) = m(1,3)+3 = (m(0,3)+3)+3 = (0+3)+3 = 6
First, the clause is found in definition which corresponds to values of input variables. Because x>0, the second clause is chosen. m(2,3) is replaced by the expression in a clause (equality 1). It is still impossible to determine the value of the expression because it contains the function m. Therefore the definition of m is used again (for input values x=1 and y=3). The second clause is chosen again (equality 2). The expression still contains m, in this case with input values x=0 and y=3, and so the first clause is used. Thus we get an expression that contains only known function + and whose value can be easily determined. If you study the program better you can observe that our mysterious function f computes the product of its two inputs.
Exclusiveness of clauses. All clauses of one function should satisfy the conditition of exclusiveness. It means that for any values of input variables at most one of the conditions on the left sides of clauses for this function can hold. Thus we can ensure that the value of a function can be determined unambiguously. If none of the conditions hold, the function returns default value 0.
Predefined functions. It is allowed to use two predefined functions in a program: + and -. The function +(a,b) returns the sum of numbers a and b. The function -(a,b) returns difference of numbers a and b if a>= b (i.e. if the difference is a natural number) or it return 0, if a< b (in this case the difference is negative and we cannot work with negative numbers). For a better readability we will use a+b instead of +(a,b) and a-b instead of -(a,b).
Conditions and expressions. Condition in a clause can contain logical operators and, relations < , >, <=, >=, = and < > and expressions. Expression can contain parentheses, constants (e.g. 0, 1, 63 etc.), input variables, predefined functions and functions defined in a program including recursive calls.
Note: If a condition of some clause determines the value of some input variable, it is possible to replace this varible by the value in entire clause. For example the clause m(x,y)=0 <- x=0 can be expressed also as m(0,y)=0.
Tail recursion. A function is written in tail recursion, if the right side of each clause contains at most one recursive call and this call is not used in a condition and is not used as an input to some another function. Moreover all other function used in a clause must be written in tail recursion or predefined.
Tail recursion is very important because it can be implemented more efficiently (it is possible to implement it as a loop in other programming languages). Our example is not written in tail recursion because the recursive call m(x-1,y) in the second clause is an input to the function +.
Example: We will write the function m using tail recursion. We will use an auxiliari function m_1 with three inputs which is written in tail recusion.
m_1(x,y,z)=z <- x=0
m_1(x,y,z)=m_1(x-1,y,z+y) <- x>0
m(x,y)=m_1(x,y,0)
Task: Write definitions of two functions listed below using tail recursion. You can use also other functions which you define in your program using tail recursion as well. Only functions + and - are predefined. Do not forget to describe the meaning of all input variables and auxiliary functions and to give arguments for correctness of your program.
Example:
x 0 1 2 3 4 5 6 7 ... f(x) 0 1 1 2 3 5 8 13 ... g(x) 0 1 2 2 2 3 3 3 ...
Note: Try to write an efficient program but remember that slower and correct program is better than more efficient but incorrect one. (Complexity is measured by number of fuction calls.)