The Sweet Spot
On software, engineering leadership, and anything shiny.

Explorations in logic programming

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:

assignment_problem_1.rblink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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:

1
2
3
4
5
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:

1
2
3
4
5
6
7
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:

assignment_problem_2.rblink
1
2
3
4
5
6
7
8
9
10
11
12
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 reading

Comments