CODEWITHSUNDEEP
rule-engineclipsexpert-systemlogic-programming
Paul Jurczak
Paul Jurczak

Reputation: 8173

Can this type of problem be easily expressed in logic programming paradigm?

For simplicity, this is a toy version of the actual problem: given a set of integers, find the longest sequence of consecutive numbers from that set.

I looked at CLIPS and other expert systems, and they seem ill-suited to express this kind of problem. Specifically, I don't see a list like data structure, which seems to be necessary to implement a solution. I'm looking for an example of implementation using logic programming.

Upvotes: 1

Views: 90

Answers (1)

Gary Riley
Gary Riley

Reputation: 10757

One way:

         CLIPS (6.4 2/9/21)
CLIPS> 
(deffacts start
   (set 1 9 2 10 4 3 11 13 5 14))
CLIPS>    
(defrule combine-1
   ?f <- (set $?b ?n $?e)
   =>
   (retract ?f)
   (assert (combine ?n))
   (assert (set ?b ?e)))
CLIPS>    
(defrule combine-2
   ?f1 <- (combine $?b ?j1)
   ?f2 <- (combine ?j2&=(+ ?j1 1) $?e)
   =>
   (retract ?f1 ?f2)
   (assert (combine ?b ?j1 ?j2 ?e)))
CLIPS>    
(defrule longest
   (declare (salience -10))
   (combine $?c)
   (not (combine $?o&:(> (length$ ?o) (length$ ?c))))
   =>
   (println "Longest is " ?c))
CLIPS> (reset)
CLIPS> (run)
Longest is (1 2 3 4 5)
CLIPS> (facts)
f-21    (set)
f-22    (combine 13 14)
f-26    (combine 1 2 3 4 5)
f-28    (combine 9 10 11)
For a total of 4 facts.
CLIPS>

Another way:

CLIPS> (clear)
CLIPS> 
(deffacts start
   (set 1 9 2 10 4 3 11 13 5 14))
CLIPS>    
(defrule sort
   ?f <- (set $?s)
   (test (neq ?s (sort > ?s)))
   => 
   (retract ?f)
   (assert (set (sort > ?s))))
CLIPS>    
(deffunction consecutive ($?s)
   (loop-for-count (?i (- (length$ ?s) 1))
      (if (<> (+ (nth$ ?i ?s) 1) (nth$ (+ ?i 1) ?s))
         then (return FALSE)))
   (return TRUE))
CLIPS>    
 (defrule longest
    (set $? $?s&:(consecutive $?s) $?)
    (not (set $? $?s2&~$?s&:(consecutive $?s2)&:(> (length$ ?s2) (length$ ?s)) $?))
    =>
    (println "Longest is " ?s))
CLIPS> (reset)
CLIPS> (run)
Longest is (1 2 3 4 5)
CLIPS> (facts)
f-2     (set 1 2 3 4 5 9 10 11 13 14)
For a total of 1 fact.
CLIPS>

Upvotes: 3

Related Questions