5

After watching Sussman's lecture http://www.infoq.com/presentations/We-Really-Dont-Know-How-To-Compute, I am inspired to give core.logic and core.match a go. The only examples I know are those constraint problem solvers that I used to do as a kid. This one was an example used in the SICP course as well as being mentioned in the talk:

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?

I found this on the rosettacode site: http://rosettacode.org/wiki/Dinesman%27s_multiple-dwelling_problem#PicoLisp

But not too sure how that translates into clojure. I am hoping that someone can provide an example of solving this using core.logic or core.match

2 Answers 2

3

Here's a solution in core.logic. It's not exactly equivalent to the picolisp algorithm because we don't have the same primitives available, but it's the same general idea. Thanks for introducing me to the problem - it was fun to invent permuteo and beforeo, and I had my first excuse to use conda. Edit: using conda there was horrible and wrong, and I'm back to conde now. Oh well, some day.

(ns dwelling.core
  (:refer-clojure :exclude [==])
  (:use clojure.core.logic))

(defn rembero [x l out]
  (fresh [head tail]
    (conso head tail l)
    (conde [(== x head) (== out tail)]
           [(fresh [new-out]
              (conso head new-out out)
              (rembero x tail new-out))])))

(defn permuteo [a b]
  (conde [(emptyo a) (emptyo b)]
         [(fresh [head tail b-tail]
            (conso head tail a)
            (rembero head b b-tail)
            (permuteo tail b-tail))]))

(defn beforeo [x y l]
  (fresh [head tail]
    (conso head tail l)
    (conde [(== x head) (fresh [more-tail]
                          (rembero y tail more-tail))]
           [(beforeo x y tail)])))

(defn not-adjacento [x y l]
  (fresh [head tail more]
    (conso head tail l)
    (resto tail more)
    (conde [(== x head) (membero y more)]
           [(== y head) (membero x more)]
           [(not-adjacento x y tail)])))

(run* [tenants]
  (fresh [a b c d e]
    (== [a b c d e] tenants)
    (permuteo tenants '[Cooper Baker Fletcher Miller Smith])
    (!= e 'Baker)
    (!= a 'Cooper)
    (!= a 'Fletcher)
    (!= e 'Fletcher)
    (beforeo 'Cooper 'Miller tenants)
    (not-adjacento 'Smith 'Fletcher tenants)
    (not-adjacento 'Fletcher 'Cooper tenants)))

;; ([Smith Cooper Baker Fletcher Miller])
4
  • Oh that is so cool =) Thank you so much! I'm going have a lot of fun in the next week playing around with how all of this works. (The entire concept of appending vowels after words hasn't clicked with me just yet).
    – zcaudate
    Jul 1, 2012 at 19:26
  • Yeah, the vowels don't make any sense to me either. I just name all my logic-functions ending with o and hope for the best. conda, conde, and condu seem to be special cases in the language. From reading The Reasoned Schemer (which I highly recommend), I got the impression the o might stand for "once", but it still doesn't make sense to me.
    – amalloy
    Jul 1, 2012 at 20:29
  • I found another puzzle here for core.logic github.com/swannodette/logic-tutorial... the 'zebra puzzle'
    – zcaudate
    Jul 2, 2012 at 23:40
  • 1
    Another possible approach after @amalloy brought this to my attention gist.github.com/3043632. Also rembero and permuteo are now a part of core.logic.
    – dnolen
    Jul 4, 2012 at 0:48
2

I just started journeying into LP myself, and my first effort is https://github.com/amalloy/doors, a solver for the automatically-generated logic puzzles at http://rooms.jmpup.com. Right now I have some relations defined that are generally-useful for all puzzles, but I haven't done any work on actually translating a particular puzzle into core.logic programmatically. You can see the one puzzle I've manually translated - webpage presentation and core.logic encoding. Perhaps this will give you an idea of how to use core.logic, although I'm still new to it myself so there are bound to be imperfections.

Edit

After looking over the picolisp solution, I don't think it translates directly to core.logic because, as far as I know, direct negation support does not exist yet.

1
  • I think I have to play that door game when I'm a little bit more sober =) How are you using the solver right now?
    – zcaudate
    Jun 29, 2012 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.