ACM 2000 Contest in Curry
December 2001

This page contains the solutions of some problems of an ACM programming contest. The contest is the 2000 Pacific NW Regional selection. The contest was won by Stanford with 5 solved problems. Portland State placed 26th with 2 solved problems.

The programming languages allowed by the contest are C, C++, Pascal and Java. In this page, I present solutions in PAKCS, a popular implementation of Curry, a declarative language.

Problem A

Problem B

The program is purely functional, i.e., no logic feature is used. In fact, the same program is executed non only by Curry, but by Haskell as well. The program represents a number as a list of (decimal) integers in the range 0 through 35. Two number representations are added element-wise. For each possible base, the representation of s1+s2 (adjusted for carries) is compared with s3.

Problem C

There are two interesting functional logic aspects in the program. One is how to partition a deal of 8 cards into 2 sets of 4 cards. For this, solve the following equations: 
        A++[P]++B++[Q]++C++[R]++D++[S]++E =:= deal
where deal is the set of 8 cards, and all the upper case letters are free variables. Then, the two sets are 
        [P,Q,R,S]
        A++B++C++D++E
The second aspect is to computation of the set of all subsets of a set hc. This is accomplished by: 
        parts = findall \x -> subset hc =:= x
              where subset [] = []
                    subset (x:xs) = x:subset xs
                    subset (_:xs) = subset xs
The proposed solution corrects an error in the second example of the problem.

Problem D

This is a fairly complicated program. A key operation of the program is to swap two elements at positions i and j of a list p. For this, solve the following equations: 
        p =:= X++Ki:Y++Kj:Z &> flength X =:= i &> flength Y + i + 1 =:= j
where X, Ki, Y, Kj and Z are free variable, and flength and ++ are flexible length and concatenation. The swapped list is then: 
        X++Kj:Y++Ki:Z
In the program, there would be some opportunities to use the encapsulated search features of Curry, but the resulting search space is too large for the small laptop that the programmer used for the code developemnt.

Problem E

The test for encoding is executed by narrowing. String and text are represented as lists of characters. A string (c:cs) is embedded in a text t if and only if the following equation holds: 
        t =:= X++(c:Ts) & length X + 1 =:= N
where X, Ts and N are free variables and the test is recursively applied to cs and Ts. In an imperative language, the above equation is replaced by 3 nested loops.

Problem F

The program solves the problem by brute force, with a binary search on the power of the transmitter. The use of some higher-order functions helps to keep the solution relatively short.

Problem G

A move is computed by solving an equation such as the following by narrowing: 
        a =:= X++[Arrow d x Z]++Y & (x==c) =:= False & Z =:= u !! (c-1)
where a defines all the arrows, u the colors of the circles, and c and d the circles holding the counters. X, Y and Z are free variables. The program is pretty standard in that it employs a couple of simple patterns. The input should be eased by library functions.

Problem H

The program is mostly functional, but it uses narrowing to parse some constructs. For example, if ip is a string containing a dotted 4-tuple representing an IP address: 
    ip =:= a++'.':b++'.':c++'.':d
the above equation extracts each element of the 4-tuple which is converted to an integer using the library operation readInt.
Contact antoy@cs.pdx.edu
Last updated Mon Sep 23 15:22:15 PDT 2002