In this contest we aimed to show that declarative approach to problemsolving can be more convenient than the traditional imperative. However, the first several problems were supposed to aquaint the competitor with the basic language syntax and its libraries. All reference solutions are written by kit1980.
To solve a quadratic equation, one has to use a library function
sqrt and an if-then-else construct. Besides, this problem was supposed to show that Picat has foating-point numbers. :-)
main => A = read_real(), B = read_real(), C = read_real(), D = B * B - 4 * A * C, X1 = (-B - sqrt(D)) / (2 * A), X2 = (-B + sqrt(D)) / (2 * A), if D == 0 then println(X1) else printf("%w %w%n", min(X1, X2), max(X1, X2)) end.
A string manipulation problem: library function
slice allows to get a substring of the given string,
reverse, well, reverses it, and
++ is concatenation operator. Alternatively, one could use loops and print the answer character-by-character.
main => S = read_line(), N = length(S), X = reverse(slice(S, 1, N // 2)) ++ reverse(slice(S, 1 + N // 2)), println(X).
This problem can be solved using complete search (for each X check whether a suitable Y exists). The reference solution uses constraint programming, which effectively implements a search with pruning and allows to get rid of explicit search loop.
import cp. main => A = read_int(), B = read_int(), C = read_int(), X #> 0, Y #> 0, if A * X + B * Y #= C then Solutions = solve_all([X, Y]) else Solutions =  end, println(length(Solutions)), foreach ([I, J] in Solutions) printf("%d %d%n", I, J) end.
A * X + B * Y #= C sets variable constraint. At this stage the system can understand that there are no solutions and proceeed to
else branch. Otherwise
solve_all function will return a list of all solutions.
This problem can be solved in a variety of ways, from imperative loops to constraint programming. The reference solution uses library function
subtract which subtracts one sorted list from another.
A..B creates a list of integers from A to B. Output is done using list comprehension. This problem is the only one in which our solution uses
:= — an exclusively imperative destructive assignment operator.
import ordset. import util. main => X = 1..1000, N = read_int(), foreach (_I in 1..N) A = read_int(), B = read_int(), X := subtract(X, A..B) end, println(join([to_string(V) : V in [length(X) | X]])).
This problem can be solved in at least two ways. The "math" way requires noticing that a set of N-2 "1"s, one "2" and one "N+D" is always a valid solution. Of course, other solutions might exist, for example for N = 4, D = 1 a valid solution is 1, 1, 3, 3.
The reference solution uses constraint programming, that allows to avoid thinking and just translate the problem statement to Picat.
import cp. import util. main => N = read_int(), D = read_int(), Vals = new_list(N), Vals :: 1..10000, prod(Vals) #= sum(Vals) + D, solve(Vals), println(join([to_string(V) : V in Vals])).
This problem uses breadth-first or depth-first search. In Picat, like in Prolog, depth-first search with backtracking is built-in. Tabling technique is used for memoization and for automated search of maximum: expression
table(+, +, +, max) means that the first three parameters of the predicate are input, the last one is output, and has to be maximized.
?=> means non-determinism: call to
jump itself can return different values for same input parameters, so
table selects the maximal of them.
best_frog uses the same technique to avoid an explicit loop over frogs to search for the best frog.
table(+, +, +, max) jump(X, Y, K, Dist) ?=> ( NewX = X + K, NewY = Y ; NewX = X - K, NewY = Y ; NewX = X, NewY = Y + K ; NewX = X, NewY = Y - K ), land(NewX, NewY), jump(NewX, NewY, K, Dist). jump(X, Y, _K, Dist) => Dist = abs(X) + abs(Y). table(-, max) best_frog(K, Dist) ?=> between(1, 10, K), jump(0, 0, K, Dist). main => N = read_int(), Facts = [$land(X, Y) : _I in 1..N, X = read_int(), Y = read_int()], cl_facts(Facts), best_frog(_K, Dist), println(Dist).
A classic dynamic programming problem. The reference solution uses tabling to implement recursion with memoization, similar to problem 530F - Jumping frogs.
table(+, +, min) edit(I, J, Cost) ?=> str(S), goal(G), N = length(S), M = length(G), ( I <= N, J <= M, edit(I + 1, J + 1, NextCost), Cost = abs(ord(S[I]) - ord(G[J])) + NextCost ; I <= N, edit(I + 1, J, NextCost), Cost = ord(S[I]) - 0'a + 1 + NextCost ; J <= M, edit(I, J + 1, NextCost), Cost = ord(G[J]) - 0'a + 1 + NextCost ; I > N, J > M, Cost = 0 ). main => S = read_line(), G = read_line(), cl_facts([$str(S), $goal(G)]), edit(1, 1, Cost), println(Cost).
This problem requires a reasonable search of possible triangle vertices with a check whether all points are inside. The points' coordinates can have values up to 100, so the triangle's vertices never need to have coordinates over 200.
import cp. main => N = read_int(), A :: 1..200, B :: 1..200, foreach (_I in 1..N) Xi = read_int(), Yi = read_int(), B * Xi #<= A * (B - Yi) end, solve([$min(A * B)], [A, B]), println(A * B / 2).
This problem is in fact a graph coloring problem. The reference solution uses constraint programming with
all_distinct constraint. To speed up program execution one had to notice that the first variable is always 1. With this observation one could also use
all_different constraint (these two constraints differ in internal algorithm implementation), without it
all_different is too slow.
import cp. import util. main => N = read_int(), K = read_int(), Vars = new_array(N), Vars :: 1..N, Vars #= 1, foreach(_I in 1..K) [_ | Indexes] = [to_integer(A) : A in split(read_line())], all_distinct([Vars[Idx] : Idx in Indexes]) end, List = to_list(Vars), MaxC #= max(List), solve([$min(MaxC)], Vars), println(join([to_string(V) : V in Vars])).