Afa Zhou's Solutions for GCJ 2017

Here are my programs, all written in Picat, for the GCJ'17 problems. My primary purpose of participating in GCJ is to have fun, and the secondary purpose is to test the Picat language and its various modules.

I solved three problems completely in the Qualification Round. The program I wrote for the Fashion Show problem was not efficient enough, even for solving the small dataset. An improved version that uses the mip module solves the large dataset easily.

Round 1A had tough problems, and I only solved two small datasets. The program for Alphabet Cake, which refines the submitted one, uses the sat module. Surprisingly it solves the large dataset without using any of the insights. The program for Play the Dragon uses the planner module. It can only solve the small dataset. Since some of the instances are unsatisfiable, the search predicate best_plan_unbounded is used, rather than best_plan, which is based on iterative deepening search and is unable to detect unsatisfiability. The program for Ratatouille was written after the competition. It can only solve the small dataset.

Round 1B looked relatively easy for Picat and me. I submitted solutions to all but the large dataset of problem C. Later the judge determined the solution to A's large dataset "incorrect". The correctecd version for problem A solves the large dataset easily.

I didn't compete in Round 1C because it was 5AM in NY. I solved the problems afterwards. The solution to problem A uses tabling; the solution to problem B is based on Alfredo Beaumont's 0/1 integer programming model; the solution to problem C (small dataset) uses an idea given in the contest analysis.

So far, all of Picat's modules for combinatorial search have been put into good use: cp is used in Tidy Numbers, mip is used in Fasion Show, Stable Neighbors, and Parenting Partnering, sat is used in Alphabet Cake, and tabling (including planner) is used in Play a Dragon and Pony Express. I can't imagine how I would do without Picat.

Qualification Round

Round 1A

Round 1B

Round 1C

Round 2

To be continued

Related Pages