Explorations in logic programming

29 November 2014

Out of Storybook, a side project I’ve been doing for a friend, I had the opportunity to model the problem domain as a constraint satisfaction problem (CSP). It goes:

A set of students are assigned a book a week. Write plan generator to create a set of student-book assignments for that week, given the following constraints:

All students must receive a book.

Each book may only be assigned to one student at a time.

A student may not be assigned a book s/he has received before.

Being that this was a Rails app, I put Amb, a Ruby-based CSP solver, to use. Amb is derived off Jim Weirich’s original source code, implementing a simple backtracking algorithm. (More interesting reading on the original idea behind the amb operator, proposed in a paper by LISP founder John McCarthy in 1963.)

Not having written any CSP logic since my university days, I tried to come up with a naive solution. It goes something like this:

``` ruby assignment_problem_1.rb https://github.com/andrewhao/storybook/blob/8bb03101d46472e36ee400b79c30d941d3a4bd39/lib/assignment_problem.rb class AssignmentProblem def solve # Generates the cross product of sids and bids. spaces = student_ids.product(bag_ids)

# Now generate combinations of those uniques
full_solution_space = spaces.permutation(student_ids.count).to_a

# Assign those to the CSP
plan = solver.choose(*full_solution_space)

solver.assert all_students_have_bags(plan)
solver.assert assigned_bags_are_unique(plan)
solver.assert assigned_bags_without_student_repeats(plan)

plan   end end ```

Well this would work for 2 students and 2 bags, 3 and 3, 4 and 4, but would blow up and overflow the stack when we got to 5 students and 5 bags. Why? I was forcing Ruby to generate the full solution space before starting the CSP search problem:

student_ids = [:s1, :s2]
bag_ids = [:b1, :b2]
# Modeled as: the complete solution space of assignments
spaces = student_ids.product(bag_ids) 
# => [[:s1, :b1], [:s1, :b2], [:s2, :b1], [:s2, :b2]]

Then I was taking that cross product and brute-force generating all possible permutations internal to that:

spaces.permutation(student_ids.count).to_a
# => [[[:s1, :b1], [:s1, :b2]], [[:s1, :b1], [:s2, :b1]],
#     [[:s1, :b1], [:s2, :b2]], [[:s1, :b2], [:s1, :b1]],
#     [[:s1, :b2], [:s2, :b1]], [[:s1, :b2], [:s2, :b2]],
#     [[:s2, :b1], [:s1, :b1]], [[:s2, :b1], [:s1, :b2]],
#     [[:s2, :b1], [:s2, :b2]], [[:s2, :b2], [:s1, :b1]],
#     [[:s2, :b2], [:s1, :b2]], [[:s2, :b2], [:s2, :b1]]]

The most obvious thing that stood out to me like a sore thumb was how I wasn’t simply trusting the constraint-based nature of the problem and expressing the problem in terms of the constraints, instead of attempting to imperatively generate the solution. Usage of Enumerable#permutation resulted in an O(n!) algorithm, which is unacceptable. Back to the drawing board:

``` ruby assignment_problem_2.rb https://github.com/andrewhao/storybook/blob/e2dd94add2b5949d87968ab650a31b4bdfb9e8a2/lib/csp/assignment_problem.rb class AssignmentProblem # Generates tuples of student => bag assignments def solve student_ids.each do |sid| bid = solver.choose(*bag_ids) partial_plan[sid] = bid solver.assert assigned_bags_are_unique(partial_plan) solver.assert assigned_bags_without_student_repeats(partial_plan) end

partial_plan.to_a   end ```

Note the main difference here is how I’ve re-tooled the solver to assign variables one at a time (in L5) and check constraints after each assignment. This simplifies the domain of the problem as a graph search and helps us more easily reason about this program.

Further explorations

Follow my csp-solvers project, where I attempt to rewrite this in Prolog and Clojure in an attempt to see how language affects how we reason about problems like these. It’s gonna be fun.

Further explorations

Further reading

Liking what you read?