Search code examples
clojureclojure-core.logic

Clojure core.logic on Finite Domain subtraction not working as expected and not documented


I have written a Clojure program to solve a fairly simple problem. Consider a vector of a fixed size that we need to fill with integers. We must abide by the following rules.

  1. Every integer must be chose from a give set of integers.
  2. Every spot in the vector has its own minimum. The assigned must be greater or equal
  3. The difference between any two adjacent integers must be no more than a given maxStep
  4. There should be only at most maxDistinct distinct integers used in the output.

This is my attempt at solving the problem with comments.

(ns thickness-optimizer.core
  (:refer-clojure :exclude [==])
  (:use clojure.core.logic)
  (:require [clojure.core.logic.fd :as fd]))


; This is not working properly. It seems very much directional, in that
; it matters if I use lower-upper or upper-lower. The result changes if
; I swap the order of the arguments on the last line of this function.
; I suspect it's an issue where the diff needs to be in the same domain
; as the lower and upper or that possibly negatives are not allowed?
(defn stepLimit [maxStep]
  (fn [lower upper]
    (let [diffDom (apply fd/domain (range (- maxStep) (+ maxStep 1)))]
      (fresh [diff]
        (fd/dom diff diffDom)
        (fd/- lower upper diff)))))
 

(defn solve [minimums valids maxStep maxDistinct]
  ; The result is a list of integers the same length as given minimums.
  (let [result (lvars (count minimums))]
    (run* [q]
      ; I'm not sure if this is okay style, but I initialize the result
      ; outside as a normal list and assign to q inside here so that I
      ; can use 'rest and 'map on it later.
      (== q result)

      ; Every lvar in the result list is in the domain of given valids.
      (everyg #(fd/dom % (apply fd/domain valids)) result)

      ; Every item in result is pairwise >= the corresponding minimum.
      (and* (map #(fd/>= %1 %2) result minimums))

      ; Between each item in result there's no more than 20 difference.
      (and* (map (stepLimit maxStep) result (rest result)))

      ; There shpuld be no more than maxDistinct distinct values in
      ; the result. This is not working obviously because I cannot take
      ; the normal clojure list of distinct values on a list of lvars.
      ; I'm not really sure how to do this with clore.logic or fd.
      ;(<= (count (distinct result)) maxDistinct)
      )))


(defn main []
  (run! println
    (solve
      [10 10 50]
      [10 20 45 50]
      20
      2)))

The believe the issue is with my usage of fd/-. Sadly as show, this function is undocumented. I also wonder if I could use intervals for that -maxStep - maxStep domain but also intervals are not documented either and I don't really know if they are interchangeable.

The output is just [50 50 50]. I would expect [20 45 50] to be valid since there's no more of a jump than 20. Of course the distinct feature would eliminate that one but it's commented out. But still [45 45 50] should work as well. I only get [50 50 50] though.

I'm interested in any critiques on core.logic style usage or how I can do this better as well.


Solution

  • If you look at the implementation of domain, it's pretty clear that its members cannot be negative. That will certainly break your implementation of stepLimit .

    I'm no fd expert, but it seems like you could work with just positive numbers. Construct a domain of the positive deltas only, and use a conde to verify that either (- x y) is in that domain, or (- y x) is.