Abstract:

Picat (picat-lang.org) is a logic-based multi-paradigm programming language that integrates logic programming, functional programming, constraint programming, and scripting. Picat takes many features from other languages, including logic variables, unification, backtracking, pattern-matching rules, functions, list/array comprehensions, loops, assignments, tabling for dynamic programming and planning, and constraint solving with CP (Constraint Programming), MIP (Mixed Integer Programming), SAT (Satisfiability), and SMT (SAT Modulo Theories). These features make Picat suitable for scripting and modeling. Picat has been used in programming competitions, including ASP, Prolog, LP/CP, and Google Code Jam. For competitive programming, a language should be both expressive and efficient. With expressiveness, algorithms and models can be coded concisely and within the allowed time limit. With efficiency of the language system, programs can produce answers within the memory and time limits. I’ll report on the solutions in Picat to the five problems used in the 2019 LP/CP Programming Contest.^[1] The problems are all combinatorial, and all have practical application backgrounds, including code deciphering, resource allocation, auto-programming, game design, and operations research optimization. The problems require different modeling techniques and solvers. One of the programs employs the CP module, one uses the planner module, and three others rely on the SAT module. These solutions well illustrate the use of Picat’s language constructs and solver tools, and, in hindsight, demonstrate the fitness of Picat for competitive programming. For each problem, I’ll give a problem description, a program, and the underlying techniques used by the program. I’ll also compare Picat, as a general-purpose language, with Prolog, Haskell, and Python, and, as a modeling language, with ASP, MiniZinc, and AMPL.


^[1] The solutions are available at: http://picat-lang.org/pc/lpcomp2019.html. I won the online track of the contest with these solutions.